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

8.3 Day 打卡：
Valid Palindrome
Implement Rand10() Using Rand7():
1. 通过 (Rand7 - 1) * 7 + (Rand7 - 1) 得到 0 - 49之间的数字， 每个数字出现概率1/49
2. 如果数字大于等于40 则 回到步骤1， 直到小于40
3. 最后的数字在 0 - 39 中  Rand10 = 数字 % 10 + 1
K-th Smallest in Lexicographical Order

今天hard dp+ minimal spanning tree + relaxing的 dp

1221.split-a-string-in-balanced-strings.java
  19.remove-nth-node-from-end-of-list.java
  322.coin-change.java
  746.min-cost-climbing-stairs.java
  754.reach-a-number.java
  graph/weightedGraph/Kruskal.java
  graph/weightedGraph/Prim.java
  graph/weightedGraph/WeightedEdge.java
  graph/weightedGraph/WeightedGraph.java
  leetcode301/301.remove-invalid-parentheses.java
  leetcode301/642.moving-average-from-data-stream
  leetcode72/72.edit-distance.java
  lintcode590/590.connecting-graph-ii.java
  lintcode629/Connection.java
  lintcode629/Solution.java
  lintcode629/UF.java
  lintcode642/642.moving-average-from-data-stream.java

8/3 打卡 Day 24

同一道题用stack 做了一遍
# 496. Next Greater Element I
two steps:
1. use stack and dictionary to find next greater number from nums2.
        a. use stack to save all temporary next numbers        b. when find next greater number, pop number from stack
       c. save pop number and current number, which is the next greater number to dictionary.  Dictionary save all numbers with next greater number.
2. iterate nums1 to find next greater number from dictionary given by step 1

刷了三道题，都是dp
第一题上楼梯问题比较简单，其实就是fibonacci的变形。
第二题三角形问题，状态转移方程也比较好想。
第三题最大子串乘积问题比较难，因为会有正和负两种情况，所以最重要的是要将最大值和最小值两种情况都考虑到状态转移方程中。

今天刷了5道leetcode，加油！

今天把Search a 2D Matrix II的divide and conquer方法和reduce search space方法做了下，
还做了tree相关的diameter of binary tree, diameter of n-ary tree。

8.3 每日一题 Valid Palindrome
想起之前也写过，回顾了一下
125 Valid Palindrome I；680 Valid Palindrome II；以及 234 Palindrome Linked List
套路基本都一致，主要考点都是字符串函数的使用吧。今天这道题讨论里有一个新鲜点是使用 Regex，比如s.replaceAll("[^A-Za-z0-9]", "")
以前Java写过这个又忘记了...看来得赶紧回顾

8.3 刷题打卡

1. Arithmetic Slices II. Map[] 记录每个idx的差和对应的个数。
2. Strobogrammatic Number III. DFS 处理。
3. Valid Palindrome. Two Pointers.

08/03 第三天

课程表 BFS拓扑排序利用入度矩阵 决定入队先后顺序
二叉树剪枝 后序遍历递归调用
二叉搜索树迭代 使用栈中序遍历

8月 Day 3 打卡