题目引用
- 复原IP地址
- 子集
- 子集II
1.复原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 中的任何数字。你可以按 任何 顺序返回答案。
示例 1:
输入:s = “25525511135”
输出:[“255.255.11.135”,“255.255.111.35”]
一看到这题目是不是没有头绪呀,这怎么又让我加入.
又让我返回结果数组的。但其实,这和我们昨天分割字符串一样的原理,只不过这里分割时需要加上判断,那是不是就是昨天另外一道回文子串的解法啦,这道题目就是把两个题目糅合了起来,既需要我们去将字符串分割,又需要我们判断其是否合法。
那么怎么做这道题呢?
首先我们需要以startIndex
为基准将其分割成一块一块的,再判断这一小段是否合法,合法后在这一小段后面加.
,接着继续遍历下一层,直到startIndex
到达字符串末尾。
那么判断函数怎么写呢?
首先,我们在这个函数中需要两个指针指向传入的一小段的头和尾,如果头在尾后面,返回false
,如果0
开头,返回false
,再遍历这一小段,如果遇到不为0-9
的符号返回false
,如果这一段大于255
,返回false
。最后返回true
。
来看代码吧:
class Solution {
public:
vector<string> res;
void backtracking(string s,int startIndex,int pointNum){
if(pointNum==3){
if(isValid(s,startIndex,s.size()-1)){
res.push_back(s);
}
return;
}
for(int i=startIndex;i<s.size()&&pointNum<=3;i++){
if(isValid(s,startIndex,i)){
s.insert(s.begin()+i+1,'.');
pointNum++;
backtracking(s,i+2,pointNum);
s.erase(s.begin()+i+1);
pointNum--;
}else break;
}
}
bool isValid(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;
}
vector<string> restoreIpAddresses(string s) {
if(s.size()<4||s.size()>12) return res;
backtracking(s,0,0);
return res;
}
};
2.子集
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的
子集
(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
这道题目与之前题目不同,这道题目需要我们遍历所有的节点,如果昨天的题目是求树的叶子节点和路径的话,那么今天的题目就是求所有的节点的总和。
所以我们在写递归函数的时候可以直接让path
入到res
结果数组中而不需要判断,当startIndex
到达数组末尾时直接返回即可。
来看代码吧:
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums,int startIndex){
res.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();
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums,0);
return res;
}
};
是不是很简单
3.子集II
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的
子集
(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
这道题目其实和上道题差不多,就是要加上去重逻辑,对nums
数组进行排序,然后创建一个used
数组,对其进行标记,具体的细节在昨天的题目中已经说过了,大家没掌握的可以回去看一眼。这里我就直接放代码了
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums,int startIndex,vector<bool> used){
res.push_back(path);
if(startIndex>=nums.size()) return;
for(int i=startIndex;i<nums.size();i++){
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(nums[i]);
used[i]=true;
backtracking(nums,i+1,used);
path.pop_back();
used[i]=false;
}
return;
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,0,used);
return res;
}
};
总结
今天的题目总体来说只有第一题比较抽象,过程是比较难想的,其他的对正在阅读的各位大佬来说应该不是什么特别难的问题,只是细节方面注意一下就好啦~