8月刷题/Mock interview接龙活动（缺米刷题的来）

刷了五道matrix和两个tropical sort，希望自己不要再有情绪了，不喜欢就move on，情绪困扰下什么事都会变得很困难

8/10 打卡第五天，今天刷了5道

今天做了Maximum Product Subarray，这道题花了好长时间，学习到的是通常比较直接的dp是dp[i]只与前面几个例如dp[i-1], dp[i-2]有关，二维dp array其实也是在二维方向上找dp[i][j]和前面几个dp[][]的关系，但是这道题提供的思路是，dp[i]本身也可以存多个状态，比如这道题相当于dp[i]有当前的max和当前的min这两种状态需要被存在dp[i]里，下一时刻的dp[i+1]虽然只跟前一时刻的dp[i]有关，但是是跟dp[i]的这两种状态都有关。这道题还有另一种解法，非常新颖，通过同时正着遍历array和反着遍历array，每乘一个数就更新一次结果，这个解法利用的是如果全是正数或有偶数个负数，那么全部乘起来就是最大product，如果有奇数个负号，那么从第一个负号之后一直到最后一个数的product和从第一个数一直到最后一个负数之前的product，这两个中大的那个就是最后的结果。碰到0，只要重置为1，就可以看做subproblem继续解决。
今天还复习了下combination sum I和II，发现还需要多复习，多理解。

打卡 刷3道

打卡第二天 今天算了三道题 复习了tree的基础知识。感觉太久不刷题，tree的前中后序遍历多都不记得了。

8月10号，

今天略忙， 就刷了一道 罪过罪过

刷题第10天

10. Regular Expression Matching 这又是一道hard题，乍一看不难，但是仔细推敲发现无法通过顺序扫描和比较处理复杂的诸如abc.*abc.*这样的字符串，后来发现要通过dynamic programming，基本版可以通过二维数组来实现，高级版本可以通过一维数组，但是要设置临时变量存储之后将要覆盖的值。

11. Container With Most Water 这题一开始想的太复杂了，一定要先把思路理清，就是两边比较大小，然后遍历一遍找个最大的就行了。

12. Integer to Roman 开始想比较复杂，后来发现只要把每一位的数字算出来，然后按照规则计算出字符串就行了。

今天刷了6道题 LT 301 可以用 LT678 count invalid 数量 然后 BFS 找到 所有 valid parenthesis

下班偶尔刷题赚点米

刷了一阵子了，每天1，2题的， 今天开始每天刷个3题
8月10日（第一天）