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

今天工作忙 只有两道题

两道指针
还有进步空间

8/4今天刷了5題：
Peak Index in a Mountain Array (easy)：一開使用的方法是檢查array中的每個資料，但是用Binary Search會快一點。
Power of Four （easy）：今天的challenge，但C++用<cmath>裡的函式應該就能處理，懂log換底公式的話代碼五行內秒殺。
Median of Two Sorted Arrays (Hard)：這一題以前學校老師教O(m + n)的方法，但題目解答有O(log(m + n))的方法，使用Divide and Conquer，但是一堆留言說答案是錯的，我自己本身也看不懂，感覺面試官也不會出這種題目，另外這一題如果用O(m + n)的方法應該難度沒有到hard。
Reverse Integer (easy)：123 -> 321，這題需要注意反轉後的數字有可能會overflow，這時要輸出0
Find Winner on a Tic Tac Toe Game(easy) : 玩OOXX決定A玩家還是B玩家贏，暴力比對每一行每一列和兩個斜對角即可，不要想其他快速的方法，因為3*3的OOXX方格大小其實沒很大。

今天三道题，两道是union find类型的，2的重点在于发现图的规律，1）share parents 2）cycle. 今天没有做easy水题

补昨天的8月3号，打卡刷题第三天，总结3道题，训练String 6道题，
如果总结对你有帮助，求大米～～

1.RecursionIII MaxPathSum BinaryTree I(from leaf node to leaf node)
subProblem:
子树当中最大的maxPathSum
base case:
if (root == null) -> return 0;
recursive rule:
首先分左右, 然后去使用一个int variable -> curMax 去记录当前最大的maxSum
然后去判断curMax能够合法更新globalMax（m[0])
合法的条件有两个：
第一个是curMax > m[0]
第二个是root.left != null && root.right != null
最后判断有无左右子树的情况，然后视情况return

return 返回有三种情况：
1.右子树为空
返回left + root.key;

2.左子树为空
返回left + root.key;

3.两边都有
返回 Math.max(left, right) + root.key;

2. MaxPathSum BinaryTree II(from any node to any node)
//subProblem:
//root的子树的最大的Max PathSum是什么
//base case
if (root == null)  return 0;
//recursive rule：
首先总体上思路是，一个root底下有两个subTree，那么就分别对两个subTree进行讨论，用一个int variable去记录当前的最大的maxSum，因为最后要求的是from any node to any node因此可以用一个new vairable来表示当前值，如果子树返回的是一个负数，那就用0替代（表示不带上子树上的node）
然后带上左右子树和历史上最大值比较，如果比历史最大还要大， 那就更新历史上的最大值
return 返回的是带上当前root的值 + 左右subTree当中最大的那边 Math.max(left, right) + root.value;

3. MaxPathSum BinaryTree III(must in the path from the root node to lead node)
//subProblem:
//root的子树的最大的Max PathSum是什么(在同一个从root到leaf node的这条path上）
//base case
if (root == null)  return 0;
//recursive rule：
首先还是分两个方向来进行讨论
左子树和右子树
因为题目条件说的是同一个path上的任意1个或几个, 但是受制于一个path，就只能取一边；
那么就随时新建一个curMax，把左右子树当中大的那个返回(当然如果最大的node笔0还小，就返回0） + root.value;
然后拿这个curMax和历史上的最大值进行比较，更新历史上的最大值（如果适用的话）

return返回的是当前这个root下能够找到的MaxPathSum（curMax）

训练的String题目分别是：
1.reverse a word
2.reverse a sentence
3.right shift by N
4.remove certain element;
5.remove space
6.remove duplication

八月打卡第三天，开启了一个新的topic刷题

8/3 Day3
125
选课日 纠结选课只做一题 惭愧

8/4 Day4
295 231 326 342
power of two three third four  一起做
用iterate 和log 方法解题

Day 43, solved 3 problems.

Tips:
1. LC 705, use modular operation to create hash;
2, 3 just traverse the input array.

leetcode day2
今天刷了3道题。。。

leetcode, 重点刷了一下heap