蜗居匹兹堡孤独刷题中

Day 26 - 2019/03/02
144. Interleaving Positive and Negative Numbers
我们必须知道正数多还是负数多，数量多的那种数的指针安排在前面。
这道题非常好，练习这两种技术： 1）如何把具有某种特性的数移动到数组的一边； 2）使用同向双指针进行interleaving排列；
注意大函数化成小函数。

200. Number of Islands
用grid初始化parent数组。用rank数组实现compressed find。

Day 27 - 2019/03/03

昨天太疯狂，打dota打的头疼欲炸，打游戏真的是比刷题累太多了，找到工作前，再也不能打了。今天一天大部分时间都在睡觉。晚上起来索性把Quantcast OA做了，第一道题真是比较恶心，字符串处理的题，又没法看到test case，怎么debug，搞了一个多小时，最后只过了4个case，还有9个case没有过。第二道题已经没时间了，大概看了看，感觉这道题还挺值得一做的，用dfs应该不难写出来，如果用并查集做，暂时还想不出来怎么做。

Day 28 - 2019/03/04

Sort Letters by Case
非常简单

75. Sort Colors
这道题比较容易想到的是做两次partition。
优化的方法是三根指针：
1）i指针碰到0，那么swap(nums, left, i)，left++， i++
2）i指针碰到1，就什么也不做，i++
3）i指针碰到2，那么swap(nums, right, i)，right--。注意，这时候i指针不能动，因为不知道这个位置的数是0还是1

Sort Colors II
基本就是Quick Sort的简化版。
(1, 2, 3, ... , k)
(1, 2, 3, ..., k/2)  |   (k/2 + 1, .... , k)
....
worst case是O(n*k), 平均时间复杂度是O(nlogk)
当k == n的时候，就是Quick Sort


209. Minimum Size Subarray Sum
暴力法是双重循环找到每一个subarray，然后check是否满足条件。O(n^2)
start: 0 -> n
    int sum = 0
    end: start -> n
        check sum <> s
如果这道题用prefixSum来解，仍然会是O(n^2)的时间复杂度。

分析这个过程中的重复计算：
在内层循环中，一旦sum满足条件，我们就不需要再增加end。
在下一个起始位置，不需要将end指针回退（这一点可以数学证明），并且可以利用当前sum，而只需要sum -= nums[start]
时间复杂度分析：表面看来是两重循环，但是两个指针都不回退，所以是O(2n) 也就是 O(n)

3. Longest Substring Without Repeating Characters
注意，在j == n的时候，我们已经包括了n-1那一位加入hash之后的结果，这样就不会丢解

76. Minimum Window Substring
这类问题的分析都是相似的，首先使用暴力法，然后分析重复计算，j指针不需要回退。
最终的时间复杂度是O(256n)

340. Longest Substring with At Most K Distinct Characters
这个题要注意 j == s.length()的时候，会少更新一次结果。

19. Remove Nth Node From End of List
只要是改变链表结构，都要使用dummy node

876. Middle of the Linked List
要用最简洁的写法，dummy并不必要

141. Linked List Cycle

142. Linked List Cycle II
方法一：HashSet
方法二：快慢指针 弗洛伊德龟兔赛跑算法

Window Sum
下标容易出错的题，都要带入具体case验证

160. Intersection of Two Linked Lists   
要么相会于交叉处，要么相会于对方末尾

283. Move Zeroes
用swap的方法比较好

Day 29 - 2019/03/05

378. Kth Smallest Element in a Sorted Matrix
[1, 5, 7]
[3, 8, 9]
[4, 9, 10]

算法一： minHeap
左上角的1是第一小，如果找第二小，那么只能出现在5和3之间，然后找第三小，只能出现在5， 8， 4之间。
于是可以用一个minHeap维护这个候选集合，用于找出当前最小。
时间复杂度是O(klogn) 空间复杂度是不是O(n)，因为用了visited，所以是O(n^2)

算法二：优化minHeap
这个算法可以小小优化一下，就是不用visited数组，一开始把最上面一行加入，然后只往下走，这样不会走回头路。对于poll出来的元素，只把它下面的元素加入，这个算法没毛病。
时间复杂度没变 O(klogn)，空间复杂度为O(n)

