刷题速记

1. 206反转链表：重点在于真正理解翻转的过程，才能利用双指针（迭代）或者递归法来写出翻转链表。重点在于先定义好需要新建联系的两个节点 pre = None和cur = Head, 然后利用temp来保存一下cur的下一个节点cur.next(也就是cur下次要移动到的地方，而pre的下个要移动的地方是cur，就不用新定义变量来保存了)

2. 215. 数组中的第K个最大元素：有时间复杂度限制，不能用先排序后返回下标为k-1的方法。可以采用快速排序法，也就是先随机定一个中枢值，pivot = random.choice(nums), 然后遍历一遍数组nums, 把大于nums的放到big里，小于nums的放到small里，等于nums的放到equal里。这样我们可以确定nums的相对位置（len(small), pivot的排序， len(big))。左边和右边里面排没排序我不管，只需要确定pivot的相对位置即可。如果k（第K大，也就是从右往左数第k个） < len(big)， 证明要找寻的数字在big数组里，递归进行快排quick_sort(big, K)。 如果在small数组里（判断条件为 k > len(eqaul) +len(big))， 就递归进行快排quick_sort(small, K - len(equal) - len(big)).难点在于如何理解递归参数的变化？因为在整个数组里的第K大（从右往左数第K个），对应到只递归small数组里就是从右往左数第 k - len(big) - len(small)个了。最后一种情况就是K位于equal数组中，用数字很难判断条件，统一放到else里就行了，直接返回pivot。

动态规划

53. 最大子数组和: dp照题目定义。转移方程为：如果当前数字本身就比dp[i-1] +nums[i]要大，就另起炉灶，自立门户，dp[i] = nums[i]。如果比不过的话就老老实实dp[i] = dp[i-1] +nums[i]吧

54. 最长回文子串：给你一个字符串 s，找到 s 中最长的 回文 子串。
    方法1：用双指针，定义从中心向外扩展，类似涟漪，直到两侧的字符不相等或者越界了，返回从这个字符开始扩展能得到的最长的回文串。由于扩展时可以从i为中心向两端，也可以从i和i+1开始向两端（对应回文子串的长度是奇数还是偶数），所以每个字符开始扩展的最大长度是max(expand(i,i), expand(i,i+1))

    方法2：用动态规划，如果s[i] == s[j], dp[i][j]是不是回文串取决于if s[i] == s[j] and (j-i <= 1 or dp[i+1][j-1]): dp[i][j] = True。意思是两端向内缩进的子字符串仍为回文子串，或者由于字符串长度小于等于1导致不能缩进的，都是回文串。这里由于要从两端朝中间缩进，所以遍历的时候，i依赖右侧的值，j依赖于左侧的值，遍历顺序为i从右侧开始，j从左侧开始遍历 for i in range(len(s)-1, -1, -1):
    for j in range(i, len(s)):

55. 最大正方形：在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。