转码野生老农刷题打卡

2022-08-09打卡

518        零钱兑换 II
Link：https://leetcode.cn/problems/coin-change-2/
题解：https://gitee.com/vincentmliu/Al ... 518CoinChange2.java
耗时： 1h


笔记：
1. 用一个int status[amount+1]来保存到达所有值的way数；
2. amount的status[amount] = status[amount - coins[i]](因子的所有可能性) + status[amount]（历史的所有可能性）
3. 所以status[j + coins[i]] = status[j] + status[j + coins[i]];
4. 初始化status[0] = 1; 表示每个coin从0到该coin的面值至少都有一条way
5. 动态规划，遍历所有coins，从j=0开始遍历，一直到j=amount，只要j+coins[i] <= amount,就满足第三条。
6. 结果返回status[amount];
时间复杂度：O(n * amount),n是coins中元素的数量
空间复杂度：O（amount）需要一个status数组来记录所有可达状态

2022-08-10打卡

64        最小路径和
Link：https://leetcode.cn/problems/minimum-path-sum/
题解：https://gitee.com/vincentmliu/Al ... MinimumPathSum.java
耗时： 1h


笔记：
1. 每个格子的最小路径和，只能从上面或者左面较小的那个格子的路径和得来
2. 用一个status来存储最小路径和, status[0][0] = grid[0][0];
3. 第一列的status只能从上面的格子得来status[i][0] = status[i-1][0] + grid[i][0];第一行同理。初始化第一行和第一列
4. 其他格子可以从上面或者左边的格子推导而来status[i][j] = Math.min(status[i-1][j], status[i][j-1]) + grid[i][j];
5. 结果返回status[m-1][n-1];
时间复杂度：O(m * n)
空间复杂度：O(m * n)需要一个status数组来记录所有可达状态

2022-08-11打卡

offer 47        礼物的最大价值
Link：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
题解：https://gitee.com/vincentmliu/Al ... uiDaJieZhiLcof.java
耗时： 5min

和昨天的题一毛一样，就是大小反过来

2022-08-12打卡

120        三角形最小路径和
Link：https://leetcode.cn/problems/triangle/
题解：https://gitee.com/vincentmliu/Al ... D00120Triangle.java
耗时： 20min


笔记：
1. 建立一个和triangle一样大小的status来保存每个节点的最小路径
2. 最左边的，只能从status[i-1][j]得来
3. 最右边的，只能从status[i-1][j-1]得来
4. 从第3行开始计算从第2个元素到倒数第2个元素的最小路径值
status[i][j] = Math.min(status[i-1][j], status[i-1][j-1]) + triangle[i][j];
5. collections sort status的最后一行，取最小的那一个就是结果


时间复杂度：O(m * n)，每个节点都需要遍历一遍
空间复杂度：O(m * n)需要一个和trangle一样大status数组来记录所有可达状态

2022-08-15打卡

62        不同路径
Link：https://leetcode.cn/problems/unique-paths/
题解：https://gitee.com/vincentmliu/Al ... 062UniquePaths.java
耗时： 5min


笔记：
1. 建立一个status[m][n}来保存每个节点的路径和
2. 最左一列都是1；
3. 第一行都是1；
4. 其余格子的路径和就是status[i][j] = status[i-1][j] + status[i][j-1];

时间复杂度：O(m * n)，每个节点都需要遍历一遍
空间复杂度：O(m * n)需要一个status数组来记录所有可达状态

2022-08-15打卡

63        不同路径 II
Link：https://leetcode.cn/problems/unique-paths-ii/
题解：https://gitee.com/vincentmliu/Al ... 3UniquePathsIi.java
耗时： 10min
画了一下路线图

笔记：
1. 建立一个status[m][n}来保存每个节点的路径和，初始化第一行和第一列，因为数组无法越界。
2. 最左一列都是1，遇到障碍就不用走了，下面的对路径贡献都是0 ；
3. 第一行都是1，遇到障碍就不用往右走了，右边对路径贡献也是0；
4. 逐行扫描时，遇到障碍就跳过，障碍对右边和下边的格子贡献是0；
5. 其余格子的路径和就是status[i][j] = status[i-1][j] + status[i][j-1];

时间复杂度：O(m * n)，每个节点都需要遍历一遍
空间复杂度：O(m * n)需要一个status数组来记录所有可达状态

2022-08-16打卡

198        打家劫舍
Link：https://leetcode.cn/problems/house-robber/
题解：https://gitee.com/vincentmliu/Al ... 198HouseRobber.java
耗时： 25min
画了一下路线图

