Leetcode笔记

最近开始刷leetcode，在这里记录一下做题的过程，不定期更新。

GitHub：https://github.com/frankgx97/leetcode

Two Sum(Easy)

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

解法1：暴力搜索

题目本身很简单，使用两个for循环遍历即可。需要注意的是同一元素不能使用两次，因此在遍历时，内层循环需要直接从外层循环+1处开始，而不是从头开始。

Solution：https://github.com/frankgx97/leetcode/blob/master/TwoSum.py

解法2：哈希表

新建一个哈希表（Python中使用字典即可），遍历数组，以数组中的值为哈希表的键，以数组中的键为哈希表的值，将数组中的内容存入哈希表。

在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中，如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

Solution：https://github.com/frankgx97/leetcode/blob/master/TwoSum(Hashmap).py

Add Two Numbers(Medium)

https://leetcode.com/problems/add-two-numbers/

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

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

解法

这个题目很有意思，输入为两个使用链表形式给出的倒序数字，要求将这两个数字相加，并将两者之和同样以倒序的链表形式输出。

我最初的解法是遍历链表，将两个数字读取为字符串，并转换成整数求和，然后再组装成链表，但是这样很没意思。

观察题目可以发现，我们可以使用加法竖式的方法来求解。以题目中给出的example为例，同时遍历两个链表：

1. 2+5 = 7，没有进位。
2. 4+6 = 10，取0，有进位。
3. 3+4 = 7，加上进位=8。
4. 得到结果7->0->8

需要注意在两个数组都遍历完成后，需要检查进位标记是否为真，如果为真则需要在开头补上一个1。

Solution：https://github.com/frankgx97/leetcode/blob/master/AddTwoNumbers.py

Valid Parentheses(Easy)

https://leetcode.com/problems/valid-parentheses

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

解法

很经典的一道题。题目给出一个包含各种括号的字符串，要求检验这些括号是否恰当地闭合。

我的方法是使用一个栈，遍历字符串。当遇到左括号时，将符号入栈；当遇到右括号时，检查栈顶元素是否为相应的左括号。如果是，将栈顶元素出栈；如果不是则直接返回false。

这个题目有几个坑需要注意：

1. 在检查栈顶元素之前先判断栈是否为空，否则遇到空栈时会报运行时错误。
2. 全部元素遍历完成后，检查栈是否为空，防止存在没有闭合的左括号。
   

Solution： https://github.com/frankgx97/leetcode/blob/master/ValidParentheses.py

Merge Two Sorted Lists(Easy)

https://leetcode.com/problems/merge-two-sorted-lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解法1：读取链表至数组之后排序

这个题目我本来想像Add Two Numbers一样同时遍历两个链表，然后将较小的那一个优先加入结果链表中。但是这种方法无法处理类似于1->5->6, 1->3->4的输入。所以我使用了比较弱智的方法，将两个链表分别遍历，将内容存入一个数组，排序后组装成链表输出。

需要注意的是OJ会给出几个输入为None的极端的用例，注意处理这种情况。

Solution: (Removed)

解法2：在其中一条链表的基础上排序

以第一条链表l1为基础。遍历链表l2 中的元素时，遍历链表l1 ，将l2 中当前的元素插入进l1 中的合适位置。由于输入的链表是已经排过序的，所以不需要每次插入后让指针回到链表头。

Solution: https://github.com/frankgx97/leetcode/blob/master/MergeTwoSortedLists.py

Container With Most Water(Medium)

https://leetcode.com/problems/container-with-most-water/

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

解法

最简单的方式是暴力搜索，如下代码实现的暴力搜索时间复杂度为O(n^2)。它仅能通过一些简单的用例，在一些超长（长达一屏半）的用例上则会TLE，所以需要想办法优化。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = 0
        max=0
        for left in range(0,len(height)):
            for right in range(left+1, len(height)):
                area = (right - left) * min(height[left], height[right])
                if area > max:
                    max = area
        return max

我考虑过从数组中值最大的位置开始，从大到小搜索，但是这种办法似乎没有办法降低复杂度，而且显然无法处理一些极端用例，比如一个递增或递减的序列。

我最后参考答案中的解法，设置分别位于数组左右两端的两个指针，计算两个指针所指向的位置的面积。然后将两个指针当中所对应的值较小的一个向数组中央移动。

Solution:https://github.com/frankgx97/leetcode/blob/master/ContainerWithMostWater.py

（未解决）3Sum(Medium)

https://leetcode.com/problems/3sum

Given an array nums of n integers, are there elements a, b, c in nums such that a+ b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法1：相反数(TLE)

题目要求三个数字之和为0，也就是说，要使两个数之和等于第三个数的相反数。这样就把问题转化为2Sum问题。

由于题目要求结果中不能包含重复的三元组。因此，每次将三元组添加到结果数组之前先将三元组排序，并判断是否已经有相同的三元组在结果中。

Solution: https://github.com/frankgx97/leetcode/blob/master/3Sum(tle).py

解法2: DFS (TLE)

尝试使用DFS，但是超时。

Solution: https://github.com/frankgx97/leetcode/blob/master/3Sum(dfs-tle).py

Letter Combination of a Phone Number(Medium)

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解法

