当前位置:   article > 正文

代码随想录算法训练营:24/60_代码随想录网站在哪

代码随想录网站在哪

非科班学习算法day24 | LeetCode93:复原IP地址 ,Leetcode78:子集 ,Leetcode90: 子集||


介绍

包含LC的几道题目,还有相应概念的补充。

相关图解和更多版本:

代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF


一、LeetCode题目

1.LeetCode93:复原ip地址 

题目链接:93. 复原 IP 地址 - 力扣(LeetCode)

题目解析

       理解角度很重要,我们可以将问题化归,将其理解为划分类似的做法,不过这次要将划线(‘.’)插入到原始字符串,当然这里也可以仍然利用路径来做,不过要注意的更多了,后面仅仅贴出尝试结果。不过哪种做法都需要一个辅助函数判断字符串是否符合地址要求,就和判断是否是回文串一样,极大的帮助我们代码分块,理清楚逻辑。

 c++代码如下:

  1. class Solution {
  2. public:
  3. // 类似分割问题,不过需要插入新的字符
  4. // 创建结果
  5. vector<string> res;
  6. // 判断合法字符串
  7. bool isValid(string s, int start, int end) {
  8. // 不满足情况
  9. // 1.没有在0255
  10. // 2.不能有前导0
  11. if (start > end)
  12. return false;
  13. if (s[start] == '0' && start != end)
  14. return false;
  15. int num = 0;
  16. for (int i = start; i <= end; i++) {
  17. if (s[i] < '0' || s[i] > '9')
  18. return false;
  19. num = num * 10 + (s[i] - '0');
  20. if (num > 255)
  21. return false;
  22. }
  23. return true;
  24. }
  25. // 回溯函数
  26. void backtracking(string& s, int index, int pointnum) {
  27. // 终止条件
  28. if (pointnum == 3) {
  29. if (isValid(s, index, s.size() - 1)) {
  30. res.push_back(s);
  31. }
  32. return;
  33. }
  34. for (int i = index; i < s.size(); ++i) {
  35. if (isValid(s, index, i)) {
  36. s.insert(s.begin() + i + 1, '.');
  37. pointnum++;
  38. backtracking(s, i + 2, pointnum);
  39. pointnum--;
  40. s.erase(s.begin() + i + 1);
  41. } else
  42. break;
  43. }
  44. }
  45. vector<string> restoreIpAddresses(string s) {
  46. backtracking(s, 0, 0);
  47. return res;
  48. }
  49. };

注意点1:最重要的i+2,因为现在引用字符串已经加入了一个点。

注意点2:引入了点计数,帮助我们判断什么时候达到中止条件,中止添加结果之前需要检查第四部分是否符合我们的地址要求!

注意点3:这个辅助函数是对字符串很经典的操作,多写多练

用路径的c++代码:

  1. class Solution {
  2. public:
  3. // 创建接受结果
  4. vector<string> res;
  5. // 创建路径
  6. string path;
  7. // 创建检验IP地址部分是否合法的函数
  8. bool isValidPart(const string& s) {
  9. if (s.empty() || s.size() > 3) return false;
  10. if (s.front() == '0' && s.size() > 1) return false; // 0开头的多位数不合法
  11. int val = stoi(s);
  12. return val >= 0 && val <= 255;
  13. }
  14. // 创建回溯函数
  15. void backtracking(string s, int startIndex, int partCount) {
  16. if (partCount == 4) {
  17. if (startIndex == s.size()) {
  18. res.push_back(path);
  19. }
  20. return;
  21. }
  22. for (int len = 1; len <= 3 && startIndex + len <= s.size(); ++len) {
  23. string curPart = s.substr(startIndex, len);
  24. if (isValidPart(curPart)) {
  25. if (partCount != 0) {
  26. path += ".";
  27. }
  28. path += curPart;
  29. backtracking(s, startIndex + len, partCount + 1);
  30. path.resize(path.size() - curPart.size());
  31. if (partCount != 0) {
  32. path.pop_back(); // 移除最后一个"."
  33. }
  34. }
  35. }
  36. }
  37. vector<string> restoreIpAddresses(string s) {
  38. backtracking(s, 0, 0);
  39. return res;
  40. }
  41. };

 2.Leetcode78:子集 

