做微信支付的网站多少钱,赣州人才网招聘信息,代码开源网站,佛山百度网站快速排名文章目录 Leetcode 93-复原 IP 地址题目描述解题思路 Leetcode 78-子集题目描述解题思路 Leetcode 90-子集 Ⅱ题目描述解题思路 Leetcode 93-复原 IP 地址
题目描述
https://leetcode.cn/problems/restore-ip-addresses/description/ 解题思路
这是一道切割问题#xff0c;… 文章目录 Leetcode 93-复原 IP 地址题目描述解题思路 Leetcode 78-子集题目描述解题思路 Leetcode 90-子集 Ⅱ题目描述解题思路 Leetcode 93-复原 IP 地址
题目描述
https://leetcode.cn/problems/restore-ip-addresses/description/ 解题思路
这是一道切割问题可以参考分割回文串的思路
采用 isValid 函数判断当前切割得到的子串是否有效
class Solution {
public:vectorstring res;bool isValid(string s, int start, int end){if(start end) return false;if (s[start] 0 end - start 0) return false;if (end - start 1 3) return false; // 添加长度检查string sub s.substr(start, end-start1);int num stoi(sub);if (num 255) return false;return true;}void backTracking(string s, int startIndex, int dotNum){if(dotNum 3){if (isValid(s, startIndex,s.size()-1)){res.push_back(s);}return;}for (int i startIndex; i startIndex3 i s.size();i){if (isValid(s, startIndex,i)){s.insert(s.begin()i1,.);dotNum 1;backTracking(s, i 2, dotNum);dotNum - 1;s.erase(s.begin()i1);}}}vectorstring restoreIpAddresses(string s) {backTracking(s,0,0);return res;}
};Leetcode 78-子集
题目描述
https://leetcode.cn/problems/subsets/description/ 解题思路
在子集问题中需要在每一层递归中进行结果的收集
class Solution {
public:vectorvectorint res;vectorint path;void backTracking(vectorint nums, int count, int startIndex){if (path.size()count) {res.push_back(path);return;}for (int i startIndex; i nums.size();i){path.push_back(nums[i]);backTracking(nums,count, i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {for (int i 0; i nums.size(); i){backTracking(nums,i,0);}return res;}
};Leetcode 90-子集 Ⅱ
题目描述
https://leetcode.cn/problems/subsets-ii/description/ 解题思路
class Solution {
public:vectorvectorint res;vectorint path;void backTracking(vectorint nums, int startIndex){res.push_back(path);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]);backTracking(nums,i1);path.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());backTracking(nums,0);return res;}
};
