LeetCode Top 100（一）

他人的整理与总结：

https://leetcode.wang/

1. & 15. K-sum 问题

此类问题的解决方法：

第一种方法：暴力法，遍历 K 轮，求几个数字的和就遍历几轮。但是由于每遍历一轮都需要 $O(n)$ 的时间复杂度，因此总的时间复杂度会达到 $O(n^K)$ 。

第二种方法：双指针。这种方法需要先对输入的数组进行排序（时间复杂度 $O(n \log n)$ ），以最基本的 2sum 问题为例，用首尾两个指针，首指针从头开始向后遍历，尾指针从尾部开始向前遍历。如果它们指向的数字之和大于 target ，则尾指针向前移动；如果小于 target ，则首指针向后移动；直至最终和等于 target 。2sum 以上的问题都可以先固定 $K-2$ 个数字，将其转化为 2sum 问题。
【补充】：这种方法可能存在一个问题：如果原始的输入数据是无序的，而且要求输出的是数字的索引而非数字本身，那么这种方法反而会很麻烦，因为排序会改变数字的索引，此时输出的索引是排序后的索引而非原始的索引。所以在这种情形下这种方法就不太合适了（比如leetcode的第一题：2sum），此时可以改用哈希表的方法。

第三种方法：使用哈希表。以2sum问题的哈希表解法为例：

只需要遍历一遍数组，在遍历的过程中把target和当前元素的差作为key，当前元素的下标作为value记录到哈希表中。然后每遍历到一个元素，就在哈希表中查找它是否已经被添加进来了。如果是，则返回它对应的value以及当前元素的索引。
这种做法是以空间换时间，时间复杂度为 $O(n)$ ，空间复杂度也为 $O(n)$ 。

leetcode 2sum问题：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) < 2:
            return None
        temp = dict()
        for i in range(len(nums)):
            if nums[i] in temp:
                return [temp[nums[i]], i]
            else:
                temp[target-nums[i]] = i # 这样能保证输出索引是按递增顺序排序的
        return None

如果题目要求输出的是数字本身。那么排序+双指针的解法就可以用。排序的时间复杂度是 $O(n \log n)$ ，双指针遍历的时间复杂度是 $O(n)$ ，因此总的时间复杂度是 $O(n\log n)$ ，空间复杂度是 $O(1)$ 。代码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) < 2:
            return None
        res = []
        nums.sort()
        lo, hi = 0, len(nums)-1
        while lo < hi:
            s = nums[lo] + nums[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                return [nums[lo], nums[hi]]

对于3sum和4sum问题，因为元素可能会重复出现，此时2sum的哈希表解法并不太适用，因为对重复元素的处理不太方便。此时最好的方法是排序+双指针的解法，3sum的时间复杂度为 $O(n \log n) + O(n^2) = O(n^2)$ ，4sum的时间复杂度为 $O(n \log n) + O(n^3) = O(n^3)$ 。代码如下：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return None
        res = []
        nums.sort() # 双指针法必须要先排序
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]: # 组间去重
                continue
            lo, hi = i+1, len(nums)-1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0:
                    lo +=1 
                elif s > 0:
                    hi -= 1
                else:
                    res.append((nums[i], nums[lo], nums[hi]))
                    while lo < hi and nums[lo] == nums[lo+1]: # 组内去重
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi-1]: # 组内去重
                        hi -= 1
                    lo += 1 # lo要向后移一位
                    hi -= 1 # hi要向前移一位
        return res
    
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return None
        res = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]: # 组间去重
                continue
            for j in range(i+1, len(nums)):
                if j > i+1 and nums[j] == nums[j-1]: # 组间去重
                    continue
                lo, hi = j+1, len(nums)-1
                while lo < hi:
                    s = nums[i] + nums[j] + nums[lo] + nums[hi]
                    if s < target:
                        lo += 1
                    elif s > target:
                        hi -= 1
                    else:
                        res.append([nums[i], nums[j], nums[lo], nums[hi]])
                        while lo < hi and nums[lo] == nums[lo+1]: # 组内去重
                            lo += 1
                        while lo < hi and nums[hi] == nums[hi-1]: # 组内去重
                            hi -= 1
                        lo += 1
                        hi -= 1
        return res

这里要注意的是要进行两组去重：组间去重和组内去重。

2. Add Two Numbers

示例：

Input: (3 -> 4 -> 2) + (4 -> 6 -> 5)
Output: (8 -> 0 -> 7)
Explanation: 342 + 465 = 807.

这一题的坑在于要考虑进位，比如输入为5和5时，输出为0 -> 1。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return None
        root = res = ListNode(-1) # 先假设一个虚拟节点，最终返回这个虚拟节点的next即可
        carry = 0 # 先假设进位为0，便于后面的while判断
        while l1 or l2 or carry: # 把进位也加到判断条件中，就不用再额外对进位进行判断了
            val1 = val2 = 0
            if l1:
                val1 = l1.val
                l1 = l1.next
            if l2:
                val2 = l2.val
                l2 = l2.next
            carry, val = divmod(val1+val2+carry, 10) # carry=a//b, val=a%b
            res.next = ListNode(val)
            res = res.next
        return root.next

这道题有一个拓展，就是如果两个表示数字的链表不是从低位到高位，而是从高位到低位，要求输出也是从高位到低位，这时该如何处理呢？（参考：https://blog.csdn.net/u013378502/article/details/38467895）

比如：

