代码随想录第27天|回溯算法

本文主要是介绍代码随想录第27天|回溯算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

93.复原IP地址

补充:
字符串的操作
str.insert() 发生重载
str.insert(str.begin(), ‘x’) 只能是插入char类型 insert(const const_iterator _Where, const _Elem _Ch)
str.insert(0, “x”) 只能是 string类型 insert(const size_type _Off, In_z const _Elem* const _Ptr)

思路:
类似字符串的切割, 传入的区间为左闭右闭 [left, right]

//自行实现, 比较复杂
class Solution {
public:vector<vector<string>> res;vector<string> res_tem;bool judge(string& str) {if (!(str.length() <= 3)) return false;if (str.length() > 1 && str[0] == '0') return false;int value = stoi(str);return (value >= 0 && value <= 255)? true : false;        }void myoperator(string& s, int index, int count) {if (res_tem.size() == 4) {res.push_back(res_tem);return;}for (int i = index; i < s.length(); i++) {if (count == 4) i = s.length() - 1;string str(s, index, i - index + 1);if (judge(str)) {res_tem.push_back(str);}   else {continue;}myoperator(s, i + 1, count + 1);res_tem.pop_back();}}vector<string> restoreIpAddresses(string s) {myoperator(s, 0, 1);vector<string> result;for (auto it = res.begin(); it != res.end(); it++) {string tem = "";for (auto i = (*it).begin(); i != (*it).end(); i++) {if (tem != "") tem += ".";tem += *i;}result.push_back(tem);}return result;}
};

78.子集

class Solution {
public:vector<vector<int>> res;vector<int> res_tem;void myoperator(vector<int>& nums, int index) {res.push_back(res_tem);if (index >= nums.size()) return;for (int i = index; i < nums.size(); i++) {res_tem.push_back(nums[i]);myoperator(nums, i + 1);res_tem.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {myoperator(nums, 0);return res;}
};

90.子集II

思路:
同样需要进行树层去重

class Solution {
public:vector<vector<int>> res;vector<int> res_tem;vector<bool> used;void myoperator(vector<int>& nums, int index) {        res.push_back(res_tem);//收集元素if (index >= nums.size()) {return;}for (int i = index; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) {//去重操作continue;//此处不是break和return, 需要继续遍历}used[i] = 1;res_tem.push_back(nums[i]);myoperator(nums, i + 1);used[i] = 0;res_tem.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {used = vector<bool>(nums.size(), 0);sort(nums.begin(), nums.end());myoperator(nums, 0);return res;}
};