leetcode_day27
本文最后更新于 2024年6月18日 晚上
今日内容:
- 93. 复原IP地址 medium
- 78. 子集 medium
- 90. 子集Ⅱ medium
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 中的任何数字。你可以按 任何 顺序返回答案。
思路:
回溯做了几天,对于简单的解空间树怎么分支比较熟悉了,这题就先按长度从1到3分割,然后下传起点,如果第四段仍然合法,则找到一个答案,不断递归回溯寻找所有答案即可。
代码
1 |
|
78. 子集
题目:
给你一个整数数组 nums
,数组中的元素
互不相同。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路:
也是很容易套上模板的回溯,不过不能不求甚解依赖模板,还是要想清楚代码逻辑。这题是求子集,高中就学过n个元素的集合有2^n个子集,虽然跟这没啥关系,不过可以认识到求子集就是求元素个数从0~n的关于全集nums的组合,所以可以分别求长度为i,i从0到n,的组合,那就是从nums里抓i个的组合,就变成了该题的上一题:77. 组合了。
对于错误思路的反思:
注意到该题的tag里有位运算字样,昨天做错的题目里我也尝试使用位运算模拟bool used[]
来记录哪些数字已经被使用过,但实际上是多余的。今天又看见位运算,由于其出现在tag里,所以深信不疑,再次尝试,WA,去掉后,AC。下面逐条分析错误核心,搞清楚什么时候用used记录用过,什么时候不用。
1 |
|
看完发现,used的确多余,但好像没有影响啊,其实WA原因在于used >> nums[i] % 2
,%运算符优先级高于>>,所以错了。
当然,改了还是会错,nums里有负数,这样就越来越复杂了。
代码
第一版 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int> &nums, int begin, int len) {
if(temp.size() == len) {
ans.push_back(temp);
return;
}
for(int i = begin;i < nums.size();i++) {
temp.push_back(nums[i]);
backtrack(nums, i + 1, len);
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
for(int i = 0;i <= nums.size();i++) {
backtrack(nums, 0, i);
}
return ans;
}
};
carl的解 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int> &nums, int begin) {
ans.push_back(temp);//提前
if(begin >= nums.size()) {
return;
}
for(int i = begin;i < nums.size();i++) {
temp.push_back(nums[i]);
backtrack(nums, i + 1);
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0);
return ans;
}
};
90. 子集Ⅱ
题目:
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
思路:
与上一题相比多了重复元素,相当于[1,2,2]的子集注意别回溯出两个[1,2],可以采用昨天40. 组合总和的相同去重思路。在昨天的blog中已经提到不能简单用used来尝试去重。所以还是乖乖用carl的写法,附图carl的解空间树:
代码
1 |
|