93. 復原 IP 地址
題目鏈接：https://leetcode.cn/problems/restore-ip-addresses/
算法思想：回溯算法。
重要的是如何切割?？梢允褂靡粋€變量point_num記錄下切割的次數(shù)，作為終止條件。
class Solution {
public:
? ? vector<vector<string>> final;
? ? vector<string> path;
? ? bool hefa(string sub)
? ? {
? ? ? ? if(sub.size()>1&&sub[0] == '0')
? ? ? ? ? ? return false;
? ? ? ? if(sub == "")
? ? ? ? ? ? return false;
? ? ? ? int sub_i = atoi(sub.c_str());
? ? ? ? if(sub_i <=255&&sub_i>=0)
? ? ? ? ? ? return true;
? ? ? ? return false;
? ? }
? ? void huisu(string &s, int start,int point_num)
? ? {
? ? ? ? if(point_num == 3)
? ? ? ? {
? ? ? ? ? ? string sub = s.substr(start, s.size()-start);
? ? ? ? ? ? // cout<<"sub:"<<sub<<endl;
? ? ? ? ? ? if(hefa(sub))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? path.push_back(s);
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(int i = start; i< s.size();i++)
? ? ? ? {
? ? ? ? ? ? string sub = s.substr(start, i-start+1);
? ? ? ? ? ? if(!hefa(sub))
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? point_num++;
? ? ? ? ? ? s.insert(s.begin()+i+1, '.');
? ? ? ? ? ? // path.push_back(sub);
? ? ? ? ? ? huisu(s, i+2, point_num);
? ? ? ? ? ? point_num--;
? ? ? ? ? ? s.erase(s.begin()+i+1);
? ? ? ? }
? ? }
? ? vector<string> restoreIpAddresses(string s) {
? ? ? ? huisu(s, 0, 0);
? ? ? ? vector<string> res;
? ? ? ? return path;
? ? }
};
78. 子集
https://leetcode.cn/problems/subsets/
算法思想: 回溯。
要注意收集結(jié)果的位置是每次進入for循環(huán)之前收集。
class Solution {
public:
? ? vector<vector<int>> res;
? ? vector<int> path;
? ? void huisu(vector<int>& nums, int start)
? ? {
? ? ? ? res.push_back(path);
? ? ? ? if(start == nums.size())
? ? ? ? {?
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? // cout<<"start:"<<start<<endl;
? ? ? ? for(int i=start; i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? path.push_back(nums[i]);
? ? ? ? ? ? huisu(nums, i+1);
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> subsets(vector<int>& nums) {
? ? ? ? huisu(nums,0);
? ? ? ? return res;
? ? }
};
90. 子集 II
題目鏈接：https://leetcode.cn/problems/subsets-ii/
算法思想：
回溯。
不包含重復元素，則需排序。
class Solution {
public:
? ? vector<vector<int>> output;
? ? vector<int> res;
? ? void huisu(vector<int>& nums, int start)
? ? {
? ? ? ? output.push_back(res);
? ? ? ? if(start==nums.size())
? ? ? ? ? ? return;
? ? ? ? for(int i=start;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? if(i!=start&&nums[i]==nums[i-1])
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? res.push_back(nums[i]);
? ? ? ? ? ? huisu(nums, i+1);
? ? ? ? ? ? res.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> subsetsWithDup(vector<int>& nums) {
? ? ? ? sort(nums.begin(), nums.end());
? ? ? ? huisu(nums, 0);
? ? ? ? return output;
? ? }
};
