天津市工程建设交易网站查汗国,上海企业网站制作哪家好,重庆seo公司,各大网站怎么把世界杯做头条93. 复原 IP 地址 这题挺难的#xff0c;实际上我觉得分割字符串的题都挺难的#xff0c;即使知道了回溯算法#xff0c;也是无从下手。因为要对字符串进行处理#xff0c;关于分割点不知道怎么处理。关键部分理解在代码里。
class Solution {
private:
// 判断分割的子串…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;// 非数字或数字大于255for (int i start; iend; i){if (s[i] 0 || s[i] 9){return false;}num num * 10 (s[i] - 0);if (num 255){return false;}}// 否则正确return true; }
public:// 结果集vectorstring 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; is.size(); i){// 先分割第一部分如果前面出现错误则不继续分割了if (isValid(s, startIndex, i)){// string类型的插入s.insert(s.begin() i 1,.);// 插入完点数加1pointNum;// 递归注意加了点数后字符串总长度增加下次的起始位置为i2backtracking(s, i2,pointNum);// 回溯点数回到原来位置擦除之前插入的点pointNum--;s.erase(s.begin() i 1);}elsebreak;}}vectorstring restoreIpAddresses(string s) {res.clear();if (s.size() 4 || s.size() 12){return res;}backtracking(s, 0, 0);return res;}
};78. 子集
求子集是最宽泛的其结束条件与加入条件都即为宽松每一层递归的中间结果都可以直接加入最终结果集仅当开始索引大于数组大小时结束递归。
class Solution {
public:// 存储中间结果的数组vectorint tmp;// 存储最终结果的数组vectorvectorint res;// 仅需一个startIndex来避免重复集合的问题void backtracking(vectorint nums, int startIndex){// 结果集的条件很宽松只要不要有重复的不管怎么组合都是一个结果res.push_back(tmp);// 可以选择性省略因为没有其他终止条件for循环会自动终止if (startIndex nums.size()){return;}for (int i startIndex; inums.size(); i){// 简单向后加入、递归、回溯tmp.push_back(nums[i]);backtracking(nums, i 1);tmp.pop_back();}}vectorvectorint subsets(vectorint nums) {backtracking(nums, 0);return res;}
};90. 子集 II
这个自己多加了一个条件——“其中可能包含重复元素”但是结果却不能包含重复的子集。因为集合中的每一个元素只能用一次且集合不存在顺序之分因此这也是一个组合元素不可重复取的问题。
class Solution {
public:vectorint path;vectorvectorint res;// 只需先排序在同一层中如果相邻元素相同直接跳过即可void backtracking(vectorint nums, int startIndex){res.push_back(path);// 这句可以不加因为for循环满足inums.size()时可以直接结束循环if (startIndex nums.size()){return;}for (int i startIndex; inums.size(); i){// 在排序后的相邻元素相同的情况下可以直接跳过if (i startIndex nums[i] nums[i-1]){continue;}path.push_back(nums[i]);// startIndex i1表示每个元素仅可使用一次backtracking(nums, i 1);path.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());backtracking(nums, 0);return res;}
};
