LeetCode刷题日常记录

3/29
220. Contains Duplicate III
需要找某个特定范围内的数的差值，可以用TreeSet，因为它用balanced binary search tree实现，便于查找floor和ceiling，同时可以避免重复。遍历数组，查找TreeSet中与其对应的floor和ceiling，如果有符合在差值范围内的，返回true；否则将这个数加入TreeSet，同时维护TreeSet的size，来保持index的范围也符合题意。遍历完毕，没有符合的数对，返回false。
还可以用bucket sort，不是很懂。

307. Range Sum Query - Mutable
303. Range Sum Query - Immutable的follow-up。因为增加了update的操作，再用数组存储sum[0:i]的话update需要O(n)时间。应该用Fenwick Tree，即Binary Index Tree，使得update的时间降为O(logN)，代价是求和的时间从O(1)变为O(logN)。创建一个FenwickTree class，内部维护一个partialSum数组。update时，从i + 1开始到n，沿途的node都增加delta，i的自增方式是其二进制表示的最后一个1bit加1（如0110 -> 0110 + 0010 -> 下一个i为1000）。query时，要求sum[0:i]，方向相反：从i + 1开始到1，sum自增，i自减，方式是其二进制表示的最后一个1bit减1（如0110 -> 0110 - 0010 -> 下一个i为0100）。求取二进制表示的最后一个1位的方法：i & (-i)。

530. Minimum Absolute Difference in BST
由于确定是BST，用inorder traversal可以得到sorted array，因此可以加以利用，在inorder traversal求取当前node与前一个node的差值diff，并更新总体差值minDiff。
follow-up：给定的不是BST，那么就维护一个TreeSet，以使用其BST的特性，求取floor和ceiling，得到差值diff，并更新总体差值minDiff。

292. Nim Game
考数学，如果n能被4整除，先手的一定输。

319. Bulb Switcher
又考数学。一个数的因子个数代表了它在会被turn on/off的次数，每个因子代表它在第几轮被turn on/off。因此，只有被操作了奇数次，它才能为on。一般一个数都有偶数个因子（如2->[1,2], 5->[1,5], 10->[1,2,5,10]），除了完全平方数，有奇数个因子（如4->[1,2,4],9->[1,3,9]），因此这个问题转化为在小于n的数中有多少个完全平方数。

04/02 准备面经的时候刷的题

42. Trapping Rain Water
用two pointers：left，right。维护变量leftMax和rightMax。比较height[left]和height[right]，由于短板效应，最大盛水量由短板决定，所以先移动较小的height（极端情况：height从左至右递增）。移动后，比较leftMax（或rightMax）和height[left]（或height[right]），并更新leftMax（或rightMax）为比较后的较大值，那么在这一步中可承载的水的unit即为leftMax - height[left]（或rightMax - height[right]）。更新pointer，直至left和right相遇。

329. Longest Increasing Path in a Matrix
暴力解法是从每个元素开始进行dfs，时间复杂度为O(m*n*m*n)。实际上，以某一个元素为起始的最长递增路径，就是值小于它的所有邻居中最长的的路径+1，所以只需要扫描四个邻居，然后记录下这个元素的最长递增路径，可被其他元素使用。因此这是一道动态规划题。可以用dfs recursion+dp，求当前元素为起始的最长递增路径。如果已经保存过，直接返回；否则调用递归。
415. Add Strings
一般要扫描两个“泛数组”，各用一个pointer指示当前元素，while loop里的条件是(i < length1 || j < length2)，然后在循环中根据i（或j）是否到达length1（或length2）进行不同的操作。
这道题中，维护两个变量digit和carry。string从后往前扫描，每轮loop中，digit初始化为carry，如果i >= 0，digit加上对应的char，否则加0；j同理。loop结束后，看是否还有carry，有就添上去。将result翻转，然后返回之。

419. Battleships in a Board
Intuition：由于题目限制了valid input，实际上简化了题目，可以直接套用200. Number of Islands，将船“沉没”变成'.'，然后count++。这样原数组会被改变。
follow-up：要求用O(1) extra memory和不改变原数组，方法是扫描每个元素，当遇到每艘船的左上角的‘X’时count++，遇到其他的‘X’则不做反应。

04/03 准备面经的时候刷的题


617. Merge Two Binary Trees

简单题，用recursion做。
1）corner case是来自某一个树的node为空时返回另一个node。
2）当两个node都不为空，sum up values，然后recursively merge left and right children。


515. Find Largest Value in Each Tree Row
1）可以用BFS，构造一个class Node存储level信息，同时同queue遍历
2）也可以用helper method，那么相当于DFS
3）当level == list.size()时，加进list中；否则，用list.get(level)的值和当前值比较，较大者替换掉list中已有的值。


117. Populating Next Right Pointers in Each Node II

1）用root来指向当前操作的parent，pre指向需要操作的child的前一个node
2）维护一个dummy，指向将要执行的下一个level
3）next的连接过程为：找到root拥有的child，pre.next = child，然后移动之，pre = pre.next
4）接下来移动root，直至root == null
5）root == null即到头了，需要进行重置，为执行下一个level做准备。具体方法是，将root指向dummy.next，重置pre = dummy，重置dummy.next = null


25. Reverse Nodes in k-Group

简单的做法是用recursion。
1）用loop边count边找到断点位置
2）loop结束后，判断：count == k，说明需要翻转，执行接下来的代码，否则直接返回head
3）断点位置用一次recursion即得到翻转完成的后半段linked list，所以只需要翻转断点前的部分
4）断点前的部分翻转完成后，连上断点后的用recursion完成的后半段linked list，然后返回head

