转码野生老农刷题打卡

2023-05-23
120. Triangle
这题反正就是动态规划了，也就是memo。进阶的那个提示有点误导人，提示是
Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

其实row和column的number是一样的。空间优化只需要一行就可以了。

2023-05-24
127. Word Ladder
策略就是BFS，一个queue，一个visited set。
主要难点在于如何判断下面哪些单词可跳。可以直接变例26个字母，每一个词需要花k*26的时间。k是单词长度。

2023-05-25
300. Longest Increasing Subsequence
暴力dp O(n2)很容易想到。
牛逼的是转换dp的表达，每个dp[i]表示的是nums中长度为i的子序列的末尾的最小值。这样就可以保障了dp的单调递增性。从而将第二个n优化成logn

2023-05-26
144. Binary Tree Preorder Traversal

2023-05-26
212. Word Search II
我擦，微软原题我都做出来了。膨胀了。
words构建Tire树，board上面dfs

2023-05-30
752. Open the Lock
哎，细节是魔鬼，细节是魔鬼，我怎么会把'9' 的 possible写成0和1呢。。。

2023-05-31
589. N-ary Tree Preorder Traversal

2023-05-31
461. Hamming Distance

2023-06-02
面试题 05.03. Reverse Bits LCCI
要用无符号诺 >>>

2023-06-05
40. Combination Sum II
liweiwei tainiule
哈哈哈，就是dfs，之前想到的解法太复杂了。基本思路是一样的
大剪枝剪 preSum + candidates[i] > target 的
小剪枝是精髓， 剪的是同层相同数字的子集。因为第一个相同数字的dfs子集已经包含后面所有相同数字的遍历结果了。