devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法篇：递归、搜索与回溯算法_递归搜索

作者：从前慢现在也慢 | 2024-07-04 13:14:33

赞

踩

递归搜索

一、递归、深搜、穷举vs暴搜vs深搜vs回溯vs剪枝：

01、面试题 08.06. 汉诺塔问题

  1. class Solution 
  2. {
  3. public:
  4.     void hanota(vector<int>& a, vector<int>& b, vector<int>& c) 
  5.     {
  6.         dfs(a, b, c, a.size());
  7.     }
  8.  
  9.     void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
  10.     {
  11.         if(n == 1) 
  12.         {
  13.             c.push_back(a.back());
  14.             a.pop_back();
  15.             return;
  16.         }
  17.  
  18.         dfs(a, c, b, n - 1);
  19.         c.push_back(a.back());
  20.         a.pop_back();
  21.         dfs(b, a, c, n - 1);
  22.     }
  23. };

02、21. 合并两个有序链表

  1. class Solution 
  2. {
  3. public:
  4.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
  5.     {
  6.         if(l1 == nullptr) return l2;
  7.         if(l2 == nullptr) return l1;
  8.  
  9.         if(l1->val <= l2->val)
  10.         {
  11.             l1->next = mergeTwoLists(l1->next, l2);
  12.             return l1;
  13.         }
  14.         else
  15.         {
  16.             l2->next = mergeTwoLists(l1, l2->next);
  17.             return l2;
  18.         }
  19.     }
  20. };

总结：

①循环（迭代）vs递归：分支越多，递归越爽；分支又少又长，则用循环（否则容易栈溢出）。
②递归的展开图，其实就是对一棵树做一次深度优先遍历（dfs）。

03、206. 反转链表

  1. class Solution 
  2. {
  3. public:
  4.     ListNode* reverseList(ListNode* head) 
  5.     {
  6.         if(head == nullptr || head -> next == nullptr) return head;
  7.         ListNode* newhead = reverseList(head->next);
  8.         head->next->next = head;
  9.         head->next = nullptr;
  10.         return newhead;
  11.     }
  12. };

04、24. 两两交换链表中的节点

  1. class Solution 
  2. {
  3. public:
  4.     ListNode* swapPairs(ListNode* head) 
  5.     {
  6.         if(head == nullptr || head->next == nullptr) return head;
  7.  
  8.         auto tmp = swapPairs(head->next->next);
  9.         auto ret = head->next;
  10.         head->next->next = head;
  11.         head->next = tmp;
  12.         
  13.         return ret;
  14.     }
  15. };

05、50. Pow(x, n)

解法快速幂  O(N)：

  1. class Solution 
  2. {
  3. public:
  4.     double myPow(double x, int n) 
  5.     {
  6.         return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
  7.     }
  8.  
  9.     double pow(double x, long long n)
  10.     {
  11.         if(n == 0) return 1.0;
  12.         auto tmp = pow(x, n / 2);
  13.         return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
  14.     }
  15. };

06、2331. 计算布尔二叉树的值

  1. class Solution 
  2. {
  3. public:
  4.     bool evaluateTree(TreeNode* root) 
  5.     {
  6.         if(root->left == nullptr) return root->val == 0 ? false : true;
  7.  
  8.         bool left = evaluateTree(root->left);
  9.         bool right = evaluateTree(root->right);
  10.  
  11.         return root->val == 2 ? left | right : left & right;
  12.     }
  13. };

07、129. 求根节点到叶节点数字之和

  1. class Solution 
  2. {
  3. public:
  4.     int sumNumbers(TreeNode* root) 
  5.     {
  6.         return dfs(root, 0);
  7.     }
  8.  
  9.     int dfs(TreeNode* root, int presum)
  10.     {
  11.         presum = presum * 10 + root->val;
  12.         if(root->left == nullptr && root->right == nullptr) return presum;
  13.         int ret = 0;
  14.         if(root->left) ret += dfs(root->left, presum);
  15.         if(root->right) ret += dfs(root->right, presum);
  16.         return ret;
  17.     }
  18. };

08、814. 二叉树剪枝

  1. class Solution 
  2. {
  3. public:
  4.     TreeNode* pruneTree(TreeNode* root) 
  5.     {
  6.         if(root == nullptr) return nullptr;
  7.  
  8.         root->left = pruneTree(root->left);
  9.         root->right = pruneTree(root->right);
  10.  
  11.         if(root->left == nullptr && root->right == nullptr && root->val == 0)
  12.         {
  13.             delete root; // 防止内存泄漏
  14.             root = nullptr;
  15.         }
  16.         return root;
  17.     }
  18. };

09、98. 验证二叉搜索树

  1. class Solution 
  2. {
  3.     long prev = LONG_MIN;
  4. public:
  5.     bool isValidBST(TreeNode* root) 
  6.     {
  7.         if(root == nullptr) return true;
  8.  
  9.         bool left = isValidBST(root->left);
  10.         // 剪枝
  11.         if(left == false) return false;
  12.         bool cur = false;
  13.         if(root->val > prev) cur = true;
  14.         // 剪枝
  15.         if(cur == false) return false;
  16.         prev = root->val;
  17.         bool right = isValidBST(root->right); 
  18.  
  19.         return left && right && cur;
  20.     }
  21. };