算法三：优化minHeap
一个很小的改动就可以将时间复杂度优化为O(klogk)，就是规定minHeap的大小为ｋ

算法四：quickSelect
如果用这个算法，也就完全没有利用这个矩阵的性质，但是跑出来才2ms，比其他的都快的多，也是醉了
平均时间复杂度是O(n^2), 最坏是 O(n^4)，其中n是正方形边长
空间复杂度是O(logk)

算法五：二分法
讨论区里高票答案有用二分法的，中间步骤中有一步是检验矩阵中有多少数比mid小，这一步的时间复杂度我觉着和暴力法没有区别，所以用二分法就没有意义了。 O(n^2 log(max-min))

算法六： StefanPochmann大神从paper上扒下来的
大致看了一下，利用 2×2 的sub - matrix，以后再研究吧。


373. Find K Pairs with Smallest Sums
这道题和378连到一起做就比较容易理解了。

26. Remove Duplicates from Sorted Array
同向双指针

27. Remove Element
同向双指针

234. Palindrome Linked List
这道题练到了两个技术：1）快慢指针；2）reverse；

457. Circular Array Loop
对于有环的定义要非常仔细：
1）一步就到达的，不算； 2）中间move的方向不一致的，不算；

在数组上实施快慢指针。
注意，快慢指针的相遇点，并不一定是起点。
也就是说对于给定index，实施快慢指针的时候，其实也检查了它之后位置的情况。
为了避免重复计算，在check了当前index，发现没有环，于是它所检查过的点，都不需要再检查了。为了避免重复计算，把这些点的值都标为0。

有一个问题：循环的出口在哪里？
我觉着可以证明：如果两个指针都在同一方向运动，又不出现环，是不可能的。

还有要注意的一点是：
java的求模运算
-1 % 1 = 0
-1 % -2 = -1；
1 % -2 = 1；
-5 % 10 = -5;

private int getNextIndex(int i, int[] nums) {
    int n = nums.length;
    int nextIndex = (i + nums[i]) % n;
    return nextIndex < 0 ? n + nextIndex : nextIndex;
}

904. Fruit Into Baskets
340的变形

30. Substring with Concatenation of All Words
窗口类同向双指针

Day 30 - 2019/03/06

61. Rotate List
第一个pass找到length是无可避免的。
然后需要注意的是k == 0的情况。

763. Partition Labels
首先第一个pass记录一下每个字母最后出现的位置。
第二个pass遍历的时候，关键在于这个substring的结束位置，在结束的时候，要保证走过的所有字母，都达到了它们最后出现的位置，也就是最后出现位置最远的那个。

80. Remove Duplicates from Sorted Array II
数组的题就是要特别细心，带入具体case

632. Smallest Range
首先应该画出示意图，sliding window的大小就是range，也就是window中的最大值减去最小值。
用minHeap，既可以使window中的node数量保持为nums.size()，并且方便取出minVal。剩下的只需要维护一个window中的最大值。
k路归并的过程中，就可得minRange

159. Longest Substring with At Most Two Distinct Characters

992. Subarrays with K Different Integers
怎么改模板都很难写出这个exactly K。
高票大神的思路：return atMostK(A, K) - atMostK(A, K - 1);
其中需要记住的是，每前进一个index，增加的subarray数量是 j - i + 1，所以count += j - i + 1;
想一想，这个计算的意义是，以j结尾的subStr的个数。

如果按照最初的思路走，硬搞出来就是第二高票哥们的思路，用了一个prefix。这个方法不如前一个优雅，以后再说吧。

977. Squares of a Sorted Array
相向双指针

723. Candy Crush
这种模拟类的题目，非常重要的是如何表示状态。
如何表示需要消掉的格子呢？取负！
取负数是个非常巧妙的方法，在接下来的扫描中，仍然可以用这个负数的绝对值和其他格子相消。
第二点是，相消时候是对每个竖列扫描。用到了同向双指针deduplication的技术。

844. Backspace String Compare
看似是个easy，其实很难写对，很考察细心

532. K-diff Pairs in an Array
这道题并不easy，用HashMapd比较好，但双指针也要会。