首先我们构造一个字典，将数字和字母的映射存入，并初始化一个数组作为存放结果的队列。遍历输入的字符串。

在第一轮迭代时，将第一个数字所对应的三个（或四个）字母推入队列。其后的每一轮迭代，都从队列中取出第一个字符串，依次追加当前数字所对应的三个（或四个）字母后，推入队尾。迭代完成后即可得到结果。如果不想使用队列的话，可以在每次迭代中将结果数组复制为一个临时数组来代替。

Solution: https://github.com/frankgx97/leetcode/blob/master/LetterCombinationOfAPhoneNumber.py

PalindromeNumber(Easy)

https://leetcode.com/problems/palindrome-number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

解法1：字符串

很经典的回文数题目。最简单的方法是将字符串转换成数组，遍历数组的同时将这个数字的前半部分进栈，然后比较栈顶数字和当前数字是否相同。需要注意区分奇数位数或偶数位数的情况。

我正在思考不将数字转换成字符串的实现方法。

Solution: https://github.com/frankgx97/leetcode/blob/master/PalindromeNumber.py

Remove n-th Node From End of List(Medium)

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

解法1：两次遍历

我试图用一次遍历来做，但是失败了，所以先尝试两次遍历。

第一次先遍历整个链表，得到节点的数量；第二次遍历时，将length-n-1 处的节点的next指向current.next.next 即可。但是这种情况无法处理head节点即为被移除节点的情况，所以需要单独处理一下。

Solution: https://github.com/frankgx97/leetcode/blob/master/RemoveNthNodeFromEndofList.py

解法2：一次遍历

这种方法需要牺牲一点空间来换取时间。

首先初始化一个空列表lst，在遍历链表的同时将每个节点写入列表。

在 Python 语言中，无论什么数据类型，都是按照引用赋值。举个栗子，

Python 3.7.1 (default, Dec 14 2018, 13:28:58)
[Clang 4.0.1 (tags/RELEASE_401/final)] :: Anaconda, Inc. on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> class Node:
...     val = 0
...     next = None
...
>>> node = Node()
>>> lst = []
>>> lst.append(node)
>>> id(lst[0])
4350381864
>>> id(node)
4350381864

我们可以看出由于列表的元素和node指向了同一地址。也就是说，列表中存储的是链表节点的引用(Reference)，操作列表中元素即为操作链表节点。

完成后找到lst[len(lst)-n-1] ，将next指向lst[len(lst)-n-1].next.next 。

但是这样无法处理头节点即为被移除节点的情况，数组会越界，需要特殊处理：

在数组索引len(lst)-n-1 < 0的情况下，直接将head赋值为head.next 即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/RemoveNthNodeFromEndofList(OnePass).py

解法3：使用虚拟头节点（Dummy Head）的一次遍历

上面两个解法都存在一个问题：需要特殊处理头节点的情况。

在使用链表时，我们无法像操作其他节点那样去操作头节点。例如要移除头节点时，我们无法将头节点的前一个节点的next直接指向其下下个节点——因为头节点的前一个节点根本不存在，因此必须对这种情况特殊处理。

后来我了解到了虚拟头节点（Dummy Head）的方法——在真正的头节点（head）前面连接一个虚拟头节点（dummy），这样一来就使head能够像其他节点一样被操作。关于Dummy Head的更多讨论请参考：我们什么时候需要给 linked list 加上 dummy head | Yang Liu’s blog

回到题目上来。本解法是在解法2的基础上优化而成。我在开始遍历之前在head之前连接了一个dummy，然后执行其他的逻辑。当操作完成后，返回dummy.next即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/RemoveNthNodeFromEndofList(OnePasswithDummyHead).py

解法4: 使用两个指针的一次遍历

本解法是在解法3的基础上优化而成。

定义current及op两个指针，初始位置均为dummy。current先开始遍历链表，op暂时停留在原地。当current移动到第n+1个节点时，op开始移动，与current保持n+1的距离。

当current移动到链表末尾时，op将其当前停留的节点的next设置为op.next.next即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/RemoveNthNodeFromEndofList(OnePasswithTwoPointers).py

Search Insert Position(Easy)

https://leetcode.com/problems/search-insert-position/

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

解法：二分查找

这个题看起来是个简单的二分查找，但是真正的难点是找到当target不存在时插入进数组的位置。解决方法是当二分查找结束后返回左侧指针所指向的节点 。

以我的解法为例：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo = 0
        hi = len(nums) - 1
        while lo <= hi:
            mid = (lo + hi)//2
            if target == nums[mid]:
                return mid
            if target >= nums[mid]:
                lo = mid + 1
            else:
                hi = mid - 1
        return lo

我们使用nums=[1,3,5,6], target=2 为例，观察一下上述代码运行的过程。

还有一个nums=[1,3,5,6], target=7 的用例。

我们可以看出，当target在数组中不存在时，在循环结束前lo 和hi 一定会指向同一节点。这个解释：C++ O(logn) Binary Search that handles duplicate – LeetCode Discuss 说明了为什么当循环结束后lo 一定指向我们需要的位置。

