赞
踩
非科班学习算法day24 | LeetCode93:复原IP地址 ,Leetcode78:子集 ,Leetcode90: 子集||
包含LC的几道题目,还有相应概念的补充。
相关图解和更多版本:
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF
题目链接:93. 复原 IP 地址 - 力扣(LeetCode)
题目解析
理解角度很重要,我们可以将问题化归,将其理解为划分类似的做法,不过这次要将划线(‘.’)插入到原始字符串,当然这里也可以仍然利用路径来做,不过要注意的更多了,后面仅仅贴出尝试结果。不过哪种做法都需要一个辅助函数判断字符串是否符合地址要求,就和判断是否是回文串一样,极大的帮助我们代码分块,理清楚逻辑。
c++代码如下:
- class Solution {
- public:
- // 类似分割问题,不过需要插入新的字符
-
- // 创建结果
- vector<string> res;
-
- // 判断合法字符串
- bool isValid(string s, int start, int end) {
- // 不满足情况
- // 1.没有在0到255
-
- // 2.不能有前导0
- if (start > end)
- return false;
- if (s[start] == '0' && start != end)
- return false;
- int num = 0;
- for (int i = start; 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 index, int pointnum) {
- // 终止条件
- if (pointnum == 3) {
- if (isValid(s, index, s.size() - 1)) {
- res.push_back(s);
- }
- return;
- }
-
- for (int i = index; i < s.size(); ++i) {
- if (isValid(s, index, i)) {
- s.insert(s.begin() + i + 1, '.');
- pointnum++;
- backtracking(s, i + 2, pointnum);
- pointnum--;
- s.erase(s.begin() + i + 1);
- } else
- break;
- }
- }
- vector<string> restoreIpAddresses(string s) {
- backtracking(s, 0, 0);
- return res;
- }
- };

注意点1:最重要的i+2,因为现在引用字符串已经加入了一个点。
注意点2:引入了点计数,帮助我们判断什么时候达到中止条件,中止添加结果之前需要检查第四部分是否符合我们的地址要求!
注意点3:这个辅助函数是对字符串很经典的操作,多写多练
用路径的c++代码:
- class Solution {
- public:
- // 创建接受结果
- vector<string> res;
- // 创建路径
- string path;
-
- // 创建检验IP地址部分是否合法的函数
- bool isValidPart(const string& s) {
- if (s.empty() || s.size() > 3) return false;
- if (s.front() == '0' && s.size() > 1) return false; // 0开头的多位数不合法
- int val = stoi(s);
- return val >= 0 && val <= 255;
- }
-
- // 创建回溯函数
- void backtracking(string s, int startIndex, int partCount) {
- if (partCount == 4) {
- if (startIndex == s.size()) {
- res.push_back(path);
- }
- return;
- }
-
- for (int len = 1; len <= 3 && startIndex + len <= s.size(); ++len) {
- string curPart = s.substr(startIndex, len);
- if (isValidPart(curPart)) {
- if (partCount != 0) {
- path += ".";
- }
- path += curPart;
- backtracking(s, startIndex + len, partCount + 1);
- path.resize(path.size() - curPart.size());
- if (partCount != 0) {
- path.pop_back(); // 移除最后一个"."
- }
- }
- }
- }
-
- vector<string> restoreIpAddresses(string s) {
- backtracking(s, 0, 0);
- return res;
- }
- };

题目解析
子集问题和组合问题最大的区别就是:组合需要全部元素,也就是说组合收集的是叶子节点,而子集问题需要的是所有的可能。
C++代码如下:
- class Solution {
- public:
- // 子集问题最重要的是收获包括中间节点
- // 结果
- vector<vector<int>> res;
- // 路径
- vector<int> path;
- // 回溯函数-还是需要index,因为要的是组合不是排列
- void backtracking(vector<int>& nums, int index) {
- // 添加结果
- res.push_back(path);
- // 中止
- for (int i = index; i < nums.size(); i++) {
- path.push_back(nums[i]);
- backtracking(nums, i + 1);
- path.pop_back();
- }
- }
- vector<vector<int>> subsets(vector<int>& nums) {
- backtracking(nums, 0);
- return res;
- }
- };

注意点1:这里需要没有显式的写中止条件,其实就是中止在for循环全部结束之后,所以可以省略中止条件。
注意点2:这里需要在进入递归时就将结果收集,而不是判断结果之后收集,可以借助空集来理解这个问题。
题目解析
子集的进阶,多了一个条件就是数组内部存在重复的元素,这就和之前在组合遇到的去重很像,就是在树枝去重。其他的部分就和子集的算法没有区别。
C++代码如下:
- class Solution {
- public:
- // 和子集的区别就是有重复元素-树层去重
- // 结果
- vector<vector<int>> res;
- // 路径
- vector<int> path;
-
- // 回溯函数
- void backtracking(vector<int>& nums, int index, vector<bool>& used) {
- // 收集结果
- res.push_back(path);
-
- for (int i = index; i < nums.size(); i++) {
- // 树层去重
- if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
- continue;
- }
- path.push_back(nums[i]);
- used[i] = true;
- backtracking(nums, i + 1, used);
- path.pop_back();
- used[i] = false;
- }
- }
- vector<vector<int>> subsetsWithDup(vector<int>& nums) {
- // 初始化usd数组-因为要借助nums所以没有放在全局
- vector<bool> used = vector<bool>(nums.size(), false);
- sort(nums.begin(), nums.end());
- backtracking(nums, 0, used);
- return res;
- }
- };

注意点1:去重一定要将数组排序!
使用set的C++代码如下:
- class Solution {
- private:
- vector<vector<int>> result;
- vector<int> path;
- void backtracking(vector<int>& nums, int startIndex) {
- result.push_back(path);
- unordered_set<int> uset;
- for (int i = startIndex; i < nums.size(); i++) {
- if (uset.find(nums[i]) != uset.end()) {
- continue;
- }
- uset.insert(nums[i]);
- path.push_back(nums[i]);
- backtracking(nums, i + 1);
- path.pop_back();
- }
- }
-
- public:
- vector<vector<int>> subsetsWithDup(vector<int>& nums) {
- result.clear();
- path.clear();
- sort(nums.begin(), nums.end()); // 去重需要排序
- backtracking(nums, 0);
- return result;
- }
- };

注意点1:学习了一下使用set的方法,set去重的逻辑也比较直接,每一次检查在设定的set中是否有之前添加的相同元素,如果有就跳过,没有就将其加入然后执行递归。
注意点2:set的find返回的是迭代器位置!
打卡第24天,坚持!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。