蜗居匹兹堡孤独刷题中

Day 35 - 2019/03/11

53. Maximum Subarray
遍历数组，计算[0, i]区间的sum，然后与之前最小的sum相减，最后要update minSum(初始化为0)。
注意：不能先update minSum再求maxSubarraySum，这样就无法处理都是负数的情况了。
这道题用DP方法其实会更加清晰：
状态变量dp: 以nums的值为结尾的最大字数组和，注意必须包括这个nums的值
初始化：dp[0] = nums[0]
状态转化方程：dp = nums + (dp[i - 1] > 0 ? dp[i - 1] : 0);　// 因为nums的值必须包括

152. Maximum Product Subarray
状态变量localMin/localMax: 以nums的值为结尾的最大子数组乘积，注意必须包括这个nums的值
初始化：localMax[0] = nums[0]
状态转化方程： 因为nums的值必须包括，所以只需要决定要不要localMax[i - 1]

Subarray Sum
利用prefixSum，这道题就变成了two sum，由于需要返回index，所以需要用到Map。
注意：sum 包括nums，i 从0开始，这就导致我们无法计算[0, i]的subarraySum, 只能计算[1, i]
这类题的初始位置要特别注意！！！

Subarray Sum Closest
Hash表已经无法解决“尽量接近”问题了，只能排序了。
这类题一定要注意prefix里存的值和题目需要返回的值之间意义的差别，index容易搞错的。
对于prefixSum而言，不包括nums的值，所以prefixSum - prefixSum[j]就是从[j, i - 1]的subarraySum

121. Best Time to Buy and Sell Stock
虽然代码很像53，但其实我感觉这是完全不同的问题。
根据定义来做： 很之前股价最低的那一天相减，就是当前index能够得到的最大利润。

Submatrix Sum
这道题真是不容易想清楚

Maximum Submatrix
令狐大神的解法很有教义！
最近入睡比较困难，不是睡不着就是睡一会就醒了。决定多做一些器械训练，让自己身体足够疲惫。
今晚先做了硬拉，这个动作我还没有掌握，也还没搞清楚自己该练传统式还是相扑式，因为膝盖有伤，所以相扑式更舒服一些。目前了解到的一些要领是：1）整个发力过程分为两段，杠铃从胫骨到膝盖段，是腿部发力阶段；然后是臀部和背部的发力阶段；下放过程也要重复这两个过程。2）背要直，背部肌肉要收紧，避免下背部受力导致腰伤。 3）发力之前挺胸吸气。
目前的问题是：1）明显感到下背部酸痛，不清楚自己是否全程保持了背部挺直，这是很大的问题。2）呼吸的节奏不太对，做到后面出现头晕。3）整个动作不连贯
这个动作还需要慢慢研究体会，争取一个月时间内能掌握好吧。
然后做了四组引体向上，四组高位下拉，四组划船。

Day 36 - 2019/03/12

120. Triangle
状态变量：dp[i][j]表示从下往上走到triangle[i][j]这一点的最短路径
方程： dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j)
初始化：for (int i = 0; i < n; i++)  dp[n - 1][i] = triangle.get(n - 1).get(i);
答案： dp[0][0]

由于本行状态只和下一行状态有关，所以可以用循环数组优化。
最终: O(n^2) time, O(n) space

Minimum Path Sum
状态变量：dp[i][j]表示从左上往右下走到grid[i][j]这一点的最短路径
方程： dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]) + grid[i][j];
初始化：容易出错。分三步走：初始化dp[0][0]，然后初始化最上面一行，最后在向下走的过程中循环外初始化dp[i % 2][0]
答案：dp[(n - 1) % 2][m - 1]

62. Unique Paths
非常相似的题

63. Unique Paths II
初始化比较容易出错，一定要注意。