笔记：
1. 一个状态记录int[][] sums = new int[n][2];所有的格子从左开始往右偷，能达到的最大值，最大值就出现在倒数第一个格子的两种状态里
2. //初始化第一个格子，无法从左边推导出来。sums[0][1] = nums[0]; //只用初始化偷的状态
3. 从1开始，每个格子有两种状态，
4. 如果当前格子 不偷，需要从上个格子的偷和不偷两个状态对比得来；
5. 如果当前格子 偷，只能从上个格子的不偷状态推导过来

时间复杂度：O(n)，每个节点都需要遍历一遍
空间复杂度：O(n)需要一个sums数组来记录所有可达状态，每个格子两种状态

2022-08-16打卡

213        打家劫舍 II
Link：https://leetcode.cn/problems/house-robber-ii/
题解：https://gitee.com/vincentmliu/Al ... HouseRobberIii.java
耗时： 25min
二叉树的存储有点忘了，一开始本来想用数组结构存储状态的，后来发现还需要给每个节点编号，需要记录层级，比较麻烦，就干脆也用了链式存储

笔记：
1. 一个状态记录类，包含节点的两种状态 偷 或者 不偷。叶子节点的左右都为 0，0的status节点。偷与不偷对叶子节点都无贡献。
2. 后续遍历，根节点最后遍历
3. 如果当前节点要偷，那么两个子节点都不能偷，只能加上当前节点的node.val
4. 如果当前节点不偷，子节点有四种情况
        //两者都偷
        int bothSteal =  thisStatus.left.stealval + thisStatus.right.stealval;
        //两者都不偷
        int bothUnSteal =  thisStatus.left.unStealval + thisStatus.right.unStealval;
        //左偷右不偷
        int leftSteal =  thisStatus.left.stealval + thisStatus.right.unStealval;
        //右偷左不偷
        int rightSteal =  thisStatus.left.unStealval + thisStatus.right.stealval;
要取四种情况的最大值
5. 返回根节点的两种情况较大的那一个

时间复杂度：O(n)，每个节点都需要遍历一遍
空间复杂度：O(n)需要一个status树来记录所有可达状态，每个节点都有两种状态

补充内容 (2022-08-17 10:18 +8:00):
这题题号标错了

应该是

337        打家劫舍 III

Link：https://leetcode.cn/problems/house-robber-iii/

下面都没啥问题

2022-08-17打卡

213        打家劫舍 II
Link：https://leetcode.cn/problems/house-robber-ii/
题解：https://gitee.com/vincentmliu/Al ... 3HouseRobberIi.java
耗时： 2h

今天这题怎么也想不出来，最后看答案，震惊了，太厉害了

笔记：
1. 首先corner case，只有1和只有2，分别是偷1和偷两者最大的那家。
2. 因为0和n-1家不兼容，按198的解法，从0开始偷，没法确定最终方案是否包含0，那么最后一家偷不偷就无法得知了。
3. 所以分成两种情况 0 家可偷 和 n-1家可偷
// 如果第0家可偷，n-1家就不可偷，可偷范围就是 [0 - (n-2)]
// 如果第n-1家可偷，0家就不可偷， 剩下的可偷范围就是范围就变成 [1 - (n-1)]

4. 牛逼的来了。不需要储存所有节点的状态，只需要保存 i-2 和 i-1 两家的最大状态就可以
//   dp[i]=max(dp[i−2]+nums[i],dp[i−1])
  dp[i−2]+nums[i] = 偷 i 家
  dp[i−1] = 不偷 i 家
//表示当前家的最大化方案就是 i-2 的最大方案 + 偷当前家； 或者是 i-1的最大方案，不偷当前家 其中哪个大，当前家的最大方案就是哪个。

5. 返回3的两种情况较大的那一个

时间复杂度：O(n)，每个节点都需要遍历一遍
空间复杂度：O(1) 只需要记录 i-2 和 i-1即可

2022-08-18打卡

714        买卖股票的最佳时机含手续费
Link：https://leetcode.cn/problems/bes ... th-transaction-fee/
题解：https://gitee.com/vincentmliu/Al ... TransactionFee.java
耗时： 2h

我是**

笔记：
1. 当天有两种更可能，一种是unhold，一种是hold。
2. 当天hold可以从昨天的 unhold - prices 和 昨天的 hold中得来，取其中最大值
3. 当天unhold可以从昨天的 hold + prices - fee 和 unhold中得出，取最大值
4. 当然，每天unhold的利润肯定是要大于等于hold。
5. 所以最后返回的结果也就是最后n-1天的unhold。

时间复杂度：O(n)，每个节点都需要遍历一遍
空间复杂度：O(1) 只需要记录 i-2 和 i-1即可