(1) At this point, low > high. That is, low >= high+1
(2) From the invariant, we know that the index is between [low, high+1], so low <= high+1. Following from (1), now we know low == high+1.

(3) Following from (2), the index is between [low, high+1] = [low, low], which means that low is the desired index

Therefore, we return low as the answer. You can also return high+1 as the result, since low == high+1

Solution: https://github.com/frankgx97/leetcode/blob/master/SearchInsertPosition.py

Search In Rotated Sorted Array(Medium)

https://leetcode.com/problems/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

解法

严格来说这个思路是不符合题目要求的，因为题目要求O(logN)的复杂度。不过实际上OJ对时间的要求没有那么严格，甚至O(N)的解法也可以通过。

想要实现O(logN)的复杂度，就只能基于二分查找来优化。我采用的方法是先从左侧开始遍历列表，期间如果遇到目标元素则直接返回。待遍历过顶点（也就是数组被翻转的位置）后，对后半部分执行二分查找。但说实话，对性能的提升似乎十分有限。

Solution: https://github.com/frankgx97/leetcode/blob/master/SearchInRotatedSortedArray.py

Climbing Stairs(Easy)

https://leetcode.com/problems/climbing-stairs/

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解法1：DFS+回溯（TLE）

前几天终于搞明白了DFS和回溯，一看到这个题就兴冲冲地用DFS+回溯去做。事实证明…能做出来，答案也是对的，不过确实慢得有点过分了…

下图是输入为35时的执行时间，用了49秒。

Solution: https://github.com/frankgx97/leetcode/blob/master/ClimbingStairs(dfs).py

解法2：动态规划

关于动态规划请参考这篇文章：动态规划算法 – Frank’s Weblog

我尝试了两种实现方式，其中递归能够得出正确答案，但是输入35时用了大约4秒，导致OJ超时；使用循环则能够顺利AC。

Solutions：

递归：https://github.com/frankgx97/leetcode/blob/master/ClimbingStairs(recursive).py

循环：https://github.com/frankgx97/leetcode/blob/master/ClimbingStairs(iterative).py

Subsets(Medium)

https://leetcode.com/problems/subsets/

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法：DFS

这道题是一个典型的深度优先搜索，类似于一个简化版的Combination Sum。与Combination Sum不同的是这个题目不允许重复元素，所以递归时传入的index参数要+1。

我在用Python做这道题时可能Leetcode的OJ出了什么bug，在一个用例上会得到完全不可能出现的输出（Playground里则是正常的）。我又用C++按照完全相同的思路重新写了一遍，顺利通过。

更新：我明白为什么会出现下面的错误了。在执行不同的测试用例时，Solution类中的属性（成员变量）不会被更改或销毁，导致后一次的结果中包含了前一次的结果。请尽量避免使用Solution类的属性来存储数据，如果一定要这么做，记得在入口函数处重新初始化这个变量。

Solutions:

C++: https://github.com/frankgx97/leetcode/blob/master/Subsets.cpp

Python: https://github.com/frankgx97/leetcode/blob/master/Subsets.py

Permutations(Medium)

https://leetcode.com/problems/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]
]

解法：DFS

这道题的目标是生成一个数组的全排列，类似C++中的next_permutation 。

这道题也是个典型DFS，和Subsets和Combination Sum类似，使用通用解法即可通过。不同的是这个题目不允许重复的元素，并且要得到全部的排列，就不能像Combination Sum一样每次将candidates的索引+1。

我使用了一个列表，记录已经搜索过的索引，当循环到已经存在于列表中的索引时即跳过。避免出现重复的元素。

Solution: https://github.com/frankgx97/leetcode/blob/master/Permutations.py

Find the Duplicate Number(Medium)

https://leetcode.com/problems/find-the-duplicate-number/

Given an array nums containing n + 1 integers where each integer is between 1 and n(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once.

解法1:

这个题目看似很简单，完全不像是Medium的难度。实际上题目有不少附加条件，比如数组不能改动；只能使用constant的，O(1)的额外存储空间等等。

我采用的方法是使用一个数组作为哈希表，在遍历数组的同时判断当前元素是否在表中，如果有则返回。该方法时间复杂度为O(n)，不过由于临时数组是动态的，不符合第二条附加要求。

Solution：https://github.com/frankgx97/leetcode/blob/master/FindTheDuplicateNumber.py

Move Zeroes(Easy)

https://leetcode.com/problems/move-zeroes/

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

解法1(WA):

我最开始尝试使用下面的代码来解答：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)):
            if nums[i] == 0:
                nums = nums[:i] + nums[i+1:] + [0]

这份代码虽然能够print出正确答案，但是OJ读取到的输出则是和输入完全一样。

原因在于Python中的变量并非直接指向该变量内存中的地址，而是类似于一个标签。当该变量被重新赋值后，变量所指向的内存地址就改变了。我用上面的代码做了个实验，在每个循环的if中打印出nums变量的地址，得到如下的结果：

可以看出，虽然我一直在对nums变量进行操作，但实际上nums所指向的地址已经被改变了，无法被OJ正确读取。

解法2:

这个方法比较常规，虽然代码看起来不太优雅。

大致思路是把遍历数组，一旦遇到0则将后面的全部元素往前移动一位，然后将数组的最后一个元素设为0。需要注意的特殊情况有：

