一.网格图DFS
适用于需要计算连通块个数、大小的题目
1.岛屿数量
给你一个由 1(陆地) 和 0（水）组成的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和\或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围
class Solution {public int numIslands(char[][] grid) {/**插旗法：真他妈牛逼，看了下题解真不是人想出来的也就是说从起点开始，从四个方向开始遍历，直到发现边界就停止边界：为0，或者到头了，或者已经被插旗这样只要是起点能连通的位置都会被插旗，剩下的就是隔着0的区域访问不到那么就相当于当前这一大块就是一个岛屿然后继续寻找下一个岛屿*/int count = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {//从[0,0]开始作为起点进行插旗if (grid[i][j] == '1') {dfs(i, j, grid);count++;}}}return count;}private void dfs(int i, int j, char[][] grid) {//边界问题if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {return;}//重点：将当前节点插旗，变为不为1的数grid[i][j] = '0';//开始四个方向进行dfs//上dfs(i - 1, j, grid);//下dfs(i + 1, j, grid);//左dfs(i, j - 1, grid);//右dfs(i, j + 1, grid);}
}2.岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid
岛屿是由一些相邻的 1(土地)构成的组合，这里的相邻要求两个1必须在水平或者竖直的四个
方向上相邻，你可以假设grid的四个边缘都被0(水)包围
岛屿的面积是岛上值为1的单元格的数目
请计算grid的最大岛屿面积，如果没有岛屿，请返回0
class Solution {public int maxAreaOfIsland(int[][] grid) {//插旗法 比上一题难一点 要算面积int sum = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {if (grid[i][j] == 1) {sum = Math.max(sum, dfs(i, j, grid));}}}return sum;}private int dfs(int i, int j, int[][] grid) {//边界问题一订要定义好 不然会越界if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {return 0;}int sum = 0;grid[i][j] = 2;sum++; //自身sum += dfs(i - 1, j, grid); //上sum += dfs(i + 1, j, grid); //下sum += dfs(i, j - 1, grid); //左sum += dfs(i, j + 1, grid); //右return sum;}
}3.水域大小
你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔
高度，若值为0则表示水域，由垂直、水平或者对角连接的水域为池塘，池塘的大小是指
相连的水域的个数，编写一个算法来计算矩阵中所有池塘的大小，返回值需要从小到大
排序
class Solution {public int[] pondSizes(int[][] land) {//我草了 还有对角线 想想对角线怎么处理？//对角线 有4个呢 那就是8个方向去遍历咯List<Integer> list = new ArrayList<>();for (int i = 0; i < land.length; i++) {for (int j = 0; j < land[i].length; j++) {if (land[i][j] == 0) {list.add(dfs(i, j, land));}}}int[] arr = new int[list.size()];list.sort((a, b) -> a - b);for (int i = 0; i < list.size(); i++) {arr[i] = list.get(i);}return arr;}private int dfs(int i, int j, int[][] land) {//边界问题if (i < 0 || i >= land.length || j < 0 || j >= land[0].length || land[i][j] != 0) {return 0;}int sum = 0;land[i][j] = 1;sum++;//上下左右，左上，左下，右上，右下sum += dfs(i - 1, j, land);sum += dfs(i + 1, j, land);sum += dfs(i, j - 1, land);sum += dfs(i, j + 1, land);sum += dfs(i - 1, j - 1, land);sum += dfs(i + 1, j - 1, land);sum += dfs(i - 1, j + 1, land);sum += dfs(i + 1, j + 1, land);return sum;}
}二.动态规划DP
动态规划解题思路：
1.寻找子问题
寻找定义子问题，如果可以把原问题变成一个和原问题相似、规模更小
的子问题，这种情况就可以用递归来解决
2.递归怎么写
状态定义与状态转移方程：
3.递归+记录返回值=记忆化搜索
因为在递归中，有着大量的重复递归调用(递归入参相同)，由于递归函数都是幂等的，
同样的入参无论计算多少次结果都是一样的，所以我们可以用记忆化搜索来优化，
就是将同样入参的计算结果放到缓存中，优先从缓存中拿结果，没有在递归
4.1：1翻译成递推
既我们可以去掉递归中的递，只保留归的部分，即自底向上计算
5.空间优化
一般dp问题，都是只会用到前面几个状态，之前已经计算过的状态在后面是永远不会
再用了的，所以我们只需要知道比如上一个状态和上上一个状态即可
1.爬楼梯
假设你正在爬楼梯，需要 n 阶你才能到达楼顶
每次你都可以爬 1 或者2个台阶，你有多少种不同的方式可以爬到楼顶呢？
第一种解法：这个解法如果数据量大的话往往会超时
class Solution {public int climbStairs(int n) {/**如果最后一步是爬了1个台阶 那么首先要爬到n-1台阶上如果最后一步是爬了2个台阶，那么首先要爬到n-2台阶上所以 而爬到n-1和n-2是两种不同的方法 所以dfs(n) = dfs(n - 1) + dfs(n - 2)*/return dfs(n);}private int dfs(int n) {if (n <= 1) return 1; //边界问题 0 和1return dfs(n - 1) + dfs(n - 2);}
}
第二种解法：+缓存
class Solution {public int climbStairs(int n) {/**如果最后一步是爬了1个台阶 那么首先要爬到n-1台阶上如果最后一步是爬了2个台阶，那么首先要爬到n-2台阶上所以 而爬到n-1和n-2是两种不同的方法 所以dfs(n) = dfs(n - 1) + dfs(n - 2)为了边界问题，0和1因为爬到0和1个台阶都是只有1种方式所以初始化dfs(0) dfs(1) = 1 然后公式演变成dfs(n + 2) = dfs(1) + dfs(0)*/Map<Integer, Integer> map = new HashMap<>();return dfs(n, map);}private int dfs(int n, Map<Integer, Integer> map) {if (n <= 1) return 1; //边界问题 0 和1if (map.get(n) != null) return map.get(n);int num = dfs(n - 1, map) + dfs(n - 2, map);map.put(n, num);return num;//这个方式会超时 因为每次都是递归了2遍 变成了 n^2次了 增加一个缓存// return dfs(n - 1) + dfs(n - 2);}
}
第三种解法：继续优化，1：1翻译成递推
dfs(i) = dfs(i - 1) + dfs(i - 2)，那么我们可以定义成这样
f[i] = f[i - 1] + f[i - 2]，之前是递归计算每个状态，现在是枚举计算每个状态
初始值f[0] = f[1] = 1，翻译自递归边界dfs(0) = 1,dfs(1) = 1
f[n] 翻译自dfs(n)
class Solution {public int climbStairs(int n) {/**1.定义子问题假设最后一次是爬1个台阶，那么就是爬到n-1需要多少种方式假设最后一次是爬2个台阶，那么就是爬到n-2需要多少种方式最后爬到n的总方式是 上面两种方式之和 即 fn = fn-1 + fn-2但是在这过程种很多都是会重复计算 那么用一个缓存来记录算过的值*/// int[] cache = new int[n + 1];// return dp(n, cache);//用逆推 0和1的时候方法是确定的int[] dp = new int[n + 1];dp[0] = 1; dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}// private int dp(int n, int[] cache) {// if (n <= 1) return 1; //0和1个台阶的时候就只有一种方法// if (cache[n] != 0) return cache[n];// int num = dp(n - 1, cache) + dp(n - 2, cache);// cache[n] = num;// return num;// }}第四种解法：继续空间优化
因为计算当前值只需要知道上一个状态和上上一个状态，所以每次只保留这两个变量即可
class Solution {public int climbStairs(int n) {/**分析子问题，假设最后一步是1各台阶，那么爬到n-1个台阶的方法就是dfs(n-1)最后一步是2个台阶，爬到n-2个台阶的方法就是n-2最后总共有 fds(n-1)+dfs(n-2)种方法那么运用缓存 因为在dfs过程中肯定会有重复计算的那么就是缓存中有的就不用计算了再优化，递推： 因为1个台阶和2个台阶的方法都是1种 再优化 n-1是上一个 n-2是上上一个 因为每次计算完上一个上上一个的值再接下来就不会用到所以每次就只使用这俩变量就可以了 */// int[] dp = new int[n + 1];// dp[0] = 1;// dp[1] = 1;// for (int i = 2; i <= n; i++) {// dp[i] = dp[i - 1] + dp[i - 2];// }// return dp[n];//优化一下空间int dp0 = 1, dp1 = 1;for (int i = 1; i < n; i++) {int dpi = dp1 + dp0;dp0 = dp1;dp1 = dpi;}return dp1;}
}2.使用最小花费爬楼梯
给你一个整数数组 cost，其中cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你
支付此费用，即可旋转向上爬一个或者两个台阶
你可以选择从下标为 0 或者 1 的台阶开始爬楼梯
请你计算并返回到达楼顶的最低花费
class Solution {public int minCostClimbingStairs(int[] cost) {/**分析子问题当最后是爬一个楼梯时，那么就是爬到n-1的费用+当前n-1的费用同理，当最后是爬2个楼梯，那么就是n-2的费用+当前n-2的费用然后取两者最小值int min = Math.min(dfs(n-1) + cost[n-1], dfs(n-2) + cost[n-2])剩下的就是开始优化优化：加缓存优化：递推 因为dfs(n-1)其实就是fn-1 同时 f0和f1是已知的都是=0 因为可以从0或者1开始 int[] dp = new int[n+1]min = Math.min(dp[n-1] + cost[n-1], dp[n-2]+cost[n-2]) */// int[] cache = new int[cost.length + 1];// Arrays.fill(cache, -1);// return dfs(cost, cache, cost.length);//进行递推 因为 f0 f1都是已知的// int n = cost.length;// int[] dp = new int[n + 1];// dp[0] = 0;// dp[1] = 0;// for (int i = 2; i <= n; i++) { //为什么从2开始呢 因为按照题目来0和1都是已知的 那么肯定从未知的第一个台阶2开始// dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);// }// return dp[n];//继续优化 dpi-1可以认为是上一个 dpi-2是上上一个 那么总是只需要这两个变量即可 //上一次的上一个和上上一个算完以后就不会再用了int dp0 = 0, dp1 = 0; //为什么是0 按照上面推理 因为可以从0或者1开始爬 所以到达0或者1不需要成本for (int i = 1; i < cost.length; i++) {int min = Math.min(dp1 + cost[i], dp0 + cost[i - 1]);dp0 = dp1;dp1 = min;}return dp1;// int f0 = 0, f1 = 0;// for (int i = 1; i < cost.length; i++) {// int fn = Math.min(f1 + cost[i], f0 + cost[i - 1]);// f0 = f1;// f1 = fn;// }// return f1;}// private int dfs(int[] cost, int[] cache, int n) {// if (n <= 1) return 0;// if (cache[n] != -1) return cache[n];// cache[n] = Math.min(dfs(cost, cache, n - 1) + cost[n - 1], dfs(cost, cache, n - 2) + cost[n - 2]);// return cache[n];// }
}3.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃
的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两件相邻的房屋在同一
晚上被小偷闯入，系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报的情况下，一夜
之内能够偷窃到的最高金额
class Solution {public int rob(int[] nums) {/**最后一个房子偷不偷 下标从0开始偷 那么就是fn-2 +hn-1 前n-2个房子+最后一间房子的金额 因为索引从0开始 n-1就是最后一间房不偷 那就是fn-1 然后就是计算这俩最高值 max = Math.max(f(n-2) + h(n-1), f(n-1));然后换算*/int n = nums.length;// int[] dp = new int[n + 1]; //从0开始// dp[0] = 0;// dp[1] = nums[0];// for (int i = 2; i <= n; i++) {// dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);// }// return dp[n];//空间优化 // int dp0 = 0, dp1 = nums[0];// for (int i = 2; i <= n; i++) {// int max = Math.max(dp1, dp0 + nums[i - 1]);// dp0 = dp1;// dp1 = max;// }// return dp1;//再优化int dp0 = 0, dp1 = 0;for (int x : nums) {int dp = Math.max(dp1, dp0 + x);dp0 = dp1;dp1 = dp;}return dp1;}
}三.贪心
1.重新分装苹果
给你一个长度为n的数组 apple 和另一个长度为 m 的数组 capacity
一共有 n 个包裹，其中第 i 个包裹中装着 apple[i]个苹果，同时，还有 m 个箱子，第 i 个
箱子的容量为 capacity[i] 个苹果，请你选择一些箱子来将这 n 个包裹中的苹果重新分装
到箱子中，返回你需要选择的最小箱子数
注意：同一个包裹中的苹果可以分装到不同的箱子中
class Solution {public int minimumBoxes(int[] apple, int[] capacity) {//妙啊 贪心 这题目没有说输出箱子的index 只是计算个数//而且1个包裹里的苹果可以放到不同箱子里 所以从大到小排序箱子//直到装完苹果为止int appleSum = 0;for (int num : apple) {appleSum += num;}Arrays.sort(capacity);int m = capacity.length;int i = m - 1;while (appleSum > 0) {appleSum -= capacity[i--];}return m - i - 1;}
}