10、230. 二叉搜索树中第K小的元素

  1. class Solution 
  2. {
  3.     int count = 0;
  4.     int ret = 0;
  5. public:
  6.     int kthSmallest(TreeNode* root, int k)
  7.     {
  8.         count = k;
  9.         dfs(root);
  10.         return ret;
  11.     }
  12.  
  13.     void dfs(TreeNode* root)
  14.     {
  15.         if(root == nullptr || count == 0) return;
  16.  
  17.         dfs(root->left);
  18.         count--;
  19.         if(count == 0) ret = root->val;
  20.         dfs(root->right);
  21.     }
  22. };

11、257. 二叉树的所有路径

  1. class Solution 
  2. {
  3.     vector<string> ret;
  4. public:
  5.     vector<string> binaryTreePaths(TreeNode* root)
  6.     {
  7.         string path; // 不能设置全局变量，否则要手动恢复现场
  8.         if(root->nullptr) return ret;
  9.         dfs(root, path);
  10.         return ret;
  11.     }
  12.  
  13.     void dfs(TreeNode* root, string path) // 不能引用，否则要手动恢复现场
  14.     {
  15.         path += to_string(root->val);
  16.         if(root->left == nullptr && root->right == nullptr)
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.         path += "->";
  22.         if(root->left) dfs(root->left, path); // 剪枝
  23.         if(root->right) dfs(root->right, path); // 剪枝
  24.     }
  25. };

