【代码随想录算法训练Day28】LeetCode 93. 复原 IP 地址、LeetCode 78.子集、LeetCode 90.子集II

本文主要是介绍【代码随想录算法训练Day28】LeetCode 93. 复原 IP 地址、LeetCode 78.子集、LeetCode 90.子集II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

93.复原IP地址

使用和分割回文串同样的思路，以 ' . ' 分割字符串，以 start 作为截取的子串的开始位置，i 作为子串的结束位置，单层递归的逻辑就是判断这个子串是否符合ip地址的要求。

正常应采取检验，排除所有非法情况，比如下面这段代码。

// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0开头的数字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法return false;}num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;
}

但我这里碰巧了，题目说了是纯数字，但我确实没有考虑到异常输入；并且力扣的测试样例里应该是没有负数的情况，我默认是大于等于0的值，所以这里判断只要小于256就是符合条件的。

对于前导0，我是通过先将字符串转换成整型，这样就得到一个没有前导0的子串对应的值了，再将整型转换回字符串，如果字符串转换前后不一致，则说明有前导0，这种情况要去除。

比较繁琐，正常操作应该是将我这思路用上面的判断是否合法的函数替换掉。

class Solution {
public:vector<string> result;string path;void backtracking(string s, int start, int dot){if(dot == 4 && start >= s.size()){result.push_back(path.substr(0, path.size()-1));return;}if(dot >= 4){return;}for(int i = start; i < s.size(); i++){//采用和分割回文串相同的思路，截取两个'.'之间的字符串进行判断//start是上一个'.'的位置，i是下一个'.'的位置，随着i向后移动，改变当前子串的选择string str = s.substr(start, i-start+1);string tmpstr = path;int tmp = atoi(str.c_str());//先转成数字string copy = to_string(tmp);//再转回字符串，如果转换前后相等则说明没有前导0if(tmp <= 255 && !str.compare(copy)){path = path + to_string(tmp) + ".";dot++;}else continue;backtracking(s, i+1, dot);dot--;path = tmpstr;}}vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return result;}
};

78.子集

这题我想记录的思路是从当前输入的元素角度出发的，即选还是不选将当前输入元素加入结果集中。

这种思路的写法如下所示。

首先是进入递归函数种，先将当前元素加入到结果集中，表示选择了当前元素，再进行递归，进到下一层递归，走下一个元素选和不选的分支。有点像二叉树的左右孩子，左是选，右是不选，这种写法就更像是二叉树的遍历了。先一直走选的分支，再回溯到上一层，这时选的元素在结果集中，我们将它pop出来，这样就是不选了，然后再进一次backtracking，走不选这个元素的分支。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int start) {if(start >= nums.size()){result.push_back(path);return;}path.push_back(nums[start]);backtracking(nums, start+1);path.pop_back();backtracking(nums, start+1);}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};

上面写法比较便于理解，但和模板不一致，不方便记忆。

按照模板的写法，模板将一部分的递归使用 for 循环迭代实现了，所以看着其实不直观，感受不到这其实像是二叉树的搜索，但思路也是一样的。先选，放进path结果集，走选的分支，然后回溯回来，pop出去当前的元素，走 for 循环，进到下一个元素，这时也是没选当前元素，走到下一个元素了。

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己if (startIndex >= nums.size()) { // 终止条件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

90.子集II

这题其实就没什么好记录的了，和 组合总和Ⅱ 这题的思路是一样的，都是在有重复元素的数据中，找出不重复的组合。思路就是对树层的去重。详细可以回顾 组合总和Ⅱ 的博客。

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int start) {result.push_back(path);if(start >= nums.size()){return;}for(int i = start; i < nums.size(); i++){if(i > start && nums[i-1] == nums[i])continue;path.push_back(nums[i]);backtracking(nums, i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());backtracking(nums, 0);return result;}
};

这篇关于【代码随想录算法训练Day28】LeetCode 93. 复原 IP 地址、LeetCode 78.子集、LeetCode 90.子集II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---