中山建设网站官网,互联网广告行业分析,肇庆 网站建设公司有哪些,wordpress 编辑器 代码93.复原IP地址 本期本来是很有难度的#xff0c;不过 大家做完 分割回文串 之后#xff0c;本题就容易很多了 题目链接/文章讲解#xff1a;代码随想录 视频讲解#xff1a;回溯算法如何分割字符串并判断是合法IP#xff1f;| LeetCode#xff1a;93.复原IP地址_哔哩哔…93.复原IP地址 本期本来是很有难度的不过 大家做完 分割回文串 之后本题就容易很多了 题目链接/文章讲解代码随想录 视频讲解回溯算法如何分割字符串并判断是合法IP| LeetCode93.复原IP地址_哔哩哔哩_bilibili Python: class Solution:def __init__(self):self.result []self.path []def isvalid(self, s, start, end):if startend: return Falseif s[start]0 and start!end: return Falsereturn 0int(s[start:end1])255def backtracking(self, s, start_index):if len(self.path)4 and start_indexlen(s):addr ..join(self.path)self.result.append(addr)returnif len(self.path) 4: returnfor i in range(start_index, min(start_index3, len(s))):if self.isvalid(s, start_index, i):self.path.append(s[start_index:i1]) self.backtracking(s, i1)self.path.pop()returndef restoreIpAddresses(self, s: str) - List[str]:if len(s)4 or len(s)12: return []self.backtracking(s, 0)return self.result C: C版本写成直接在string里insert更简洁一些C没有类似python string.join的写法。 class Solution {
public:vectorstring result;void backtracking(string s, int startIndex, int pointNum) {if (pointNum 3) {if (isValid(s, startIndex, s.size()-1)) {result.push_back(s);}return; }for (int i startIndex; i s.size(); i) {if (isValid(s, startIndex, i)) {s.insert(s.begin() i 1, .);backtracking(s, i 2, pointNum1);s.erase(s.begin() i 1);} else break;}}bool isValid(const strings, int start, int end) {if (start end) return false;if (s[start] 0 start ! end) return false;int num0;for (int istart; iend; i) {if (s[i]9 || s[i]0) return false;num num * 10 (s[i] - 0);if (num255) return false;}return true;}vectorstring restoreIpAddresses(string s) {result.clear();if (s.size()4 || s.size()12) return result;backtracking(s, 0, 0);return result;}
}; 78.子集 子集问题就是收集树形结构中每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。 题目链接/文章讲解代码随想录 视频讲解回溯算法解决子集问题树上节点都是目标集和 | LeetCode78.子集_哔哩哔哩_bilibili 本题比较简单 Python class Solution:def __init__(self):self.result []self.path []def backtracking(self, nums, start_index):self.result.append(self.path[:])for i in range(start_index, len(nums)):self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()returndef subsets(self, nums: List[int]) - List[List[int]]:self.backtracking(nums, 0)return self.result C: class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {result.push_back(path); // 要放在终止条件前面否则回漏掉自己if (startIndex nums.size()) return;for (int istartIndex; inums.size(); i) {path.push_back(nums[i]);backtracking(nums, i1);path.pop_back();}return;}vectorvectorint subsets(vectorint nums) {backtracking(nums, 0);return result; }
}; 90.子集II 大家之前做了 40.组合总和II 和 78.子集 本题就是这两道题目的结合建议自己独立做一做本题涉及的知识之前都讲过没有新内容。 题目链接/文章讲解代码随想录 视频讲解回溯算法解决子集问题如何去重| LeetCode90.子集II_哔哩哔哩_bilibili 和上一题类似区别在于去重去重部分和40.组合总和II 类似。 Python: class Solution:def __init__(self):self.result []self.path []def backtracking(self, nums, start_index):self.result.append(self.path[:]) for i in range(start_index, len(nums)):if istart_index and nums[i]nums[i-1]: continue # 去重self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()returndef subsetsWithDup(self, nums: List[int]) - List[List[int]]:nums.sort()self.backtracking(nums, 0)return self.result C: class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {result.push_back(path);for (int istartIndex; inums.size(); i) {if (istartIndex nums[i]nums[i-1]) continue; //去重path.push_back(nums[i]);backtracking(nums, i1);path.pop_back();}return;}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());backtracking(nums, 0);return result; }
};
