7月缺米的来刷题/Mock interview活动

7.9 打卡

1. K Empty Slots. 把based on time slot 转化成 based on position 然后用sliding window解决
2. Smallest Rectangle Enclosing Black Pixels.  Binary Search 分别找出最左，最右，最上，最下的点。
3. Maximum Width of Binary Tree. BFS 层序遍历。

六题
kth smallest in sorted matrix 变形
sort + merge intervals
剩下的不难

继续刷DP!

三道题
LC819 most common word: 使用map存word和对应的个数，parse paragraph, 遇到空格符号就往后跳，遇到char就放到stringbuilder里（如果是大写要转换成小写），每次收集到一个word（如果不在banned里面）就放到map里面更新count。paragraph parse结束之后，找到map里最大count对应的word。
LC200 number of islands: 使用union and find. traverse grid matrix，遇到1就找四个方向的neighbor，分别对每一个neighbor和当前元素做union并且update count，全部做完之后的count就是island number
LC662 max width of binary tree: breath first search (similar to level order print). Use a class to represent a TreeNode and the index of this node in that level. Print tree level by level and at each level calculate the diff of first node index and last node index to get the max width of current level. The largest width of all levels is the answer.

第9天打卡：
今天刷了3题
分别是：
Unique Binary Search Trees
Unique Binary Search Trees II
Maximum Width of Binary Tree

20200709:
3: 0379, 0503, 0707, 0739, 0901, 1019, 1367
4:
5:

day 6

Thu, Jul 9, 2020, 2:04 PM        Algorithms       
Sudoku Solver
Question you were asked
H-Tree Construction

正好前一天复习了sudoku，最近很押题是怎么回事。。

lc
集中学习了rabin-karp算法 O(n)的强大算法（比KMP友好多了。。
主要步骤就是把string转为int， 再给每个k长的序列hashcode，每移动一步调整code，
用set记录遇到过的code

总结catalan number 非常好的题目
95. Unique Binary Search Trees II
96. Unique Binary Search Trees
241. Different Ways to Add Parentheses

困难：
324. Wiggle Sort II O(n) O(1)解法还是不会
KMP还是晕

Wiggle Sort II   15 minutes ago
AcceptedjavaWiggle Sort   17 minutes ago
AcceptedjavaKnight Dialer   30 minutes ago
AcceptedjavaKnight Dialer   33 minutes ago
AcceptedjavaKnight Dialer   34 minutes ago
Wrong AnswerjavaKnight Dialer   34 minutes ago
Compile ErrorjavaKnight Dialer   37 minutes ago
AcceptedjavaRestore IP Addresses   55 minutes ago
AcceptedjavaRestore IP Addresses   1 hour ago
AcceptedjavaCombinations   1 hour, 29 minutes ago
AcceptedjavaCombinations   1 hour, 35 minutes ago
AcceptedjavaPath Sum II   1 hour, 46 minutes ago
AcceptedjavaPath Sum II   1 hour, 54 minutes ago
AcceptedjavaPath Sum II   1 hour, 59 minutes ago
AcceptedjavaPath Sum II   2 hours, 1 minute ago
AcceptedjavaPath Sum II   2 hours, 1 minute ago
AcceptedjavaDifferent Ways to Add Parentheses   2 hours, 6 minutes ago
AcceptedjavaDifferent Ways to Add Parentheses   2 hours, 12 minutes ago
AcceptedjavaDifferent Ways to Add Parentheses   2 hours, 21 minutes ago
Compile ErrorjavaDifferent Ways to Add Parentheses   2 hours, 21 minutes ago

D8：  打卡第8天 (UTC: 10/07/2020)
继续学习： DFS + backtracking
               
1: N-Queens。 所有的。。。。 ---》 DFS + 回溯
   可以套用昨天 回溯的模板。
   思路：
    枚举当前皇后放置的列，若不合法则跳过  ； 若合法则递归枚举下一行的皇后
   位置合法：不在同一列，同一行，同一斜线。
   斜线攻击的条件：同一个斜线上的坐标之差相等，反方向上是同一个斜线上坐标之和相等。
   
   判断位置的合法性 ：isValid(List<Integer> cols, int col)
   只需要列的信息， 比如：[0, 3, 1] , 0 -》 false。
   List<N>，List中第N个元素的值代表第N行的皇后位置

2: N-Queens II        : 返回n皇后不同的解决方案的数量       
   算法基本一样，用个计数器。
   
3: Numbers of Islands       

  当遍历点值为1时，岛屿数量加一。
  然后从这个点开始dfs，搜索所有与其相连的点。上下左右四个方向选择一个未走过的合法点继续走，
  合法点需要坐标合法且值为1，将走过的点数值改为0，当该点所有可走方向均为0点，则回溯上一层，
  直到遍历所有可以走到的点.

明天试一下BFS.  

7.10 之前连续的断档了。 今天算Day1，只刷了一题简单。好不努力惹。
155. Min Stack
写的时候，没思考。直接用了一个stack，完成了所有需求。但其实在返回min值时，时间复杂度时不符合题意的。
去看题解，用了一个辅助栈来存储每一次的minValue，遂改之。
经验：题目不难，关键在于审题。（特别是简单题干后面的特殊要求。

day10 #sql 3题
1. group_conat(字段，符号)与group by搭配使用