Input: (3 -> 4 -> 2) + (4 -> 6 -> 5)
Output: (8 -> 0 -> 7)

解析：拓展题目看起来和原题差不多，但实际上会复杂更多。首先，因为两个链表的长度可能不一样，所以一开始要比较两个链表的长度，用0填充较短的链表。原题是求出新的节点后放在旧节点的后面，而拓展题目则需要添加节点到结果链表的前面，因此要用递归解决。递归需要传递两个参数：结果链表节点和进位。代码如下：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return None
        
        # 查询两个链表的长度，并将短的链表用0填充
        len1 = self.getLength(l1)
        len2 = self.getLength(l2)
        l1 = self.paddingZero(l1, len2 - len1) if len1 < len2 else l1
        l2 = self.paddingZero(l2, len1 - len2) if len1 > len2 else l2

        # 对两个链表进行求和
        node, carry = self.addTwoList(l1, l2)

        # 判断最终结果是否有进位
        if carry:
            carry_node = ListNode(1)
            carry_node.next = node
            return carry_node
        else:
            return node
    
    def getLength(self, l): # 获取链表的长度
        length = 0
        while l:
            length += 1
            l = l.next
        return length
    
    def paddingZero(self, l, len_zero): # 用0填充短链表
        res = ListNode(-1)
        res.next = l
        for i in range(len_zero):
            node = ListNode(0)
            node.next = res.next
            res.next = node
        return res.next

    def addTwoList(self, l1, l2): # 递归求每一个节点的和
        if not l1 and not l2:
            res = None
            carry = 0
            return res, carry
        next_node, next_carry = self.addTwoList(l1.next, l2.next)
        cur_carry, cur_val = divmod(l1.val+l2.val+next_carry, 10)
        cur_node = ListNode(cur_val)
        cur_node.next = next_node
        return cur_node, cur_carry
        

if __name__ == '__main__':
    sol = Solution()
    node11 = ListNode(3)
    node12 = ListNode(4)
    node13 = ListNode(2)
    node21 = ListNode(4)
    node22 = ListNode(6)
    node23 = ListNode(5)
    node11.next = node12
    node12.next = node13
    node21.next = node22
    node22.next = node23
    y = sol.addTwoNumbers(node11, node21)
    while y:
        if y.next:
            print(y.val, end=' -> ')
        else:
            print(y.val)
        y = y.next
    # 输出结果：8 -> 0 -> 7

3. Longest Substring Without Repeating Characters

这道题和《剑指offer》的第48题是一样的，属于动态规划问题。

本题要用到首尾两个指针，让它们分别指向不含重复字符的子字符串的头部和尾部。

只需遍历整个字符串一次，时间复杂度 $O(n)$ 。但这是以额外的空间复杂度为代价的。需要用一个字典保存尾指针已经扫过的字符，然后拿当前字符和字典中的字符进行比较。

如果当前字符在字典中已经出现过，那就表明重复了，此时要让头指针指向当前字符后面的一个字符。尾指针不断后移，直至遍历完整个字符串。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = lo = 0
        temp = {}
        for hi, cur in enumerate(s): # 让end直接出现在循环体中
            if cur in temp:
                lo = max(lo, temp[cur]+1)
            temp[cur] = hi # 哈希表中的字符若有重复的索引，则总是会将其更新为最大的索引值
            res = max(res, hi-lo+1)
        return res

4. Median of Two Sorted Arrays

中位数的定义：如果某个有序数组长度是奇数，那么中位数就是最中间的那个数；如果是偶数，那么中位数就是最中间两个数字的平均值。

拓展到两个有序数组的中位数：假设两个有序数组的长度分别为m和n，由于两个数组长度之和m+n的奇偶性不定，因此需要分情况来讨论。对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。

解这道题的关键并不是高超的算法，而是心中要有一副这样的图：
（参考：https://juejin.im/post/5c8c9ec16fb9a049af6e2a0d）

              left side       |  right side 
nums1:   A(0),A(1),...,A(i-1) | A(i),...,A(m-1)
nums2:   B(0),B(1),...,B(j-1) | B(j),...,B(n-1)

我们把两个数组看成一个整体，有一根竖线将其中的元素从中间分开，且左边的部分和右边部分的元素相同（总数为奇数情况下，左边比右边多 1 个元素），那么当 $m+n$ 为偶数时，中位数为
$\frac{\max[A(i-1), B(j-1)] + \min[A(i), B(j)]}{2}$
当 $m+n$ 为奇数时，中位数为
$\max[A(i-1), B(j-1)]$
我们都知道，左边的元素为 $i+j$ 个，而左右两边元素相同，则
$i+j = \frac{m+n+1}{2}$
我们可以用 $i$ 来表示 $j$ ，则
$j = \frac{m+n+1}{2}-i$
所以，该题就变成了，在数组 A 中寻找一个 $i$ ，使得 $A(i) \ge B(j-1)$ ，且 $A(i-1) \le B(j)$ 成立，这两个不等式的含义是，竖线右边最小的数一定不比左边最大的数小，满足该条件，我们就可以说找到了这个竖线。

我们在找 $i$ 的过程中，难免会碰到 $A(i) < B(j-1)$ 的时候，此时我们需要将 $i$ 向右移，使 $A(i)$ 增大，当 $i$ 右移， $i$ 增大的同时， $j$ 会减少，即 $B(j-1)$ 的值会变小，这样操作 $i$ 之后，会让我们更接近目标；同理，当 $B(j) < A(i-1)$ 时，我们需要将 $i$ 向左移。