Knight Shortest Path II
这道题能用DP，关键是因为从左到右的方向性，外圈loop一定是从左到右才可以 (j : 0 ~ m)
每个点只可能来自于左边的四个点，比较这四个点，哪个的路径短。
状态变量：f[i][j]到达这一点的最短路径
方程：f[i][j] = min(f[i - 1][j - 2], f[i + 1][j - 2], f[i - 2][j - 1], f[i + 2][j - 1]) + 1
初始化：原点外所有点都初始化为Integer.MAX_VALUE, f[0][0] = 0;
答案：f[n - 1][m - 1]

70. Climbing Stairs
状态变量：f[i] 到达i stair的方案总数
方程： f[i % 2] = f[(i - 2) % 2] + f[(i - 1) % 2];
初始化： f[0] = 1, f[1] = 1
答案： f[n % 2]

55. Jump Game
1.从DFS的角度考虑，从原点出发，在它所能跳到的范围内再次出发。
所以递归的定义是以当前位置出发，是否可以到达最右。
方案个数是 O(2 ^ n)，每个方案的时间是 O(n), 所以一共是O(n * 2^n)
Space complexity : O(n). Recursion requires additional memory for the stack frames.
2.很容易想到记忆化搜索来优化到O(n^2)
3.这种记忆化搜索都可以不用递归来做。 可以从左往右，也可以从右往左倒推。
状态变量：f[i]表示能否到达最右
方程：在jumpLimit范围内，f[i] = f[j] (j > i)
初始化： f[n - 1] = true;
答案：f[0]
4.贪心法
还是从右向左走，发现不需要记录所有点的状态，只需要记录最左边的f = true的点。

45. Jump Game II
这道题是一维版的Knight Shortest Path II
状态变量：f[i] 从index 0出发到达index i的最小步数
方程： f[j] = min(f[j], f[i] + 1)
初始化： 除index = 0以外的所有点都初始化为Index.MAX_VALUE
答案： f[n - 1]
O(n ^ 2) time, O(n) space

贪心法：O(n) time O(1) space
搞清楚当前这一跳的最远距离和下一条的最远距离。

Day 37 - 2019/03/13

198. House Robber
State Variable： f[i] represents the maximum amount can be robed from [0, i]
Function: f[i % 2] = max(f[(i - 2) % 2] + nums[i], f[(i - 1) % 2])
Initialization: f[0] = nums[0]; f[1] = max(nums[0], nums[1]);
Answer: f[(n - 1) % 2]

213. House Robber II
Math.max(robHelper(nums, 0, n - 2), robHelper(nums, 1, n - 1));

221. Maximal Square
1. 暴力法遍历一个矩阵中的正方形需要O(n^4)
2. 可以分析出这其中重复计算的地方，尝试记忆化搜素。但是如何确定状态变量是一个难题。
状态变量：f[i][j]表示(i, j)点为正方形的左下角，正方形全为一的最大边长值。
同时还需要up[i][j]和left[i][j]这两个变量表示向左和向右的最大延伸量。
方程：f[i][j] = Math.min(Math.min(left[i][j - 1], up[i - 1][j]), f[i - 1][j - 1]) + 1;
初始化：比较复杂。四个内容：1) left[i][0]然后left[i][j]; 2) up[0][j]然后up[i][j]; 3) f[0][j],f[i][0]; 4) maxLen
答案：maxLen * maxLen
O(n^2) time, O(n^2) space
3. 在方法二的初始化过程中，可以发现其实f[i - 1][j]可以替代up[i - 1][j], f[i][j - 1]可以替代left[i][j - 1]，这样就减少了不少代码量
状态变量：f[i][j]表示以(i, j)为左下角的最大边长
方程：f[i][j] = Math.min(Math.min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1;
初始化：1）f[0][j],f[i][0]; 2) maxLen
答案：maxLen * maxLen
O(n^2) time, O(n^2) space
4. 滚动数组优化空间复杂度
f[i % 2][j] = Math.min(Math.min(f[i % 2][j - 1], f[(i - 1) % 2][j]), f[(i - 1) % 2][j - 1]) + 1;
特别注意，有两个地方容易出错，用滚动数组的时候，它的值不是自动为0的：
1）if (matrix[i][0] == '0') f[i % 2][0] = 0;
2）if (matrix[i][0] == '0') f[i % 2][j] = 0;

