在职有娃刷题自我督促贴

159_Longest_Substring_with_At_Most_Two_Distinct_Characters
解substring的相关题 需要熟悉sliding window算法 做法一般是维护一个hashmap 和一个left , right两个pointer 先右移right index 然后观察hashmap里的记录是否符合题目要求 如果超过要求则从hashmap里pop出相应元素 同时移动left
hashmap里一般会存储 key:相应字符, value:字符最后出现的位置

172. Factorial Trailing Zeroes
https://zxi.mytechroad.com/blog/ ... al-trailing-zeroes/


All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

alternatively, we can do the following

1000/5 = 200

200/5 = 40

40/5 = 8

8/5 = 1

1/5 = 0

200 + 40 + 8 + 1 + 0 = 249

947. Most Stones Removed with Same Row or Column
https://www.jianshu.com/p/30d2058db7f7
https://buptwc.com/2018/11/25/Le ... Same-Row-or-Column/

对于一个连通的图，我们始终可以删除n-1个石头，其中n是这个连通图内的石头总数
我们使用dfs去找到这样的图，每次答案加上这次dfs遍历的石头数减一即可

补充内容 (2019-3-24 02:26):
这个思路和Number of Islands I 很像 但是卡在在做DFS的时候如何记录一次dfs遍历的石头数

补充内容 (2019-3-24 05:39):
原始点的个数 减去 岛屿的数量(这里的岛屿是指col和row连通的数量) 就是move的总次数

202. Happy Number
为了判断循环是否开始重复，要用一个字典（dict）或集合（set）来保存已经出现的数字

举例:
11不是快乐数
1^2+1^2 = 4
4^2 = 16
1^2+6^2=37
3^2+7^2=9+49=58
5^2+8^2=25+64=89
8^2+9^2=64+81=145
1^2+4^2+5^2=1+16+25=42
4^2+2^2=20
2^2+0^2=4 (有重复)

857. Minimum Cost to Hire K Workers
o(n^2)的暴力解太慢 需要按照每个人的ratio从小到大进行排序

https://buptwc.com/2018/06/26/Le ... -to-Hire-K-Workers/

299. Bulls and Cows
用hashmap即可。注意处理cows的时候之前bulls已经做过统计，不需要再处理

687. Longest Univalue Path
对全局变量的使用 self.ans
对树的处理一般都是递归 这道题需要用root.val和root.left.val (root.right.val)进行比较 从而对结果递加

437. Path Sum III
需要两次dfs 第一次就是遍历所有节点 第二次是对某个节点来说 判断这个节点是否能找到相应path满足target

60. Permutation Sequence
要用数学的方法进行计算 如果用递归算出所有组合后会超时

77. Combinations
用DFS+回溯 注意防入结果集里的结果需要用[:] 也就是说不能传入引用 应该传入数据的完全拷贝

86. Partition List
设置两个pointer , before/ after
每次遇到新的值 决定放入before还是after  最后把两个list连起来

62. Unique Paths
70. Climbing Stairs
91. Decode Ways
509. Fibonacci Number

都是dp的题 推导状态转移方程


补充内容 (2019-4-2 22:35):
91. Decode Ways
动态规划的题需要定义四个方面：
物理意义
初始值
转移方程
最终解的结果

dp[i]代表解析s[:i]字符串所有可能的方式数目

补充内容 (2019-4-2 22:38):
参考
https://www.youtube.com/watch?v=hFuj6GaaGpY

补充内容 (2019-4-2 22:54):
91. Decode Ways

dp[i] = dp[i-1] if s[i] != '0'
       + dp[i-2] if '9' < s[i-2:i] < '27'