• 在遇到0并前移所有后方元素之后，在下一次循环时指针应该停留在原地，以处理两个或多个0相邻的情况。
• 每次遇到一个0后，将循环次数-1，以节省时间。

Solution:https://github.com/frankgx97/leetcode/blob/master/MoveZeroes.py

Hamming Distance(Easy)

https://leetcode.com/problems/hamming-distance/

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 2³¹.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

汉明距离 – 维基百科，自由的百科全书

解法1：字符串

这是个笨办法：将两个数转换为二进制，并在较小的一个前面补0。遍历两个字符串，计算相同位置上两者不同的数量。

Solution：https://github.com/frankgx97/leetcode/blob/master/HammingDistance.py

解法2：异或运算

根据汉明距离的定义，很明显可以使用异或运算来解决。首先计算x和y的异或c。然后计算c的二进制中含有1的数量即可。

Solution：https://github.com/frankgx97/leetcode/blob/master/HammingDistance(xor).py

Rotate Image(Medium)

https://leetcode.com/problems/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]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

解法：

[1,2,3],        [7,4,1],
[4,5,6],   ->   [8,5,2],
[7,8,9],        [9,6,3],

观察这两个矩阵，我们可以得出如下的坐标变换。

OLD Matrix   NEW Matrix
( 0 , 0 ) -> ( 0 , 2 )
( 0 , 1 ) -> ( 1 , 2 )
( 0 , 2 ) -> ( 2 , 2 )
( 1 , 0 ) -> ( 0 , 1 )
( 1 , 1 ) -> ( 1 , 1 )
( 1 , 2 ) -> ( 2 , 1 )
( 2 , 0 ) -> ( 0 , 0 )
( 2 , 1 ) -> ( 1 , 0 )
( 2 , 2 ) -> ( 2 , 0 )

得到公式如下：

new_matrix[j][n-i-1] = old_matrix[i][j]

我选择的方法需要牺牲一点空间，首先对输入的matrix深拷贝，赋值给另一个变量，然后按照上面的公式对matrix重新赋值即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/RotateImage.py

Single Number(Easy)

https://leetcode.com/problems/single-number/

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

解法1：哈希表

我使用了一个哈希表存储列表中数字出现的频率。其中键为数字，值为出现的次数。第一次遍历结束后，按照键遍历哈希表，找出其中值为1的键即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/SingleNumber.py

Min Stack(Easy)

https://leetcode.com/problems/min-stack/

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

解法：

最最基础的数据结构。

Solution: https://github.com/frankgx97/leetcode/blob/master/MinStack.py

Majority Element

https://leetcode.com/problems/majority-element/

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

解法1：哈希表

使用一个字典存储遍历到的数字及其出现次数，完成后遍历该字典的键，返回值大于n/2的键。

Solution： https://github.com/frankgx97/leetcode/blob/master/MajorityElement.py

解法2：摩尔投票算法

这是一个最基本的摩尔投票问题，找出一组数字序列中出现次数大于总数1/2的数字。摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

Solution：https://github.com/frankgx97/leetcode/blob/master/MajorElement(Boyer-Moore-Voting).py

Reverse Linked List(Easy)

https://leetcode.com/problems/reverse-linked-list

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

解法1:循环

遍历输入的链表，在经过每一个节点时，将当前节点的next暂存，并将其next指向前一个节点即可，以此类推。

Solution: https://github.com/frankgx97/leetcode/blob/master/ReverseLinkedList(iterative).py

Find All Numbers Disappeared in an Array(Easy)

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

解法1:遍历(TLE)

遍历1到len(nums)+1区间内的数字，如果被遍历到的数字在输入数组中不存在，则将其加入结果数组中。

Solution: https://github.com/frankgx97/leetcode/blob/master/FindAllNumbersDisappearedInAnArray(TLE).py

解法2:集合

这个方法利用了集合的特性。首先将输入数组转换为集合，其中重复的元素将被自动去除。然后初始化一个范围为1到len(num)的range，同样转换为集合。将两个集合相减，即可得到其中缺失的元素。

Solution: https://github.com/frankgx97/leetcode/blob/master/FindAllNumbersDisappearedInAnArray.py

Binary Tree Inorder Traversal(Easy)

https://leetcode.com/problems/binary-tree-inorder-traversal/

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

解法1:递归

最简单的中序遍历。

Solution: https://github.com/frankgx97/leetcode/blob/master/BinaryTreeInorderTraversal.py

Intersection of Two Linked Lists(Easy)

https://leetcode.com/problems/intersection-of-two-linked-lists/

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

解法：

这道题目我最开始试着先遍历第一条链表，并使用一个数组存储每一个节点的引用。然后在遍历第二条链表时依次对比是否相同。但是这个方法过于暴力，OJ会超时。

因为两个链表长度可能不同，可以先分别遍历两个链表，得到两个链表的长度。将长的一个截短至与短的链表一样长，然后从两个链表头同时开始遍历，返回两个指针相遇的位置即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/IntersectionofTwoLinkedLists.py

Path Sum III(Easy)

https://leetcode.com/problems/path-sum-iii/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

解法1:DFS