72. Edit Distance
状态变量： f[i][j] to be the minimum number of operations to convert word1[0..i-1] to word2[0..j-1].
方程： if (word1.charAt(i - 1) == word2.charAt(j - 1))
      f[i][j] = Math.min(Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1), f[i - 1][j - 1]);
    else
      f[i][j] = Math.min(Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1), f[i - 1][j - 1] + 1);
初始化：要初始化word1为空或者word2为空的情况 f[i][0], f[0][j], 所以f[i][j]对应着(i - 1, j - 1);
答案： f[n][m]

300. Longest Increasing Subsequence
方法一：暴力法是无法在O(n^2)时间内完成的。因为在内层循环中，即使遇到了比当前数大的数，可以选择用或者不用，例如：[10,9,2,5,3,4]，从2出发，可以经过5，也可以不经过5.所以这样算法的时间复杂度是O(2^n)级别

方法二：DP方法: O(n^2) time, O(n) space
状态变量：f[i]表示一共只有[0, i]个数的时候，以nums[i]为最后一位的最长subsequence。
                 往前遍历数组的时候，需要检查之前所有的数，看和谁能够接起来。
方程： for: 0 ~ i - 1, if (nums[j] < nums[i]) f[i] = Math.max(f[i], f[j] + 1);
初始化： for: 0 ~ n - 1, f[i] = 1;
答案： max(f[0] ... f[n - 1])

方法三：DP + BinarySearch
难想难解释，暂时放弃了

Day 38 - 2019/03/14

279. Perfect Squares
首先可以判断这道题有解，最坏情况是拆成n个1。然后就根据定义来做：
状态变量：f[n]是least number of perfect square numbers
方程： f[n] = min(f[n - 1*1] + 1, f[n - 2*2] + 1, f[n - 3*3] + 1, ..... f[n - lastSqRt*lastSqRt] + 1)
初始化：f[0] = 0; f[i] = i;
答案：f[n]

时间复杂度：O(n * sqrt(n)), 空间复杂度：O(n)

这道题还有数学解法： Lagrange's Four Square theorem
没看

368. Largest Divisible Subset
猛一看这道题是求具体方案的，而不是方案总数的，没法用DP啊。
既然需要判断整除，sort一下是必要的。
状态变量：f[i]表示 以第i个数结尾的最长的龙有多长
方程： if (nums[i] % nums[j] == 0) f[i] = max(f[i], f[j] + 1)
初始化： f[i] = 1
答案： max(f[0], f[1], ... , f[n - 1])

由于需要具体方案，所以用一个prev[]数组记录当前index的数接到之前哪个数上。
初始化prev[i] = i;

O(n^2) time, O(n) space

354. Russian Doll Envelopes
这道题跟368很像，因为要套上去，所以先排序。
state: f[i] represents the maximum number of envelopes using env[i]
function: if env[i] fits env[j], then f[i] = Math.max(f[i], f[j] + 1);
initialization: f[i] = 1;
answer: max(f[i])
O(n^2) time, O(n) space

Day 39 - 2019/03/15

今天感觉自己无可救药了，什么都干不进去

509. Fibonacci Number
动归滚动数组

Day 40 - 2019/03/16
674. Longest Continuous Increasing Subsequence

Lintcode: Longest Continuous Increasing Subsequence (从左到右和从右到左都要算)

Longest Increasing continuous Subsequence 2D
直接DFS，O(n^4) time
思维转换：f[i][j] 表示以(i, j)点为结束的最长subsequence。
这样就比较容易使用记忆化搜索对DFS进行pruning了。 O(n^2) time.

Coins in a Line
主要练习一下博弈类dp怎么画先后手的决策树