同学。tree的题不同于general 图的题，tree的核心大部分是 recursion，找subproblem。你说那个bfs dfs，是在特殊题目中，需要把tree 当图来处理才好做的情况。

Day 31 - 2019/03/07

438. Find All Anagrams in a String
567. Permutation in String
这两道是基本一样的题

524. Longest Word in Dictionary through Deleting
假设word的长度为m，字典中有n个词
方法一：sort dictionary first
时间复杂度O(nlogn + mn)
方法二：遍历字典，打擂台
时间复杂度O(mn)

语法学习：//return the longest word with the smallest lexicographical order
if (word.length() > rst.length() || word.compareTo(rst) < 0) rst = word;

923. 3Sum With Multiplicity

学习lee大神的数学求法：
3 cases covers all possible combination:
i == j == k  三个数都相等
i == j != k  两个数相等，另一个数可大可小
i < k && j < k  因为在循环中，不能体现大小关系，所以这里需要规定大小关系的，用来避免重复计算

算法中涉及到一个combination问题的计算：
n个球拿出3个，一共几种组合：n * (n - 1) * (n - 2) / 6

rst需要用long，map也需要用long，因为某个数的出现次数也会overflow。

个人而言，掌握最常规解法更重要。
首先排序，然后遍历第一个数，双指针遍历第二个数。
关键是处理A[i] + A[l] + A[r] == target时候的两种情况：
1）A[l] == A[r]这意味这剩下的所有为遍历的数都相等，可以直接计算最终结果了rst += (r - l + 1) * (r - l) / 2;
2）A[l]！= A[r] 这个地方很重要，因为重复数字的存在，不知道能不能l++或者r--。这时候要查出来l后面有几个一样的，r前面有几个一样的，然后再移动指针。rst += countL * countR;

828. Unique Letter String
又是lee大神的思维转换大法：
只有一个字符在subStr里以unique形式出现的时候，它才会被记入最终结果。
当我知道第一个和第三个A的index的时候，我就可以计算第二个A在subStr中以unique身份出现的次数：
对于"XAXAXXAX"
For the first "A": (6-3) * (3-(-1))"
For the second "A": (9-6) * (6-3)"
For the third "A": (n-9) * (9-6)"

这道题常规方法应该掌握DP方法：
Let dp[i] is sum of unique char in all substring ending at i, then the answer is sum(dp[i]), i=[0..n-1].
char c = s.charAt(i)
dp[i] = dp[i-1] + ( i - lastPosOf(c) ) - ( lastPosOf(c) - secondLastPosOf(c) )
        = dp[i - 1] + i - 2 * lastPosOf(c) - secondLastPosOf(c)

当新的字符O在i出现的时候，以O为结尾并且O是unique的subStr的个数是(i - f),
由于这新的O的出现，导致之前一部分subStr的计算作废了，那就是在f位置以O为结尾的那些subStr, 他们的个数是(f - s)

821. Shortest Distance to a Character
两轮，正着一轮，反着一轮。

838. Push Dominoes
Lee大神总是可以一针见血：
Whether be pushed or not, depend on the shortest distance to 'L' and 'R'.
但是这方法并不好写，浪费了很多时间也没有写对。
还是直接背住他的另一个方法好了
'R......R' => 'RRRRRRRR'
'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
'L......R' => 'L......R'
'L......L' => 'LLLLLLLL'
双指针维护这个区间的头尾，然后以此处理这四种情况。
为了处理两头的情况，在最左边加一个字符‘L'，最后边加一个字符’R'

Day 32 - 2019/03/08
360. Sort Transformed Array

a > 0， 抛物线开口向上，对于数组两端点的值，我需要找方程结果较大的那个。
a < 0, 抛物线开口向下，我需要取出方程结果较小的那个。
a = 0的情况，把它包括到上面任何一种情况中都可以，因为我既可以取到方程结果大的那个数也可以取到小的那个，唯一需要做的是，写对index，放到结果数组。

这道题的要求是返回sorted order，有一个隐含的要求，就是要从大到小就都从大到小，不能有些返回的是从大到小，有些返回的是从小到大

986. Interval List Intersections
当前两个interval: A和B[j]有三种位置关系：
1）A在B前: i++;
2) B在A前: j++;
3) 相交： 求出intersection，用了谁的end，谁的指针向前