使用递归对这棵二叉树进行深度优先遍历，找出能够凑出目标数字的节点。由于节点之和并不一定从树的根部开始计算，所以需要从树的每一个节点都开始一次递归。

Solution: https://github.com/frankgx97/leetcode/blob/master/PathSumIII.py

https://github.com/frankgx97/leetcode/blob/master/PathSumIII(alt).py

Daily Temperature(Easy)

https://leetcode.com/problems/daily-temperatures/

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

解法1:Brute Force(TLE)

我尝试了递归和循环两种写法，都在一个超长用例上超时了。暴力解法的复杂度是O(n^2)，显然是不行的。

Solution: https://github.com/frankgx97/leetcode/blob/master/DailyTemperture(recursive,%20tle).py

解法2:单调栈

这个方法在遍历输入列表的同时维护一个单调递减的栈。如果当前元素小于栈顶元素，则将当前元素入栈；如果当前元素大于栈顶元素，则将栈中所有小于当前元素的元素出栈。每个栈内元素与比其大的元素的距离即为栈内元素与当前元素的索引之差。想要更详细地了解单调栈及其应用可以参考这篇文章：https://zhuanlan.zhihu.com/p/26465701。

Solution: https://github.com/frankgx97/leetcode/blob/master/DailyTemperture.py

Best Time to Buy and Sell Stock(Easy)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

解法1:Brute Force

Solution: https://github.com/frankgx97/leetcode/blob/master/BestTimetoBuyandSellStock(BruteForce).py

解法2: Kadane算法

Solution: https://github.com/frankgx97/leetcode/blob/master/BestTimetoBuyandSellStock(kadane).py

解法3:单调栈

Solution: https://github.com/frankgx97/leetcode/blob/master/BestTimetoBuyandSellStock(monostack).py

Maximum Subarray(Easy)

https://leetcode.com/problems/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.

解法1:单调栈

首先我们遍历整个数组，将array[i]赋值为array[0:i]中所有元素之和。也就是说，每个节点的值为从数组头到当前节点的所有数字之和。

这样，下标i和j之间的子序列之和就等于array[j] - array[i]。寻找最大子序列之和的问题就被转换为遍历数组中所有元素，并在其左侧找到一个最小的数，使两者之差最大的问题。

寻找最小的数当然可以使用min()来解决，然而这种方法过于暴力，无法满足题目的时间要求。为了实现更低的复杂度，我们使用一个递增的单调栈来实现。

单调递增栈的核心为在每次迭代中判断当前元素是否大于栈顶元素。

如果是，则将当前元素进栈。此时，当前元素是目前为止最大的元素，栈底元素是目前为止最小的元素。两者之差即是目前为止最大的子序列之和。

如果否，则将栈中所有大于当前元素的元素出栈，再将当前元素进栈。

以示例用例为例，单调栈的变化过程请参考：https://gist.github.com/frankgx97/63de78420e2aae98a82a27f53b8108cb

Solution: https://github.com/frankgx97/leetcode/blob/master/MaximumSubarray(monostack).py

解法2: Kadane算法

Kadane 算法是在动态规划的基础上的进一步优化。在动态规划算法 – Frank’s Weblog文中，我们提到动态规划的核心在于找出状态及状态之间的转移关系。

在Kadane算法中，每扫描到数组中的一个新元素可视为一种状态，状态之间的转移有两种情况：

• max = sum(array[0:i-1]) + array[I]
• max = array[i]

两者之中较大的一个为局部的最优解，在所有的局部最优解中最大的一个即为全局最优解。

Solution: https://github.com/frankgx97/leetcode/blob/master/MaximumSubarray(kadane).py

参考资料：循环列表中的最大子序列和问题 | 始终

WordBreak(Medium)

https://leetcode.com/problems/word-break/

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

解法1: 队列(WA)

我在遍历字符串的同时使用一个队列来暂存字符，每轮迭代中将字符串中的第一个字符入队，并判断队列中所有节点所组成的字符串是否存在于wordDict中。

但是这种方法的问题在于不能处理”aaaaaaa”, [“aaaa”,”aaa”]这样的用例。每当栈中凑够三个a时，就会匹配到dict中的aaa而出队。等遍历结束后就会剩下一个a在队列中，导致答案错误。

解法2: DFS

使用DFS搜索字符串中能够匹配的字符串。然而这段代码在答案为False的用例上及其缓慢，连示例用例都会超时。

Solution: https://github.com/frankgx97/leetcode/blob/master/WordBreak(dfs).py

解法3: DP

我们将每次迭代视为一个状态，使用一个大小为s+1的列表dp存储每个状态的结果，s与dp的对应关系如下：

#s = "leetcode", wordDict = ["leet", "code"]
s:          l   e   e   t   c   o   d   e
index:  0   1   2   3   4   5   6   7   8
dp:     1   0   0   0   1   0   0   0   1

其中，dp的初始状态全部为False; dp[0]为True; dp[i]的值需要以下几个条件来判断：

