转码野生老农刷题打卡

2022-08-19打卡

309        最佳买卖股票时机含冷冻期
Link：https://leetcode.cn/problems/bes ... tock-with-cooldown/
题解：https://gitee.com/vincentmliu/Al ... ckWithCooldown.java
耗时： 20min



笔记：
1. 每有两种更可能，一种是unhold，一种是hold。
2. 第一天不持有dp[0][0] = 0;第一天持有dp[0][1] = -prices[0];
3. 第二天不持有，可以从第一天不买dp[0][0] 和 第一天买第二天卖得出dp[0][1] + prices[1]
4. 第二天持有，可以从第一天买dp[0][1] 和 第一天不买第二天买得出dp[0][0] - prices[1]
5. dp从第三天开始，状态转移公式
分两种状态
//不持有
//可以从 昨天也没有 dp[i-1][0] 和 昨天有今天卖得出dp[i-1][1] + prices[i]
//持有
//可以从 昨天也持有 dp[i-1][1] 和 前天（1天冷冻期）没有今天买得出
6. 要注意的是，昨天没有dp[i-1][0]今天不一定可以买，所以只能从前天不持有的状态dp[i-2][0] - prices[i]推导过来

时间复杂度：O(n)，每个节点都需要遍历一遍
空间复杂度：O(2n) 可以优化成O(1)

2022-08-19打卡

70        爬楼梯
Link：https://leetcode.cn/problems/climbing-stairs/
题解：https://gitee.com/vincentmliu/Al ... ClimbingStairs.java
耗时： 5min



笔记：
1. 每一阶共有dp（i - 1）上一步 + dp（i - 2）上两步种方式可以到达
2. n1 = 1
3. n2 = 2
4. dp从n3开始


时间复杂度：O(n)，每个节点都需要遍历一遍
空间复杂度：O(1) 只需记录last和lastBLast就行

2022-08-21打卡

Offer 14- I        剪绳子
Link：https://leetcode.cn/problems/jian-sheng-zi-lcof/
题解：https://gitee.com/vincentmliu/Al ... ianShengZiLcof.java
耗时： 1day


笔记：
1. dp记录长度为i的绳子剪成m段之后的最大乘积int[n+1], 从2开始，初始化dp[2]=1;
2. j代表绳子剪掉一段长度后，剩下绳子的长度为i-j，有两种选择
a. 剩下的绳子不剪，那么乘积就是 j * (i-j)
b. 剩下的绳子剪，那么乘积就是 j * dp[i-j]
3. 两者取最大值，对所有不同j的情况，取dp[i]的最大值。
4. j不用循环到i，只需要循环到j <= i/2 + 1就可以了，因为后面的情况都相同

时间复杂度 O(n)
空间复杂度 O(n)

2022-08-24打卡

139         单词拆分
Link：https://leetcode.cn/problems/word-break/
题解：https://gitee.com/vincentmliu/Al ... 00139WordBreak.java
耗时： 2h



笔记：
1. dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词。
2. 每次循环，边界条件 dp[0] = true 表示空串S1 合法， 表示只需判断 0..i-1的s2是否合法就可以
3. 从第一个字母开始判断
4. s1 [0, j-1] 和 s2 [j, i-1]是否合法


时间复杂度：O(n²)，每个节点都需要遍历一遍,而且最坏情况每个节点前的所有分割点j都要判断一遍
空间复杂度：O(n) 需要一个数组，记录每个字母之前可否被合法拆分

2022-08-25打卡

1143        最长公共子序列
Link：https://leetcode.cn/problems/longest-common-subsequence/
题解：https://gitee.com/vincentmliu/Al ... monSubsequence.java
耗时： 2h



笔记：
1. 因为比较两个字符串，需要双指针进行遍历,所以dp采用矩阵模式
2.dp[i][j]保存的是字符串前缀t1[0:i) 和 t2 [0:j)的 LCS
3. 初始化边界条件：dp[i][0] 表示 t2为空串前缀，所有LCS都是0，同理 dp[0][j] 表示 t1 为空串前缀，所有LCS都是0
4. 状态转移，按顺序从左到右遍历两个字符串
5. 如果碰到相等的字符，当前t1 和 t2 的 LCS +1
6. 如果字符不相等，LCS长度就等于前一前缀两者较大的那个LCS
因为t1 或 t2 指针前进一格，对 dp都没有贡献，所以 dp只能是前面两者的最大值
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

时间复杂度：O(m * n)，m和n分别是两个字串的长度
空间复杂度：O(m * n) 需要一个 dp[m+1][n+1]来保存LCS的状态

2022-08-30打卡

72. 编辑距离
Link：https://leetcode.cn/problems/edit-distance/
题解：https://gitee.com/vincentmliu/Al ... 72EditDistance.java
耗时： 5day


