徐州英才网最新招聘信息,seo文案范例,wordpress添加源代码,建站之星和凡科建站哪个系统好目录
LeetCode:93.复原IP地址
基本思路
C代码
LeetCode:78.子集
基本思路
C代码
LeetCode:90.子集II
基本思路
C代码
通过used实现去重
通过set实现去重
不使用used和set版本 LeetCode:93.复原IP地址 力扣代码链接 文字讲解#xff1a;LeetCode:93.复原IP地…目录
LeetCode:93.复原IP地址
基本思路
C代码
LeetCode:78.子集
基本思路
C代码
LeetCode:90.子集II
基本思路
C代码
通过used实现去重
通过set实现去重
不使用used和set版本 LeetCode:93.复原IP地址 力扣代码链接 文字讲解LeetCode:93.复原IP地址 视频讲解回溯算法如何分割字符串并判断是合法IP 基本思路 首先应该意识到属于切割问题而切割问题就是和之前做过的分割回文串是类似的要通过回溯算法将所有的可能性搜索出来抽象为树形结构可以表示为 递归函数参数 需要定义一个全局变量vectorstring result用来存放符合条件的结果。 参数startIndex一定是需要的因为不能重复分割记录下一层递归分割的起始位置。另外还需要一个变量pointNum记录添加逗点的数量。
vectorstring result;// 记录结果
// startIndex: 搜索的起始位置pointNum:添加逗点的数量
void backtracking(string s, int startIndex, int pointNum)
递归终止条件 本题明确要求只会分成4段所以不能用切割线切到最后作为终止条件而是分割的段数作为终止条件。pointNum表示逗点数量pointNum为3说明字符串分成了4段了。然后验证一下第四段是否合法如果合法就加入到结果集里。
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)循环中 [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;}
};LeetCode:78.子集 力扣代码链接 文字讲解LeetCode:78.子集 视频讲解回溯算法解决子集问题树上节点都是目标集和 基本思路 如果把子集问题、组合问题、分割问题都抽象为一棵树的话那么组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点但是要求解集中不能包含重复的子集写回溯算法的时候for就要从startIndex开始而不是从0开始当然如果{1, 2} 和{2, 1}是两个集合那么我们就需要从0开始。 递归函数参数
全局变量数组path为子集收集元素二维数组result存放子集组合。
参数前面已经提到需要传入startIndex以及整数数组nums。
vectorvectorint result;
vectorint path;
void backtracking(vectorint nums, int startIndex)
递归终止条件 startIndex表示集合搜索的位置那么如果startIndex超过了nums的size不就说明没有元素可取了也就可以停止循环了但其实本来startIndex nums.size()就是for循环的终止条件。
if (startIndex nums.size()) {return;
}
单层搜索逻辑
求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。
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;}
};LeetCode:90.子集II 力扣代码链接 文字讲解LeetCode:90.子集II 视频讲解回溯算法解决子集问题如何去重 基本思路 这个题目和上一题的区别在于集合里有重复元素了而且求取的子集要去重。其实和之前做到的组合总和很像是一个套路。因此理解“树层去重”和“树枝去重”非常重要。 从图中可以看出同一树层上重复取2就要过滤掉同一树枝上就可以重复取2因为同一树枝上元素的集合才是唯一子集
去重思路和40.组合总和II这里就直接给出代码。
C代码
通过used实现去重
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;}
};
通过set实现去重
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {result.push_back(path);unordered_setint uset;for (int i startIndex; i nums.size(); i) {if (uset.find(nums[i]) ! uset.end()) {continue;}uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}public:vectorvectorint subsetsWithDup(vectorint nums) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 去重需要排序backtracking(nums, 0);return result;}
};
不使用used和set版本
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {result.push_back(path);for (int i startIndex; i nums.size(); i) {// 而我们要对同一树层使用过的元素进行跳过if (i startIndex nums[i] nums[i - 1] ) { // 注意这里使用i startIndexcontinue;}path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}public:vectorvectorint subsetsWithDup(vectorint nums) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 去重需要排序backtracking(nums, 0);return result;}
};
