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取

04/07


289. Game of Life

两种做法。
解法一、copy一个二维数组，然后in-place改变原二维数组。
1）nested loop扫描每一个cell
2）对于每个cell，用一个helper method来实现update
3）在helper method中，扫描当前cell的8个neighbor，维护一个count来数live neighbor cells。当count == 3 || (count == 2 && current cell is live)时，在原二维数组中将当前cell标记为1
4）时间复杂度：O(m*n)；空间复杂度：O(m*n)

解法二、利用bit的最后两位记录状态。最后一位是current state，倒数第二位是next state。00: dead <- dead; 01: dead <- live; 10: live <- dead; 11: live <- live
1）2）同上
3）用board[row][col] & 1，得到最后一位bit表示的current state，进而count live cells。update过后，所有元素从0，1变为2，3
4）再次遍历所有元素，右移一位，得到新的状态
5）时间复杂度：O(m*n)；空间复杂度：O(1)


73. Set Matrix Zeroes
遍历两次。第一次记录哪些行列需要变为0，第二次将这些行列变为0。
1）如果遇到0，那么将这一行和这一列的第一个元素都设为0作为标记。因此会产生一个问题，那就是无法分辨第一行和第一列中出现的0到底是因为原本在第一行/列就有0，需要变为0，还是来自于标记的0。因此，维护两个boolean值来记录是否在第一行和第一列原本就有0
2）第二次遍历时，从row = 1和col = 1开始遍历，并将对应行列变为0
3）第一行和第一列单独遍历，根据boolean值来决定是否变为0
4）时间复杂度：O(m*n)；空间复杂度：O(1)



287. Find the Duplicate Number

由于需要满足题目的三个条件：不能改变原array，额外空间O(1)，时间复杂度小于 O(n²)，因此不能直接sort。正确解法是用一快一慢两个指针。
1）fast和slow都初始化为nums[0]。数学上可以证明在长度为n+1的数组里存1...n一定会有重复，从0出发一定不会再回到nums[0]
2）用do while循环（重点注意，否则下一步会变成死循环），fast走两步，即fast = nums[nums[fast]]；slow走一步，即nums[slow]，直至fast == slow
3）再用一个指针search = nums[0]，每次走一步，直至和slow相等
4）时间复杂度：O(n)；空间复杂度：O(1)



268. Missing Number

解法一：sort找第一个index和value不对应的值
解法二：把数组所有value求和得到actualSum，然后再把所有index求和再加nums.length得到expectedSum，差值即为所求
解法三：用bit manipulation，将数组的value和index做XOR (^)，再^nums.length，因为缺失的数只有其对应的index，所以XOR的结果即为所求


283. Move Zeroes

1）维护left和right两个pointer。其中left指向左边第一个0，right指向第一个未被扫描的数，left和right之间都是扫描过的0，left左边是所有扫描过的被交换过去的非0数。
2）如果right是0，继续向前
3）如果right非0，交换left和right，然后left和right都向前一步
4）时间复杂度：O(n)；空间复杂度：O(1)



238. Product of Array Except Self
1）维护数组products，最后返回
2）先从左向右扫描。维护一个变量left，记录当前元素的左边所有元素的乘积，赋值给products[i]。边扫描边更新left和products[i]。扫描结束后，products[i]即为当前元素的左边所有元素的乘积
3）然后从右向左扫描。维护一个变量right，记录当前元素的右边所有元素的乘积，然后products[i]乘上right为新的products[i]。边扫描边更新right和products[i]。扫描结束后，products数组即为所求
4）时间复杂度：O(n)；空间复杂度：O(1)



169. Majority Element

解法一：sort，取nums[nums.length / 2]。题目保证了majority element个数一定大于nums.length / 2，所以无论数组元素个数是奇数还是偶数，sort后的中间元素一定就是所求数
解法二：Boyer-Moore Voting Algorithm。
1）维护一个变量candidate，初始化为nums[0]；同时维护其对应的count，初始化为1
2）遍历数组，如果count == 0，那么candidate为空，所以将当前nums[i]赋值为candidate，同时count = 1
3）如果遇到相同元素，count++；
4）如果遇到不同元素，candidate数量被抵消，count--。最后剩下的一定是有多余的未被抵消的candidate
5）时间复杂度：O(n)；空间复杂度：O(1)



229. Majority Element II

169的follow-up，同样是用Boyer-Moore Voting Algorithm
1）维护两个变量candidate1和candidate2，都初始化为Integer.MIN_VALUE；同时维护其对应的count1和count2，初始化为0
2）如果count1 == 0，那么candidate1为空，所以将当前nums[i]赋值为candidate1，同时count1 = 1
3）count2 == 0，对应赋值candidate2，同时count2 = 1
4）遇到与candidate1或candidate2，count1++或count2++
5）遇到第三种数，count1和count2同时自减1（被抵消了）
6）得到两个candidate后，还需再进行一次循环，只有满足个数大于n / 3才符合要求
5）时间复杂度：O(n)；空间复杂度：O(1)