0.引言
● 93.復(fù)原IP地址
● 78.子集
● 90.子集II
93.# 復(fù)原 IP 地址
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (57.85%) | 1180 | - |
有效 IP 地址 正好由四個整數(shù)（每個整數(shù)位于 0 到 255 之間組成叠殷，且不能含有前導(dǎo) 0）剥悟，整數(shù)之間用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址都哭，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 無效 IP 地址裳朋。
給定一個只包含數(shù)字的字符串 s 灭贷，用以表示一個 IP 地址削茁，返回所有可能的有效 IP 地址，這些地址可以通過在 s 中插入 '.' 來形成粟害。你 不能 重新排序或刪除 s 中的任何數(shù)字蕴忆。你可以按 任何 順序返回答案。
示例 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僅由數(shù)字組成
回溯
這些個老六題目：
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) { // 當(dāng)有三個點時就是分割到了最后
// 判斷最后一段是否合法
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;
// 非數(shù)字
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;
// 數(shù)字大于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 | - |
給你一個整數(shù)數(shù)組 nums 悲幅，數(shù)組中的元素 互不相同 套鹅。返回該數(shù)組所有可能的子集（冪集）站蝠。
解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集卓鹿。
示例 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中的所有元素 互不相同
回溯
想通過當(dāng)前的size來實現(xiàn)菱魔，好像不太行：
/*
* @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]); // 理解：這里是推入的一個數(shù)
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
還是統(tǒng)一模板最炫酷：
/*
* @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 | - |
給你一個整數(shù)數(shù)組 nums 藻治，其中可能包含重復(fù)元素，請你返回該數(shù)組所有可能的子集（冪集）巷挥。
解集 不能 包含重復(fù)的子集桩卵。返回的解集中，子集可以按 任意順序 排列倍宾。
示例 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