刷帖带我一个好吗~~~~~！加个微信组个群什么的

04/04 准备面经的时候刷的题


72. Edit Distance

一道比较难但也很典型的DP题。可以从一般的情况着手，归纳规律。如从“abbe”变为“ace”，如果最后一个字母相同，那么实际上“abbe” -> “ace”和“abb” -> “ac”的操作数是一样的。这时只要讨论“abb” -> “ac”的最小操作数。“abb” -> “ac”可以通过三种操作得到：insertion（如果已知“abb” -> “a”，那么“a” -> “ac”只需插入‘c’，这里改变了word2），deletion（如果已知“ab” -> “ac”，那么“abb” -> “ab”只需删除‘b’，这里改变了word1），replace（如果已知“ab” -> “a”，那么“abb” -> “ac”只需将‘b’替换成‘c’，这里同时改变word1和word2）。
1）维护二维dp数组做memoization。dp[i][j]表示word1[0...i]变换为word2[0...j]的最小操作数，初始化为-1。
2）求取和memoization的过程由helper method完成。
3）如果其中一个word为空，那么变换成另一个word最少需要另一个word的长度length这么多的操作数。
4）如果已经求解过，直接返回dp[i][j]。
5）如果dp[i][j] == -1，那么它的值将是1+插入、删除、替换的较小值，即1+min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])。
6）time complexity: O(length1*length2); space complexity: O(length1*length2)


215. Kth Largest Element in an Array

至少有三种解法。1. Java偷懒解法：直接sort，然后取length - k的数。2. minHeap法，维护一个size为k的heap，当加入一个新的数时，将top即最小值删除，保证heap中k个数一直是局部最大，最终得到全局最大。3. quick select算法。
如果在刷题时偷懒，出来混总是要还的，在面试里将会跪得很惨。所以应该详细了解第3种方法。
1）由于找第k大的数，所以把较大的数放pivot左边，较小的数放pivot右边
2）用helper method求出当前指定的pivot在排序后的位置pos。while (start <= end)：如果pos == k - 1，意味着nums[pos]左边有k - 1个比它大的数，即nums[pos]是第k大的数，返回之。否则，如果pos < k - 1，那个数在其右边，start = pos + 1；如果pos  > k - 1，那个数在其左边，end = pos - 1
3）helper method中，以nums[start]作为pivot，left = start + 1，right = end。while (left <= right)（等号很重要！）：不断交换，使得left的左边放的是大于pivot的数，right的右边放的是小于pivot的数，直至left crosses right。接下来的重点是：pivot和left还是right交换？因为要保持pivot的左边都是大于pivot的数，而right的右边是小于pivot的数，意味着right指向第一个大于等于pivot的数，符合要求，所以pivot要和right交换。


补充内容 (2019-4-5 23:50):
quick select的time complexity: average O(n); worse case O(n^2)
space complexity: O(1)

girllily4 发表于 2019-4-5 16:02
刷帖带我一个好吗~~~~~！加个微信组个群什么的

可以私我

emm 你看我这个白板有能力私信么 下资料的大米都没有 捂脸 yiwenl1997 这是我微信

girllily4 发表于 2019-4-6 01:27
emm 你看我这个白板有能力私信么 下资料的大米都没有 捂脸 yiwenl1997 这是我微信

备注下哦

04/06 开始二刷前400中做过的未上锁的easy和medium，同时也做一些hard。如果有follow up，也一起做。


382. Linked List Random Node

Intuition: 数node的个数，然后random sampling。
time complexity: O(n); space complexity: O(1)
follow-up: 用reservoir sampling，不是很懂。


470. Implement Rand10() Using Rand7()

很有意思的问题。
1）用两次Rand7()，得到7 * 7 = 49个数，然后取前40个数，来模拟Rand10()
2）以第一次Rand7()作为行，第二次Rand7()作为列，得到一个表。根据行列号求出一维num。如果得到的num是41-49，那么进入下一个循环，再两次Rand7()
3）如果得到的num是1-40，那么num % 10 + 1即为所求（如果不+1，那么求取的是0-9）
time complexity: worse case O(∞); space complexity: O(1)



495. Teemo Attacking

1）关键点：如果后一个time point正处于前一time point的duration中，会被刷新从新算duration。
2）one pass扫描数组，取i和i - 1的差值与duration之中的较小值，累加到total
time complexity: O(n); space complexity: O(1)



485. Max Consecutive Ones

注意corner case：全是1
time complexity: O(n); space complexity: O(1)


380. Insert Delete GetRandom O(1)

对数据的insert, delete, getRandom()以及查找都要O(1)时间，暗示要用HashMap。
1）维护一个List存放元素，和一个HashMap存放元素在List中的index
2）insert时，List和HashMap增加相应的元素和index
3）delete时，判断是否删除最后一个元素。如果不是，那么需要将这个元素和List最后一个元素交换位置，更新List和Map信息，将最后一个元素放在被删除的元素的index
4）getRandom()直接根据List的size取


381. Insert Delete GetRandom O(1) - Duplicates allowed

380的follow-up。难点在于允许重复插入相同元素，所以将HashMap的value变为一个List来存储相同元素的所有index。
1）维护一个List存放元素，和一个HashMap存放元素在List中的所有index
2）insert时，List和HashMap增加相应的元素和index
3）delete时，判断是否删除最后一个元素。如果不是，那么需要将这个元素和List最后一个元素交换位置，更新List和Map信息，将最后一个元素放在被删除的元素的index 。对于Map的更新，可以删除最后一个元素的lastIndex，然后加入被删除的元素的index。
4）getRandom()直接根据List的size取