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

本文主要是介绍leetcode解题思路分析（五十四）462 - 468 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

462. 最少移动次数使数组元素相等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;}
};

463. 岛屿的周长
     给定一个 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;}
};

464. 我能赢吗
     给定一个整数 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];}
};

466. 统计重复个数
     由 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' 个 s2pre_loop = {s1cnt_prime, s2cnt_prime};// 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2in_loop = {s1cnt - s1cnt_prime, s2cnt - s2cnt_prime};break;} else {recall[index] = {s1cnt, s2cnt};}}// ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loopint 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 个 S2return 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;}
};

468. 验证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();//这里判断首字母是否为0if(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的个数大于1if(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;}
};

这篇关于leetcode解题思路分析（五十四）462 - 468 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---