12、46. 全排列

  1. // 决策树
  2. class Solution 
  3. {
  4.     vector<vector<int>> ret;
  5.     vector<int> path;
  6.     bool check[7];
  7. public:
  8.     vector<vector<int>> permute(vector<int>& nums) 
  9.     {
  10.         dfs(nums);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(vector<int>& nums)
  15.     {
  16.         if(path.size() == nums.size())
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         for(int i = 0; i < nums.size(); i++)
  23.         {
  24.             if(check[i] == false)
  25.             {
  26.                 path.push_back(nums[i]);
  27.                 check[i] = true;
  28.                 dfs(nums);
  29.                 // 回溯 -> 恢复现场
  30.                 path.pop_back();
  31.                 check[i] = false;
  32.             }
  33.         }
  34.     }
  35. };

13、78. 子集

解法一：

  1. class Solution 
  2. {
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5. public:
  6.     vector<vector<int>> subsets(vector<int>& nums) 
  7.     {
  8.         dfs(nums, 0);
  9.         return ret; 
  10.     }
  11.  
  12.     void dfs(vector<int>& nums, int pos)
  13.     {
  14.         if(pos == nums.size())
  15.         {
  16.             ret.push_back(path);
  17.             return;
  18.         }
  19.  
  20.         // 选
  21.         path.push_back(nums[pos]);
  22.         dfs(nums, pos + 1);
  23.         path.pop_back(); // 恢复现场
  24.  
  25.         // 不选
  26.         dfs(nums, pos + 1);
  27.     }
  28. };

解法二： 

  1. class Solution 
  2. {
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5. public:
  6.     vector<vector<int>> subsets(vector<int>& nums) 
  7.     {
  8.         // 解法二：
  9.         dfs(nums, 0);
  10.         return ret; 
  11.     }
  12.  
  13.     void dfs(vector<int>& nums, int pos)
  14.     {
  15.         ret.push_back(path);
  16.         for(int i = pos; i < nums.size(); i++)
  17.         {
  18.             path.push_back(nums[i]);
  19.             dfs(nums, i + 1);
  20.             path.pop_back(); // 恢复现场
  21.         }
  22.     }
  23. };

 14、1863. 找出所有子集的异或总和再求和

  1. class Solution 
  2. {
  3.     int path = 0;
  4.     int sum = 0;
  5. public:
  6.     int subsetXORSum(vector<int>& nums) 
  7.     {
  8.         dfs(nums, 0);
  9.         return sum;
  10.     }
  11.  
  12.     void dfs(vector<int>& nums, int pos)
  13.     {
  14.         sum += path;
  15.         for(int i = pos; i < nums.size(); i++)
  16.         {
  17.             path ^= nums[i];
  18.             dfs(nums, i + 1);
  19.             path ^= nums[i]; // 亦或运算：消消乐
  20.         }
  21.     }
  22. };

 15、47. 全排列 II

算法原理：
前提：先把整个数组排序。
剪枝：
①同一个节点的不同分支中，相同的元素只能选择一次。
②同一个数只能选择一次->check。

两种解法：

①只关心“不合法”的分支。

  1. class Solution 
  2. {
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5.     bool check[10];
  6. public:
  7.     vector<vector<int>> permuteUnique(vector<int>& nums) 
  8.     {
  9.         sort(nums.begin(), nums.end());
  10.  
  11.         dfs(nums, 0);
  12.         return ret;
  13.     }
  14.  
  15.     void dfs(vector<int>& nums, int pos)
  16.     {
  17.         if(pos == nums.size())
  18.         {
  19.             ret.push_back(path);
  20.             return;
  21.         }
  22.  
  23.         for(int i = 0; i < nums.size(); i++)
  24.         {
  25.             // 剪枝
  26.             if(check[i] == true || (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false))
  27.                 continue;
  28.             path.push_back(nums[i]);
  29.             check[i] = true;
  30.             dfs(nums, pos + 1);
  31.             path.pop_back(); // 恢复现场
  32.             check[i] = false;
  33.         }
  34.     }
  35. };

②只关心“合法”的分支。 

  1. class Solution 
  2. {
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5.     bool check[10];
  6. public:
  7.     vector<vector<int>> permuteUnique(vector<int>& nums) 
  8.     {
  9.         sort(nums.begin(), nums.end());
  10.         dfs(nums, 0);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(vector<int>& nums, int pos)
  15.     {
  16.         if(pos == nums.size())
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         for(int i = 0; i < nums.size(); i++)
  23.         {
  24.             // 剪枝
  25.             if(check[i] == false && (i == 0 || nums[i - 1] != nums[i] || check[i - 1] != false))
  26.             {
  27.                 path.push_back(nums[i]);
  28.                 
  29.                 check[i] = true;
  30.                 dfs(nums, pos + 1);
  31.                 path.pop_back(); // 恢复现场
  32.                 check[i] = false;
  33.             }
  34.         }
  35.     }
  36. };

16、17. 电话号码的字母组合

  1. class Solution 
  2. {
  3.     string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  4.     string path;
  5.     vector<string> ret;
  6. public:
  7.     vector<string> letterCombinations(string digits) 
  8.     {
  9.         if(digits.size() == 0) return ret;
  10.         dfs(digits, 0);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(string& digits, int pos)
  15.     {
  16.         if(pos == digits.size())
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         for(auto ch : hash[digits[pos] - '0'])
  23.         {
  24.             path.push_back(ch);
  25.             dfs(digits,pos + 1);
  26.             path.pop_back();
  27.         }
  28.     }
  29. };

17、22. 括号生成

有效的括号组合：
①左括号的数量=有括号的数量。
②从头开始的任意一个字串，左括号的数量>=右括号的数量。

  1. class Solution 
  2. {
  3.     int left, right, n;
  4.     vector<string> ret;
  5.     string path;
  6. public:
  7.     vector<string> generateParenthesis(int _n) 
  8.     {
  9.         n = _n;
  10.         dfs();
  11.         return ret; 
  12.     }
  13.  
  14.     void dfs()
  15.     {
  16.         // 递归出口
  17.         if(right == n)
  18.         {
  19.             ret.push_back(path);
  20.             return;
  21.         }
  22.  
  23.         if(left < n) // 添加左括号
  24.         {
  25.             path.push_back('(');
  26.             left++;
  27.             dfs();
  28.             path.pop_back(); // 恢复现场
  29.             left--;
  30.         }
  31.         
  32.         if(right < left) // 添加右括号
  33.         {
  34.             path.push_back(')');
  35.             right++;
  36.             dfs();
  37.             path.pop_back(); // 恢复现场
  38.             right--;
  39.         }
  40.     }
  41. };

​18、77. 组合

  1. class Solution 
  2. {
  3.     int n, k;
  4.     vector<vector<int>> ret;
  5.     vector<int> path;
  6. public:
  7.     vector<vector<int>> combine(int _n, int _k) 
  8.     {
  9.         n = _n;
  10.         k = _k;
  11.         dfs(1);
  12.         return ret;
  13.     }
  14.  
  15.     void dfs(int start)
  16.     {
  17.         if(path.size() == k)
  18.         {
  19.             ret.push_back(path);
  20.             return;
  21.         }
  22.  
  23.         for(int i = start; i <= n; i++) // 剪枝
  24.         {
  25.             path.push_back(i);
  26.             dfs(i + 1);
  27.             path.pop_back(); // 恢复现场
  28.         }
  29.     }
  30. };

19、494. 目标和

path作为全局变量：

  1. class Solution 
  2. {
  3.     int path, ret, aim;
  4. public:
  5.     int findTargetSumWays(vector<int>& nums, int target) 
  6.     {
  7.         aim = target;
  8.         dfs(nums, 0);
  9.         return ret;
  10.     }
  11.  
  12.     void dfs(vector<int>& nums, int pos)
  13.     {
  14.         if(pos == nums.size())
  15.         {
  16.             if(path == aim) ret++;   
  17.             return;
  18.         }
  19.  
  20.         // 加法
  21.         path += nums[pos];
  22.         dfs(nums, pos + 1);
  23.         path -= nums[pos]; // 恢复现场
  24.  
  25.         // 减法
  26.         path -= nums[pos];
  27.         dfs(nums, pos + 1);
  28.         path += nums[pos]; // 恢复现场
  29.     }
  30. };

path作为参数：

  1. class Solution 
  2. {
  3.     int ret, aim;
  4. public:
  5.     int findTargetSumWays(vector<int>& nums, int target) 
  6.     {
  7.         aim = target;
  8.         dfs(nums, 0, 0);
  9.         return ret;
  10.     }
  11.  
  12.     void dfs(vector<int>& nums, int pos,int path)
  13.     {
  14.         if(pos == nums.size())
  15.         {
  16.             if(path == aim) ret++;   
  17.             return;
  18.         }
  19.  
  20.         // 加法
  21.         dfs(nums, pos + 1, path + nums[pos]);
  22.  
  23.         // 减法
  24.         dfs(nums, pos + 1, path - nums[pos]);
  25.     }
  26. };

20、39. 组合总和

解法一：

  1. class Solution 
  2. {
  3.     int sum, aim;
  4.     vector<int> path;
  5.     vector<vector<int>> ret;
  6. public:
  7.     vector<vector<int>> combinationSum(vector<int>& nums, int target) 
  8.     {
  9.         aim = target;
  10.         dfs(nums, 0, 0);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(vector<int>& nums, int pos, int sum)
  15.     {
  16.         if(sum == aim)
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         if(pos == nums.size() || sum > aim) return;
  23.  
  24.         for(int i = pos; i < nums.size(); i++)
  25.         {
  26.             path.push_back(nums[i]);
  27.             dfs(nums, i, sum + nums[i]);
  28.             path.pop_back();
  29.         }
  30.     }
  31. };

解法二：

  1. class Solution 
  2. {
  3.     int sum, aim;
  4.     vector<int> path;
  5.     vector<vector<int>> ret;
  6. public:
  7.     vector<vector<int>> combinationSum(vector<int>& nums, int target) 
  8.     {
  9.         aim = target;
  10.         dfs(nums, 0, 0);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(vector<int>& nums, int pos, int sum)
  15.     {
  16.         if(sum == aim)
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         if(pos == nums.size() || sum > aim) return;
  23.  
  24.         // 枚举个数
  25.         for(int k = 0; k * nums[pos] + sum <= aim; k++)
  26.         {
  27.             if(k) path.push_back(nums[pos]);
  28.             dfs(nums, pos + 1, sum + k * nums[pos]);
  29.         }
  30.  
  31.         // 恢复现场
  32.         for(int k = 1; k * nums[pos] + sum <= aim; k++)
  33.         {
  34.             path.pop_back();
  35.         }
  36.     }
  37. };

21、784. 字母大小写全排列

  1. class Solution 
  2. {
  3.     vector<string> ret;
  4.     string path;
  5. public:
  6.     vector<string> letterCasePermutation(string s) 
  7.     {
  8.         dfs(s, 0);
  9.         return ret;
  10.     }
  11.  
  12.     void dfs(string& s, int pos)
  13.     {
  14.         if(pos == s.size())
  15.         {
  16.             ret.push_back(path);
  17.             return;
  18.         }
  19.  
  20.         char ch = s[pos];
  21.         path.push_back(ch);
  22.         dfs(s, pos + 1);
  23.         path.pop_back();
  24.  
  25.         if(ch < '0' || ch > '9')
  26.         {
  27.             char tmp = change(ch);
  28.             path.push_back(tmp);
  29.             dfs(s, pos + 1);
  30.             path.pop_back();
  31.         }
  32.     }
  33.  
  34.     char change(char ch)
  35.     {
  36.         if(ch >= 'a' && ch <= 'z') ch -= 32;
  37.         else ch += 32;
  38.         return ch;
  39.     }
  40. };

22、526. 优美的排列

  1. class Solution 
  2. {
  3.     bool check[16];
  4.     int ret;
  5. public:
  6.     int countArrangement(int n) 
  7.     {
  8.         dfs(1, n);
  9.         return ret;
  10.     }
  11.  
  12.     void dfs(int pos, int n)
  13.     {
  14.         if(pos == n + 1)
  15.         {
  16.             ret++;
  17.             return;
  18.         }
  19.  
  20.         for(int i = 1; i <= n; i++)
  21.         {
  22.             if(!check[i] && (pos % i == 0 || i % pos == 0))
  23.             {
  24.                 check[i] = true;
  25.                 dfs(pos + 1, n);
  26.                 check[i] = false; // 恢复现场
  27.             }
  28.         }
  29.     }
  30. };

23、51. N 皇后？

  1. class Solution 
  2. {
  3.     bool checkCol[10], checkDig1[20], checkDig2[20];
  4.     vector<vector<string>> ret;
  5.     vector<string> path;
  6.     int n; 
  7. public:
  8.     vector<vector<string>> solveNQueens(int _n) 
  9.     {
  10.         n = _n;
  11.         path.resize(n);
  12.         for(int i = 0; i < n; i++)
  13.             path[i].append(n, '.');
  14.  
  15.         dfs(0);
  16.         return ret;
  17.     }
  18.  
  19.     void dfs(int row)
  20.     {
  21.         if(row == n)
  22.         {
  23.             ret.push_back(path);
  24.             return;
  25.         }
  26.  
  27.         for(int col = 0; col < n; col++) // 尝试在这一行放皇后
  28.         {
  29.             // 剪枝
  30.             if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col])
  31.             {
  32.                 path[row][col] = 'Q';
  33.                 checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
  34.                 dfs(row + 1);
  35.                 // 恢复现场
  36.                 path[row][col] = '.';
  37.                 checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
  38.             }
  39.         }
  40.     }
  41. };

24、36. 有效的数独

  1. class Solution 
  2. {
  3.     bool row[9][10];
  4.     bool col[9][10];
  5.     bool grid[3][3][10];
  6.  
  7. public:
  8.     bool isValidSudoku(vector<vector<char>>& board) 
  9.     {
  10.         for(int i = 0; i < 9; i++)
  11.             for(int j = 0; j < 9; j++)
  12.             {
  13.                 if(board[i][j] != '.')
  14.                 {
  15.                     int num = board[i][j] - '0';
  16.                     // 是否是有效的
  17.                     if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
  18.                         return false;
  19.                     row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
  20.                 }
  21.             }
  22.         return true;
  23.     }
  24. };

25、37. 解数独

  1. class Solution 
  2. {
  3.     bool row[9][10], col[9][10], grid[3][3][10];
  4. public:
  5.     void solveSudoku(vector<vector<char>>& board) 
  6.     {
  7.         // 初始化
  8.         for(int i = 0; i < 9; i++)
  9.         {
  10.             for(int j = 0; j < 9; j++)
  11.             {
  12.                 if(board[i][j] != '.')
  13.                 {
  14.                     int num = board[i][j] - '0';
  15.                     row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
  16.                 }
  17.             }
  18.         }
  19.         dfs(board);
  20.     }
  21.  
  22.     bool dfs(vector<vector<char>>& board)
  23.     {
  24.         for(int i = 0; i < 9; i++)
  25.         {
  26.             for(int j = 0; j < 9; j++)
  27.             {
  28.                 if(board[i][j] == '.')
  29.                 {
  30.                     // 填数
  31.                     for(int num = 1; num <= 9; num++)
  32.                     {
  33.                         if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num])
  34.                         {
  35.                             board[i][j] = '0' + num;
  36.                             row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
  37.                             if(dfs(board) == true) return true;
  38.                             // 恢复现场
  39.                             board[i][j] = '.';
  40.                             row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
  41.                         }
  42.                     }
  43.                     return false;
  44.                 }
  45.             }
  46.         }
  47.         return true;
  48.     }
  49. };

26、79. 单词搜索

  1. class Solution 
  2. {
  3.     bool vis[7][7];
  4.     int m, n;
  5. public:
  6.     bool exist(vector<vector<char>>& board, string word) 
  7.     {
  8.         m = board.size(), n = board[0].size();
  9.         for(int i = 0; i < m; i++)
  10.             for(int j = 0; j < n; j++)
  11.             {
  12.                 if(board[i][j] == word[0])
  13.                 {
  14.                     vis[i][j] = true;
  15.                     if(dfs(board, i, j, word, 1)) return true;
  16.                     vis[i][j] = false;
  17.                 }
  18.             }
  19.         return false;
  20.     }
  21.  
  22.     int dx[4] = {0, 0, -1, 1};
  23.     int dy[4] = {1, -1, 0, 0};
  24.  
  25.     bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
  26.     {
  27.         if(pos == word.size()) return true;
  28.  
  29.         // 向量的位置，定义上下左右四个位置
  30.         for(int k = 0; k < 4; k++)
  31.         {
  32.             int x = i + dx[k], y = j + dy[k];
  33.             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos])
  34.             {
  35.                 vis[x][y] = true;
  36.                 if(dfs(board, x, y, word, pos + 1)) return true;
  37.                 vis[x][y] = false;
  38.             }
  39.         }
  40.         return false;
  41.     }
  42. };

