在职有娃刷题自我督促贴

93. Restore IP Addresses
注意DFS的条件 这道题因为是判断IP地址 而IP地址是由四个string中间间隔三个点组成 因此DFS的if条件要相应变化

116. Populating Next Right Pointers in Each Node I
用DFS
117. Populating Next Right Pointers in Each Node II
用BFS! 注意如何按层用queue进行遍历 如果某一层的queue进行更新 要在每层里新建list 然后用新list更新原有list

128. Longest Consecutive Sequence
注意最后一位也可能是consecutive sequence中的一个 因此在for循环里应该用一个变量记录当前的长度 (而不是记录当前的index) 最后再和总的最长长度进行比较

142. Linked List Cycle II
这道题和Linked List Cycle I类似 还是需要fast和slow指针。难点在于推导在第一次相遇以后，fast和slow继续走会第二次相遇在环的初始点。

143. Reorder List
大致思路分三步：
(1) 找到链表后一半。  -> 规律：如果链表长度为L，无论L是奇数还是偶数，都从第k = L/2+1 个节点起反转。

(2) 将后一半节点反转。
(3) 将后一半节点依次插入前一半。



补充内容 (2019-4-13 23:46):
http://bangbingsyb.blogspot.com/ ... e-reorder-list.html

33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II
可以用二分查找来解 但二分查找的条件有变化

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

190. Reverse Bits
因为是unsigned int, 所以可以直接把整数用bin转换为二进制，去除前两位的'0b'就是后面的0和1组成的字符串 然后按32位补齐 (末尾补0)
然后再用int(,2)转换为整数即可
参考
https://blog.csdn.net/fuxuemingzhu/article/details/79254344

201. Bitwise AND of Numbers Range
http://www.cnblogs.com/grandyang/p/4431646.html

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 (有重复)