立flag今年一定要成功换工作，宝妈刷题打卡

第一次发现一亩三分地这个刷题板块，很多娃妈跟我一样也在刷题打卡，开个帖子督促自己，目标刷完高频200开始投，iOS方向刷题量不大，主要是相关方向的知识，但是bless自己今年一定要跳到大公司啊。
2019 session 目前40道

52道，今天时间都很碎片化，做一道完完整整的题的时间很少，应该利用碎片时间思考问题，利用整块时间调试程序。
Unique Email Addresses
Number of Islands
Trapping Rain Water
Remove Duplicates from Sorted List
Add Two Numbers
Group Anagrams
另外看了下swift5.1的更新
Swift中ascii码的表示
func helper(_ str:String) -> String{
        var count = Array(repeating: 0, count: 26)
        for scalar in str.unicodeScalars{
            var key:Int = Int(scalar.value) - Int(UnicodeScalar("a")!.value)
            count[key] +=  1
        }
        var result = ""
        for i in 0..<count.count {
            for j in 0..<count[i] {
                var asciiFora = Int(UnicodeScalar("a")!.value)
                result.append(String(UnicodeScalar(i+asciiFora)!))
            }
            
        }
        return result
    }



42. Trapping Rain Water
首先想到的是一个time O(n), space O(n) 的解法，但显然不是最优解，最优解的空间复杂度是O(1)

s.split(separator:" ")
name.firstIndex(of: " ")

一共46道，今天就这样了洗洗睡了
Maximum Subarray
Same Tree
Length of Last Word       
Merge Intervals
Jump Game
Minimum Path Sum
40 combination sum II
这道题以前做过，给定的array中可能有多个重复的数字，但是重复的数字不能用多次，想了一会儿没思路，后来看到答案明白了，第n层代表结果中第n个数字，这个empty spot可以用任何不重复的数值填满。这个解法保证了每一层每个数字只出现一次，而如果有重复的数字，则在下一层记录下来，和当前层无关。
解法dfs：注意要sort array，并且下一层的起始可选的数字要从当前层数字的下一个算起
还是有点绕的，还有就是时间复杂度o(2^n)

56. Merge Intervals
这道题不难corner case也不算太复杂，但开始想错了方向，实际上应该保存一个current interval和当前sort好的interval比较，需要改动边界时，选择数值较大的去改写，trick的地方是最好事先声明一个interval变量，不要使用start或者end指针，避免生成新的object增加不必要的时间复杂度

49. Group Anagrams
首先想到sort的方法，但看了下讨论，这个在时间复杂度上不是最优解，因为sort的时间至少是nlogn，有一些方法可以让时间复杂度降到O（n*m），看了一下讨论最容易理解的方法是count每个单词中字母出现个数，生成一个flag，存入hashmap中。实际上就是改变了flag的生成方式。

好久没来打卡了，这几天不是闲着，因为开始投简历了，所以每天要联系的人很多，不过基本投的简历都有了回应，现在进入面试流程的有amazon，offerup，google，uber，godaddy，microsoft还有家门口的小公司，fb据说必须三年经验以上，再加上最近联系的的确有点多，准备不过来，先放一边了。都是iOS岗。有一些不是很符合我的tech stack比如offerup和godaddy，确认使用的是objc和react native，我还是比较偏向swift和objectivec混用的，刚刚做完amazon OA，感觉不太好，没做出最优解，只能求bless了。不知道要不要把重点放在amazon，microsoft这种公司，我的算法真的很烂很烂也不及希望与有奇迹，属于刷了好几遍也没啥进步的。。。

59道 感觉easy都刷的差不多了，接下来可能速度会变慢了
Reverse String
Meeting Rooms II
Best Time to Buy and Sell Stock
Reverse Linked List
Longest Substring with At Most Two Distinct Characters
Fruit Into Baskets
Longest Substring Without Repeating Characters
LRU Cache

63道，娃开始上daycare了，白天终于有时间了！
Unique Paths
ZigZag Conversion
Unique Binary Search Trees
K Closest Points to Origin

luntcz213 发表于 2019-4-10 15:44
63道，娃开始上daycare了，白天终于有时间了！
Unique Paths
ZigZag Conversion

K Closest Points to Origin
KTH LARGEST快速排序解法的时间复杂度为什么是O(N)的
我们快拍中做一个partition，假设平均的分成了两半，那么kth元素要不落在前一半，要不落在后一半。快排需要两边都递归，而我们找kth元素，是不需要两边都递归的，只需要在其中一半寻找即可。
所以期望复杂度就是 O(n) + O(n/2) + O(n/4) + ... + O(1) = O(2n) = O(n)
这只是期望复杂度。

67
Word Break
Insert Delete GetRandom O(1)
Kth Largest Element in an Array
Jewels and Stones
Product of Array Except Self
215. Kth Largest Element in an Array
现在这种找K大的题都有一个最优解法就是使用quik sort排一半的解法，这种解法时间复杂度只有O（n），但需要注意的是，每次sort的指针范围要缩减一位，防止无限循环的发生

380. Insert Delete GetRandom O(1)
这道题remove element的test case要多考虑考虑，尤其是仅有一个元素remove的情况，还有就是注意两个map都要update

75题
这段时间公司出了点问题，因此决定提前开始投简历找工作了，这周都在忙着改简历找内推，catch up一些iOS的知识点，重新温故apple doc。进度可能会有点慢。

297. Serialize and Deserialize Binary Tree
4. Median of Two Sorted Arrays
corner case 不要太多，这道题光看最优解写code就耗费了两个小时

跟godaddy和amazon的HM聊过了，他们都催我准备好就去面试，但是我这个coding水平还是有点low，最后两周冲刺一下吧，不能再拖了。

Lowest Common Ancestor of a Binary Search Tree
Search in a Binary Search Tree
Search a 2D Matrix II   
Count Primes
Binary Tree Level Order Traversal
Two Sum II - Input array is sorted
最优解是O（logn）不是O（n）

Valid Anagram
Serialize and Deserialize Binary Tree
Rotate Array
注意处理k超过array范围的情况

Partition Labels
Greedy
存一遍最后出现的index的位置
在便利一遍，存一个最大值和start位置，当最大值和遍历的位置相同时，说明为patition最后一位，存好后更新start