• dp[i]所对应的位置为某个可以匹配wordDict中的单词的结尾（例如上面下标4对应的t为leet单词的结尾）
• dp[i]所指向尾部的单词的头部的前一个位置为True，表示当前匹配到的单词能够衔接到前一个匹配的单词的结尾处。
• 由于判断时会遍历wordDict中的所有单词，其中必然会包含能够匹配的和不能够匹配的，因此只要有一个wordDict中的单词可以匹配，即可将dp[i]设为True。

Solution: https://github.com/frankgx97/leetcode/blob/master/WordBreak(dp).py

参考资料：Simple DP solution in Python with description – LeetCode Discuss

House Robber(Easy)

https://leetcode.com/problems/house-robber/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

解法：DP

每到一个房子面前，抢劫者有两个选项

1. 抢劫当前房子i
2. 不抢劫当前房子i

当劫匪选择选项1时，意味着他不能抢劫i-1房子，但是可以抢劫i-2房子；当选择选项2时，意味着他可以抢劫包括i-1在内的所有房子。

因此问题转化为比较下面两者哪个收益更大：

• 抢劫当前房子的收益加上抢劫i-2及之前房子的收益
• 抢劫i-1及之前房子的收益

得到状态转移方程如下：

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

如果使用递归，递归方法是自顶向下的，也就是从r(len(nums)-1)开始向下递归，直到r(0)处。循环方法与递归相反，循环从数组左侧开始，直到遍历完输入数组后结束。

Solutions:

循环：https://github.com/frankgx97/leetcode/blob/master/HouseRobber(iterative).py

递归：https://github.com/frankgx97/leetcode/blob/master/HouseRobber(recursive-tle).py

Number of Islands(Medium)

https://leetcode.com/problems/number-of-islands/

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

解法1: Flood Fill

顾名思义，Flood Fill就是扫描矩阵中的每一个节点，如果该节点是陆地，则计数后将当前节点淹没，并向周围四个方向递归执行。

Flood Fill可以同DFS或BFS来实现，这里使用的是DFS。

Solution: https://github.com/frankgx97/leetcode/blob/master/NumberofIslands.py

参考资料: Flood fill – Wikipedia

Maximal Square(Medium)

https://leetcode.com/problems/maximal-square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

解法1: 二维DP

首先初始化一个和matrix相同大小的矩阵dp，将matrix中为”1″处赋值为1, matrix中为”0″处赋值为0。用于存储DP过程的每一个状态。

在横纵坐标的1,len(matrix)范围内遍历matrix，当matrix[i][j]为”1″时，从dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1] 中取最小的一个，+1后赋值给dp[i][j] 。

由此得到状态转移方程

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Solution: https://github.com/frankgx97/leetcode/blob/master/MaximalSquare(dp).py

Top K Frequent Elements(Medium)

https://leetcode.com/problems/top-k-frequent-elements/

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size

解法1：桶排序

首先需要遍历整个数组，得到一个以数字为键，以该数字出现的次数为值的哈希表。

我们要得到出现频率最高的几个元素，就需要对哈希表的值进行排序。这里我们使用简化版的桶排序，桶的数量等于数组的大小。

依次遍历哈希表的键，将键i存储到第map[i]个桶中。也就是说，这个桶以数字出现的频率为索引，桶中存储频率所对应的数字。由于题目要的是出现频率最高的k个数字，所以从索引最大的桶处倒着遍历，即可得到出现频率最大的数字。

Solution: https://github.com/frankgx97/leetcode/blob/master/TopKFrequentElements.py

Queue Reconstruction by Height(Medium)

https://leetcode.com/problems/queue-reconstruction-by-height/

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解法1（WA）

按照题目的逻辑，我们可以得到如下代码：这段代码遍历数组中每一个元素，按照“其前方有多少个大于等于自身的元素”的原则将当前元素放进适当的位置中。但是这种方法会带来一个问题：在当前状态下，某元素的位置是符合要求的，然而当其他的元素移动之后，其位置就不符合题目要求了。

def reconstruct(people):
    for i in range(len(people)):
        p = people.pop(i)
        count = 0
        flag = 0
        for j in range(len(people)):
            if count == p[1]:
                people.insert(j, p)
                flag = 1
                break
            elif people[j][0] >= p[0]:
                count += 1
        if not flag:
            people.append(p)
    return people

解法2

我后来在讨论区看到了这个解法。首先对数组进行排序：以二元组的第一个数字为准降序排序，在此基础上，以二元组的第二个数字为准升序排序。

以题目的示例用例为例

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 

排序后得到下面的数组：