27、1219. 黄金矿工

  1. class Solution 
  2. {
  3.     bool vis[16][16];
  4.     int dx[4] = {0, 0, -1, 1};
  5.     int dy[4] = {1, -1, 0, 0};
  6.     int m, n, ret;
  7. public:
  8.     int getMaximumGold(vector<vector<int>>& g) 
  9.     {
  10.         m =  g.size(), n =  g[0].size();
  11.         for(int i = 0; i < m; i++)
  12.             for(int j = 0; j < n; j++)
  13.             {
  14.                 if(g[i][j])
  15.                 {
  16.                     vis[i][j] = true;
  17.                     dfs(g, i, j, g[i][j]);
  18.                     vis[i][j] = false;
  19.                 }
  20.             }
  21.         return ret;
  22.     }
  23.  
  24.     void dfs(vector<vector<int>>& g, int i, int j, int path)
  25.     {
  26.         ret = max(ret, path);
  27.         for(int k = 0; k < 4; k++)
  28.         {
  29.             int x = i + dx[k], y = j + dy[k];
  30.             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y])
  31.             {
  32.                 vis[x][y] = true;
  33.                 dfs(g, x, y, path + g[x][y]);
  34.                 vis[x][y] = false;
  35.             }
  36.         }
  37.     }
  38. };

 28、980. 不同路径 III

  1. class Solution 
  2. {
  3.     bool vis[21][21];
  4.     int dx[4] = {0, 0, -1, 1};
  5.     int dy[4] = {1, -1, 0, 0};
  6.     int ret;
  7.     int m, n, step;
  8. public:
  9.     int uniquePathsIII(vector<vector<int>>& grid) 
  10.     {
  11.         m = grid.size(), n = grid[0].size();
  12.  
  13.         int bx = 0, by = 0;
  14.         for(int i = 0; i < m; i++)
  15.             for(int j = 0; j < n; j++)
  16.                 if(grid[i][j] == 0) step++;
  17.                 else if(grid[i][j] == 1)
  18.                 {
  19.                     bx = i;
  20.                     by = j;
  21.                 }
  22.         step += 2;
  23.         vis[bx][by] = true;
  24.         dfs(grid, bx, by, 1);
  25.         return ret;
  26.     }
  27.  
  28.     void dfs(vector<vector<int>>& grid, int i, int j, int count)
  29.     {
  30.         if(grid[i][j] == 2)
  31.         {
  32.             if(count == step) // 判断是否合法
  33.                 ret++;
  34.             return;
  35.         }
  36.  
  37.         for(int k = 0; k < 4; k++)
  38.         {
  39.             int x = i + dx[k], y = j + dy[k];
  40.             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1)
  41.             {
  42.                 vis[x][y] = true;
  43.                 dfs(grid, x, y, count + 1);
  44.                 vis[x][y] = false;
  45.             }
  46.         }    
  47.     }
  48. };

