leetcode解题思路分析（五十四）462 - 468 题

绝地灬酷狼 2022-12-29 02:10 83阅读 0赞

1.  最少移动次数使数组元素相等2  
    给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

**找到中位数，和中位数的差值就是最小值**

class Solution { 
    public:
        int minMoves2(vector<int>& nums) { 
            int res = 0, i = 0, j = nums.size() - 1;
            sort(nums.begin(), nums.end());
            while(i < j) { 
                res += nums[j--] - nums[i++];
            }
            return res;
        }
    };

1.  岛屿的周长  
    给定一个 row x col 的二维网格地图 grid ，其中：grid\[i\]\[j\] = 1 表示陆地， grid\[i\]\[j\] = 0 表示水域。网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

**遍历一遍，减去计算多的边即可**

class Solution { 
    public:
        int islandPerimeter(vector<vector<int>>& grid) { 
            if (grid.size() == 0 || grid[0].size() == 0) 
                return 0;
    
            int ret = 0, multi = 0;
            for (int i = 0; i < grid.size(); i++)
            { 
                for (int j = 0; j < grid[0].size(); j++)
                { 
                    if (grid[i][j])
                    { 
                        ret += 4;
    
                        if (i < grid.size() - 1)
                        { 
                            if (grid[i + 1][j])
                                multi += 2;
                        }
    
                        if (j < grid[0].size() - 1)
                        { 
                            if (grid[i][j + 1])
                                multi += 2;
                        }
                    }
                }
            }
    
            return ret - multi;
    
        }
    };

1.  我能赢吗  
    给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

**记忆化递归求解**

class Solution { 
    public:
        bool canIWin(int maxChoosableInteger, int desiredTotal) { 
            if (desiredTotal <= 0)
                return true;
            
            int sum = 0;
            int maxbits = 0;
            for (int i = maxChoosableInteger; i >= 1 && sum < desiredTotal; i--) { 
                sum += i;
                maxbits += (1 << (i - 1));
            }
            if (sum < desiredTotal)
                return false;
            
            vector<bool> dp0(maxbits + 1);
            vector<bool> dp1(maxbits + 1);
            for (int i = maxbits; i >= 0; i--) { 
                int s = 0;
                for (int k = 1; k <= maxChoosableInteger; k++)
                    if ((1 << (k - 1)) & i)
                        s += k;
                
                if (s >= desiredTotal) { 
                    dp0[i] = false;
                    dp1[i] = true;
                } else { 
                    dp0[i] = false;
                    dp1[i] = true;
                    for (int j = 1; j <= maxChoosableInteger; j++) { 
                        if ((1 << (j - 1)) & i)
                            continue;
                        
                        if (dp1[i] && ((s + j >= desiredTotal) || !dp0[((1 << (j - 1)) | i)]))
                            dp1[i] = false;
                        
                        if (!dp0[i] && ((s + j >= desiredTotal) || dp1[((1 << (j - 1)) | i)]))
                            dp0[i] = true;
                        
                        if (dp0[i] && !dp1[i])
                            break;
                    }
                }
            }
            return dp0[0];
        }
    };

1.  统计重复个数  
    由 n 个连接的字符串 s 组成字符串 S，记作 S = \[s,n\]。例如，\[“abc”,3\]=“abcabcabc”。如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，“abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=\[s1,n1\] 、S2=\[s2,n2\] 。请你找出一个可以满足使\[S2,M\] 从 S1 获得的最大整数 M 。

