转码野生老农刷题打卡

2022-07-25打卡

529        扫雷游戏
Link：https://leetcode-cn.com/problems/minesweeper/
题解：https://gitee.com/vincentmliu/Al ... 529Minesweeper.java
耗时： 60min


笔记：
1. 分两种情况，碰到M就返回X，碰到E就dfs递归
2. dfs递归里面的可选集有点像bfs，周围一圈都要检查一下{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {1, -1}, {-1, 1}}
3. 记录周边M的数量，如果M > 0就转变为数字，停止DFS
4. 如果M ==0， 那就接着遍历周围为'E'的grid
5. 终止条件--- E 已经被转换为 B或者数字
时间复杂度，基本所有格子都要遍历一遍 m * n
空间复杂度，不需要额外的visited数组，所以为 O(1)

阅读理解转换为逻辑比较麻烦，搞明白终止条件和递归条件就容易了。

2022-07-25打卡

9        回文数
Link：https://leetcode.cn/problems/palindrome-number/
题解：https://gitee.com/vincentmliu/Al ... 529Minesweeper.java
耗时： 20min


笔记：
1. 不用转换成string，可以每一位%10，添加到list中，然后用双指针
2. 巧妙解法，可以先求出x的位数div， int div = 1; while(x / div >= 10) div *= 10;
3. 每次left = x / div; right = x % 10；
4. 下一轮的x是 (x % div) / 10, 消掉高低两位
5. 下一轮div /= 100， 消掉两位；
6. 终止条件 x < =0

这题很考编程基本功和逻辑思维啊。。二刷居然10min内没做出来。。伤心了

2022-07-26打卡

127        单词接龙
Link：https://leetcode-cn.com/problems/word-ladder/
题解：https://gitee.com/vincentmliu/Al ... 0127WordLadder.java
耗时： 30min


笔记：
1. BFS，每次遍历一遍wordList数组，查看是否能跳，如果没被遍历过，并且可跳，添加到queue中
2. 用visited数组记录已经检测过的单词。
3. 重点！！要记录每一层的可跳单词数nextStepSize，此层thisStepSize遍历结束之后，开始遍历下一层，将下一层的单词数赋值到本层上thisStepSize = nextStepSize。step++
时间复杂度: 最坏每次遍历N层，N跳过去，那就是O(N²)
空间复杂度，需要额外一个数组记录visited，O（N）

这题和Interview 17.22几乎一毛一样 https://leetcode-cn.com/problems/word-transformer-lcci/

2022-07-28打卡

126        单词接龙 II
Link：https://leetcode-cn.com/problems/word-ladder-ii/
题解：https://gitee.com/vincentmliu/Al ... 26WordLadderIi.java
耗时： 2days


笔记：
1. 常规的递归，每次遍历wordList，会使用时间复杂度变为O(mn * mn), m是字符串的长度，n是wordlist的长度
2. 变换思路，每次改变一个char,从wordSet中查询是否存在，存在就能跳，那么递归的时间复杂度就变成了O(26m)也就是O(m), wordlist中查找匹配词的循环被HashSet的O(1)替代了。
3. 只要用了回溯就会超时,所以直接用BFS一次到底，每次分支都记录一个path，然后取path的最后一个单词作为下一层遍历的种子。但是这样会导致path数目指数增长，还是超时。
4. 最后用BFS来画图，用一个rootmap<String, HashSet<String>>来表示每个节点的上一个节点。
5. 用一个sizeMap来记录每一个节点应该属于第几层，如果a-z的过程中发现szieMap中包含这个词，且这个词就在下一层，那么添加该词的root节点为当前节点，相当于给path多加一个分支，root又能多分出来一条线。
6. 重点！！！每遍历完一次，从wordSet中删除掉该单词，这样使得wordSet具备了visited的功能。不要在当前层积攒一个subVisitedSet，最后从wordSet中removeAll，这样耗时要比每次从wordSet中remove多许多，并且会超时。
7.  最后用回溯返回path，有点像并查集。
时间复杂度：O(m * n), 最差要遍历每个单词，每个单词还得来一遍26m
空间复杂度：O（3n）,一个wordSet，一个rootMap，一个sizeMap


本来嚣张的以为这题和127一样简单，结果没想到一思考就是两天，每一步都要不断优化才能AC

2022-07-29打卡

58        最后一个单词的长度
Link：https://leetcode.cn/problems/length-of-last-word/
题解：https://gitee.com/vincentmliu/Al ... ngthOfLastWord.java
耗时： 2min