二、floodfill算法： 

30、 733. 图像渲染

  1. class Solution 
  2. {
  3.     int m, n, prev;
  4.     int dx[4] = {0, 0, -1, 1};
  5.     int dy[4] = {1, -1, 0, 0};
  6. public:
  7.     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
  8.     {
  9.         if(image[sr][sc] == color) return image;
  10.  
  11.         m = image.size(), n = image[0].size();
  12.         prev = image[sr][sc];
  13.         dfs(image, sr, sc, color);
  14.         return image;
  15.     }
  16.  
  17.     void dfs(vector<vector<int>>& image, int i, int j, int color)
  18.     {
  19.         image[i][j] = color;
  20.  
  21.         for(int k = 0; k < 4; k++)
  22.         {
  23.             int x = i + dx[k], y = j + dy[k];
  24.             if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
  25.             {
  26.                 dfs(image, x, y, color);
  27.             }
  28.         }
  29.     }
  30. };

 31、200. 岛屿数量

  1. class Solution 
  2. {
  3.     vector<vector<bool>> vis;
  4.     int dx[4] = {0, 0, -1, 1};
  5.     int dy[4] = {1, -1, 0, 0};
  6.     int m, n, ret;
  7. public:
  8.     int numIslands(vector<vector<char>>& grid) 
  9.     {
  10.         m = grid.size(), n = grid[0].size();
  11.         vis = vector<vector<bool>>(m, vector<bool>(n));
  12.  
  13.         for(int i = 0; i < grid.size(); i++)
  14.             for(int j = 0; j < grid[0].size(); j++)
  15.             {
  16.                 if(!vis[i][j] && grid[i][j] == '1')
  17.                 {
  18.                     ret++;
  19.                     dfs(grid, i, j);
  20.                 }
  21.             }
  22.         return ret;
  23.     }
  24.  
  25.     void dfs(vector<vector<char>>& grid, int i, int j)
  26.     {
  27.         vis[i][j] = true;
  28.         for(int k = 0; k < 4; k++)
  29.         {
  30.             int x = i + dx[k], y = j + dy[k];
  31.             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
  32.             {
  33.                 dfs(grid, x, y);
  34.             }
  35.         }
  36.     }
  37. };