Coins in a Line II
State: dp[i] 表示还剩i个硬币，现在先手最多取到的硬币价值，当前index = n - i, 先手可以涉及的硬币是coin[n - i]和 coin[n - i + 1]
Function: 画出先后手的决策树，才可以搞清楚谁是决策者，进而搞清楚min / max
    dp[i] = max( (min(dp[i-2], dp[i-3])+coin[n - i])，(min(dp[i-3], dp[i-4])+coin[n - i]+coin[n - i + 1]) )
Intialization: 这里很容易搞错
• dp[0] = 0
• dp[1] = coin[n - 1]
• dp[2] = coin[n - 1] + coin[n - 2]
• dp[3] = coin[n - 2] + coin[n - 3]
Answer:  dp[n] > sum - dp[n]

方法二：考虑后手。对于这道题，这样比较绕，容易写错
State: dp[i] 表示还剩i个硬币，现在先手最多取到的硬币价值
Function:
• i 是当前所剩硬币数目
• sum[i] 是后i个硬币的价值总和
• dp[i] = max(sum[i]-dp[i-1], sum[i] - dp[i-2])
Intialize:
• dp[0] = 0
• dp[1] = coin[n - 1]
• dp[2] = coin[n - 1] + coin[n - 2]
Answer: dp[n] > sum - dp[n]

Day 41 - 2019/03/17

[leetcode]877.Stone Game / [lintcode]Coins in a Line III
方法一：先手当前回合取值和下一次取值的相互关系
state: f[j]表示现在还剩下第i到第j的硬币，先手最后取到最多多少硬币价值。
function: f[j] = max( coin + min(f[i + 2][j], f[i + 1][j - 1]) , coin[j] + min(f[j - 2], f[i + 1][j - 1]) )
initialization: 递归的出口
if (i > j) f[j] = 0;
if (i == j) f[j] = coin;
if (i == j - 1) f[j] = max(coin, coin[j]);
answer: f[0][n - 1] >= sum - f[0][n - 1]
时间复杂度O(n^2)，空间复杂度O(n^2)
方法二：用后手的取值结果，反推先手的当前取值结果。比较绕，容易出错。

403. Frog Jump
方法一：DFS方法 O(3^n) time, for every step there are at least 3 choice.

方法二：DP
为了求解是否能跳到最后一个，我比较关心两个变量，首先是，能不能跳到倒数第二个石头上，然后是，在倒数第二个石头上的步数选择是多少？

状态变量：map.get(i)表示跳到第i块石头上可以用的步数集合。
方程：从第i块石头的步数，可以推导出它跳到的那些石头的部分步数集合，update map。
初始化：map.get(0).add(0);
       map.get(1).add(1);
答案：!map.get(stones[n - 1]).isEmpty()
O(n) time, O(1) space

[LintCode] Stone Game
这道题的贪心法是错的，反例：[6,4,4,6]
一时没有思路，就用暴力搜索的方法，画出搜索树，这样DFS的时间复杂度是(n!)级别，对吧？
如何实现搜索中的记忆化呢？如何表示状态？因为涉及到合并，所以不好实施区间表示方法。
思维转换：把整个过程反过来（从下往上看），倒数第二步是怎么一路合并过来的 (每个搜索的子树，最初是从哪里切开来的)
状态变量：f[j]表示把从stone到stone[j]全部合并到一起，最小的总花费。
方程：sums[i, j]表示从stone到stone[j]的总价值
           f[j] = min(f[k] + f[k][j] + sum[i, j]) (i <= k && k < j) 在这些切法中，求最小值
初始化：if (i ==j) f[j] = 0;
答案：f[0][n - 1]
O(n^3) time, O(n^2) space

312. Burst Balloons
如果用多重循环的思维，从小往大想，枚举第一次在哪里打爆。这样状态不好表示。
思维转换：记忆化搜索，从大往小想。

状态变量：f[j]把从i到ｊ都打爆，获得的最大总价值。
方程：

