软件介绍下载网站建设,你的网站尚未进行备案,国内ui做的好的网站,怎么寻找要建设网站的客户群三刷day28 93.复原IP地址判断子串是否合法 78.子集回溯三部曲 90.子集II 93.复原IP地址
题目链接 解题思路#xff1a; 切割问题就可以使用回溯搜索法把所有可能性搜出来 回溯三部曲
递归参数
startIndex一定是需要的#xff0c;因为不能重复分割#xff0c;记录下一层递… 三刷day28 93.复原IP地址判断子串是否合法 78.子集回溯三部曲 90.子集II 93.复原IP地址
题目链接 解题思路 切割问题就可以使用回溯搜索法把所有可能性搜出来 回溯三部曲
递归参数
startIndex一定是需要的因为不能重复分割记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum记录添加逗点的数量。
所以代码如下
vectorstring result;// 记录结果
// startIndex: 搜索的起始位置pointNum:添加逗点的数量
void backtracking(string s, int startIndex, int pointNum) {递归终止条件
终止条件和131.分割回文串
情况就不同了本题明确要求只会分成4段所以不能用切割线切到最后作为终止条件而是分割的段数作为终止条件。
pointNum表示逗点数量pointNum为3说明字符串分成了4段了。
然后验证一下第四段是否合法如果合法就加入到结果集里
代码如下
if (pointNum 3) { // 逗点数量为3时分隔结束// 判断第四段子字符串是否合法如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;
}单层搜索的逻辑
在131.分割回文串中已经讲过在循环遍历中如何截取子串。
在for (int i startIndex; i s.size(); i)循环中 [startIndex, i] 这个区间就是截取的子串需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.表示已经分割。
如果不合法就结束本层循环如图中剪掉的分支 然后就是递归和回溯的过程
递归调用时下一层递归的startIndex要从i2开始因为需要在字符串中加入了分隔符.同时记录分割符的数量pointNum 要 1。
回溯的时候就将刚刚加入的分隔符. 删掉就可以了pointNum也要-1。
代码如下
for (int i startIndex; i s.size(); i) {if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() i 1 , .); // 在i的后面插入一个逗点pointNum;backtracking(s, i 2, pointNum); // 插入逗点之后下一个子串的起始位置为i2pointNum--; // 回溯s.erase(s.begin() i 1); // 回溯删掉逗点} else break; // 不合法直接结束本层循环
}判断子串是否合法
最后就是在写一个判断段位是否是有效段位了。
主要考虑到如下三点
段位以0为开头的数字不合法段位里有非正整数字符不合法段位如果大于255了不合法
代码如下
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string s, int start, int end) {if (start end) {return false;}if (s[start] 0 start ! end) { // 0开头的数字不合法return false;}int num 0;for (int i start; i end; i) {if (s[i] 9 || s[i] 0) { // 遇到非数字字符不合法return false;}num num * 10 (s[i] - 0);if (num 255) { // 如果大于255了不合法return false;}}return true;
}可以写出如下回溯算法C代码
class Solution {
private:vectorstring result;// 记录结果// startIndex: 搜索的起始位置pointNum:添加逗点的数量void backtracking(string s, int startIndex, int pointNum) {if (pointNum 3) { // 逗点数量为3时分隔结束// 判断第四段子字符串是否合法如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for (int i startIndex; i s.size(); i) {if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() i 1 , .); // 在i的后面插入一个逗点pointNum;backtracking(s, i 2, pointNum); // 插入逗点之后下一个子串的起始位置为i2pointNum--; // 回溯s.erase(s.begin() i 1); // 回溯删掉逗点} else break; // 不合法直接结束本层循环}}// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string s, int start, int end) {if (start end) {return false;}if (s[start] 0 start ! end) { // 0开头的数字不合法return false;}int num 0;for (int i start; i end; i) {if (s[i] 9 || s[i] 0) { // 遇到非数字字符不合法return false;}num num * 10 (s[i] - 0);if (num 255) { // 如果大于255了不合法return false;}}return true;}
public:vectorstring restoreIpAddresses(string s) {result.clear();if (s.size() 4 || s.size() 12) return result; // 算是剪枝了backtracking(s, 0, 0);return result;}
};78.子集
题目链接 解题思路 从图中红线部分可以看出 遍历这个树的时候把所有节点都记录下来就是要求的子集集合。
回溯三部曲
递归函数参数
全局变量数组path为子集收集元素二维数组result存放子集组合。也可以放到递归函数参数里
递归函数参数在上面讲到了需要startIndex。
代码如下
vectorvectorint result;
vectorint path;
void backtracking(vectorint nums, int startIndex) {递归终止条件
从图中可以看出 剩余集合为空的时候就是叶子节点。
那么什么时候剩余集合为空呢
就是startIndex已经大于数组的长度了就终止了因为没有元素可取了代码如下:
if (startIndex nums.size()) {return;
}其实可以不需要加终止条件因为startIndex nums.size()本层for循环本来也结束了。
单层搜索逻辑
求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。
那么单层递归逻辑代码如下
for (int i startIndex; i nums.size(); i) {path.push_back(nums[i]); // 子集收集元素backtracking(nums, i 1); // 注意从i1开始元素不重复取path.pop_back(); // 回溯
}可以写出如下回溯算法C代码
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {result.push_back(path); // 收集子集要放在终止添加的上面否则会漏掉自己if (startIndex nums.size()) { // 终止条件可以不加return;}for (int i startIndex; i nums.size(); i) {path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}
public:vectorvectorint subsets(vectorint nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};90.子集II
题目链接 解题思路 代码如下
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex, vectorbool used) {result.push_back(path);for (int i startIndex; 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;}path.push_back(nums[i]);used[i] true;backtracking(nums, i 1, used);used[i] false;path.pop_back();}}public:vectorvectorint subsetsWithDup(vectorint nums) {result.clear();path.clear();vectorbool used(nums.size(), false);sort(nums.begin(), nums.end()); // 去重需要排序backtracking(nums, 0, used);return result;}
};