笔记：
1. 两行代码。。split和.length
时间复杂度 O(n)
空间复杂度 O(1)


困死，哄娃睡觉

周末带娃，前来蹭卡
2022-07-30打卡

offer 05        替换空格
Link：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
题解：https://gitee.com/vincentmliu/Al ... HuanKongGeLcof.java
耗时： 2min


笔记：
1. 循环char，碰到空格就换成%20添加到新list里面；
2. 最后用list.stream转换成新的字符串
时间复杂度 O(n)
空间复杂度 O(n)

2022-07-31打卡

offer 58 II        左旋转字符串
Link：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
题解：https://gitee.com/vincentmliu/Al ... nZiFuChuanLcof.java
耗时： 2min


笔记：
就最后的字符放前面，前面的字符放后边。。别的咱也想不到么不是
时间复杂度 O(n)
空间复杂度 O(n)

2022-08-02打卡

416        分割等和子集
Link：https://leetcode.cn/problems/partition-equal-subset-sum/
题解：https://gitee.com/vincentmliu/Al ... EqualSubsetSum.java
耗时： 1days


笔记：
1. 拆分成2个partition，且左右相等。必须要nums的sum是偶数，如果是奇数，直接返回false;
2. 假设把所有元素依次放到左子集，那么sum/2就是要达到的target，类似于0-1背包问题的背包最大承重能力w
3. 用一个一维boolean数组表示能达到的状态。如果target - nums[i] ==0，直接返回true; 如果 （前一步的某个可达状态 + nums[i]）== target, 就返回true
时间复杂度：O(n * sum), 求sum需要遍历所有nums元素，求每一层的科大状态需要 n * sum/2 的遍历时间，所以综合下来是O （n * sum）
空间复杂度：O（sum）需要一个status数组来记录所有可达状态


初学动态规划，多花了点时间啊

2022-08-04打卡

494        目标和
Link：https://leetcode.cn/problems/target-sum/
题解：https://gitee.com/vincentmliu/Al ... 00494TargetSum.java
耗时： 30min


笔记：
1. 先求一个sum，因为nums中全是正整数，sum表示 nums中所有的数字能达到的最远状态
2. 定义status数组，纵列表示第几步，横列表示状态值。因为能达到的状态可以为[-sum , +sum]，左开右开。所以status[i].length需要初始化为 2*sum + 1
3.  初始化第一行，可达状态是 +nums[0] 和 -nums[0], 因为数组下标无法用负数表示，集体偏移一个+sum；
4. 开始动态求解，当前行的状态等于 能到达当前状态的上一行状态的状态之和。
        // status[i][j - nums[i]] += status[i-1][j]; //来自负号
       //status[i][j + nums[i]] += status[i-1][j]; //来自正号
5. 获取结果只需要看最后一行，target + sum（偏移）中，最终的方案数量之和 status[nums.length -1][target + sum]
时间复杂度：O(n * sum), n是数组中元素的数量，sum是可以达到的状态，去掉了常数2
空间复杂度：O（n * sum）需要一个status数组来记录所有可达状态

2022-08-08打卡

322        零钱兑换
Link：https://leetcode.cn/problems/coin-change/
题解：https://gitee.com/vincentmliu/Al ... 0322CoinChange.java
耗时： 30min


笔记：
1. 先sort，找出小于amount的所有coin。
2. 列一个int[] status = new int[amount + 1]; status[0] = 0; 用来记录到达这些面值需要的最小coin数目
3. 初始化 status，每个coin的value在status中初始化为1，表示用1枚硬币就能达到该值。
4. 遍历所有coins，每个coin遍历相应的status值，如果status >0,说明该值可达。
5. status可达，意味着可以计算 status[ 当前值 + coin], 如果status[ 当前值 + coin] == 0 ，说明以前不可达，当前可达了，status[ 当前值 + coin] = status[ 当前值] + 1;
6. 如果status[ 当前值 + coin] > 0 说明曾经就可达，需要比较一个较小的值，填入该状态。
7. 小心坑！遍历过程中发现 (当前值 + coin) == amount, 这时候不要直接返回结果。因为可能出现coins=[5,3,2,1], amount = 11; 但是遍历到2的时候就已经出现amount = 11的情况了即 3+3+3+2， 但实际遍历1的时候，会出现 5+5+1。 如果直接返回会无法取到最小值。
8. 全部遍历完之后再取status[amount]。

时间复杂度：O(n * amount), n是coins中元素的数量，前期还有个coins的排序，可以做到logN，低阶忽略了。
空间复杂度：O（amount）需要一个status数组来记录所有可达状态