笔记：
1. 拆分子问题，如果用dp[i][j]来表示word1的前i个字母转变成word2的前j个字母，那么如何从上一步推导过来呢？有三种方案，分别是dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]
2. dp[i-1][j] 和 dp[i][j] 相比，word1增加了一个字母，最多可以先变成i-1，然后变成j。那么dp[i-1][j]推导到dp[i][j]最多就是dp[i-1][j] + 1步
同理， dp[i][j] = dp[i][j-1] + 1;(word2增加了一个字母，可以先变成j-1然后变成j)
3. dp[i-1][j-1]推导到dp[i][j]分两种情况
a.最后一个字母相同，那不用转变dp[i][j] =  dp[i-1][j-1];
b.如果最后一个字母不同，那么需要一步转变dp[i][j] = dp[i-1][j-1] + 1;

4. 综上，每个dp[i][j]就等于三个转变方案的最小值。
5. 如何初始化dp，从空串变成i或者j就必须要i步和j步，所以dp[i][0] = i、 dp[0][j] = j

时间复杂度 O(n * m)
空间复杂度 O(n * m)

补充内容 (2022-08-31 09:40 +8:00):
dp[i][j-1] 表示word1前i个字符转换到word2前j-1个字符的距离，在此基础上，在word2后增加一个字符，word1前i个字符转换到word2前j个字符的距离为dp[i][j-1]+1 。这是word2增，等价于word1删。 同理，dp[i-1][j] + 1 是word1增，等价于word2删。

2022-08-31打卡

300        最长递增子序列
Link：https://leetcode.cn/problems/longest-increasing-subsequence/
题解：https://gitee.com/vincentmliu/Al ... ingSubsequence.java
耗时： 2h



笔记：
1. dp[i] 可以从 nums[0..i-1] > nums[i] && max[0..i-1]推导出来。也就是说
a. 要找到0..i-1中，比nums[i]小的数字
b. 从上面数字中找到最大的dp值 + 1；

时间复杂度：O(n²)，每次需要遍历dp[0..i-1]的状态
空间复杂度：O(n) 需要一个 dp[n]

2. 贪心
a. 数组遍历O(n)没法优化，可以优化找nums[i]之前，比i小的max(dp)
b. dp[i] 改为保存 长度为 i 的LIS的最小nums[i]元素。比如 1,2,3,4 长度为3的子序列里面有1，2，3和2，3，4, 那么dp[3] = min(3,4) = 3;
c. dp[i] 是单调递增的，假设两个数字 a < b, d[a]的LIS 可以包含在d[b] 的 LIS中。那么 d[a] 必然小于 d[b];
d. 转移方程： 设 res 为 dp 当前长度，代表直到当前的最长上升子序列长度。设 j∈[0,res)，
考虑每轮遍历 nums[i]时，通过二分法遍历 [0,res)列表区间，找出 nums[k] 的大小分界点，会出现两种情况：

区间中存在 dp[index] > nums[i]： 将第一个满足 dp[index] > nums[i] 执行 dp[index] = nums[i] ；因为更小的 nums[i] 后更可能接一个比它大的数字。
区间中不存在 dp[index] > nums[i] ： 意味着 nums[i] 可以接在前面所有长度的子序列之后，因此肯定是接到最长的后面（长度为 res ），新子序列长度为 res + 1。

时间复杂度 O(nlogn)
空间复杂度 O(n)

2022-09-02打卡

437        路径总和 III
Link：https://leetcode-cn.com/problems/path-sum-iii/
题解：https://gitee.com/vincentmliu/Al ... 0437PathSumIii.java
耗时： 1day


笔记：
1. 新增了DP做法，二叉树上后序遍历；
2. 将当前节点的所有子节点能形成的pathSum用一个Map保存起来，key: pathSum, value: 相同path的数量。
3. 遍历到当前节点时，将所有pathSum + node.val，形成新的pathSum Map。
4. 在遍历过程中，遇到等于targetSum的时候便记录

时间复杂度 O(n²) 要在所有节点遍历当前节点的子path数目，1 + 2 +3 ... n = n(n+1)/2
空间复杂度 O(n²) 需要一个map来保存所有可能的pathSum，最坏情况也是 1 + 2 + 3 ....

2022-09-05打卡

344        反转字符串
Link：https://leetcode.cn/problems/reverse-string/
题解：https://gitee.com/vincentmliu/Al ... 4ReverseString.java
耗时： 5min



笔记：
1. i从左，j从右
2. 终止条件是 i<j

时间复杂度 O(n)
空间复杂度 O(1)

2022-09-05打卡

Interview 16.24        数对和
Link：https://leetcode.cn/problems/pairs-with-sum-lcci/
题解：https://gitee.com/vincentmliu/Al ... irsWithSumLcci.java
耗时： 20min


笔记：
1.用双指针来遍历数组，避免暴力n * n;
2. 先排序数组，花费时间O(n)
3. 左右双指针，终止条件是 i >= j;
4. 如果sum > target 就表示因子大了，需要减小因子，右指针左移
同理，如果小了，需要增大因子，左指针右移
5. 如果sum == target, 保留结果

时间复杂度 O(n) 一次排序耗费n(快排或者归并)，一次遍历耗费n
空间复杂度 O(n) 需要保存结果