93. 复原 IP 地址
这题挺难的,实际上我觉得分割字符串的题都挺难的,即使知道了回溯算法,也是无从下手。因为要对字符串进行处理,关于分割点不知道怎么处理。关键部分理解在代码里。
class Solution {
private:
// 判断分割的子串是否合理
bool isValid(const string& s, int start, int end){
// 初始大于末尾,肯定错了
if (start > end){
return false;
}
// 如果以0开头的数字
if (s[start] == '0' && start != end){
//不是单个数字,但是以0开头
return false;
}
int num = 0;
// 非数字,或数字大于255
for (int i = start; 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;
}
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(); i++){
// 先分割第一部分,如果前面出现错误,则不继续分割了
if (isValid(s, startIndex, i)){
// string类型的插入
s.insert(s.begin() + i + 1,'.');
// 插入完点数加1
pointNum++;
// 递归,注意加了点数后字符串总长度增加,下次的起始位置为i+2
backtracking(s, i+2,pointNum);
// 回溯,点数回到原来位置,擦除之前插入的点
pointNum--;
s.erase(s.begin() + i + 1);
}
else
break;
}
}
vector<string> restoreIpAddresses(string s) {
res.clear();
if (s.size() < 4 || s.size() > 12){
return res;
}
backtracking(s, 0, 0);
return res;
}
};
求子集是最宽泛的,其结束条件与加入条件都即为宽松,每一层递归的中间结果都可以直接加入最终结果集,仅当开始索引大于数组大小时结束递归。
class Solution {
public:
// 存储中间结果的数组
vector<int> tmp;
// 存储最终结果的数组
vector<vector<int>> res;
// 仅需一个startIndex来避免重复集合的问题
void backtracking(vector<int>& nums, int startIndex){
// 结果集的条件很宽松,只要不要有重复的,不管怎么组合都是一个结果
res.push_back(tmp);
// 可以选择性省略,因为没有其他终止条件,for循环会自动终止
if (startIndex >= nums.size()){
return;
}
for (int i = startIndex; i<nums.size(); i++){
// 简单向后加入、递归、回溯
tmp.push_back(nums[i]);
backtracking(nums, i + 1);
tmp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
这个自己多加了一个条件——“其中可能包含重复元素”,但是结果却不能包含重复的子集。因为集合中的每一个元素只能用一次,且集合不存在顺序之分,因此这也是一个组合元素不可重复取的问题。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
// 只需先排序,在同一层中如果相邻元素相同直接跳过即可
void backtracking(vector<int>& nums, int startIndex){
res.push_back(path);
// 这句可以不加,因为for循环满足i>=nums.size()时可以直接结束循环
if (startIndex >= nums.size()){
return;
}
for (int i = startIndex; i<nums.size(); i++){
// 在排序后的相邻元素相同的情况下可以直接跳过
if (i > startIndex && nums[i] == nums[i-1]){
continue;
}
path.push_back(nums[i]);
// startIndex i+1表示每个元素仅可使用一次
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
backtracking(nums, 0);
return res;
}
};