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

2020-6-11

打卡第12天

230. Kth Smallest Element in a BST：用stack inorder遍历，每次弹出一个数counter加1，counter等于k的时候就找到了kth smallest元素。

235. Lowest Common Ancestor of a Binary Search Tree：利用bst的特点recursive，p，q两个数和root比大小，如果都小，recursive call on left child，如果都大，call on right child，如果一大一小，返回root。

236. Lowest Common Ancestor of a Binary Tree：recursive在left child和right child中找p，q中任意一个，找到第一个就返回不用管另一个，如果left child有p，q中的一个，right child有另一个，返回root，如果left child中找到了p就返回p，因为q肯定是p的child，同理先找到q就返回q。

238. Product of Array Except Self：这个题tricky的地方是不让用除法，解决方法是从左扫一遍记录每个元素左边所有元素的product，存在一个数组里，从右扫一遍记录每个元素右边所有元素的product，存在另一个数组里，然后把这两个数组对位相乘就是答案了，

242. Valid Anagram：创建两个26个元素的数组统计字符出现频率，两个数组如果完全一样就是anagram。

268. Missing Number：数组全部元素相加和等差数列求和之差就是missing number。

Day 8，5个题

merge sort，recursively的解法和in-place non-recursively的解法，insertion sort花了很多时间消化，关键在于track好要insert的node和insert到哪里

打卡第11天
笔记
疫情每天打卡写题
https://www.1point3acres.com/bbs/thread-635271-1-1.html
(出处: 一亩三分地)

• Maximal Product when Cutting Rope
• Largest Sum of a subarray
• Rainbow sort II
• Rainbow sort III

Day4, Database Questions,共3題

尴尬 之前的图片有些问题，重新传一下图片

哇塞 没想到真的有大米，好开心呀，太感谢楼主了，最近才用一亩三分地 正在攒大米。我再更新一下我最近的刷题情况，我自己有列Excel表，方便看；因为leetcode中国会员便宜 我后来主要用中国账号，英文主要是用来做每周六的contest。
6.5号有事休息了一天；
6.6号 4题（其中有三题是每周六的contest）
6.7号 2题
6.8号 4题
6.9号  10题
6.10号  8题

刷题打卡第六天， 做了daily contest 和 company tag的题1 Search Insert Position： 二分查找，三种不同的template的适用情况，边界条件处理
2 Sort Colors： 双指针 + swap in array， 注意loop结束的condition
3  Task Scheduler： 贪心算法， 插空法， 结果是所有tasks + 剩余的空位（如果有的话）

坚持的第9天，
做了**3道**heap和stack的题目
今日总结：
1. 用priority queue，aka，heapq的时候可以用 minus 来把小的element放在前面，但在最后提取top k的时候要记得 .reverse()
2. Insert Delete GetRandom O(1) 不难，但很考验基础，牢记，并把follow up的可以允许duplicate的情况考虑
3. import heapq, heappop, heappush 的 parameter list 要记住， 面试的时候不会有visual studio code或是 jupyter一样的提示

前几天忘了打卡 其实一直有在刷    前两天被sliding window搞得几乎放弃  还是耐心点吧
今天写了 7 道！！！！！！

day8
28 Implement strStr(): review  KMP and robin carp
132 pattern  dp+ stack
496. Next Greater Element I : monotone decreasing stack       
462. Minimum Moves to Equal Array Elements II :  quick select       
464. Can I Win:  backtrack + bitmask+ memorize       
467. Unique Substrings in Wraparound String: dp[i] to denotes length of longest matching substring ended with i.   then scan from left to right.       
468. Validate IP Address： divide and conquer       
469. Convex Polygon:  cross product , check direction one bye one
470. Implement Rand10() Using Rand7()： rejection sampling