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

打卡第二天 刷了3道题 hard的题做了一个多小时 尝试做了另外两道hard没有做出来 加油！

Day 3:
Task Scheduler, need to return max(input.size(),res), as the n(gap) could be 0
Sparse Matrix Multiplication, m[i][k] += m1[i][j]*m2[j][k]
Valid Number , need to figure out the principle, like no e before number, no e before .
First Bad Version, binary search, actually is to find the last good version, then +1
Continuous Subarray Sum, store the remainder to the prefix sum map
Accounts Merge,union find, use a map to connect email

打卡第四天~
Backtracking 练习，感觉这方面做得不太好，就多做一些

Combination Sum II   https://www.lintcode.com/problem/combination-sum-ii/
Combination Sum      https://www.lintcode.com/problem/combination-sum/
letter-combinations-of-a-phone-number https://www.lintcode.com/problem/letter-combinations-of-a-phone-number/description
split-string    https://www.lintcode.com/problem/split-string/

外加LeetCode July Challenge
--- Island Perimeter       

菜鸡七月第八天

今天做了一些island相关的
1. island perimeter: 找周长，可以找单独的岛的个数和相邻的岛的个数，相邻的岛主要看下边的和右边的, ie.(i+1, j)和(i, j+1),
    最后的周长是岛的个数*4-相邻的个数*2，因为单独的岛contribute 四条边，相邻的需要减去两条边
2. max area of island: 学习了一下recursive dfs，helper function里只要是valid island，就return 1 + 相邻的坐标的recursive
    function，main function里面每次update
3. number of islands: 可以用一个helper function把见过的岛和邻居设成0， 如果不是valid island就直接return，是的话就设成0，
    然后再上下左右的邻居坐标上call recursive function，这样loop through the grid
4. flood fill: 和之前有点类似，如果old color 和new color一样就直接return，不然的话就设成new color再看四周相邻的element
5. surrounded regions: 先把四条边上的O设成*，同时看直接相邻的element如果是O就是没法被enclose的，也设成*，最后再loop
    一遍grid，如果还是O就设成X，如果是*，就说明是没办法被围的O，再重新设为O

第7天打卡
刷了3题
Subsets II
Remove Duplicates from Sorted Array
Acceptedpython3Island Perimeter

谢谢各位大佬给分，继续努力 。 打好基础，再去看DP

D6：  打卡第6天 (UTC: 08/07/2020)
继续学习： DFS/BFS

昨天太累了， 今天补上一道。
1：binary-tree-level-order-traversal (102)
  使用queue 不断加入节点遍历；每次取出queue首个节点，遍历左右子树，继续压入queue.
  这道题是bfs 的基础题。

然后看了几道排列的题。  有两到看了半天，才看明白。

2. (31) Next Permutation
    这个算法， 除了背诵，好像没有什么办法。 跟bfs/dfs 完全无关。
        a:From right to left, find the first digit that violates ascending trend. Call it partition number.
        b:From right to left , find the first digit that is larger than partition number. Call it change number.
        c:swap partition number and the change number.
        d:Reverse all the digit on the right of partition number.
       
        6 8 7 4 3 2 --》 7 2 3 4 6 8
        关键即是求出数组末尾的最长的非递增子序列。
    数组nums中，nums[k+1]…nums[n]均满足前一个元素大于等于后一个元素，即这一子序列非递增。  k=0
    把nums[k]与其后序列中稍大于nums[k]的数交换 ： 6 与7交换
        再逆序nums[k+1]…nums[n]即可 ： 8 6 4 3 2 逆序

       
3. (46) Permutations
        DFS + 用一个数组记录已经放到permutation了。
       
4. (47) Permutations II
    有重复元素。
        a: 排序 让相同的digit 挨着，剪枝
        b: 跳过重复 nums[k] = nums[k-1] && nums[k-1] 已经访问过了
       
5  (60) Permutation Sequence
   这个算法， 除了背诵，好像也没有什么办法
   康托展开

睡前来三道…

0707 Day7 打卡三题

Moving Average from Data Stream，使用循环队列和window sum，O(1)复杂度
Number of Atoms，字符串处理+recursion，每次去掉第一组最外层括号，将括号之内以及括号之后的recusion处理
Island Perimeter，对于每个land，count周围0的个数；也可以用减法的方式，每遇到一个land给结果加4，然后查看上边和左边是否是1，没遇到一个1将结果减2（自己的边以及邻居的边）

07/08 第八天

. 跳水板 用set去除重复需要特别注意 两种corner case
珠玑妙算 两次遍历 第一次建立未猜对 然后第二字典里比较大小
插入 利用移位和位运算

day 4
(截图有点麻烦，我就复制一下文字8）

Tue, Jul 7, 2020, 2:04 PM        Algorithms        
Shortest Word Edit Path
Decrypt Message

mock 题目是word ladder， 一眼就看出来了hh
但是有一些困惑，
BFS使用了set 代替q，对方建议我恪守传统，用q
对方建议有的部分另外写helper function，不要全写在一起，但我感觉写在一起打字比较快
不知道业界规定是怎么样。。

lc 新题 2，复习10+
整理一下一些 split的技巧
描述： we tokenize/split input （into words）by using whitespaces/dot as delimiters.
s.split("\\s+") means one or more white space
s.split(“ # ”, -1)), -1 is to prevent null
在split中”.”代表任何数，所以要用split(“\\.”)

Minimum Possible Integer After at Most K Adjacent Swaps On Digits   36 minutes ago
AcceptedjavaMinimum Possible Integer After at Most K Adjacent Swaps On Digits   40 minutes ago
AcceptedjavaLast Moment Before All Ants Fall Out of a Plank   54 minutes ago
Compile ErrorjavaLast Moment Before All Ants Fall Out of a Plank   55 minutes ago
Compile ErrorjavaLast Moment Before All Ants Fall Out of a Plank   55 minutes ago
AcceptedjavaLast Moment Before All Ants Fall Out of a Plank   56 minutes ago
AcceptedjavaCan Make Arithmetic Progression From Sequence   56 minutes ago
Compile ErrorjavaCan Make Arithmetic Progression From Sequence   57 minutes ago
AcceptedjavaCan Make Arithmetic Progression From Sequence   57 minutes ago
AcceptedjavaCan Make Arithmetic Progression From Sequence   58 minutes ago
Compile ErrorjavaCan Make Arithmetic Progression From Sequence   58 minutes ago
AcceptedjavaShortest Subarray with Sum at Least K   1 hour, 4 minutes ago
AcceptedjavaShortest Subarray with Sum at Least K   1 hour, 7 minutes ago
Compile ErrorjavaShortest Subarray with Sum at Least K   1 hour, 8 minutes ago
AcceptedjavaWord Ladder   6 hours, 55 minutes ago
AcceptedjavaWord Ladder   7 hours, 12 minutes ago