👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：暴力深搜
👉⭐️第一题💎
✨题目
✨思路：
for循环+递归，先从那n个数中选取一个，用set进行标记（这里设置成一个数组进行标记更快，因为数组是支持随机访问的），然后递归剩下的数，注意回溯时要恢复现场（因为这里是引用，如果是按值传递的话则不需要恢复现场，因为本身“现场”就没有改变）
✨代码：
class Solution { public: void dfs(vector<vector<int>> &result,int I, int n, int k, vector<int> &lab, set<int> &f) { if (f.size() == k) { result.push_back(lab); return; } for (int i = I; i <= n; i++) { if (f.find(i) != f.end()) continue; f.insert(i); lab.push_back(i); //I=i; dfs(result,++I, n, k, lab, f); lab.pop_back(); f.erase(i); } } vector<vector<int>> combine(int n, int k) { vector<vector<int>> result; vector<int> lab; set<int> f; dfs(result,1, n, k, lab, f); return result; } };
👉⭐️第二题💎
✨题目
✨思路：
深搜其实就是递归，注意这里退出条件需要是判断是否是叶子节点，最好不要是node==nullptr，因为这样会导致当只有一条路径的时候出错，另外需要判断输入[ ]时的输出为false（注意边界），分别找左右子节点进行判断，如果不是Null，则继续往下遍历，否则返回
✨代码：
class Solution { public: bool dfs(TreeNode *node, int sum, int targetSum) { int p = node->val; if (node->left == nullptr && node->right == nullptr) return sum + p == targetSum ? true : false; if (node->left && dfs(node->left, sum + p, targetSum)) return true; if (node->right && dfs(node->right, sum + p, targetSum)) return true; return false; } bool hasPathSum(TreeNode *root, int targetSum) { if(root==nullptr)return false; return dfs(root, 0,targetSum); } };
👉⭐️第三题💎
✨题目
✨思路：
直接想到遍历每一个单元格，模拟以该单元格为起点雨水的流向，将可以同时流进太平洋和大西洋的单元格放进ans中，但这样会多次重复单元格搜索，时间复杂度太高，所以采取反向搜索的方法；即以矩阵边界的单元格为起点，分别寻找雨水可以流经的区域，随后找两大洋的共同区域
✨代码：
int[] X = {0, 0, -1, 1}; int[] Y = {-1, 1, 0, 0}; boolean flag1 = false; boolean flag2 = false; List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> pacificAtlantic(int[][] heights) { int m = heights.length; int n = heights[0].length; boolean[][] used = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { flag1 = false; flag2 = false; dfs(heights,i,j,used); if (flag1 && flag2){ List<Integer> list = new ArrayList<>(); list.add(i); list.add(j); res.add(list); } } } return res; } private void dfs(int[][] heights, int i, int j,boolean[][] used) { used[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + X[k]; int y = j + Y[k]; if (x < 0 || y < 0){ flag1 = true; }else if (x >= heights.length || y >= heights[0].length) { flag2 = true; }else if (!used[x][y] && heights[x][y] <= heights[i][j]){ dfs(heights,x,y,used); } if (flag2 && flag1){ used[i][j] = false; return; } } used[i][j] = false; }
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
