提供企业网站建设公司,前端如何优化seo,个体工商户营业执照,视频网站建设工具93.复原IP地址
题目链接#xff1a;93.复原IP地址思路#xff1a; 做法和分割回文字符串那题类似#xff0c;是对字符串进行切割#xff1b;本题需要多几个条件#xff0c;就是每次回溯字符串的长度最多三位#xff0c;字符串对应的数值必须 在[0, 255]之间#xff0c;…93.复原IP地址
题目链接93.复原IP地址思路 做法和分割回文字符串那题类似是对字符串进行切割本题需要多几个条件就是每次回溯字符串的长度最多三位字符串对应的数值必须 在[0, 255]之间并且不能有前导0的存在并且只能被切割成4个字符串 代码
class Solution {
public:vectorstring restoreIpAddresses(string s) {vectorstring ans;vectorstring tmp;if(s.size() 12) // 字符串长度最大为12return {};int n s.size();auto dfs [](auto dfs, int k) {if(k n tmp.size() 4) // 切割了四个数但是字符串还剩下不符合return;if(k n tmp.size() 4) { // 符合条件stringstream ss; // 将字符串数组转化为ip地址for(int i 0; i 4; i) {ss tmp[i];if(i ! 3) ss .;} ans.push_back(ss.str());}string str ;for(int i k; i n i k 3; i) {str s[i];if(stoi(str) 255) { // 在[0. 255]之前tmp.push_back(str);dfs(dfs, i1);tmp.pop_back();}if(s[k] 0) // 去除前导0break;}};dfs(dfs, 0);return ans;}
};
78.子集
题目链接78.子集思路本题较为简单每次一个数没有被选择的数即可组成一个集合将集合放入到答案中即可代码
class Solution {
public:vectorvectorint subsets(vectorint nums) {vectorvectorint ans;vectorint tmp;int n nums.size();auto dfs [](auto dfs, int i) {ans.push_back(tmp); // 记录集合if(i n) {return;}for(int j i; j n; j) {tmp.push_back(nums[j]); // 选一个数dfs(dfs, j1);tmp.pop_back();}};dfs(dfs, 0);return ans;}
};
90.子集II
题目链接90.子集II思路思路和子集那道题一样不同的是这道题需要进行去重相同数字在一次回溯函数过程中只能被选择一次需要进行去重所以需要先排序代码 class Solution {
public:vectorvectorint subsetsWithDup(vectorint nums) {vectorvectorint ans;vectorint tmp;ranges::sort(nums); // 数组排序方便去重int n nums.size();auto dfs [](auto dfs, int i) {ans.push_back(tmp);if(i n) {return;}for(int j i; j n; j) {if(j ! i nums[j] nums[j-1]) // 去重continue;tmp.push_back(nums[j]);dfs(dfs, j1);tmp.pop_back();}};dfs(dfs, 0);return ans;}
};
