刷题记录帖子

LC 1582 Special Positions in a Binary Matrix   

还是周赛题目，其实就是先计算下，row sum 和 col sum，然后不断 check 是不是都满足 1 的条件。

LC 198 House Robber

老题目了，是 dp 的基础题。

Lc 58 Length of Last Word

简单题，但是还是很好的复习 Python 字符串的用法，比如 strip() 可以去掉多个空格。

所以可以简化代码，下面这个解法就繁琐了。

最好的解法如下：

LC 238. Product of Array Except Self

和同学一起练习，复习这道题目。还是非常经典的， 用 two pass 巧妙的 in place O(N) 解决。

Lc 121. Best Time to Buy and Sell Stock

复习老题，又一次忘了。仔细思考起来，其实已经把握住了重点，但是在细致思考的时候失去了焦点，导致失败。



其实只需要两个信息，

（1） 当前元素之前最小的元素
（2） 能不能得到 更大的 profit

所以记录两个变量即可。

Lc 53. Maximum Subarray

还是复习老题目，但是这道题目，还是有思路，但是具体求解的时候陷入到陷阱里面没有想出来更好的方法，铭记下自己的失误。

lz加油！

134 Gas Station

还是比较明确的，主要方法是 求 diff 数组，然后只能从 postive diff 找可能的起始点。但是 O（N2） 复杂度

所以还有更加简单的方法如下，可以 O（N） 实现。
参考这个视频， https://maxming0.github.io/2020/09/23/Gas-Station/

其实是和 diff 数组类似的思想，但是在 accumulation 的过程中就在动态设置起始点。

这个起始点， start 的好处是找到一段连续数组的 起始位置。这样保证了，curr 设置的 start 的这段是正的，同时 因为 total 也是正的，所以，这段正和必定大于 另外一段之和，即使另外一段之和是负数。
妙～！

389 Find the Difference

写的是最 general 的情况，其实考虑到只会添加一个新的不同的 char，可以用字典来做。
对于 s 增加统计，对于 t 减少统计，如果不是 0 就返回，其实返回的那个应该是 -1.因为s没出现过，t出现一次，减一个，就是 -1。

同时不能用 set 因为没说不能添加相同的 char。

又是一道需要记忆的题目，而且思路很巧妙。
我最先的想法是 转化成 str 去做这道题，但是这个想法并不 work，很简单的一个 case。 对于 "3","30"， 字符串是 “30” 在前面，结果 303 但是其实是 330 更大。

所以比较大小的方法，其实是把两个数组合起来然后得到大小的比较。

在这儿要记忆下 Python 3 取消了 cmp 所以 必须写 rich comparsion 的 __lt__比较操作。而且需要生成一个 class 来比较。https://www.cnblogs.com/grandyang/p/4225047.html

Python 3 的规定， https://portingguide.readthedocs.io/en/latest/comparisons.html

我仿照的写法如下：