• f[j] = max(f[k -  1] + f[k + 1][j] + midRst)
• midRst = balloons[i - 1] * balloons[k] * balloons[j + 1]
  
• 其中k >= i && k <= j, ｋ表示从i到ｊ区间内，最后一个被打爆的气球。
  

注意：

• 先打爆 i 到 k - 1 区间的气球，或者先打爆 k + 1到 j 区间的气球，对f[j]的计算没有影响
  
  

• midRst的计算是在[i, k - 1]和[k + 1, j]区间气球都被打爆之后计算的
• 注意，ｋ可以等于i和ｊ，并且初始化的case: i == j都包括了。
  

初始化：if (i == j) f[j] = balloons[i - 1] * balloons * balloons[i + 1]
答案：f[0][n - 1]
时间复杂度：O(n^3)，空间复杂度O(n^2)
[i][i][i][i][i][i][/i][/i][/i][/i][/i][/i]

Day 42 - 2019/03/18

87. Scramble String　

状态变量：f[i][j][len] 表示s1.substring(i, i + len)能否通过变换成为s2.substring(j, j + len)
状态转移方程：
partition这个长度为len的两个子串。设 k >= 1 && k < len, 左半部份长为k，右半部份长为len - k
if (f[i][j][k] == true && f[i + k][j + k][len - k] == true) f[i][j][len] = true;　// s2分开的两部分没有swap
if (f[i][j + len - k][k] == true && f[i + k][j][len - k] == true) f[i][j][len] = true;  // 把s2分开之后swap了
初始化：
if (s1.charAt(i) == s2.charAt(j)) f[i][j][1] = true;
答案：f[0][0][n]
时间复杂度：O(n^4). 空间复杂度：O(n^3)
这个的时间复杂度我有点说不清楚。

Day 43 - 2019/03/19

160. Intersection of Two Linked Lists

29. Divide Two Integers
考察对各种边界情况。
1）divident = 0； 2）divisor = 0； 3）sign； 4）overflow like case: Integer.MIN_VALUE / -1 and case: -2147483648 / 1

509. Fibonacci Number
可以用滚动数组优化

22. Generate Parentheses
回溯法

674. Longest Continuous Increasing Subsequence
同向双指针之sliding window

50. Pow(x, n)
暴力法O(n)time TLE
递归O(logn) time O(logn) space
方法三: x^n = (x * x) ^ (n / 2) 注意n的奇偶性
注意:只要是涉及Integer的题,都要考虑-2147483648, eg. x = 2.00000, n = -2147483648

144. Binary Tree Preorder Traversal
递归,非递归和分治

QuickSort

867. Transpose Matrix
方法一:直接复制 rst[j][i] = A[i][j]
方法二:在n == m的时候可以inplace

540. Single Element in a Sorted Array
要求是O(logn) time O(1) space 那就只能是二分法

Day 44 - 2019/03/20

581. Shortest Unsorted Continuous Subarray
方法一： compare with sorted array
让原数组和sorted数组比较，用到int[] sorted_nums = Arrays.copyOf(nums, nums.length);
O(nlogn) time, O(n) space
方法二：two pass 两个subarray
找到第一个subarray，where nums[l] > nums[l + 1] and nums[r] < nums[r - 1]
然后在这个subarray里找最大值maxInSubarray最小值minInSubarray
l指针向左回退，直到找到nums[l] < minInSubarray
r指针向右回退，直到找到nums[r] > maxInSubarray
return r - l - 1;
O(n) time, O(1) space
方法三：one pass
可以证明:
1) i is the largest index such that nums[i] != max[i];  max[i] is the maximum value of the subarray nums[0, i]
2) j is the smallest index such that nums[j] != min[j];  min[j] is the minimum value of the subarray nums[j, n - 1]
最后就是初始化的时候尽量直接cover整个数组已经完全sort的情况

54. Spiral Matrix

78. Subsets

1. Two Sum

236. Lowest Common Ancestor of a Binary Tree
下一次再用非递归吧