32、 695. 岛屿的最大面积​​​​​​​

  1. class Solution 
  2. {
  3.     vector<vector<bool>> vis;
  4.     int dx[4] = {0, 0, -1, 1};
  5.     int dy[4] = {1, -1, 0, 0};
  6.     int m, n, count;
  7. public:
  8.     int maxAreaOfIsland(vector<vector<int>>& grid) 
  9.     {
  10.         m = grid.size(), n = grid[0].size();
  11.         vis = vector<vector<bool>>(m, vector<bool>(n));
  12.  
  13.         int ret = 0;
  14.         for(int i = 0; i < grid.size(); i++)
  15.             for(int j = 0; j < grid[0].size(); j++)
  16.             {
  17.                 if(!vis[i][j] && grid[i][j] == 1)
  18.                 {
  19.                     count = 0;
  20.                     dfs(grid, i, j);
  21.                     ret = max(ret, count);
  22.                 }
  23.             }
  24.         return ret;
  25.     }
  26.  
  27.     void dfs(vector<vector<int>>& grid, int i, int j)
  28.     {
  29.         count++;
  30.         vis[i][j] = true;
  31.         for(int k = 0; k < 4; k++)
  32.         {
  33.             int x = i + dx[k], y = j + dy[k];
  34.             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
  35.             {
  36.                 dfs(grid, x, y);
  37.             }
  38.         }
  39.     }
  40. };

33、 130. 被围绕的区域

  1. class Solution 
  2. {   // 正难则反
  3.     int dx[4] = {0, 0, -1, 1};
  4.     int dy[4] = {1, -1, 0, 0};
  5.     int m, n;
  6. public:
  7.     void solve(vector<vector<char>>& board) 
  8.     {
  9.         // 1、把边界的0相连的连通块，全部修改成'.'
  10.         m = board.size(), n = board[0].size();
  11.         for(int j = 0; j < n; j++)
  12.         {
  13.             if(board[0][j] == 'O') dfs(board, 0, j);
  14.             if(board[m - 1][j] == 'O') dfs(board, m - 1, j);
  15.         }
  16.  
  17.         for(int i = 0; i < m; i++)
  18.         {
  19.             if(board[i][0] == 'O') dfs(board, i, 0);
  20.             if(board[i][n - 1] == 'O') dfs(board, i, n - 1);
  21.         }
  22.  
  23.         // 2、还原
  24.         for(int i = 0; i < m; i++)
  25.             for(int j = 0; j < n; j++)
  26.             {
  27.                 if(board[i][j] == '.') board[i][j] = 'O';
  28.                 else if(board[i][j] == 'O') board[i][j] = 'X';
  29.             }
  30.     }
  31.  
  32.     void dfs(vector<vector<char>>& board, int i, int j)
  33.     {
  34.         board[i][j] = '.';
  35.         for(int k = 0; k < 4; k++)
  36.         {
  37.             int x = i + dx[k], y = j + dy[k];
  38.             if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
  39.             {
  40.                  dfs(board, x, y);
  41.             }
  42.         }
  43.     }
  44. };

 34、417. 太平洋大西洋水流问题

  1. class Solution 
  2. {
  3.     int dx[4] = {0, 0, -1, 1};
  4.     int dy[4] = {1, -1, 0, 0};
  5.     int m, n;
  6. public:
  7.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) 
  8.     {
  9.         m = h.size(), n = h[0].size();
  10.         vector<vector<bool>> pac(m, vector<bool>(n));
  11.         vector<vector<bool>> atl(m, vector<bool>(n));
  12.  
  13.         // 1、先处理 pac 洋
  14.         for(int j = 0; j < n; j++) dfs(h, 0, j, pac);
  15.         for(int i = 0; i < m; i++) dfs(h, i, 0, pac);
  16.  
  17.         // 2、先处理 atl 洋
  18.         for(int i = 0; i < m; i++) dfs(h, i, n - 1, atl);
  19.         for(int j = 0; j < n; j++) dfs(h, m - 1, j, atl);
  20.  
  21.         vector<vector<int>> ret;
  22.         for(int i = 0; i < m; i++)
  23.             for(int j = 0; j < n; j++)
  24.                 if(pac[i][j] && atl[i][j])
  25.                     ret.push_back({i, j});
  26.         return ret;
  27.     }
  28.  
  29.     void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>>& vis)
  30.     {
  31.         vis[i][j] = true;
  32.         for(int k = 0; k < 4; k++)
  33.         {
  34.             int x = i + dx[k], y = j + dy[k];
  35.             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j])
  36.             {
  37.                  dfs(h, x, y, vis);
  38.             }
  39.         }
  40.     }
  41. };

