目录
- 一、复原IP地址-LeetCode 93
- 思路
- 实现代码
- 个人问题
- 总结
- 二、子集-LeetCode 78
- 思路
- 实现代码
- 个人问题
- 三.子集Ⅱ-LeeCode 90
- 思路
- 实现代码
- 个人问题
一、复原IP地址-LeetCode 93
Leecode链接: leetcode 93
文章链接: 代码随想录
视频链接: B站
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
示例:
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
思路
这道题是一个分割问题,可以用回溯穷举出所有结果。主要分为三个部分:切割ip段、验证ip段是否合法、插入结果到res中。ip切割这里不是使用substr函数,只需要使用insert成员函数即可,因为结果只需要一个完整的ip段,而不是一段一段。验证ip写一个自定义函数即可,插入结果到res这一步使用index来判断已经不适用了,因为ip有四个段,所以判断依据只需要改为是否使用了三个点即可。
实现代码
//cpp
class Solution {
public:vector<string>res;bool isvalid(const string& s,int begin,int end){if(begin > end) return false;if(s[begin] == '0' && begin != end) return false;int num = 0;for(int i = begin;i<=end;i++){if(s[i]<'0' || s[i]>'9') return false;num = num*10+(s[i]-'0');if(num>255) return false;}return true;}void restor(int pointnum,string&s,int index){if(pointnum==3){if(isvalid(s,index,s.size()-1)){res.push_back(s);}return;}for(int i = index;i<s.size();i++){if(isvalid(s,index,i)){pointnum++;s.insert(s.begin()+i+1,'.');restor(pointnum,s,i+2);pointnum--;s.erase(s.begin()+i+1);}else{break;}}}vector<string> restoreIpAddresses(string s) {res.clear();restor(0,s,0);return res;}
};
个人问题
没有想到怎么在字符串中插入字符’.',对insert用的比较少。
总结
难度中等,与分割回文串那题类似,需要注意的点有:插入结果的条件不再依靠index,而是依据段数;递归时不能传入i+1,因为插入字符后,前面的字符都往后移动一位;插入结果时需要对最后一段进行额外的一次判断,因为会有这种情况:192.168.1.399,这显然是不对的。
二、子集-LeetCode 78
Leecode链接: LeetCode 78
文章链接: 代码随想录
视频链接: B站
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的
子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
思路
题目与求组和类似,但有一个地方不同,在插入数据到res中时,组合需要进行一个判定,而子集不需要进行判断,每次进入一层递归就将结果插入到res中。至于为什么不需要判断,因为题目要求所有子集,任意一个数或者他们的组合都是子集,也就不要条件判断。
实现代码
//cpp
class Solution {
public:vector<vector<int>>res;vector<int>path;void sub(vector<int>& nums,int index){res.push_back(path);for(int i = index;i<nums.size();i++){path.push_back(nums[i]);sub(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {res.clear();path.clear();sub(nums,0);return res;}
};
个人问题
无。
三.子集Ⅱ-LeeCode 90
Leecode链接: LeetCode 90
文章链接: 代码随想录
视频链接: B站
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的
子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
思路
题目有重复元素,需要去重,不能包含重复的子集。解题思路与与组合总和Ⅱ类似。个人没有使用数组来判断是否使用相同的元素,感觉这样比较方便。
实现代码
//cpp
class Solution {
public:vector<int>path;vector<vector<int>>res;void sub(int index,vector<int>& nums){res.push_back(path);for(int i = index;i<nums.size();i++){if(i>index && nums[i] == nums[i - 1]){continue;}path.push_back(nums[i]);sub(i+1,nums);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {res.clear();path.clear();sort(nums.begin(),nums.end());sub(0,nums);return res;}
};
个人问题
无。