语法学习：
Interval[] rst = new Interval[list.size()];
return list.toArray(rst);

881. Boats to Save People

保证每人都能上船，也就是最沉的那个也不超限。每条船最多上两个人，问最少用几条船。
这很容易让人想到一个贪心解法：
让最重的和最轻的一起上，如果最轻的都不能和他一起上，那他就只能自己上了。
面试的时候应该不用让证明贪心法正确性吧？

826. Most Profit Assigning Work
设m = difficulty.length, n = worker.length
给定一个工人的能力，遍历难度数组，找他能完成的最难工作，这样时间复杂度是O(m * n)
如果给两个数组都排序，时间复杂度是O(mlogm + nlogn + n + m);
如果m和n都很大，排序是优化的算法，space: O(m)

925. Long Pressed Name
两根指针都从左开始。如果匹配了就都往前走，如果不匹配，检查typed当前字符是否和前一个一样，如果一样，就向前，如果不一样就return false。
都检查完了，typed指针有可能没有走完，让它走完最后一个字符一样的。
最后检查是否两个指针都走到头了。

我知道了，Lee大神在2018年十月底总结了很多two pointer标签的题。

487. Max Consecutive Ones II
受Lee大神828解法的启发，将最后两次出现0的位置存下来。
Follow up:
What if the input numbers come in one by one as an infinite stream?

1004. Max Consecutive Ones III
窗口类同向双指针

424. Longest Repeating Character Replacement
窗口类同向双指针

23. Merge k Sorted Lists
K路归并：
1）minHeap法，O(nlogk) time, O(logk) space ；
2）分治法, O(nlogk)time, O(logk) stack space；
3）两两归并, O(nlogk)time, O(k) space；这个空间复杂度对不对？有点拿不准啊

56. Merge Intervals
先以start排序，不需要考虑start相等的情况，不影响最终结果。
遍历list，主要在于找到当前interval的end，这就是merge的过程。

349. Intersection of Two Arrays
1）先Sort再Merge，注意除重的部分。 O(nlogn + mlogm) time, O(1) space
2）用两个HashSet，把其中一个array存入，另外一个set用来保存结果以便除重。O(m + n) time, O(min(m, n)) space
3)给其中较小的那个数组排序，以便用于binary search，用set保存结果除重。 O((m + n)logn) time, O(min(m, n)) space

Day 33 - 2019/03/09

今天我都干了神马！

Intersection of Arrays
这道题有一个很重要的条件就是：每个数组中无重复，这样就简单了不少。
方法一：最容易想的方法是用一个Map,把所有数都存进去，然后再数哪个数有k个。设每个数组平均长度n，k个数组，那就是O(nk)时间，O(nk)空间
方法二：用一个minHeap进行k路归并排序，记录当前的值，如果有k个当前值，就说明是一个intersection。注意跳出循环的时候有可能少算一个。 O(nlogn + nklogk)时间，O(k)空间

Day 34 - 2019/03/10

今天废了，就一道题

311. Sparse Matrix Multiplication
关键是要把矩阵相乘的图画出来，A的哪一行和B的哪一列相乘，对应结果的哪一行哪一列。结果中的每一个数都是由B.length个product相加得来的。

求 K 个排序数组的中位数
二分法之按值二分, 中间步骤又用到了二分法之OOXX
在[0, Integer.MAX_VALUE]区间内，二分查找。
每次的判定条件是：在整个数组矩阵中，数出来有多少个数比这个数小。
在排序数组中count多少个数比给定数小，又用到了二分查找。
所以总体时间复杂度是：O(klogn * logInteger.MAX_VALUE)

想起来378. Kth Smallest Element in a Sorted Matrix讨论区也有一个这样的解法
一直有个疑问就是，按值二分找到的这个第K大的数，怎么就能保证它是这些数组中的数呢？

二分法之OOXX能够找到第一个比target大的值，然后计算在这个数组中有多少个数比target大。进而计算矩阵中有多少个数比target大。
这个按值二分也是一个二分查找之OOXX，这里需要满足的条件是有>= k个比target大的数
并且，关键是我们找的是最后一个满足这样条件的数。
这样查找的结果，一定是矩阵中的某一个数，越过了这个数，就没法满足条件了。