93.?復(fù)原 IP 地址
思路：
這道題的難點(diǎn)在于如何實(shí)現(xiàn)字符串的切割與有效性驗(yàn)證。切割的方法與第131題一致署咽，用index與i來劃分切割的區(qū)間近顷。注意：遞歸回溯的條件可以用逗點(diǎn)控制，如果逗點(diǎn)為3且最后一個(gè)區(qū)間的字符串也是有效的話宁否，則找到了有效字符串窒升，輸出到res數(shù)組即可。判斷字符串是否有效有以下幾點(diǎn)：1慕匠、區(qū)間左端點(diǎn)小于等于右端點(diǎn)饱须；2、區(qū)間不止一個(gè)元素台谊，且首元素不能為0蓉媳；3譬挚、區(qū)間的每個(gè)字符串都是在0-9之間；4酪呻、區(qū)間數(shù)值不大于255减宣。
代碼：
class Solution {
public:
? ? vector<string> res;
? ? bool isvaild(const string& s, int start, int end)
? ? ? ? {
? ? ? ? ? ? if (start > end) {
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? if (s[start] == '0' && start != end) {
? ? ? ? ? ? ? ? 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) {
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return true;
? ? ? ? }
? ? void backtracking(string& s,int index,int pointsum)
? ? {
? ? ? ? if(pointsum==3)
? ? ? ? {
? ? ? ? ? ? if(isvaild(s,index,s.size()-1))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? res.push_back(s);
? ? ? ? ? ? }
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? for(int i=index;i<s.size();i++)
? ? ? ? {
? ? ? ? ? ? if(isvaild(s,index,i))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s.insert(s.begin() + i + 1 , '.');
? ? ? ? ? ? ? ? pointsum++;
? ? ? ? ? ? ? ? backtracking(s,i+2,pointsum);
? ? ? ? ? ? ? ? s.erase(s.begin() + i + 1);
? ? ? ? ? ? ? ? pointsum--;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? vector<string> restoreIpAddresses(string s) {
? ? ? ? if(s.size()<4||s.size()>12)return res;
? ? ? ? backtracking(s,0,0);
? ? ? ? return res;
? ? }
};
78.?子集
思路：
這道題與以往題目不同的是，在每一次遞歸的過程中都需要收集結(jié)果玩荠，同時(shí)在下一次遞歸之前保存結(jié)果漆腌。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(vector<int>& nums,int index)
? ? {
? ? ? ? res.push_back(path);
? ? ? ? if(index>=nums.size()) return ;
? ? ? ? for(int i=index;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? path.push_back(nums[i]);
? ? ? ? ? ? backtracking(nums,i+1);
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> subsets(vector<int>& nums) {
? ? ? ? backtracking(nums,0);
? ? ? ? return res;
? ? }
};
90.?子集 II
思路：
本題與第78題不一致的地方在于題目給定的數(shù)組中含有重復(fù)的元素，但是輸出的結(jié)果在不能包含重復(fù)的組合阶冈。解體可以分為兩個(gè)環(huán)節(jié)闷尿，收集子集環(huán)節(jié)與第78題一致，去重環(huán)節(jié)與第40題一致眼溶。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(vector<int>& nums,int index,vector<bool> used)
? ? {
? ? ? ? res.push_back(path);
? ? ? ? if(index>=nums.size())return ;
? ? ? ? for(int i=index;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? 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();
? ? ? ? }
? ? }
? ? vector<vector<int>> subsetsWithDup(vector<int>& nums) {
? ? ? ? vector<bool> used(nums.size(),false);
? ? ? ? sort(nums.begin(), nums.end());
? ? ? ? backtracking(nums,0,used);
? ? ? ? return res;
? ? }
};
