0.引言
● 93.复原IP地址
● 78.子集
● 90.子集II
93.# 复原 IP 地址
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (57.85%) | 1180 | - |
有效 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"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20-
s仅由数字组成
回溯
这些个老六题目：
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> IPS;
back_tracking(s, 0, 0, IPS);
return IPS;
}
private:
void back_tracking(string& s, int idx, int point_num, vector<string>& IPS) {
// 1.终止条件
if (point_num == 3) { // 当有三个点时就是分割到了最后
// 判断最后一段是否合法
if (is_valid(s, idx, s.size() - 1)) {
IPS.push_back(s);
}
return;
}
// 2.遍历
for (int i = idx; i < s.size(); ++i) {
if (is_valid(s, idx, i)) {
// 插入 ‘.’
s.insert(s.begin() + i + 1, '.');
point_num++;
back_tracking(s, i + 2, point_num, IPS);
point_num--;
s.erase(s.begin() + i + 1);
} else {
break; // 不合法直接break
}
}
}
bool is_valid(string& s, int start_idx, int end_idx) {
if (start_idx > end_idx) return false;
// 0 开头不合法
if (s[start_idx] == '0' && start_idx != end_idx) return false;
// 非数字
long int num = 0;
for (int i = start_idx; i <= end_idx; ++i) {
if (s[i] < '0' || s[i] > '9') return false;
num = num * 10 + s[i] - '0';
}
if (num > 255) return false;
// 数字大于255 非法
// string str = s.substr(start_idx, end_idx);
// if (std::stoi(str) > 255) return false;
return true;
}
};
78.# 子集
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (81.05%) | 1976 | - |
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10-
nums中的所有元素 互不相同
回溯
想通过当前的size来实现，好像不太行：
/*
* @lc app=leetcode.cn id=78 lang=cpp
*
* [78] 子集
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<std::vector<int>> res;
std::vector<int> subset;
int cur_subset_size = 1;
res.push_back(subset);
dfs(nums, 0, cur_subset_size, subset, res);
return res;
}
private:
void dfs(std::vector<int>& nums, int start_idx, int& cur_subset_size,
std::vector<int>& subset, std::vector<std::vector<int>>& res) {
// 1.终止条件
if (subset.size() == cur_subset_size) {
res.push_back(subset);
if (start_idx >= nums.size()-1) {
cur_subset_size++;
}
return;
}
// 2.遍历
for (int i = start_idx; i < nums.size(); ++i) {
subset.push_back(nums[i]);
dfs(nums, i + 1, cur_subset_size, subset, res);
subset.pop_back();
}
}
};
// @lc code=end
有意思哦：
/*
* @lc app=leetcode.cn id=78 lang=cpp
*
* [78] 子集
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<std::vector<int>> res;
std::vector<int> subset;
res.push_back(subset);
dfs(nums, 0, subset, res);
return res;
}
private:
void dfs(std::vector<int>& nums, int start_idx, std::vector<int>& subset,
std::vector<std::vector<int>>& res) {
// 1.终止条件
if (start_idx >= nums.size()) {
return;
}
// 选择第 i 个元素的情况下，进行后面元素的递归选择
subset.push_back(nums[start_idx]); // 理解：这里是推入的一个数
res.push_back(subset);
dfs(nums, start_idx + 1, subset, res); // 递归
// 第一次递归回溯到这里后，再次进行操作
// 取消选择第 i 个元素，再次进行递归
subset.pop_back(); // 从subset中剔除第 i 个元素的选择
dfs(nums, start_idx + 1, subset, res);
}
};
// @lc code=end
还是统一模板最炫酷：
/*
* @lc app=leetcode.cn id=78 lang=cpp
*
* [78] 子集
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<std::vector<int>> res;
std::vector<int> subset;
dfs(nums, 0, subset, res);
return res;
}
private:
void dfs(std::vector<int>& nums, int start_idx, std::vector<int>& subset,
std::vector<std::vector<int>>& res) {
res.push_back(subset); // 收集子集，要放在终止条件的上面，否则会漏掉自己
// 1.终止条件
if (start_idx >= nums.size()) {
return;
}
// 2.遍历
for (int i = start_idx; i < nums.size(); ++i) {
subset.push_back(nums[i]);
dfs(nums, i + 1, subset, res);
subset.pop_back();
}
}
};
// @lc code=end
90.# 子集 II
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (63.68%) | 1060 | - |
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
回溯法
/*
* @lc app=leetcode.cn id=90 lang=cpp
*
* [90] 子集 II
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
std::vector<std::vector<int>> res;
std::vector<int> subset;
std::vector<bool> used(nums.size(), false);
std::sort(nums.begin(), nums.end()); // 去重需要排序
dfs(nums, 0, used, subset, res);
return res;
}
private:
void dfs(std::vector<int>& nums, int start_idx, std::vector<bool>& used,
std::vector<int>& subset, std::vector<std::vector<int>>& res) {
res.push_back(subset); // 收集子集，要放在终止添加的上面，否则会漏掉自己
// 1.终止条件
if (start_idx >= nums.size()) {
return;
}
// 2.遍历
for (int i = start_idx; i < nums.size(); ++i) {
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 而我们要对同一树层使用过的元素进行跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
subset.push_back(nums[i]);
used[i] = true;
dfs(nums, i + 1, used, subset, res);
used[i] = false;
subset.pop_back();
}
}
};
// @lc code=end
