一、参考资料
复原IP地址
题目链接/文章讲解:https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
视频讲解:https://www.bilibili.com/video/BV1XP4y1U73i/
子集
题目链接/文章讲解:https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
视频讲解:https://www.bilibili.com/video/BV1U84y1q7Ci
子集II
题目链接/文章讲解:https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
视频讲解:https://www.bilibili.com/video/BV1vm4y1F71J
二、LeetCode93.复原IP地址
https://leetcode.cn/problems/restore-ip-addresses/description/
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。
例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 " [email protected]" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的 有效 IP 地址,这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1:
输入:s = "25525511135" 输出:["255.255.11.135","255.255.111.35"]
示例 2:
输入:s = "0000" 输出:["0.0.0.0"]
示例 3:
输入:s = "101023" 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示:
1 <= s.length <= 20
s 仅由数字组成
切割问题可以抽象为树型结构,如图:
![](/i/ll/?i=img_convert/7e62528d0b9fbe58e15113db7e4d182f.png)
感觉在昨天的基础上理解~思路顺畅好多
- class Solution {
- private:
- vector<string> res;
- bool isValid(string s, int begin, int end) {
- if (begin > end) return false;
- if (s[begin] == '0' && begin != end) return false;
- int num = 0;
- for (int i = begin; i <= end; i++) {
- if (s[i] < '0' || s[i] > '9') return false;
- num = num * 10 + (s[i] - '0');
- if (num > 255) return false;
- }
- return true;
- }
- void backtracking(string& s, int startIndex, int pointNum) {
- if (pointNum == 3) {
- if (isValid(s, startIndex, s.size() - 1)) {
- res.push_back(s);
- }
- return ;
- }
- for (int i = startIndex; i < s.size(); i++) {
- if (isValid(s, startIndex, i)) {
- s.insert(s.begin() + i + 1, '.');
- pointNum += 1;
- backtracking(s, i + 2, pointNum);
- pointNum -= 1;
- s.erase(s.begin() + i + 1);
- } else break;
- }
- }
- public:
- vector<string> restoreIpAddresses(string s) {
- if (s.size() < 4 || s.size() > 12) return res;
- backtracking(s, 0, 0);
- return res;
- }
- };
带注释版:
- class Solution {
- private:
- vector<string> result;// 记录结果
- // startIndex: 搜索的起始位置,pointNum:添加逗点的数量
- void backtracking(string& s, int startIndex, int pointNum) {
- if (pointNum == 3) { // 逗点数量为3时,分隔结束
- // 判断第四段子字符串是否合法,如果合法就放进result中
- 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)) { // 判断 [startIndex,i] 这个区间的子串是否合法
- s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
- pointNum++;
- backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
- pointNum--; // 回溯
- s.erase(s.begin() + i + 1); // 回溯删掉逗点
- } else break; // 不合法,直接结束本层循环
- }
- }
- // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
- bool isValid(const string& s, int start, int end) {
- if (start > end) {
- return false;
- }
- if (s[start] == '0' && start != end) { // 0开头的数字不合法
- return false;
- }
- int num = 0;
- for (int i = start; i <= end; i++) {
- if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
- return false;
- }
- num = num * 10 + (s[i] - '0');
- if (num > 255) { // 如果大于255了不合法
- return false;
- }
- }
- return true;
- }
- public:
- vector<string> restoreIpAddresses(string s) {
- result.clear();
- if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
- backtracking(s, 0, 0);
- return result;
- }
- };
三、LeetCode78.子集
https://leetcode.cn/problems/subsets/description/
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!
![](/i/ll/?i=img_convert/13b42df15a0905ef8e39e7125948639b.png)
从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合。
- class Solution {
- private:
- vector<vector<int>> result;
- vector<int> path;
- void backtracking(vector<int>& nums, int startIndex) {
- result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉自己
- if (startIndex >= nums.size()) { // 终止条件可以不加
- return;
- }
- for (int i = startIndex; i < nums.size(); i++) {
- path.push_back(nums[i]);
- backtracking(nums, i + 1);
- path.pop_back();
- }
- }
- public:
- vector<vector<int>> subsets(vector<int>& nums) {
- result.clear();
- path.clear();
- backtracking(nums, 0);
- return result;
- }
- };
在注释中,可以发现可以不写终止条件,因为本来我们就要遍历整棵树。
有的同学可能担心不写终止条件会不会无限递归?
并不会,因为每次递归的下一层就是从i+1开始的。
我写的如下~【唔,理解了思路后first blood】
- class Solution {
- private:
- vector<int> path;
- vector<vector<int>> res;
- void backtracking (vector<int> nums, int startIndex) {
- res.push_back(path);
- if (startIndex > nums.size()) return ;
- for (int i = startIndex; i < nums.size(); i++) {
- path.push_back(nums[i]);
- backtracking(nums, i + 1);
- path.pop_back();
- }
- }
- public:
- vector<vector<int>> subsets(vector<int>& nums) {
- backtracking(nums, 0);
- return res;
- }
- };
四、LeetCode90.子集II
https://leetcode.cn/problems/subsets-ii/description/
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
带注释版:
- class Solution {
- private:
- vector<vector<string>> result;
- vector<string> path; // 放已经回文的子串
- void backtracking (const string& s, int startIndex) {
- // 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
- if (startIndex >= s.size()) {
- result.push_back(path);
- return;
- }
- for (int i = startIndex; i < s.size(); i++) {
- if (isPalindrome(s, startIndex, i)) { // 是回文子串
- // 获取[startIndex,i]在s中的子串
- string str = s.substr(startIndex, i - startIndex + 1);
- path.push_back(str);
- } else { // 不是回文,跳过
- continue;
- }
- backtracking(s, i + 1); // 寻找i+1为起始位置的子串
- path.pop_back(); // 回溯过程,弹出本次已经填在的子串
- }
- }
- bool isPalindrome(const string& s, int start, int end) {
- for (int i = start, j = end; i < j; i++, j--) {
- if (s[i] != s[j]) {
- return false;
- }
- }
- return true;
- }
- public:
- vector<vector<string>> partition(string s) {
- result.clear();
- path.clear();
- backtracking(s, 0);
- return result;
- }
- };
优化后的代码就没详细学了
我能自己写出这个题的代码,已经觉得自己真的进步很大了:
- class Solution {
- private:
- vector<string> path;
- vector<vector<string>> res;
- bool isPalinedromic(string s, int begin, int end) {
- for (int i = begin, j = end; i < j; i++, j--) {
- if (s[i] != s[j]) return false;
- }
- return true;
- }
- void backtracking (string s, int startIndex) {
- if(startIndex > s.size()) return ;
- if (startIndex == s.size()) {
- res.push_back(path);
- return ;
- }
- for(int i = startIndex; i < s.size(); i++) {
- if(isPalinedromic(s, startIndex, i)) {
- string str = s.substr(startIndex, i - startIndex + 1);
- path.push_back(str);
- } else continue;
- backtracking(s, i + 1);
- path.pop_back();
- }
- }
- public:
- vector<vector<string>> partition(string s) {
- backtracking(s, 0);
- return res;
- }
- };
今日总结:
题目确实是当天写完的,只是博客没有及时写
感觉到自己真的进步好多了,能够理解懂视频的题目讲解,经历一些debug后还能尝试控制时间的前提下独立完成代码。
今天的难点应该挺多的,我花了很多时间理解来着,讲解回文串分割的视频应该看了两遍。
另外今天的组合数一个不太容易想到题解的“去重”问题,也是挺困扰,希望真的掌握后能做到举一反三呢
继续加油哈小赵~
标签:return,nums,int,随想录,II,startIndex,vector,子集,backtracking From: https://www.cnblogs.com/ucaszym/p/17113160.html