35、529. 扫雷游戏 

  1. class Solution 
  2. {
  3.     int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
  4.     int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
  5.     int m, n;
  6.     
  7. public:
  8.     vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
  9.     {
  10.         m = board.size(), n = board[0].size();
  11.         int x = click[0], y = click[1];
  12.         if(board[x][y] == 'M') // 直接点到地雷
  13.         {
  14.             board[x][y] = 'X';
  15.             return board;        
  16.         }
  17.         dfs(board, x, y);
  18.         return board;
  19.     }
  20.  
  21.     void dfs(vector<vector<char>>& board, int i, int j)
  22.     {
  23.         // 统计一下周围的地雷个数
  24.         int count = 0;
  25.         for(int k = 0; k < 8; k++)
  26.         {
  27.             int x = i + dx[k], y = j + dy[k];
  28.             if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
  29.             {
  30.                 count++;
  31.             }
  32.         }
  33.         if(count) // 周围有地雷
  34.         {
  35.             board[i][j] = count + '0';
  36.             return;
  37.         }
  38.         else // 周围没有地雷
  39.         {
  40.             board[i][j] = 'B';
  41.             for(int k = 0; k < 8; k++)
  42.             {
  43.                 int x = i + dx[k], y = j + dy[k];
  44.                 if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
  45.                 {
  46.                     dfs(board, x, y);
  47.                 }
  48.             }
  49.         }
  50.     }
  51. };

三、记忆化搜索：

37、509. 斐波那契数

解法一：递归  O(2^N)

解法二：记忆化搜索  O(N)
①是什么：带备忘录的递归。
②怎么实现：添加一个备忘录<可变参数，返回值>，把结果放到备忘录里面，在每次进入递归的时候向备忘录里查找一下。

  1. class Solution 
  2. {
  3.     int memo[31]; // memory 
  4. public:
  5.     int fib(int n) 
  6.     {
  7.         // 初始化
  8.         memset(memo, -1, sizeof memo);
  9.         return dfs(n);
  10.     }
  11.  
  12.     int dfs(int n)
  13.     {
  14.         // 往备忘录里查找一下
  15.         if(memo[n] != -1) // 剪枝
  16.         {
  17.             return memo[n];
  18.         }
  19.  
  20.         if(n == 0 || n == 1)
  21.         {
  22.             memo[n] = n; // 返回之前放进备忘录里面
  23.             return n;
  24.         }
  25.  
  26.         memo[n]  = dfs(n - 1) + dfs(n - 2); // 返回之前放进备忘录里面
  27.         return memo[n];
  28.     }
  29. };

解法三：
①确定状态表示（dfs函数的含义）；
②推导状态转移方程（dfs的函数体）；
③初始化（dfs函数的递归出口）；
④确定填表顺序（填写备忘录的顺序）；
⑤确定返回值（主函数是如何调用dfs的）。

  1. class Solution 
  2. {
  3.     int dp[31];
  4. public:
  5.     int fib(int n) 
  6.     {
  7.         // 动态规划
  8.         dp[0] = 0, dp[1] = 1;
  9.         for(int i = 2; i <= n; i++)
  10.             dp[i] = dp[i - 1] + dp [i - 2];
  11.         return dp[n];
  12.     }
  13. };

总结：动态规划和记忆化搜索的本质：
①暴力解法（暴搜）。
②对暴力解法的优化：把已经计算过的值存起来。

问题：
①所有的递归（暴搜、深搜），都能改成记忆化搜索吗？
不是的，只有在递归的过程中，出现了大量的完全相同的问题时，才能用记忆化搜索的方式优化。
②带备忘录的递归 vs 带备忘录的动态规划 vs 记忆化搜索？
都是一回事。
③自顶向下 vs 自底向上？
记忆化搜索：自顶向下。
常规动态规划：自底向上。
④暴搜->记忆化搜索->动态规划 vs 常规动态规划？
80%可以用前者的思考方式，但有些题用暴搜的时间成本太高了（暴搜只是为我们确定状态表示提供方向）。

