缺大米的请参加这个刷题/Mock interview活动

Day 10

SQL 6道题

20200613 LC203/400by200705计划第19天 地里发帖第15天
今日完成3题 /leetcode 207, 210, 269
昨天不知怎么一半就发了 今天补上

1. 127 预处理构建adj list; 双向BFS https://leetcode.com/articles/word-ladder/
126 后续需要DFS

2. 51&52 经典八皇后问题 https://www.jiuzhang.com/solution/n-queens/

菜鸡第十三还是十四天
做了三道题，今天还是一样的菜
1. Ugly Number: 看integer n的prime factor是不是只有2，3，5. 这个就用while loop直接除的，如果没法整除2/3/5的话就return false
2. Count Numbers with Unique Digits：一位数的时候有十个numbers w unique digits，两位数的时候第一位有1-9九种选择，第二位除去前一位用掉的还有九种选择(+0)
    位数更高的时候选择就更少，loop through n的时候要记得加上之前算出来的，ex. n=2 时，number = 10 + 9*9 = 81，n超过十以后就没有新的unique digits
3. Coin Change：今天试图 做了coin change，但还是看答案写的。double loop 一个看coins 一个看amount，如果想要的amount>coin value，就可以看
    dp[i] = min(dp[i], dp[i - coin value] + 1)-可以先把所有dp initialize到amount，再看如果用一个新的coin value会不会少用conis

今天又是毫无动力的一天，明天希望可以好一点

打卡第一天！刷了五道题

慕容清 发表于 2020/06/12 11:40:26
打卡第七天

做了一道combination sum的题目，和昨天做的几道思路很像。最后添加list的时候，还是得声明...

打卡第八天又做了一道二分法的题目，但是感觉在边值的取等条件上还是弄不清楚。感觉需要哪天专门总结一下自己做的所有的二分法的题目。在leetcode给出的sulution里面用到了mid和mid-1或者mid 和mid + 1直接比较的方式，尽管是可以跑出来，但是会出现越界的问题，还是用最基本的二分法比较保险。

今天刷了3道题，围绕扫描线算法：
1. Number of Airplanes in the Sky: 将take off和landing时间放入数组，然后对数组排序。最后遍历数组，根据taking off或者landing更新计数器。
2. Meeting Rooms: 对会议interval按照start time排序，只需要确保上一个会的end时间点不能比这个会的start时间点晚即不会冲突。
3. Meeting Room II: 扫描线算法，得到在同一个时间点上进行的最多会议个数，即为最小的会议室数目。

Jun 13 打卡第13天 做了9题
114. Flatten Binary Tree to Linked List, 1) 右边连接到左边的后面；2）左边连接到root；3）左边null；
最后一个node用于下一次连接，1）rightLast!=null; 2)leftLast!=null 3) root; 解法二：stack，右边先入栈，然后左边入栈，接到stack peek，最后cur.left=null;
617. Merge Two Binary Trees, 递归，加到一个树的val；left，right递归。
212. Word Search II, Trie+Backtracking; 注意变量cur+c会导致重复添加，以及“aaa”, “aaab”这种，不能到”aaa”就直接return，需要继续dfs。【题解有一种Trie，记录word，TrieNode.word，如果不为null，说明是单词的结尾；为了避免重复，可以在找到这个单词后，TrieNode.word=null；】

day11
不知道刚才发成了木有 7 道tree

day 11
7 道 tree 题
python tree 删除的时候不能直接把当前node set 成None

打卡Day3 6道DP
Q684 Redundant Connection
- dfs -> for each edge, check if nodes are connected, if not, add the edge -> O(n^2)
- union find -> for each edge, find if the roots of the two nodes are the same-> O(nlogn)
Q32 Longest Valid Parentheses
- dp
- stack -> base as the last valid position
- 2 counts for left and right
Q62 Unique Paths
- 典型的dp 单行row来存储
Q123 Best Time to Buy and Sell Stock III
- 作为dp的话 左右分开 两边分别算max -> left_profit and right_profit
- SC = O(1)的方法* 分别记录当目前为止买卖第一支股票以及在第一支收益的基础上买卖第二支的成本和收益
Q303 Range Sum Query - Immutable
- sum of i-j = sum of 0-j minus sum of 0-i-1
Q357 Count Numbers with Unique Digits
Update:
- prev += cur
- cur *= available_nums
- available_nums -= 1
- 注意第一位不可以是0，后面都可以是0