408算法题leetcode--第31天

93. 复原 IP 地址

题目地址：93. 复原 IP 地址 - 力扣（LeetCode）

题解思路：回溯

时间复杂度：O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式

空间复杂度：O(n)

代码:

class Solution {
public:vector<string>ret;bool isValid(string& str, int start, int end){if(end < start){return false;}if(str[start] == '0' && start != end){return false;}int num = 0;for(int i = start; i <= end; i++){num = 10 * num + (str[i] - '0');if(num > 255){return false;}}return true;}void backtrack(string& s, int start, int point){// 只能有三个小数点if(point == 3){if(isValid(s, start, s.size() - 1)){ret.push_back(s);}return ;}int size = s.size();for(int i = start; i < size; i++){if(isValid(s, start, i)){s.insert(s.begin() + i + 1, '.');  // 插入小数点point++;backtrack(s, i + 2, point);point--;s.erase(s.begin() + i + 1);} else {break;}}}vector<string> restoreIpAddresses(string s) {// 剪枝if(s.size() < 4 || s.size() > 12) return ret;backtrack(s, 0, 0);return ret;}
};

78. 子集

题目地址：78. 子集 - 力扣（LeetCode）

题解思路：找子集问题

时间复杂度：O(n * 2^{n)，n个数，每个数考虑选or不选（2}n）

空间复杂度：O(n)

代码:

class Solution {
public:vector<vector<int>>ret;vector<int>v;void backtrack(vector<int>&nums, int start){ret.push_back(v);  // 子集if(start >= nums.size()){return ;}int size = nums.size();for(int i = start; i < size; i++){v.push_back(nums[i]);backtrack(nums, i + 1);v.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {// 子集问题，找到所有节点集合backtrack(nums, 0);return ret;}
};