class Solution { 
    public:
        int getMaxRepetitions(string s1, int n1, string s2, int n2) { 
            if (n1 == 0) { 
                return 0;
            }
            int s1cnt = 0, index = 0, s2cnt = 0;
            // recall 是我们用来找循环节的变量，它是一个哈希映射
            // 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符
            // 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了
            // 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果
            // 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组
            // 循环节就是；
            // - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
            // - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
            // 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配
            // 注意 s2 要从第 index 个字符开始匹配
            unordered_map<int, pair<int, int>> recall;
            pair<int, int> pre_loop, in_loop;
            while (true) { 
                // 我们多遍历一个 s1，看看能不能找到循环节
                ++s1cnt;
                for (char ch: s1) { 
                    if (ch == s2[index]) { 
                        index += 1;
                        if (index == s2.size()) { 
                            ++s2cnt;
                            index = 0;
                        }
                    }
                }
                // 还没有找到循环节，所有的 s1 就用完了
                if (s1cnt == n1) { 
                    return s2cnt / n2;
                }
                // 出现了之前的 index，表示找到了循环节
                if (recall.count(index)) { 
                    auto [s1cnt_prime, s2cnt_prime] = recall[index];
                    // 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
                    pre_loop = { s1cnt_prime, s2cnt_prime};
                    // 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
                    in_loop = { s1cnt - s1cnt_prime, s2cnt - s2cnt_prime};
                    break;
                } else { 
                    recall[index] = { s1cnt, s2cnt};
                }
            }
            // ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop
            int ans = pre_loop.second + (n1 - pre_loop.first) / in_loop.first * in_loop.second;
            // S1 的末尾还剩下一些 s1，我们暴力进行匹配
            int rest = (n1 - pre_loop.first) % in_loop.first;
            for (int i = 0; i < rest; ++i) { 
                for (char ch: s1) { 
                    if (ch == s2[index]) { 
                        ++index;
                        if (index == s2.size()) { 
                            ++ans;
                            index = 0;
                        }
                    }
                }
            }
            // S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
            return ans / n2;
        }
    };

467 环绕字符串中唯一的子字符串  
现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。

**找出连续的子串，然后计算其可以组成的子串长度，最后累加**

class Solution { 
    public:
        int findSubstringInWraproundString(string p) { 
            if (!p.size()) return 0;
            vector<int> vec(128, 0);
            int curlen = 1;
            int result = 1;
            vec[p[0]] = 1;
            for (int i = 1; i < p.size(); ++i) { 
                if (p[i] == p[i-1] + 1 || p[i] == 'a' && p[i-1] == 'z') { 
                    curlen ++;
                } else { 
                    curlen = 1;
    
                }
                if (curlen > vec[p[i]]) { 
                    result += curlen - vec[p[i]];
                    vec[p[i]] = curlen;
                }
            }
            return result;
        }
    };

1.  验证IP地址  
    编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。

**按规则匹配即可**

class Solution { 
        public:
            string validIPAddress(string IP) { 
                string str1 = "IPv4";
                string str2 = "IPv6";
                string str3 = "Neither";
                //ipv4的限制 开头不能为0 有4组值 并且不能出现空数组
                int i = 0;
                bool ipv4 = false;
                int index = 0;
                bool ipv6 = false;
                if(IP.length() == 0 || IP[IP.length()-1] == ':' || IP[IP.length()-1] == '.' || IP[0] == '0') return str3;
                while(i < IP.length()){ 
                    stack<char> s;
                    while(i < IP.length() && IP[i] != '.' && IP[i] != ':') {  s.push(IP[i++]);}
                    index++;
                    if(IP[i] == '.' && i < IP.length()) ipv4 = true;
                    if(IP[i] == ':' && i < IP.length()) ipv6 = true;
                    if(ipv4 && ipv6) return str3;  
                    if(ipv4){ 
                        if(index > 4 || s.empty()) { return str3;}
                        int tmp = 0;
                        int k = 1;
                        int n = s.size();
                        while(!s.empty()){ 
                            if(s.top() == '-') return str3;
                            int tmp2 = (s.top() - '0');
                            s.pop();
                            //这里判断首字母是否为0
                            if(s.empty() && tmp2 == 0 && n != 1) return str3;
                            tmp += tmp2 * k;
                            k = k * 10;
                            if(tmp > 255) return str3;
                        }
                        if(tmp > 255) return str3;
                    }else{ 
                        //可以0开头 不能出现连续的0 并且0的个数大于1
                        if(index > 8 || s.empty()) { return str3;}
                        int n = s.size();
                        if(n > 4) return str3;
                        while(!s.empty()){ 
                            if(s.top() == '-') return str3;
                            if( s.top() >= 'A' && s.top() <= 'Z' && s.top() > 'F') return str3;
                            if( s.top() >= 'a' && s.top() <= 'z' && s.top() > 'f') return str3;
                            s.pop();
                        }
                    }
                    i++;
                }
                if(ipv4 && index == 4) return str1;
                else return index == 8 ? str2 : str3;
            }
    };