代码随想录算法训练营第二十一天 | LeetCode93.复原IP地址、LeetCode78.子集、LeetCode90.子集II
01-1 LeetCode93.复原IP地址
相关资源
题目链接：93. 复原 IP 地址
文章讲解：LeetCode93：复原IP地址
视频讲解：LeetCode：93.复原IP地址
题目：
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
第一想法：类似于回文子串，用"."进行分割
遇到的困难：这道题目写了好久好久才写出来，主要问题在于递归的终止条件不太清楚，并且判断每个整数段是否位于 0 到 255 之间组成，且不能含有前导 0写法上出错过。
实现：
class Solution {
public:vector<string> result;string str;bool judge(string& s, int start, int end){int count = 0;if(end-start+1>3){return false;}if(end==start){return true;}if(end==start+1){if(s[start]=='0'){return false;}else{return true;}}if(end==start+2){if(s[start]=='0'){return false;}else{count += (s[start]-'0')*100+(s[start+1]-'0')*10+s[start+2]-'0'; if(count<=255){return true;}else{return false;}}}return false; }void backtracking(string& s, int startIndex, int part){if(startIndex >= s.size()){return;}if(part == 3){if(judge(s,startIndex,s.size()-1)){string str_cut = s.substr(startIndex, s.size()-startIndex);string str_temp = str + str_cut;result.push_back(str_temp);}return;}for(int i = startIndex; i <= startIndex + 2 && i < s.size(); i++ ){if(judge(s,startIndex,i)){string str_cut = s.substr(startIndex, i-startIndex+1);str = str + str_cut + ".";backtracking(s,i+1,part+1);for(int i = 0; i < str_cut.size() + 1; i++){str.pop_back();}}}return;}vector<string> restoreIpAddresses(string s) {backtracking(s,0,0);return result;}
};
看完代码随想录之后的想法： 思路大差不差，但录哥直接在原字符串中insert和erease
ToDo：复习！
01-2 LeetCode78.子集
相关资源
- 题目链接：78. 子集
- 文章讲解：LeetCode78.子集
- 视频讲解：LeetCode：78.子集
题目：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
第一想法：其实就是组合，但需要把空集加入结果集，并且每个叶子节点都要记录
实现：
class Solution {
public:vector<vector<int>> result;vector<int> rec;void backtracking(vector<int>& nums, int startIndex){if(startIndex >= nums.size()){return;}for(int i = startIndex; i < nums.size(); i++){rec.push_back(nums[i]);result.push_back(rec);backtracking(nums, i+1);rec.pop_back();}return;}vector<vector<int>> subsets(vector<int>& nums) {result.push_back(rec);backtracking(nums,0);return result;}
};
看完代码随想录之后的想法：思路一致
ToDo：复习
01-3 LeetCode90.子集II
相关资源
题目链接：90. 子集 II
文章讲解：子集II
视频讲解： LeetCode：90.子集II
题目：
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
第一想法：和之前的组合总和II很相似，也是需要一个去重的过程
实现：
class Solution {
public:vector<vector<int>> result;vector<int> rec;void backtracking(vector<int>& nums, int startIndex){result.push_back(rec);if(startIndex >= nums.size()){return;}for(int i = startIndex; i < nums.size(); i++){if(i>startIndex && nums[i]==nums[i-1]){continue;}rec.push_back(nums[i]);backtracking(nums, i+1);rec.pop_back();}return;}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());backtracking(nums,0);return result;}
};
看完代码随想录之后的想法：思路一致
ToDo：勤加复习