38、​​​​​​​62. 不同路径

解法一：暴搜->记忆化搜索：

  1. class Solution 
  2. {
  3. public:
  4.     int uniquePaths(int m, int n) 
  5.     {
  6.         // 记忆化搜索
  7.         vector<vector<int>> memo(m + 1, vector<int>(n + 1));
  8.         return dfs(m, n, memo);
  9.     }
  10.  
  11.     int dfs(int i, int j, vector<vector<int>>& memo)
  12.     {
  13.         if(memo[i][j] != 0) return memo[i][j];
  14.  
  15.         if(i == 0 || j == 0) return 0;
  16.         if(i == 1 && j == 1)
  17.         {
  18.             memo[i][j] = 1;
  19.             return 1;
  20.         }
  21.  
  22.         memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
  23.         return memo[i][j];
  24.     }
  25. };

解法二：动态规划：

  1. class Solution 
  2. {
  3. public:
  4.     int uniquePaths(int m, int n) 
  5.     {
  6.         // 1、创建dp表
  7.         vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  8.  
  9.         // 2、初始化
  10.         dp[0][1] = 1;
  11.  
  12.         // 3、填表
  13.         for(int i = 1; i <= m; i++)
  14.         {
  15.             for(int j = 1; j <= n; j++)
  16.             {
  17.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  18.             }
  19.         }
  20.         
  21.         // 4、返回值
  22.         return dp[m][n];
  23.     }
  24. };

39、​​​​​​​​​​​​​​300. 最长递增子序列

解法一：暴搜->记忆化搜索：

  1. class Solution 
  2. {
  3. public:
  4.     int lengthOfLIS(vector<int>& nums) 
  5.     {
  6.         int n = nums.size();
  7.         vector<int> memo(n);
  8.  
  9.         int ret = 0;
  10.         for(int i = 0; i < nums.size(); i++)
  11.             ret = max(ret, dfs(i, nums, memo));
  12.         return ret;
  13.     }
  14.  
  15.     int dfs(int pos, vector<int>& nums, vector<int>& memo)
  16.     {
  17.         if(memo[pos] != 0) return memo[pos];
  18.         int ret = 1;
  19.         for(int i = pos + 1; i < nums.size(); i++)
  20.         {
  21.             if(nums[i] > nums[pos])
  22.             {
  23.                 ret = max(ret, dfs(i, nums, memo) + 1);
  24.             }
  25.         }
  26.         memo[pos] = ret;
  27.         return memo[pos];
  28.     }
  29. };

解法二：动态规划：

  1. class Solution 
  2. {
  3.     int ret = 0;
  4.     int n = nums.size();
  5. public:
  6.     int lengthOfLIS(vector<int>& nums) 
  7.     {
  8.         // 动态规划
  9.         vector<int> dp(n, 1);
  10.  
  11.         // 填表顺序：从后往前（以i为首的最长递增子序列）
  12.         for(int i = n - 1; i >= 0; i--)
  13.         {
  14.             for(int j = i + 1; j < n; j++)
  15.             {
  16.                 if(nums[j] > nums[i])
  17.                 {
  18.                     dp[i] = max(dp[i], dp[j] + 1);
  19.                 }
  20.             }
  21.             ret = max(ret, dp[i]);
  22.         }
  23.         return ret;
  24.     }
  25. };

 40、375. 猜数字大小 II?

  1. class Solution 
  2. {
  3.     int memo[201][201];
  4. public:
  5.     int getMoneyAmount(int n) 
  6.     {
  7.         return dfs(1, n);
  8.     }
  9.  
  10.     int dfs(int left, int right)
  11.     {
  12.         if(left >= right) return 0;
  13.         if(memo[left][right] != 0) return memo[left][right];
  14.  
  15.         int ret = INT_MAX;
  16.         for(int head = left; head <= right; head++) // 选择头结点·
  17.         {
  18.             int x = dfs(left, head - 1);
  19.             int y = dfs(head + 1, right);
  20.             ret = min(ret, head + max(x, y));
  21.         }
  22.         memo[left][right] = ret;
  23.         return memo[left][right];
  24.     }
  25. };

  41、329. 矩阵中的最长递增路径

  1. class Solution 
  2. {
  3.     int dx[4] = {0, 0, -1, 1};
  4.     int dy[4] = {1, -1, 0, 0};
  5.     int m, n;
  6.     int memo[201][201];
  7.  
  8. public:
  9.     int longestIncreasingPath(vector<vector<int>>& matrix) 
  10.     {
  11.         int ret = 0;
  12.         m = matrix.size(), n = matrix[0].size();
  13.  
  14.         for(int i = 0; i < m; i++)
  15.             for(int j = 0; j < n; j++)
  16.             {
  17.                 ret = max(ret, dfs(matrix, i, j));
  18.             }
  19.         return ret;
  20.     }
  21.  
  22.     int dfs(vector<vector<int>>& matrix, int i, int j)
  23.     {
  24.         if(memo[i][j] != 0) return memo[i][j];
  25.  
  26.         int ret = 1;
  27.         for(int k = 0; k < 4; k++)
  28.         {
  29.             int x = i + dx[k], y = j + dy[k];
  30.             if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
  31.             {
  32.                 ret = max(ret, dfs(matrix, x, y) + 1);
  33.             }
  34.         }
  35.         memo[i][j] = ret;
  36.         return memo[i][j];
  37.     }
  38. };

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号