题目链接:78. 子集 - 力扣(LeetCode)

题目解析

       子集问题和组合问题最大的区别就是:组合需要全部元素,也就是说组合收集的是叶子节点,而子集问题需要的是所有的可能。

 C++代码如下: 

  1. class Solution {
  2. public:
  3. // 子集问题最重要的是收获包括中间节点
  4. // 结果
  5. vector<vector<int>> res;
  6. // 路径
  7. vector<int> path;
  8. // 回溯函数-还是需要index,因为要的是组合不是排列
  9. void backtracking(vector<int>& nums, int index) {
  10. // 添加结果
  11. res.push_back(path);
  12. // 中止
  13. for (int i = index; i < nums.size(); i++) {
  14. path.push_back(nums[i]);
  15. backtracking(nums, i + 1);
  16. path.pop_back();
  17. }
  18. }
  19. vector<vector<int>> subsets(vector<int>& nums) {
  20. backtracking(nums, 0);
  21. return res;
  22. }
  23. };

 注意点1:这里需要没有显式的写中止条件,其实就是中止在for循环全部结束之后,所以可以省略中止条件。

注意点2:这里需要在进入递归时就将结果收集,而不是判断结果之后收集,可以借助空集来理解这个问题。

3.Leetcode90:子集||

题目链接:90. 子集 II - 力扣(LeetCode)

题目解析

       子集的进阶,多了一个条件就是数组内部存在重复的元素,这就和之前在组合遇到的去重很像,就是在树枝去重。其他的部分就和子集的算法没有区别。

C++代码如下:

  1. class Solution {
  2. public:
  3. // 和子集的区别就是有重复元素-树层去重
  4. // 结果
  5. vector<vector<int>> res;
  6. // 路径
  7. vector<int> path;
  8. // 回溯函数
  9. void backtracking(vector<int>& nums, int index, vector<bool>& used) {
  10. // 收集结果
  11. res.push_back(path);
  12. for (int i = index; i < nums.size(); i++) {
  13. // 树层去重
  14. if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
  15. continue;
  16. }
  17. path.push_back(nums[i]);
  18. used[i] = true;
  19. backtracking(nums, i + 1, used);
  20. path.pop_back();
  21. used[i] = false;
  22. }
  23. }
  24. vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  25. // 初始化usd数组-因为要借助nums所以没有放在全局
  26. vector<bool> used = vector<bool>(nums.size(), false);
  27. sort(nums.begin(), nums.end());
  28. backtracking(nums, 0, used);
  29. return res;
  30. }
  31. };

注意点1:去重一定要将数组排序!

使用set的C++代码如下:

  1. class Solution {
  2. private:
  3. vector<vector<int>> result;
  4. vector<int> path;
  5. void backtracking(vector<int>& nums, int startIndex) {
  6. result.push_back(path);
  7. unordered_set<int> uset;
  8. for (int i = startIndex; i < nums.size(); i++) {
  9. if (uset.find(nums[i]) != uset.end()) {
  10. continue;
  11. }
  12. uset.insert(nums[i]);
  13. path.push_back(nums[i]);
  14. backtracking(nums, i + 1);
  15. path.pop_back();
  16. }
  17. }
  18. public:
  19. vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  20. result.clear();
  21. path.clear();
  22. sort(nums.begin(), nums.end()); // 去重需要排序
  23. backtracking(nums, 0);
  24. return result;
  25. }
  26. };

注意点1:学习了一下使用set的方法,set去重的逻辑也比较直接,每一次检查在设定的set中是否有之前添加的相同元素,如果有就跳过,没有就将其加入然后执行递归。

注意点2:set的find返回的是迭代器位置!

总结


打卡第24天,坚持!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/973845
推荐阅读
相关标签
  

闽ICP备14008679号