通过上面的分析，我们最终可以使用二分查找法来寻找这个 $i$ 值，又由于二分查找的时间复杂度为 $O(\log n)$ ，这种方法可以满足题目的要求。

代码：（参考： https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2567/Python-O(log(min(mn))-solution ）

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        return self.findKth(nums1, nums2, length//2) if length%2==1 else \
              (self.findKth(nums1, nums2, length//2-1)+self.findKth(nums1, nums2, length//2))/2.0
    
    def findKth(self, A, B, k):
        if len(A) > len(B):
            A, B = B, A
        if not A:
            return B[k]
        if k == len(A) + len(B) - 1:
            return max(A[-1], B[-1])
        i = len(A) // 2
        j = k - i
        if A[i] > B[j]:
            return self.findKth(A[:i], B[j:], i)
        else:
            return self.findKth(A[i:], B[:j], j)

这里要注意的是，在C++中切片操作如 A[i:] 的时间复杂度是 $O(1)$ ，但是在Python中这样做的时间复杂度是 $O(n)$ 。因此上述代码的时间复杂度应为 $O(n \log (\min (m, n)))$ 。

5. Longest Palindromic Substring（最长回文子串）

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000

代码：（参考： https://leetcode.com/problems/longest-palindromic-substring/discuss/3337/Manacher-algorithm-in-Python-O(n) ）

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # Transform S into T.
        # For example, S = "abba", T = "^#a#b#b#a#$".
        # ^ and $ signs are sentinels appended to each end to avoid bounds checking
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range (1, n-1):
            P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
            # Attempt to expand palindrome centered at i
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1
    
            # If palindrome centered at i expand past R,
            # adjust center based on expanded palindrome.
            if i + P[i] > R:
                C, R = i, i + P[i]
    
        # Find the maximum element in P.
        maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
        return s[(centerIndex  - maxLen)//2: (centerIndex  + maxLen)//2]

思路分析：

上述代码是 Manacher Algorithm (马拉车算法) 的 Python 实现。关于这一算法的介绍可以参考： https://www.jianshu.com/p/392172762e55

Manacher Algorithm 的时间复杂度和空间复杂度均为 $O(n)$ 。

10. Regular Expression Matching（正则表达式匹配）

题目描述：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

代码：

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern: return not text
        match_res = bool(text) and pattern[0] in {text[0], '.'} # 这里bool(text)的作用是为了保证后面的text[0]不会发生索引越界的情况（因为text有可能为空）
        
        if len(pattern) > 1 and pattern[1] == '*':
            return self.isMatch(text, pattern[2:]) or 
                   (match_res and self.isMatch(text[1:], pattern))
        else:
            return match_res and self.isMatch(text[1:], pattern[1:])

思路分析：

本题和《剑指offer》的第19题是一样的。如果 pattern 中没有 * ，则问题可以通过如下的递归来解决：

def match(text, pattern):
    if not pattern: return not text # 先写递归基
    match_res = bool(text) and pattern[0] in {text[0], '.'} # text只要不空，转化为bool均返回True
    return match_res and match(text[1:], pattern[1:])

当 * 出现时，前面一定会跟一个其他字符，所以每一次对 pattern 切片后，* 一定会出现在 pattern[1] 的位置。如何应对 * 出现时的情况呢？有如下两种解决方案：

其一，因为 * 代表它前面的字符可以出现 0 次，所以跳过 * 和它前面的那个字符，从 * 后面的字符开始重新对当前的 text[0] 进行匹配，即 match(text, pattern[2:])；
其二，因为 * 代表它前面的字符可以出现任意次，所以 * 和它前面的那个字符可以重复使用。如果当前这一轮 text[0] 和 pattern[0] 匹配成功，那么在下一轮递归时，text 要匹配的是 text[1:] ，而 pattern 则可以重复使用，不使用的情况已经在上面那一条说过了，重复使用的情况就是 pattern 不进行切片，仍然将当前 pattern 的全部内容传入下一轮递归中，即 match(text[1:], pattern) 。

可以看到，如果 pattern 中有 * ，则每一轮递归都有两条路可以选，而且在进入到下一轮递归后仍然有两条路可以选。

整个代码的思路是：

首先，不管哪种情况，由于 * 不可能出现在 pattern[0] 的位置，因此每次都要先判断第 0 个字符是否能匹配，判断的方法是：
```
match_res = bool(text) and pattern[0] in {text[0], '.'}
```
当前 pattern 的长度大于 1 而且 pattern[1] == * 吗？
- 如果上述条件满足，则又分为两条路：
  - match(text, pattern[2:])
  - match(text[1:], pattern)
    
    以上这两条路是并行执行的，而且只要有一条路满足就可以，所以要用 or 连接。
- 如果上述条件不满足，就可以认为 pattern[0] 和 pattern[1] 里面均不包含 * （至少在当前 pattern 的前两个位置是没有 * 的，后面的位置有 * 的情况先不管。因为代码是递归进行的，所以后面的位置如果有 * ，早晚有一天这个 * 肯定会挪到 pattern[1] 的位置，到那时再对它进行处理也不迟。）。那么这种情况退化为最开始的那种没有 * 的情况，此时在进行下一轮递归时，text 和 pattern 都要往后挪一位，即 match(text[1:], pattern[1:]) 。

在代码中，or 之前的那个分支之所以没有加上对 match_res 的判断，是因为可能会出现下面这种情况：

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

11. Container With Most Water

题目描述：

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

代码：

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < 2:
            return None
        res = 0
        lo, hi = 0, len(height)-1
        while lo < hi:
            res = max(res, min(height[lo],height[hi])*(hi-lo))
            if height[lo] < height[hi]:
                k = lo
                while k < hi and height[k] <= height[lo]: # 这里必须是小于等于号，
                    k += 1
                lo = k
            else:
                k = hi
                while k > lo and height[k] <= height[hi]: # 否则会引起死循环
                    k -= 1
                hi = k
        return res

思路分析：

参见： https://blog.csdn.net/a83610312/article/details/8548519

时间复杂度： $O(n)$

17. Letter Combinations of a Phone Number

题目描述：
见： https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

代码：

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        mapping = {
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'}
        res = [c for c in mapping[digits[0]]]
        for d in digits[1:]:
            res = [prev + cur for prev in res for cur in mapping[d]]
        return res

从下到上的循环思路分析：

字符串中可能会有多个数字，假设我们一个一个地将其中的数字取出。当取第一个数字时，可能会有三个或四个组合。然后当我们取第二个数字时，做一个全排列即可。关键是从第三个数字开始，每一个新来的数字都可以用到前面的结果，这样就避免了大量的重复。

19. Remove Nth Node From End of List

题目描述：

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = fast = head
        for i in range(n):
            fast = fast.next
        if not fast: # 这个判断语句是为了处理一些边界情况
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

思路分析：

用双指针：slow 和 fast 。参见： https://www.cnblogs.com/yangyalong/p/9744829.html

20. Valid Parentheses（有效的括号）

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

代码：

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        mapping = {')':'(', '}':'{', ']':'['}
        for p in s:
            if p in mapping.values():
                stack.append(p)
            elif p in mapping.keys():
                if not stack or mapping[p] != stack.pop():
                    return False
            else:
                return False
        return not stack

思路分析：

括号匹配问题要用栈来帮助解决。在代码中首先要自定义一个 mapping ，用来表示括号的对应规则。

21. Merge Two Sorted Lists

题目描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = temp = ListNode(-1)
        while l1 and l2:
            if l1.val > l2.val:
                temp.next = l2
                l2 = l2.next
            else:
                temp.next = l1
                l1 = l1.next
            temp = temp.next
        temp.next = l1 or l2
        return head.next

22. Generate Parentheses

题目描述：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

代码：

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        self.backtrack(res, '', 0, 0, n)
        return res
    
    def backtrack(self, res=[], pth='', start=0, end=0, n=0):
        if end == n:
            res.append(pth)
            return
        if start < n:
            self.backtrack(res, pth+'(', start+1, end, n)
        if end < start:
            self.backtrack(res, pth+')', start, end+1, n)

23. Merge k Sorted Lists

题目描述：

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例：
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

优先级队列的概念：

参考：

优先级队列与普通队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。优先级队列底层是用堆实现的。

Python的PriorityQueue是用 heapq 实现的。（ https://blog.csdn.net/liu2012huan/article/details/53264162 ）

代码：

from Queue import PriorityQueue
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        q = PriorityQueue(maxsize=len(lists))
        cur = dummy = ListNode(None)
        for idx, node in enumerate(lists):
            if node:
                q.put((node.val, idx, node))
        while q.qsize() > 0:
            _, idx, cur.next = q.get() # get()会将节点弹出
            cur = cur.next
            if cur.next:
                q.put((cur.next.val, idx, cur.next))
        return dummy.next

这里有一些细节需要注意：

优先级队列需要明确将哪个量设置为优先级的评价标准，这里 node.val 就是用来作为这一标准的；
为什么还要引入 idx ？这是因为如果“第一评价标准”的优先级相同（这里即为 node.val ），代码就会比较“第二评价标准”。这里如果不设置“第二评价标准”，代码便会将 node 作为“第二评价标准”，而 node 是一个节点类，可能没有重写比较的方法，此时代码就会报错（这便是在 https://leetcode.com/problems/merge-k-sorted-lists/discuss/10511/10-line-python-solution-with-priority-queue 中 @ __fibo__ 提到的问题）。因此必须要找一个辅助变量作为“第二评价标准”，这里选取的是节点在列表中的索引。

复杂度分析：（强烈建议参考： https://blog.csdn.net/hellozhxy/article/details/81055397 ）

前已述及，优先级队列的底层是用堆实现的。因此往一个长度为 $n$ 的优先级队列中插入一个元素的时间复杂度为 $O(\log n)$ 。如果总共有 $m$ 个元素，则将这 $m$ 个元素插入这个长度为 $n$ 的优先级队列中的时间复杂度为 $O(m \log n)$ 。

现在代码中优先级队列的最大长度为 $k$ ，把最初的 $k$ 个头结点插入这个优先级队列的时间复杂度为 $O(k \log k)$ 。

关于时间复杂度的分析，@ gulshan98125 认为：假设 $n$ 是所有链表中最长的链表长度，现在总共有 $k$ 个链表，则总的时间复杂度为 $O(nk \log k)$ ；而 @spitza 认为，把 $n$ 当成是 $k$ 个链表中所有的节点个数显得更直观一些，这样一来时间复杂度将会变成 $O(n \log k)$ 。我个人的观点是，把 $n$ 当成是这 $k$ 个链表的平均长度，这样时间复杂度为 $O(nk \log k)$ 。

空间消耗在于维护一个长度为 $k$ 的优先级队列（其实是维护一个容量为 $k$ 的堆），因此空间复杂度为 $O(k)$ 。

31. Next Permutation（下一个排列）

题目描述：

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

代码：

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        is_possible = False
        
        # step 1: find the first nums[i] < nums[ii] from the tail
        for i in range(len(nums)-1, 0, -1):
            if nums[i-1] < nums[i]:
                i, ii = i-1, i
                is_possible = True
                break
        
        # step 2: find the first nums[j] > nums[i] from the tail and swap nums[i], nums[j]
        if is_possible:
            for j in range(len(nums)-1, -1, -1):
                if nums[j] > nums[i]:
                    nums[i], nums[j] = nums[j], nums[i]
                    # step 3: reverse all the elements starting from ii
                    nums[ii:] = nums[ii:][::-1]
                    break
        else:
            nums[:] = nums[::-1]

什么是下一个排列以及本题的思路分析：

核心思想是：

step 1：首先从最尾端开始往前寻找两个相邻元素，令第一元素为 i ，第二个元素为 ii ，且满足 nums[i] < nums[ii] ；
step 2：找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个大于 i 的元素，令为 j ，将 nums[i] 和 nums[j] 对调；
step 3：再将 nums[ii:] 反转（reverse）。

曾出错过的地方：

题目中明确说明不能返回任何东西，所以最开始写代码时，发现在VScode中能够通过，但是在LeetCode中总是报错，而且在LeetCode中的输出和在VScode中的输出不一致。后来发现是自己在代码中写了 return nums 语句，从而导致出错；
range 是 左闭右开 的，在上述代码中用到了两处 range ，第一处是 range(len(nums)-1, 0, -1) ，这里右边只能取到 1，是无法取到 0 的（第二处的 range(len(nums)-1, -1, -1) 只能取到 0 而无法取到 -1），这一点在写代码时必须非常明确，否则非常容易出错。
最后的 else 语句不能写成 nums = nums[::-1] 。

32. Longest Valid Parentheses

题目描述：

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

代码：

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        ans = 0
        for idx, p in enumerate(s):
            if p == '(':
                stack.append(idx)
            else:
                stack.pop()
                if not stack:
                    stack.append(idx)
                else:
                    ans = max(ans, idx-stack[-1])
        
        return ans

分析：

这里是将括号的索引 append 到栈中，而不是直接将括号加进去，这样做的好处是直接根据索引的差值就能计算出括号的长度，而不用通过每次加 2 的方式去累积有效长度，可以避免很多不必要的麻烦；
另外一个比较巧妙的地方是代码的第 7 行：
```
stack = [-1]
```
即在初始化栈的时候就往里面添加了一个 -1，这样做一方面可以解决索引值和真实长度的数值之间相差 1 的麻烦（因为索引从 0 开始），另一方面可以保证 stack.pop() 总是合法的，从而省去一些额外的判断条件。
时间复杂度： $O(n)$ 。

33. Search in Rotated Sorted Array

题目描述：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

代码：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lo, hi = 0, len(nums)-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            
            if nums[mid] >= nums[lo]:
                # 前半段有序
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                # 后半段有序
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        
        return -1

分析：

参考 https://leetcode.wang/leetCode-33-Search-in-Rotated-Sorted-Array.html 的第三种解法：题给数组从任意位置劈一刀后，至少有一半是有序的。然后，再根据哪一半有序进行分类讨论，进而缩短区间范围，实现二分查找。代码中有些需要注意的小细节：

第 9 行，循环的边界条件为什么要包含 lo == hi 这种情况？

答：这种做法是为了应对 len(nums) = 1 的特殊情况。在这种情况下，如果 target 包含在数组中，将会返回 0。
退出 while 循环的方式有两种：一种是找到了 target ，返回 mid ；另一种是没有找到，这种情况在上述代码中并没有用显式的 break ，而是强制索引越界，即 hi 要等于 mid - 1 而不是 mid ，lo 要等于 mid + 1 而不是 mid ，这样可以避免在区间中只剩两个数字时引起死循环。
前半段有序时，if 语句的判断条件是 nums[lo] <= target < nums[mid] （注意区间是左闭右开）；

后半段有序时，if 语句的判断条件是 nums[mid] < target <= nums[hi] （注意区间是左开右闭）。
时间复杂度： $O(\log n)$ 。

34. Find First and Last Position of Element in Sorted Array

题目描述：

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

代码：

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1, -1]
        return [self.search_left(nums, target), self.search_right(nums, target)]
    
    def search_left(self, nums, target):
        lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo if nums[lo] == target else -1
    
    def search_right(self, nums, target):
        lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = (lo + hi) // 2 + 1
            if nums[mid] > target:
                hi = mid - 1
            else:
                lo = mid
        return lo if nums[lo] == target else -1

分析：

本题实际上是“找左边”和“找右边”这两个问题的合并。和普通二分查找的区别是：普通的二分查找在找到 target 之后算法就停止了，而本题中为了能够找到“左边”和“右边”，在 nums[mid] == target 之后算法不能停止，而是要继续进行二分查找，直到最终 lo < hi 的循环条件不成立。

“找左边”和“找右边”是两种不同的情况，因此在找到 target 后它们边界条件的设置是不一样的：

在”找左边“中，要继续设置 hi = mid ；
在“找右边”中，要继续设置 lo = mid ；
直至最终 lo = hi ，此时无论是“找左边”还是“找右边”，均有 nums [lo] = nums[hi] = target 。
在“找右边”的情况中，在搜索区间中只剩下两个数字的时候可能会引起死循环，为了避免这一情况，我们需要让 mid 往后挪一位，即设置 mid = (lo + hi) // 2 + 1 ，详细的分析参见： https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14699/Clean-iterative-solution-with-two-binary-searches-(with-explanation)

39. Combination Sum

题目描述：

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

代码实现：（参考： https://leetcode.com/problems/combination-sum/discuss/16510/Python-dfs-solution. ）

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans, tmp = [], []
        candidates.sort()
        self.backtrack(candidates, target, tmp, ans, 0)
        return ans
    
    def backtrack(self, nums=[], remain=0, tmp=[], ans=[], start=0):
        if remain == 0:
            ans.append(tmp)
        else:
            for i in range(start, len(nums)):
                if nums[i] > remain: # 这里是为了避免不必要的循环
                    break
                self.backtrack(nums, remain-nums[i], tmp+[nums[i]], ans, i)

思路分析：
回溯法。先前向列举所有情况，得到一个解或走不通的时候就回溯。（ https://leetcode.wang/leetCode-39-Combination-Sum.html ）

其他和回溯法有关的例子： https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

41. First Missing Positive

题目描述：

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:

Your algorithm should run in O(n) time and uses constant extra space.

代码：

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        
        return len(nums) + 1

上述代码中有两个需要注意的地方：

第一个是第 8 行的判断语句中的 nums[i] > 0 ，此处不能写成 nums[i] ，即不能将数值当布尔值使用；（原因尚不明确）
第二个是第 9 行的交换语句：
```
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
```
不能写成：
```
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
```
因为如果先交换 nums[i] ，就会使 nums[i] 的值改变，这样当程序要交换 nums[nums[i] - 1] 时，这里的 nums[i] 已经不是原来的 nums[i] 了，而是一个新的值，这样程序就会得到意想不到的结果。例如，如果输入 nums = [3, 4, -1, 1] ，在上述错误的交换语句的作用下，在前 5 轮循环中，nums 的值变化情况如下：
```
[-1, 4, 3, 1] # 正确情况：[-1, 4, 3, 1]
[4, 1, 3, 1]  # 正确情况：[-1, 1, 3, 4]
[4, 4, 3, 1]  # 正确情况：[1, -1, 3, 4]
[4, 1, 3, 1]  # 正确情况：循环退出
[4, 4, 3, 1]
```
可以看到，在第 2 轮中，首先执行 nums[i] = nums[nums[i] - 1] ，即 nums[1] = nums[nums[1] - 1] = nums[4 - 1] = 1 ，使得 nums 由 [-1, 4, 3, 1] 变为 [-1, 1, 3, 1] ；然后再执行 nums[nums[i] - 1] = nums[i] ，这里要注意的是，等号左边的 nums[i] 已经变成了 1 ，而非原来的 4 ，这就导致左边变成了 nums[nums[i] - 1] = nums[1 - 1] = nums[0] 而非 nums[nums[i] - 1] = nums[4 - 1] = nums[3] ，也就是说，本来是要对第 3 个位置赋值，而现在变成了对第 0 个位置赋值。而等号右边的 nums[i] 则依旧是原来的 nums[i] ，即为 4。因此，程序的执行结果是将 4 赋给第 0 个位置。同时，由于第三个位置没有接受新的赋值，所以仍保持原来的数值不变，即仍为 1 。这就解释了在第 2 轮循环时，nums 为什么会变为 [4, 1, 3, 1] 而非 [-1, 1, 3, 4] 。

时间复杂度： $O(n)$ 。尽管代码中有一个两重循环，但是任意一个数字至多只需要被交换两次即可找到属于它的位置。

42. Trapping Rain Water

题目描述：

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

image

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

代码实现：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        lo, hi =  0, len(height)-1
        left = right = 0
        ans = 0
        while lo < hi:
            left = max(left, height[lo])
            right = max(right, height[hi])
            if left <= right:
                ans += left - height[lo]
                lo += 1
            else:
                ans += right - height[hi]
                hi -= 1
        
        return ans

分析：

这里采用的做法是从两边向中间，逐个格子地累加每个格子可以盛放的雨水。代码中用到了两个辅助变量 left 和 right ，分别用来表示左半部分的历史最大值（即最高的柱子）和右半部分的历史最大值，然后通过比较 left 和 right 的大小来判断到底应该是加左边还是加右边。

值得注意的一点是代码第 10 行循环语句的边界条件，这里无论是写成 while lo < hi 还是写成 while lo <= hi ，代码都可以通过。

时间复杂度： $O(n)$ 。

46. Permutations

题目描述：

Given a collection of distinct integers, return all possible permutations.

Example:
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = [[]]
        for num in nums:
            ans = [tmp[:i] + [num] + tmp[i:] for tmp in ans for i in range(len(tmp)+1)]
        
        return sorted(ans)

需要注意的一些细节：

第 7 行在初始化 ans 的时候，不能写成 ans = [] ，否则会导致最终输出的 ans 仍为空；
第 11 行，为了使输出更好看，可以在输出结果时对 ans 进行排序。

48. Rotate Image

题目描述：

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:
Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

代码实现：

1.如果可以用 Python 自带的 zip() 函数，则代码可以简化为只有下面的一行：

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = list(zip(*matrix[::-1]))

2.如果不能用 Python 自带的函数，则可以用下面的代码来实现：

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = matrix[::-1]
        for i in range(len(matrix)):
            for j in range(i+1, len(matrix[i])):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

思路分析：

逆时针旋转矩阵就是先进行转置，再上下翻转，即：
```
list(zip(*matrix))[::-1]
```
其中，list(zip(*matrix)) 完成转置操作，[::-1] 完成上下翻转操作。
顺时针旋转矩阵就是先上下翻转，再进行转置，即：
```
list(zip(*matrix[::-1]))
```
其中，matrix[::-1] 先完成上下翻转操作，list(zip(*)) 再完成转置操作。

此外， https://leetcode.com/problems/rotate-image/discuss/18872/A-common-method-to-rotate-the-image 也提供了一个对矩阵旋转问题的很好的解释。

49. Group Anagrams (相同字母异序词)

题目描述：

Given an array of strings, group anagrams together.

Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Note:

All inputs will be in lowercase.

The order of your output does not matter.

代码实现：

from collections import defaultdict
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        hashmap = defaultdict(list)
        for _str in strs:
            hashmap[tuple(sorted(_str))].append(_str)
        
        return hashmap.values()

分析：

思路类似于 https://leetcode.com/problems/group-anagrams/discuss/19176/Share-my-short-JAVA-solution ，都是用一个额外的哈希表来表征某一组的公共特征。然后当来一个新字符串的时候，就和这些公共特征进行比较，并对号入座。
为什么要用 defaultdict 而不用默认的 dict ？
这篇文章分析的很清楚。defaultdict 会为每个未知的 key 分配一个初始的 value ，从而即使直接从 defaultdict 中取键对应的值，也不会报错。而用默认的 dict 时，如果事先不为键分配一个初始值，则直接根据键取值会报错。
如果结果还要求对输出进行排序，则可将最后一行的 return 语句改为：
```
return map(sorted, hashmap.values())
```
第 10 行为什么要转化为 tuple ？
参考： https://blog.csdn.net/you_are_my_dream/article/details/61616646 。在 Python 中，字典的 key 不能是 list 或 dict ，因为它们是 unhashable (不可哈希的)。而 tuple 是可哈希的。

53. Maximum Subarray

题目描述：

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

代码：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        maxSoFar = maxEndingHere = nums[0]
        for i in range(1, len(nums)):
            maxEndingHere = max(maxEndingHere + nums[i], nums[i])
            maxSoFar = max(maxSoFar, maxEndingHere)
        
        return maxSoFar

思路分析：
参见： https://leetcode.com/problems/maximum-subarray/discuss/20211/Accepted-O(n)-solution-in-java

这是一个动态规划问题。如何划分子问题是需要考虑的首要因素（划分过程可以参考： https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts ），对于一个完整的 nums ，我们可以先掐掉它尾部的一个元素。然后，如果我们能知道剩余数组连续最大和是多少，那么我们就可以将这个剩余数组看做是一个黑箱整体，将问题转化为下面的两个元素的连续最大和问题：

nums = [a, b]

然后，

dp[i] = max(dp[i-1] + nums[i], nums[i])

是整个数组以 i 结尾的最大值，然后将它和历史最大值比较即可得出全局最大值：

maxSoFar = max(maxSoFar, dp[i])

但是如果用一个数组来存储每一个 dp[i] 的话，会造成空间资源的浪费。事实上我们只需要记录最后一个 dp 值就可以了，因此，不妨将 dp[i-1] 记为 maxEndingHere ，表示以剩余数组中最后一个元素结尾的最大值，这样就有了最开始的那个代码。

代码第 11 行中，因为题目要找的是连续子数组的最大和，所以 nums[i] 是必须要加的。

55. Jump Game

题目描述：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

代码：

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        maxEndingHere = nums[0]
        for i in range(1, len(nums)):
            if maxEndingHere < i: # 如果小于i，就表明到不了i这个位置了
                return False
            maxEndingHere = max(maxEndingHere, i + nums[i])
        
        return True

参考： https://leetcode.com/problems/jump-game/discuss/20917/Linear-and-simple-solution-in-C%2B%2B

56. Merge Intervals

题目描述：

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

思路分析：(参考： https://leetcode.com/problems/merge-intervals/discuss/21222/A-simple-Java-solution)

先根据区间左端点的大小进行排序；
然后遍历排序后的区间集，每遍历到一个，就和 ans 中最后一个区间的右端点进行比较，并更新该右端点的值，然后再取出下一个区间进行比较......

代码如下：

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        ans = []
        for interval in sorted(intervals): # 这里默认是按第一个元素进行排序
            if ans and interval[0] <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], interval[1])
            else:
                ans.append(interval)
        
        return ans

上述代码参考了 https://leetcode.com/problems/merge-intervals/discuss/21227/7-lines-easy-Python ，有以下两个好处：

可以避免对输入数组的修改；
不必再额外地将第一项加到 ans 中，而是将其整合到了循环中。

62. Unique Paths

题目描述：

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

img

Above is a 7 x 3 grid. How many possible unique paths are there?

Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
Constraints:

1 <= m, n <= 100

It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

思路分析：
本题需要用到动态规划，参见： https://leetcode.com/problems/unique-paths/discuss/22954/C%2B%2B-DP
上述链接中提供了三份代码，一步一步地减小空间复杂度，下面来探究一下为什么可以这样做。

第一份代码：时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$

Python 实现如下：

import numpy as np
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1] * n for i in range(m)]
        print(np.array(dp))
        print()
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                print('i = {}, j = {}, dp = \n{}'.format(i, j, np.array(dp)))
                print()
        
        return dp[m-1][n-1]

if __name__ == '__main__':
    y = Solution().uniquePaths(3, 3)

输出如下：

[[1 1 1]
 [1 1 1]
 [1 1 1]]

i = 1, j = 1, dp =
[[1 1 1]
 [1 2 1]
 [1 1 1]]

i = 1, j = 2, dp =
[[1 1 1]
 [1 2 3]
 [1 1 1]]

i = 2, j = 1, dp =
[[1 1 1]
 [1 2 3]
 [1 3 1]]

i = 2, j = 2, dp =
[[1 1 1]
 [1 2 3]
 [1 3 6]]

可以看到，当 i >= 1 and j >= 1 时，每一个数字都等于它上方及左方紧邻的数字之和。我们最终需要的仅仅只是 dp[m-1][n-1] ，因此没有必要把整个 dp 矩阵都存储下来。这便有了第二份代码的考虑：我们只需要保存两行即可——当前行（用 cur 表示）和上一行（用 pre 表示）。

第二份代码：时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$

Python 实现如下：
```
import numpy as np
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        cur, pre = [1] * n, [1] * n
        print('pre = {}\ncur = {}'.format(pre, cur))
        print()
        for i in range(1, m):
            for j in range(1, n):
                cur[j] = pre[j] + cur[j-1]
                print('pre = {}\ncur = {}'.format(pre, cur))
                print()
            pre, cur = cur, pre
        
        return pre[n-1]

if __name__ == '__main__':
    y = Solution().uniquePaths(3, 3)
```
输出如下：
```
pre = [1, 1, 1]
cur = [1, 1, 1]

pre = [1, 1, 1]
cur = [1, 2, 1]

pre = [1, 1, 1]
cur = [1, 2, 3]

pre = [1, 2, 3]
cur = [1, 3, 1]

pre = [1, 2, 3]
cur = [1, 3, 6]
```
- 第 17 行 pre, cur = cur, pre 的作用是什么？
  
  pre 和 cur 就相当于两个指针，分别指向上一行和当前行。在当前行计算完成之后，要将 pre 指向当前行，而 cur 之所以能够指向上一行，是因为整个 dp 矩阵的第一行和第一列恒为 1。将 cur 指向上一行，实际上只是用到了 pre 的第一个元素 1，这样在求新的 cur 时，它的第一个元素就已经确定了，从而为后面的 cur[j] = pre[j] + cur[j-1] 做准备。对于新的 cur 而言，从它的第二个元素开始，pre, cur = cur, pre 语句中等号右边的 pre 已经没有任何可利用的价值了。
- 至此，为什么还会有第三份代码？
  
  这是因为，仔细观察第 14 行和第 17 行的代码，可以发现，pre 和 cur 交换之后，cur + pre 本质上是 cur + previous(cur) ，即 cur 自己和自己相加。这样，便可以去掉 pre ，只保留 cur ，于是便有了第三份代码。

第三份代码：时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$

Python 实现：

import numpy as np
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        cur = [1] * n
        print('cur = {}'.format(cur))
        print()
        for i in range(1, m):
            for j in range(1, n):
                cur[j] += cur[j-1]
                print('cur = {}'.format(cur))
                print()
        
        return cur[n-1]

if __name__ == '__main__':
    y = Solution().uniquePaths(3, 3)

输出如下：

cur = [1, 1, 1]

cur = [1, 2, 1]

cur = [1, 2, 3]

cur = [1, 3, 3]

cur = [1, 3, 6]

最终代码：

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        
        return dp[-1]

时间复杂度： $O(m \times n)$ ，空间复杂度： $O(n)$

一种神奇的解法：(参考：https://leetcode.wang/leetCode-62-Unique-Paths.html)

对于一个 $m \times n$ 的网格，从 $(0, 0)$ 点走到 $(m-1, n-1)$ 点，只能向下或向右走。那么不管怎么走，总要向下走 $m-1$ 步，向右走 $n-1$ 步，于是总共要走的步数是 $m+n-2$ 步。

现在问题便转换为排列组合问题：在这 $m+n-2$ 步中，哪几步是向右走、哪几步是向下走呢？于是总的走法就可以用如下的组合公式来表示：
$C_{m+n-2}^{m-1} = C_{m+n-2}^{n-1} = \frac {(m+n-2)!}{(m-1)!(n-1)!} \tag 1$
注意到
$C_n^k = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots (n-k+1)}{(n-k)(n-k-1)\cdots 1} \tag 2$
因此，为了便于代码实现，可以进一步将上面的公式变形为：
$\frac{(m+n-2)!}{(m-1)!(n-1)!} = \frac{(m+n-2)(m+n-3)\cdots n}{(n-1)!}\\ =\frac{[(m-1)+(n-1)][(m-1)+(n-2)]\cdots [(m-1)+1]}{(n-1)(n-2)\cdots 1} \tag 3$
Python 实现：

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        ans = 1
        for i in range(1, n):
            ans = ans * (m - 1 + i) / i
        
        return int(ans)

在上述代码中，第 10 行如果写成下面的形式，则无法通过 LeetCode：

ans *= (m - 1 + i) / i

比如，如果输入 m = 3, n = 7 ，则提交后会报错：

这是因为 ans 每次乘的都是取整后的值，即

ans *= int((m - 1 + i) / i)

因此必须要写成 ans = ans * (m - 1 + i) / i 的形式。