[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

然后使用insert方法，以二元组中的第二个数字为索引，将每个二元组插入到结果数组的相应位置即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/QueueReconstructionbyHeight.py

Search a 2D Matrix(Medium)

https://leetcode.com/problems/search-a-2d-matrix/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

解法: 二分查找

由于数组在横纵两个维度上都是已经排序好了，所以可以先纵向使用一次二分查找，定位到目标值所对应的行，再横向使用一次二分查找。

在正常情况下，我们使用如下的代码进行二分查找：

def bin_search(data_list, val):    
    low = 0                         # 最小数下标    
    high = len(data_list) - 1       # 最大数下标    
    while low <= high:        
        mid = (low + high) // 2     # 中间数下标        
        if data_list[mid] == val:   # 如果中间数下标等于val, 返回            
            return mid        
        elif data_list[mid] > val:  # 如果val在中间数左边, 移动high下标            
            high = mid - 1        
        else:                       # 如果val在中间数右边, 移动low下标            
            low = mid + 1    
    return # val不存在, 返回None

在横向使用二分查找时，如果查找目标不存在，直接返回False即可。但是在纵向查找时，我们需要找到查找目标所在的行。

也就是说，当纵向查找不到目标元素时，则返回目标预计所在位置左侧的元素。在没有找到目标元素的情况下right指针指向的是较小的元素。返回right所对应的数值即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/Searcha2DMatrix.py

Remove Element(Easy)

https://leetcode.com/problems/remove-element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

解法：

这个题目要求in-place，所以需要在输入列表的引用上进行操作。难点在于在循环中移除列表元素，因为Python的for循环本质上是一个类似于foreach的迭代器，如果在循环过程中移除了元素，则会造成数组访问越界。

按照下面链接所提供的方案，我们在迭代时使用数组切片来实现。

python – How to remove items from a list while iterating? – Stack Overflow

for i in nums[:]:
    do_something()

Solution: https://github.com/frankgx97/leetcode/blob/master/RemoveElement.py

Combinations(Medium)

https://leetcode.com/problems/combinations/

解法：DFS

题目要求得出从数字1-n中选出k个数字的全部组合。这道题目和Combination Sum有一些相似，都可以用DFS来解答。

Solution: https://github.com/frankgx97/leetcode/blob/master/Combinations.py

Counting Bits(Medium)

https://leetcode.com/problems/counting-bits/

解法：短除法转换二进制

这个题目只要把输入的数字直接转换成二进制，并计算其中1的数量即可。在Python中只需要使用bin()函数即可将十进制整数转换成二进制，但是这样题目就没什么意义了，因此我手写了一个转换二进制的函数。

十进制转二进制的算法请参考如何从十进制转换为二进制。

Solution: https://github.com/frankgx97/leetcode/blob/master/CountingBits.py

Sqrt(x)(Medium)

https://leetcode.com/problems/sqrtx

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

解法：二分查找

这道题目可以被视为从已排序的1-x的序列中找出平方为x的那一个数。依次遍历的速度会比较慢，因此使用二分查找。如果找到了，则返回当前的mid，如果没有，则返回right。

另外，通常情况下，搜索的范围是1-x。我们可以把搜索的初始范围设为1-x//2来节省一些时间。这样会造成1这个例外情况，所以单独对输入为1的用例返回1即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/Sqrt(x).py

SimplifyPath(Medium)

https://leetcode.com/problems/simplify-path/

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4:

Input: "/a/./b/../../c/"
Output: "/c"

Example 5:

Input: "/a/../../b/../c//.//"
Output: "/c"

Example 6:

Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

解法：

这个题目给出了一个可能包含有.，..，以及重复的斜杠的不标准UNIX路径，要求将输入的路径转换为标准的UNIX路径。

首先将输入字符串使用split()函数按照反斜杠分割，分割完成后所有的斜杠即被去除。初始化一个列表，同时遍历分割后的所有元素，如果为空或是. 则忽略，如果是.. 则移除数组中的最后一个元素，如果是其他内容则将元素添加到列表尾部。

遍历完成后，如果栈为空，则直接返回/ ，否则将列表中每个元素加上/ 并返回。

Solution: https://github.com/frankgx97/leetcode/blob/master/SimplifyPath.py

Unique Paths(Medium)

https://leetcode.com/problems/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?

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

Note: m and n will be at most 100.

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

解法：二维DP

这是一个典型的二维动态规划。动态规划的核心在于找出其状态及状态转移方程。

首先初始化一个m x n的矩阵，矩阵中的每一格用于存储从开始位置到当前位置的途径的数量。由于题目规定机器人只能向右或向下走，所以第一排和第一列上每一格的值均为1。

接着我们发现，每一格的值为其左边一格的值加上上边一格的值。因此得到状态转移方程：

dp[i][j] = dp[i-1][j] + dp [i][j-1]

这样我们可以继续填出整个矩阵，完成后返回右下角的值即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/UniquePaths.py

Partition List(Medium)

https://leetcode.com/problems/partition-list/

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

解法：

题目要求将链表分成小于及大于等于x的两个部分，并且不改变原本的顺序。这本身是一个普通的链表操作，但是当被修改的是链表头节点时，会带来一些麻烦。因此在开始之前先给原链表的头部连接一个虚拟头节点(dummy head)，然后再按照原本的思路进行操作。

Solution: https://github.com/frankgx97/leetcode/blob/master/PartitionList.py

Reverse Linked List II(Medium)

https://leetcode.com/problems/reverse-linked-list-ii/

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

解法：

这个题目是Reverse Linked List的加强版，要求只翻转给定区间内的部分。我们首先初始化4个指针 start, end, left, right，分别代表翻转的开始和结束的位置，以及翻转区间的之外的左侧和右侧的节点。当完成第一次遍历之后，我们可以将这些指针都指向对应的位置。

然后我们单独对需要翻转的区间进行操作，这样就把问题转化为了和Reverse Linked List相同的问题。在翻转的区间内，在每次循环中维护prev,current和temp三个指针。首先将current.next暂存至temp，然后将current.next指向prev，再将prev赋值为current，最后将current指向之前暂存的temp。重复这些步骤直到翻转区间结束。

完成后将left.next指向end，将start.next指向right即可重新串起整个链表。

这个题目有两种特殊情况，一种是链表的从头到尾都需要翻转的情况，这种情况只需要处理好边界，避免出现空指针即可。另一种是m和n相等，即不需要翻转，直接返回原本的链表即可。

Solution: https://github.com/frankgx97/leetcode/blob/master/ReverseLinkedListII.py

Restore IP Addresses(Medium)

https://leetcode.com/problems/restore-ip-addresses/

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

解法：DFS

这种类型的题目很显然是DFS，只不过这道题目的判断条件更复杂一些。另外需要特别注意处理多个0重叠的情况。

Jump Game(Medium)

https://leetcode.com/problems/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.

解法：DP

看到这个题目第一反应是DFS。但实际上，题目只要求得出是否有可行的路径，不需要给出这个路径具体是什么。所以可以使用DP解决。

首先初始化一个数组memo用于保存对应数组中是否有路径可以到达这个点。因此将memo[0]设为1，其余为0。然后遍历nums数组，从memo中对应位置开始向前nums个位置设为1，以此类推直到数组结尾。如果memo的最后一个位置为1，则返回True，反之返回False。

Solution: https://github.com/frankgx97/leetcode/blob/master/JumpGame.cpp

Merge K Sorted Lists(Hard)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

解法：

?这是我在Leetcode上做的第一道Hard！不过看起来也没有那么难，这个题目是之前的Merge 2 Sorted Lists的升级版，不过因为这次链表的数目不定，所以会稍微难一些。

我们首先分析一下输入的数据结构。输入的结构是一个列表，其中列表的每一个元素都是一个指针，指向每个链表的头节点。

按照惯例，我们首先初始化一个链表节点作为结果链表的dummy head。然后进入一个循环。

在循环中，我们需要找到各个链表当前节点中最小的一个，将上一个链表的next指针指向这个节点。然后将这个节点所在的链表的指针右移一个位置，这样已经被加入结果的节点就不会再被比较。如果这个节点已经是链表终点，则将该指针从列表中移除，并开始下一循环，直到lists为空。

Solution: https://github.com/frankgx97/leetcode/blob/master/MergekSortedLists.py

Insert Delete GetRandom O(1)(Medium)

https://leetcode.com/problems/insert-delete-getrandom-o1/

这道题目要求我们实现一个数据结构，其中包含插入，删除和随机返回任意一个值。其中每个操作的复杂度都需要为O(1)。

这个题目本身并不难，但是需要我们了解Python中各项数据结构操作的复杂度。

我使用一个dict结构作为主要的存储结构。对于insert操作，我们首先需要判定要插入的这个元素是否已经在dict的key里，如果已经存在则直接返回False，如果不存在，以该元素为键，插入dict中，值为任意。其中dict使用in操作符的复杂度为O(1)，dict的get和set复杂度均为O(1).

对于remove操作，思路和insert类似。大致为先判断要移除的元素是否存在，如果是，则把该元素pop掉，否则返回False。

对于getRandom，首先我们需要获取到dict中所有key的数量，使用len()即可，然后生成一个该范围内的随机数。

然后需要在dict中的所有key中返回随机数对应的那个key。由于dict的keys不能直接索引，所以需要先把dict的所有keys使用list()转换成list类型。这里存疑的一点是我不清楚list(dict)的复杂度，所以虽然这个解法能过OJ，但我不清楚这个解法是否符合题目要求。

Solution: https://github.com/frankgx97/leetcode/blob/master/InsertDeleteGetRandomO(1).py

Course Schedule(Medium)

Course Schedule – LeetCode

拓扑排序（Topological Sorting）是一种针对有向无环图（DAG）的排序算法。DAG 是一个由节点和有向边构成的图，其中每条边的起点必须在终点之前。

拓扑排序算法将 DAG 中的节点排成一条线性序列，使得每条边的起点都排在其终点的前面。如果 DAG 中存在环路，则不存在拓扑排序，因为无法确定环路中的节点先后关系。

根据题目中的要求，我们可以将 prerequisites 数组转化为有向图。如果需要先完成课程 bi 才能完成课程 ai，那么就在 bi 和 ai 之间连一条有向边。

接下来，我们需要对这个有向图进行拓扑排序。如果有环路，则无法完成所有课程；否则，可以完成所有课程。

具体实现可以使用 Kahn 算法。Kahn 算法使用了一个队列和一个数组来记录每个节点的入度。首先，将所有入度为 0 的节点放入队列中。然后，从队列中取出一个节点，将其所有相邻节点的入度减 1。如果相邻节点的入度为 0，则将其放入队列中。重复这个过程，直到队列为空。

如果这个过程结束后，所有节点的入度都变成了 0，则说明图中不存在环路，可以完成所有课程；否则，说明存在环路，无法完成所有课程。

Solution: leetcode/CourseSchedule.py at master · frankgx97/leetcode (github.com)

参考资料

https://wiki.python.org/moin/TimeComplexity

https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

…待续…