leetcode 数据结构

对常用数据结构及 Leetcode 相关练习进行总结，包括栈与队列、哈希表、二叉树、数组、链表五个部分。

栈与队列

栈是一个只能从同一端插入或删除的线性表，是先进后出。插入删除端为栈顶，另一端为栈底。
对于栈 [1, 2, 3, 4], 1 是栈底，4 是栈顶。

队列是一个从一端插入，从另一端删除的线性表，是先进先出。插入端为队尾，删除端队头。
对于队列 [4, 3, 2, 1], 1 是队尾，4 是队头。

用栈实现括号匹配

Leetcode : 20. Valid Parentheses (Easy)

思路：栈最典型的应用即验证配对情况，对一个有效的括号对，左括号必定在右括号前面，因此可以将所有的左括号入栈，遇到匹配的右括号就将栈顶的括号消除，必定会有至少一对括号在 s 中是相邻的，因此一直消除栈顶，如果遇到不匹配的括号，直接返回 False，但栈为空时，即没有左括号，此时仍有右括号，则返回 False，最后所有字符都遍历完成后，栈为空则返回 True， 栈非空返回 Flase。

可以利用 dict 来存储括号对，从而提高代码效率。

时间复杂度为 o(n), 空间复杂度为 o(n)。

def is_valid(s):
    stack = []
    dict = {'(': ')', '[': ']', '{': '}'}
    for c in s:
        if c in dict:
            stack.append(c)
        elif len(stack) == 0 or dict[stack.pop()] != c:
            return False
    return not stack

Evaluate Reverse Polish Notation

Leetcode : 150. Evaluate Reverse Polish Notation (Medium)

逆波兰式

除法的时候需要注意：python中的 ‘//‘ 除法和 C语言 不太一样。在 python 中，(-1)//2=-1，而在 C语言中，(-1)/2=0。
这道题的 oj 是默认的 C语言 中的语法，所以需要在遇到 ‘/‘ 的时候注意一下。

def evalRPN(self, tokens):
    stack = []
    for char in tokens:
        if char != '+' and char != '-' and char != '*' and char != '/': # 如果是负数，用 isdigit() 无效
            stack.append(int(char))
        else:
            a = stack.pop()
            b = stack.pop()
            if char == '+':
                stack.append(a+b)
            if char == '-':
                stack.append(b-a)
            if char == '*':
                stack.append(a*b)
            if char == '/':
                if a*b < 0:
                    stack.append(-((-b)//a))
                else:
                    stack.append(b//a)
    return stack.pop()

判断是否为整数，若为负数时，可以用 if char.lstrip(‘-‘).isdigit()

最小值栈

Leetcode : 155. Min Stack (Easy)

问题描述：题目要求得到最小值的时间复杂度为 o(1)，因此需要以空间换时间，可以使用两个栈来实现，一个栈存储原始数据，另一个栈存储最小值。

class MinStack:
    def __init__(self):
        self.stack, self.minstack = [], []

    def push(self, x):
        self.stack.append(x)
        if not self.minstack or x <= self.minstack[-1]:  #1
            self.minstack.append(x)
        
    def pop(self):
        if self.minstack and self.minstack[-1] == self.top():
            self.minstack.pop()
        self.stack.pop()

    def top(self):
        return self.stack[-1]
       
    def getMin(self):
        return self.minstack[-1]

备注： 1. 必须要是 x <= self.minstack[-1]，重复元素也应该加到 minstack 中，否则在删除时会删除唯一的 min 值。

用栈实现队列

Leetcode : 232. Implement Queue using Stacks (Easy)

问题描述：用栈来实现队列，假设队列 q = [1, 2, 3, 4]，那么其在栈里面的顺序是 s = [4, 3, 2, 1]。push() 要在队列 q 的队尾增加一个元素， 则在栈 s 中应该在栈顶增加一个元素，变为 s = [x, 4, 3, 2, 1]，可以使用两个栈来实现，一个只进行入栈 push 操作，一个只进行出栈 pop 操作，因此只需要在 instack 中追加元素 x 即可实现；pop() 删除队头元素 1，而在栈 s 中 1 是先进后出，因此可以将其全部 push 到 outstack 中，再取出栈顶元素即可。

push() 时间复杂度 o(1)
pop(), peek() 时间复杂度 o(n)

class MyQueue:
    def __init__(self):
        self.instack, self.outstack = [],[]

    def push(self, x):
        self.instack.append(x)

    def pop(self):
        self.in2out()
        self.outstack.pop()
        
    def peek(self):
        self.in2out()
        return self.outstack[-1]
        
    def empty(self):
        return not self.instack and not self.outstack
    
    def in2out(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())

用队列实现栈

Leetcode : 225. Implement Stack using Queues (Easy)

class MyStack:
    def __init__(self):
        self.queue = [] 

    def push(self, x):
        self.queue.append(x)

    def pop(self):
        for i in range(len(self.queue) - 1):
            self.queue.append(self.queue.pop(0))
        return self.queue.pop(0)

    def top(self):
        for i in range(len(self.queue) - 1):
            self.queue.append(self.queue.pop(0))
        result = self.queue[0]
        self.queue.append(self.queue.pop(0)) # 恢复原样
        return result

    def empty(self):
        return not self.queue

哈希表

python 的内建数据类型字典是用哈希表来实现的，使用哈希表可以快速查找一个元素是否存在，但需要一定的存储空间。因此在优先考虑时间复杂度的情况下，可以使用哈希表来以空间换时间。

字典 dict 的遍历
遍历 key 值：for key in dict
遍历 value 值：for value in dict.values()
遍历字典项：for kv in dict.items()
遍历 key 和 value 值 : for key, value in dict.items()

dict.get(key) : 返回指定键的值，不存在则返回 None
dict.has_key(key) : 键在字典中返回 true，否则 false
dict.pop(key) ：删除该 key 和 value

两数之和 Two Sum

Leetcode : 1. Two Sum (Easy)

思路：使用字典来存储数组元素和索引的映射，将 nums[i] 和 i 存储到 dict 中，遍历一遍数组，若 target - nums[i] 在 dict 中，则直接返回两个数的下标。

时间复杂度为 o(n)，空间复杂度为 o(n)

def twoSum(nums, target):
    dic = {}
    if len(nums) <= 1:
        return false
    for i in range(len(nums)):
        tmp = target - nums[i]
        if tmp in dic:
            return [dic[tmp], i]
        else:
            dic[nums[i]] = i

无重复字符的最长子串 Longest Substring Without Repeating Characters

Leetcode : 3. Longest Substring Without Repeating Characters(Medium)

思路：使用哈希表来记录字符及其位置，当遇到重复字符时，应该从该字符的下一个字符开始重新计数，并且更新该字符在哈希表中的位置值。记录计数的起始位置为 start，当前字符位置为 i，则子串的长度为 i-start+1，不断更新最大长度得到最终结果。

注意：start <= dict[s[i]] 也就是要小于等于重复字符的上一个位置市才重新开始计数，否则就加上该字符。

时间复杂度为 o(n), 空间复杂度为 o(1)

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        maxlength = start = 0
        dict = {}
        for i in range(len(s)):
            if s[i] in dict and start <= dict[s[i]]:
                start = dict[s[i]] + 1
            else:
                maxlength = max(maxlength, i-start+1)
            dict[s[i]] = i
        return maxlength

Single Number

Leetocde : 136. 137. Single Number(Easy)

思路：用哈希表来记录数字及其出现的次数

def singleNumber(nums):
    cnt = {}
    for num in nums:
        if num not in cnt:
            cnt[num] = 1
        else:
            cnt[num] += 1
    for num, count in cnt.items():
        if count == 1:
            return num

Repeated DNA Sequences

Leetocde : 187. Repeated DNA Sequences (Medium)

def findRepeatedDnaSequences(self, s):
    dic = {}
    res = []
    for i in range(len(s)-9):
        key = s[i:i+10]
        if key not in dic:
            dic[key] = 1
        else:
            if key not in res:
                res.append(key)
    return res

同构字符串 Isomorphic Strings

Leetcode : 205. Isomorphic Strings (Easy)

问题描述：判断两个字符串是否是同构字符串，如果一个字符串 s 中的字符可以替换成别的字符，从而得到另一个字符串 t，则 s 和 t 是同构字符串。并且 s 中的所有相同字符都要被替换，保持原来的顺序，两个不同的字符不可以替换成相同的字符，字符也可以不替换。

思路：用字典来存储 s[i] 和 t[i]，将第一个字符串 s 的字符作为 key，第二个字符串 t 的字符作为 value，遍历一遍数组，有两种情况：

1. 当 s[i] 在 dic 中时，s[i] 的 value 不等于 t[i] 时，则直接返回 False，相等则继续遍历。
2. 当 s[i] 不在 dic 中时，若此时对应的 t[i] 却在 dic 的 values 中，则表明已经有一个 key 对应了这个 t[i]，现在 s[i] 对应的字符也是 t[i]，由于不能有两个不同的字符对应同一个字符，因此返回 False；否则将这一对 s[i] 作为 key，t[i] 作为 value 存入 dic 中。

def isIsomorphic(self, s, t):
    dic = {}
    for i in range(len(s)):
        if s[i] in dic:
            if t[i] != dic[s[i]]:
                return False 
        else:
            if t[i] in dic.values():
                return False
            dic[s[i]] = t[i]
    return True

最长和谐序列 Longest Harmonious Subsequence

Leetcode : 594. Longest Harmonious Subsequence (Easy)

问题描述：找出数组中的最长和谐序列，其最大数和最小数之间只相差 1。

思路：在最长和谐序列中，只可能出现两种数字，这两个数字之间相差 1，因此可以先对 nums 进行计数，得到 nums[i]：count[i] 的一个字典，遍历该字典，对每个 key 判断 key+1 是否在其中，并返回次数和的最大值。

def find_LHS(nums):
    dict = collections.Counter(nums)
    output = 0
    for key in dict:
        if key + 1 in dict:
           output = max(output, dict[key] + dict[key+1])
    return output

备注：python 标准库 collections 模块中的 Counter 类，用于跟踪值出现的次数，以字典的键对值形式进行存储，元素作为 key，其计数作为 value。

二叉树

二叉树（Binary Tree）是 n 个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

• 满二叉树的第 i 层有 2^i-1 个节点， 总共有 2ⁱ-1 个节点，总节点数一定是奇数。
• 若二叉树有 n 个节点，则该二叉树的高度为 h=log₂(n+1)。

递归

二叉树是一种递归结构，很多问题可以使用递归解决。

下面各题中对于二叉树的定义：

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

相同树

Leetcode : 100. Same Tree (Easy)

class Solution(object):
    def isSameTree(self, p, q):
        if (not p and q) or (not q and p):
            return False
        if not p and not q:
            return True
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

对称树

Leetcode : 101. Symmetric Tree (Easy)

思路： 由于输入只有 root，而判断对称树需要比较左右节点是否相等，因此可以构造一个辅助函数 symmetric 来比较左右节点的值。

1. 终止条件是已经到了叶子节点，即 left == None and right == None
2. 当左右节点的值相等时，继续递归比较左节点的左子树与右节点的右子树是否相等，以及左节点的右子树与右节点的左子树是否相等。

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True # 空树为对称树
        return self.symmetric(root.left, root.right)
         
    def symmetric(self, left, right):
        if not left and not right:
            return True
        if left and right and left.val == right.val:
            return self.symmetric(left.left, right.right) and self.symmetric(left.right, right.left)
        else:
            return False

二叉树的高度

Leetcode : 104. Maximum Depth of Binary Tree (Easy)

问题描述： 求二叉树的高度，利用递归计算，返回左子树和右子树中较大的深度，再加上 1 作为原二叉树的深度。

时间复杂度为 o(n)

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

平衡二叉树

Leetcode : 110. Balanced Binary Tree (Easy)

思路：平衡二叉树是二叉树的任意节点的两颗子树之间的高度差小于等于 1。对于平衡二叉树，其左子树和右子树也是平衡二叉树，因此可以递归判断。需要构造一个函数来求二叉树的高度，可以用之前的 maxDepth。

1. 终止条件：当左子树和右子树的最大高度相差 1 时，返回 False
2. 继续递归调用 isBalanced, 判断 root.left 和 root.right 是不是平衡二叉树。

class Solution:
    def isBalanced(self, root):
        if not root:
            return True
        if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
        
    def maxDepth(self, root):
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

二叉树的最小高度

Leetcode : 111. Minimum Depth of Binary Tree (Easy)

思路：简单思考有四种情况

1. 空树，返回 0
2. 只有右子树，返回右子树高度
3. 只有左子树，返回左子树高度
4. 左右子树都有，返回左右子树高度的较小值

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        if not root.left and root.right:
            return self.minDepth(root.right) + 1
        if not root.right and root.left:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

路径和

Leetcdoe : 112. Path Sum (Easy)

思路：利用递归实现，如果根节点为空，则直接返回 False，如果到最后都没有出现 sum == 0 的情况时，再进行一轮递归，则 root == None， 因此也返回 False。必须要注意的是最后的返回一定是递归的结果，当 sum == 0 并且该节点为叶子节点时才返回 True。

class Solution:
    def hasPathSum(self, root, sum):
        if not root:
            return False
        sum -= root.val
        if sum == 0 and not root.left and not root.right:
            return True
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

Path Sum II

Leetcdoe : 113. Path Sum II (Medium)

需要返回路径和等于 target 的所有路径集合。
思路： 与上一题类似，但需要保存符合要求的节点集合，需要注意的是递归的时候不要用 append 去追加元素到 path 中，会变为全局修改。在递归时，需要判断左右子树是否存在。

class Solution(object):
    def __init__(self):
        self.res = []
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root:
            return []
        return self.findPath([], sum, root)
        
    def findPath(self, path, sum, root):
        path = path + [root.val]
        sum = sum - root.val
        if sum == 0 and not root.left and not root.right:
            self.res.append(path)
        if root.left:
            self.findPath(path, sum, root.left)
        if root.right:
            self.findPath(path, sum, root.right)
        return self.res

Populating Next Right Pointers in Each Node

Leetcode : 116. Populating Next Right Pointers in Each Node(Medium)

思路：将二叉树的每个节点都加上一个 next 属性，指向其右边的节点。假设每个父节点都有两个子节点。
因此可以如果该节点有左孩子，则必定有右孩子，此时 左孩子.next 指向 右孩子；
如果将节点的 next 不是 None，name说明该节点必定不是最右边的节点，则 右孩子.next = 该节点.next.left；
否则，该节点是最右边的节点，此时 该节点.right.next = None。

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root and root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
            else:
                root.right.next = None
            self.connect(root.left)
            self.connect(root.right)

Populating Next Right Pointers in Each Node II

Leetcode : 117. Populating Next Right Pointers in Each Node II (Medium)

Sum Root to Leaf Numbers

Leetcode : 129. Sum Root to Leaf Numbers (Medium)

计算所有路径组成的数的和。
思路： 用 pre 来存储该节点 root 之前的路径组成的数，则加上该节点后的数为 pre = pre * 10 + root.val
然后返回左右子树相加递归的结果。 当遇到叶子节点时，该条路径遍历完，则返回 pre。

class Solution(object):
    def sum(self, root, pre):
        if not root:
            return 0
        pre = pre*10 + root.val
        if not root.left and not root.right:
            return pre
        return self.sum(root.left, pre) + self.sum(root.right, pre)
        
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.sum(root, 0)

DFS 解：

class Solution(object):
    def __init__(self):
        self.sum = 0
    def sumNumbers(self, root):
        if not root:
            return 0

        def dfs(root, num):
            if not root.left and not root.right:
                self.sum += num*10 + root.val
                return 
            if root.left:
                dfs(root.left, num*10+root.val)
            if root.right:
                dfs(root.right, num*10+root.val)
            
        dfs(root, 0)
        return self.sum

反转二叉树

Leetcode : 226. Invert Binary Tree (Easy)

思路：反转二叉树，对于一个节点 root 而言，只需要将其左孩子和右孩子交换即可实现反转，递归调用即可。

class Solution:
    def invertTree(self, root):
        if not root:
            return None
        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)        
        return root

归并二叉树

Leetcode : 617. Merge Two Binary Trees (Easy)

思路：

def mergeTrees(self, t1, t2):
    if not t1 and not t2:
        return None
    if not t1:
        return t2
    if not t2:
        return t1
    root = TreeNode(t1.val + t2.val)
    root.left = self.mergeTrees(t1.left, t2.left)
    root.right = self.mergeTrees(t1.right, t2.right)
        
    return root

遍历

    1
   / \
  2   3
 / \   \
4   5   6

1. 层次遍历，[1, 2, 3, 4, 5, 6]
2. 前序遍历（根左右），[1, 2, 4, 5, 3, 6]
3. 中序遍历（左根右），[4, 2, 5, 1, 3, 6]
4. 后序遍历（左右根），[4, 5, 2, 6, 3, 1]
   层次遍历使用 广度优先搜索 BFS 实现，
   前中后序遍历使用 深度优先搜索 DFS 实现。

前序遍历

Leetcode : 144. Binary Tree Preorder Traversal (Medium)

递归实现

class Solution(object):
    def __init__(self):
        self.result = []
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root:
            self.result.append(root.val)
            self.preorderTraversal(root.left)
            self.preorderTraversal(root.right)
        return self.result

非递归实现：
利用堆栈，用迭代来实现二叉树的前序遍历，一直将左子树进栈，root->left->right

1. 当根节点存在时，保存根节点的值，并将根节点入栈
2. 将根节点指向左子树
3. 当根节点不存在时（即没有左子树），栈顶元素出栈，并将根节点指向栈顶元素的右子树
4. 循环 123 步

总结：
非空：访问，进栈，向左走
空：出栈，向右走

class Solution(object):
    def preorderTraversal(self, root):
        result = []
        stack = []
        while root or stack:
            while root:
                result.append(root.val)
                stack.append(root)
                root = root.left
            if stack:
                node = stack.pop()
                root = node.right
        return result

中序遍历

Leetcode : 94. Binary Tree Inorder Traversal (Medium)

非递归实现：
中序遍历同样利用堆栈实现，堆栈定义与前序遍历相同。left->root->right

1. 当根节点存在时，将根节点入栈，并将根节点指向左子树
2. 当根节点不存在时（即没有左子树），栈顶元素出栈，保存栈顶元素的值（第一次即最左节点），并将根节点指向栈顶元素的右子树

class Solution(object):
    def inorderTraversal(self, root):
        result = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                node = stack.pop()
                result.append(node.val)
                root = node.right
        return result

后序遍历

Leetcode : 145. Binary Tree Postorder Traversal (Hard)

非递归实现：
后序遍历同样利用堆栈实现，left->right->root，可以通过 root->right->left 的结果逆序输出得到，即与前序遍历相似

class Solution(object):
    def postorderTraversal(self, root):
        result = []
        stack = []
        while root or stack:
            while root:
                result.append(root.val)
                stack.append(root)
                root = root.right
            if stack:
                node = stack.pop()
                root = node.left
        return result[::-1]

层次遍历

Leetcode : 102. Binary Tree Level Order Traversal (Medium)

思路：层次遍历利用队列的先进先出特性，将先进入队列的元素 pop 出来。
题中需要按照层次来打印出遍历结果，可以用一个临时列表存储二叉树一层的所有节点。即用 queue 来存储当前层元素， tmp 存储下一层元素。

class Solution(object):
    def levelOrder(self, root):
        result = []
        if not root:
            return result
        queue = [root]
        while queue:
            result.append([node.val for node in queue])
            tmp = []
            for node in queue:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            queue = tmp
        return result

Leetcode : 107. Binary Tree Level Order Traversal II (Easy)

层次遍历，倒序输出遍历结果; 直接翻转102的结果，return result[::-1]

Binary Tree Right Side View

Leetcode : 199. Binary Tree Right Side View (Medium)

复用层次遍历的代码即可，用 queue 存储当前层的节点， tmp 存储下一层的节点，输出每一层 queue 最后一个节点的值即可。

def rightSideView(self, root):
    if not root:
        return []
    res = []
    queue = [root]
    while queue:
        res.append(queue[-1].val)
        tmp = []
        for node in queue:
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        queue = tmp
    return res

得到左下角节点值

Leetcode : 513. Find Bottom Left Tree Value (Medium)

思路：利用层次遍历，记录下每一层的元素，返回最后一层的第一个元素即可。

class Solution(object):
    def findBottomLeftValue(self, root):
        queue = [root]
        result = root
        while queue:
            tmp = []
            result = queue[0]
            for node in queue:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            queue = tmp
        return result.val

二叉树每层节点的平均值

637. Average of Levels in Binary Tree (Easy)

class Solution(object):
    def averageOfLevels(self, root):
        result = []
        queue = [root]
        while queue:
            tmp = []
            sum = 0.0
            for node in queue:
                sum += node.val
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            result.append(sum/len(queue))
            queue = tmp
        return result

Zigzag遍历

Leetcode : 103. Binary Tree Zigzag Level Order Traversal (Medium)

思路： 之字形遍历二叉树，奇数行从左往右，偶数行从右往左，…
可以修改层次遍历的代码，通过判断 res 的长度，来判断当前行是奇数行还是偶数行，若是偶数行，则将结果翻转即可。

def zigzagLevelOrder(self, root):
    res = []
    if not root:
        return res
    queue = [root]
    while queue:
        nodes = [node.val for node in queue]
        if len(res) % 2 == 0:
            res.append(nodes)
        else:
            res.append(nodes[::-1])
        tmp = []
        for node in queue:
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        queue = tmp
    return res

通过前序和中序遍历构造二叉树

Leetcode : 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

思路： 前序遍历的第一个元素必定是 root，在中序遍历中 root 左边的是左子树，右边是右子树，因此只要找到 root 在 inorder 中的位置，就分割成了左右子树，之后再根据左右子树的前序遍历和中序遍历进行递归构造二叉树即可。

def buildTree(self, preorder, inorder):
    if not preorder or not inorder:
        return None
    root = TreeNode(preorder[0])
    index = inorder.index(preorder[0])
    root.left = self.buildTree(preorder[1:index+1], inorder[:index])
    root.right = self.buildTree(preorder[index+1:], inorder[index+1:])
    return root

通过中序和后序遍历构造二叉树

Leetcode : 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)

与上一题类似，需要注意的是 array 切片的边界问题。

def buildTree(self, inorder, postorder):
    if not inorder or not postorder:
        return None
    root = TreeNode(postorder[-1])
    index = inorder.index(root.val)
    root.left = self.buildTree(inorder[:index], postorder[:index])
    root.right = self.buildTree(inorder[index+1:], postorder[index:-1])
    return root

二叉查找树

二叉查找树（BST），又称二叉排序树、二叉搜索树。

1. 没有键值相等的节点
2. 若左子树不为空，则左子树上节点值均小于根节点的值
3. 若右子树不为空，则右子树上节点值均大于根节点的值
4. 任意节点的左、右子树也是二叉查找树

二叉查找树中序遍历一遍的结果是单调递增的，可以用于二分搜索。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为 o(logn)，但当二叉查找树退化为单链表时，查找效率最低，最低为 o(n)。

Unique Binary Search Trees

Leetcode : 96. Unique Binary Search Trees (Medium)

思路： 给定条件，求有多少种解，一般都是用动态规划，此时只要求解的数量。
序列从 1 到 n，当使用 1…n 中的每个数 i 作为根节点时，则 1…i-1 组成左子树，i+1…n 组成右子树，之后再递归构造左右子树，由于根节点唯一，则这样构造的二叉树都是唯一的。

使用两个变量来记录：
G(n)： 长度为 n 的序列组成的 unique BST 数量
F(i,n)： 以 i 为根节点的，长度为 n 的序列组成的 unique BST 数量
那么 G(n) = F(1,n) + F(2,n) + … + F(n,n), 有 G(0) = 1, G(1) = 1
F(i,n) = G(i-1) * G(n-i)，即左子树有 i-1 个节点能构造的 BST 数与右子树有 n-i 个节点能构造的 BST 数之积。

因此有 G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 【卡特兰数】

但是需要注意的是： 直接递归会超时。因此用动态规划解决。

def numTrees(self, n):
    dp = [0]*(n+1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n+1):
        for j in range(0, i):
            dp[i] += dp[j]*dp[i-j-1]
    return dp[n]

Unique Binary Search Trees II

Leetcode : 95. Unique Binary Search Trees II (Medium)

此题不理解

输出上一题的所有结果，需要枚举，考虑 DFS。

根据 BST 的性质，1…i-1 构成左子树，i+1…n 构成右子树。
当 begin > end 时，返回 [None]； 当 begin <= end 时，用 left 和 right 来递归构造左右子树。

def generateTrees(self, n):
    """
    :type n: int
    :rtype: List[TreeNode] # 返回一个根节点的list即可
    """
    if n == 0:
        return []
    return self.dfs(1, n)
        
def dfs(self, begin, end):
    if begin > end:
        return [None]
    res = []
    for i in range(begin, end+1):
        left = self.dfs(begin, i-1)
        right = self.dfs(i+1, end)
        for l in left:
            for r in right:
                root = TreeNode(i)
                root.left = l
                root.right = r
                res.append(root)
    return res

验证二叉查找树

Leetcode : 98. Validate Binary Search Tree (Medium)

思路：利用 BST 中序遍历是有序数组的特点来求解，只要当前节点的值小于或等于上一个节点的值，则直接返回 False，当遍历完成后返回 True

class Solution(object):
    def isValidBST(self, root):
        if not root or (not root.left and not root.right):
            return True
        stack = []
        pre_val = float('-inf')
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                node = stack.pop()
                if node.val <= pre_val:
                    return False
                pre_val = node.val
                root = node.right
        return True

有序数组构造二叉查找树

Leetcode : 108. Convert Sorted Array to Binary Search Tree (Easy)

思路：BST 二叉查找树即 left < root < right，因此利用有序数组构造 BST，且需要满足平衡二叉树的定义，注意到题中只要求给出一种解法，因此可以利用数组中间的数来作为 root，该数左边的用来构造左子树，右边的构造右子树，即将数组分成三个部分， [0, mid-1], mid, [mid+1, len(nums)-1]，再递归产生左右子树即可。

class Solution:
    def sortedArrayToBST(self, nums):
        if len(nums) == 0:
            return None
        return self.toBST(nums, 0, len(nums)-1)
        
    def toBST(self, nums, start, end):
        if start > end:
            return None
        mid = (start + end) // 2 
        root = TreeNode(nums[mid])
        root.left = self.toBST(nums, start, mid - 1)
        root.right = self.toBST(nums, mid + 1, end)
        return root

直接使用中间点来构造，一直二分，可以保证是平衡二叉树

def sortedArrayToBST(self, nums):
    if not nums:
        return None
    i = len(nums) // 2
    root = TreeNode(nums[i])
    root.left = self.sortedArrayToBST(nums[:i])
    root.right = self.sortedArrayToBST(nums[i+1:])
    return root

有序链表构造二叉查找树

Leetcode : 109. Convert Sorted List to Binary Search Tree (Medium)

直接将链表转为数组，再调用上一题的代码即可。

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        if not arr:
            return None
        return self.sortedArrayToBST(arr, 0, len(arr)-1)
        
    def sortedArrayToBST(self, arr, start, end):
        if start > end:
            return None
        mid = (start + end) // 2
        root = TreeNode(arr[mid])
        root.left = self.sortedArrayToBST(arr, start, mid-1)
        root.right = self.sortedArrayToBST(arr, mid+1, end)
        return root

二叉查找树中第k小的数

Leetcode : 230. Kth Smallest Element in a BST (Medium)

思路：利用中序遍历，当遍历到第 k 个数时返回当前节点的值。

class Solution(object):
    def kthSmallest(self, root, k):
        stack =[]
        count = 0
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                node = stack.pop()
                count += 1
                if count == k:
                    return node.val
                root = node.right

二叉查找树的最近公共祖先

Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree (Easy)

思路：由于二叉查找树的左子树节点的值小于根节点，右子树节点的值大于根节点，因此可以从根节点出发递归判断。

1. 若 root 的值大于 p 和 q 的值，则 LCA 在左子树
2. 若 root 的值小于 p 和 q 的值，则 LCA 在右子树
3. 若 root 的值介于 p 和 q 之间，则 root 就是 LCA

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

二叉树的最近公共祖先

Leetcode : 236. Lowest Common Ancestor of a Binary Tree (Medium)

思路：重点在于找到节点 p 和 q 在左子树还是右子树

1. 若当前结点为空或者与 p 和 q 一致，则返回该节点
2. 递归寻找 p 和 q 在左、右子树的位置
3. 若 p 和 q 分别在左、右子树上，则返回 root，否则就在左、右子树上

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p ,q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        if left:
            return left
        return right

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
除了最后一层之外，其余层的结点都是满的，且最后一层结点靠左对其。

Count Complete Tree Nodes

Leetcode : 222. Count Complete Tree Nodes (Medium)

求完全二叉树的节点数。
思路： 简单做法为直接遍历，返回 len(res)，但没意义，会超时。

对于完全二叉树：

• 若左子树高度等于右子树高度，则左子树为满二叉树，右子树可能是完全二叉树也可能是满二叉树
• 若左子树高度大于右子树高度，则右子树为满二叉树，左子树为完全二叉树或满二叉树

因此，可以通过求左右子树的高度来计算节点，高度只需要遍历最左边的节点即可。

• 构造 get_height(root) 来得到树高
• 若左右子树高度相等，则返回节点数为 2^left_height-1 + 1 + self.countNodes(root.right), 即左子树节点数+root节点+右子树节点数。
• 若左子树高度大于右子树高度，则返回节点数为 2^right_height-1 + 1 + self.countNodes(root.left)。

class Solution:
    def countNodes(self, root):
        if not root:
            return 0
        count = 0
        left_height = self.get_height(root.left)
        right_height = self.get_height(root.right)
        if left_height == right_height:
            count = 2 ** left_height + self.countNodes(root.right)
        else:
            count = 2 ** right_height + self.countNodes(root.left)
        return count
        
    def get_height(self, root):
        height = 0
        while root:
            height += 1
            root = root.left
        return height

其他

二叉树转链表 Flatten Binary Tree to Linked List

Leetcode : 114. Flatten Binary Tree to Linked List (Medium)

问题描述：将一个二叉树变为一个链表。

思路：变平后的链表实际上是二叉树前序遍历的结果，因此先对二叉树进行前序遍历，得到结果，再重新组织该二叉树，注意需要的是原地操作。

def flatten(self, root):
    """
    :type root: TreeNode
    :rtype: void Do not return anything, modify root in-place instead.
    """
    res = []    
    def preOrderTraversal(root):
        if not root:
            return None
        res.append(root)
        preOrderTraversal(root.left)
        preOrderTraversal(root.right)
    preOrderTraversal(root)
    
    for i in range(1, len(res)):
        root.left = None
        root.right = res[i]
        root = root.right

Binary Search Tree Iterator

Leetcode : 173. Binary Search Tree Iterator (Medium)

实现 BST 的 hasNext() 和 next() 方法。 next() 输出下一个最小的值。
简单做法： BST 中序遍历结果是递增的，直接先对 BST 进行中序遍历，再 pop(0) 删除第一个元素来输出。
可以用递归和非递归方法来进行中序遍历，该题中用递归的速度会更快一些。

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.inorderTraversal(root)
    
    def inorderTraversal(self, root):
        if root:
            self.inorderTraversal(root.left)
            self.stack.append(root.val)
            self.inorderTraversal(root.right)

    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.stack) > 0

    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop(0)

前缀树Trie

Trie，又称前缀树或字典树，是一种有序树状的数据结构，用于保存关联数组，其中的键通常是字符串。

基本性质：

1. 根节点不包含字符，根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符串不相同。

实现Trie

Leetcode : 208. Implement Trie (Prefix Tree) (Medium)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

数组

两个有序数组的中位数 Median of Two Sorted Arrays

Leetcode : 4. Median of Two Sorted Arrays (Hard)

def findMedianSortedArrays(self, nums1, nums2):
    nums = nums1 + nums2
    nums.sort()
    n = len(nums)
    if n % 2 == 0:
        return float('%.1f' %((nums[n//2-1] + nums[n//2])/2))
    else:
        return float('%.1f' %(nums[(n-1)//2]))

Remove Duplicates from Sorted Array

Leetcode : 26. Remove Duplicates from Sorted Array(Easy)

思路：数组有序，则重复元素必定相邻。使用两个下标，i 记录当前元素位置，j 记录新数组的元素位置，当 nums[i] != nums[i-1] 时，就将这个重复元素放到新数组中（注意这里是 in-place 操作）。
时间复杂度 o(n), 空间复杂度 o(1)

def removeDuplicates(nums):
    if not nums:
        return 0
    j = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i-1]:
            nums[j] = nums[i]
            j += 1
    return j

Remove Duplicates from Sorted Array II

Leetcode : 80. Remove Duplicates from Sorted Array II (Medium)

思路: 计算数字出现的次数，当次数为 1 或 2 时，就把其加到新数组中。 要注意的是题中需要 in-place 操作，因此直接覆盖 nums 即可。

def removeDuplicates(self, nums):
    if not nums:
        return 0
    count = 1
    j = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            count += 1
        else:
            count = 1
        if count == 1 or count == 2:
            nums[j] = nums[i]
            j += 1
    return j

Remove Element

Leetcode : 27. Remove Element(Easy)

思路：与上一题相同

def removeElement(nums, val):
    j = 0
    for i in range(len(nums)):
        if nums[i] != val:
            nums[j] = nums[i]
            j += 1
    return j

Next Permutation

Leetcode : 31. Next Permutation (Medium)

思路：

1. 从后往前扫描，寻找两个相邻的升序元素，nums[i] < nums[i+1]；
2. 从后往前扫描，找到第一个比 nums[i] 更大的元素， nums[j]；
3. 交换 nums[i] 和 nums[j]，并对 i 之后的元素进行升序排列。

def nextPermutation(self, nums):
    n = len(nums)
    if n <= 1:
        return
    flag = 0
    for i in range(n-2, -1, -1):
        if nums[i] < nums[i+1]:
            for j in range(n-1, i, -1):
                if nums[j] > nums[i]:
                    nums[i], nums[j] = nums[j], nums[i]
                    nums[i+1:] = sorted(nums[i+1:])
                    flag = 1
                    break
            break
    if not flag:
        nums.sort() # nums[:] = sorted(nums[:])

Merge Intervals

Leetcode : 56. Merge Intervals (Medium)

思路：首先对 intervals 进行排序，然后选 i=0 的数的 start 和 end 作为比较基准，当下一个数的 start 小于前一个数的 end 时，则表明两个 inteval 可以合并，并将新的 end 置为两者之间的较大者。 当不能合并时，就前一个数添加到 res 中。

def merge(self, intervals):
    """
    :type intervals: List[Interval]
    :rtype: List[Interval]
    """
    if len(intervals) <= 1:
        return intervals
    res = []
    intervals = sorted(intervals, key=lambda x: (x.start, x.end))
    left = intervals[0].start
    right = intervals[0].end
    for i in range(1, len(intervals)):
        if right >= intervals[i].start:
            right = max(right, intervals[i].end)
        else:
            interval = Interval(left, right)
            res.append(interval)
            left = intervals[i].start
            right = intervals[i].end
    interval = Interval(left, right)
    res.append(interval)
    return res

Insert Interval

Leetcode : 57. Insert Interval (Hard)

将 newInterval 插入到 intervals 中，再复用上一题的代码即可，但效率不高。

归并两个有序数组 Merge Sorted Array

Leetcode : 88. Merge Sorted Array (Easy)

def merge(self, nums1, m, nums2, n): 
    while m > 0 and n > 0:
        if nums1[m-1] >= nums2[n-1]:
            nums1[m+n-1] = nums1[m-1]
            m -= 1
        else:
            nums1[m+n-1] = nums2[n-1]
            n -= 1
    if n > 0:
        nums1[:n] = nums2[:n]

投机做法：

def merge(nums1, m, nums2, n):
    nums1[m:] = nums2[:n]
    nums1.sort()

Pascal’s Triangle

Leetcode : 118. Pascal’s Triangle (Easy)

def generate(self, numRows):
    res = []
    for i in range(numRows):
        if i <= 1:
            res.append([1]*(i+1))
        else:
            row = [1] + [0] * (i-1) + [1]
            for j in range(1, i):
                row[j] = res[i-1][j-1] + res[i-1][j]
            res.append(row)
    return res

Pascal’s Triangle II

Leetcode : 119. Pascal’s Triangle II (Easy)

def getRow(self, rowIndex):
    res = []
    for i in range(rowIndex+1):
        if i <= 1:
            res = [1] * (i+1)
        else:
            tmp = []
            for j in range(i-1):
                tmp.append(res[j] + res[j+1])
            res = [1] + tmp + [1]
    return res

旋转数组 Rotate Array

Leetcode : 189. Rotate Array(Easy)

思路: 要注意 k 可能会比 len(nums) 更大，因此先要取余数，除尽的部分相当于 nums 没改变
要求原地操作，切片是一个原地操作
时间复杂度 o(n)， 空间复杂度 o(n)

class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k]

要求时间复杂度 O(1)，对于 [1,2,3,4,5,6,7], k=3
[1,2,3,4] -> [4,3,2,1]; [5,6,7] -> [7,6,5]; [4,3,2,1,7,6,5] -> [5,6,7,1,2,3,4]

class Solution(object):
    def rotate(self, nums, k):
        k = k % len(nums)
        n = len(nums)
        self.reverse(nums, 0, n-k-1) # 必须要传入 nums，如果传入切片无法修改 nums
        self.reverse(nums, n-k, n-1)
        self.reverse(nums, 0, n-1)
        
    def reverse(self, nums, i, j):
        while i <= j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

Contains Duplicate

Leetcode : 217. Contains Duplicate (Easy)

若直接暴力解决，遍历数组，用 arr 存储遍历过的值，若后面出现过相同的数，则返回 True，该方法会超时。

思路一：将 nums 转为 set，这样 set 中都是不重复的数字，若 set 与 nums 长度不同，则说明有重复数字。

def containsDuplicate(self, nums):
    s = set(nums)
    return True if len(s) != len(nums) else False

思路二： 先将 nums 排序，再判断前后是否有相同数字即可。

Contains Duplicate II

Leetcode : 219. Contains Duplicate II (Easy)

思路： 利用字典来存储某个元素上一次出现的位置，当再次出现该元素时，计算两个重复元素之间的距离是否 <= k，是的话就 return True

def containsNearbyDuplicate(self, nums, k):
    dic = {}
    for i in range(len(nums)):
        if nums[i] in dic:
            j = dic[nums[i]]
            if i - j <= k:
                return True
        dic[nums[i]] = i
    return False

Contains Duplicate III

Leetcode : 220. Contains Duplicate III (Medium)

Majority Element

Leetcode : 169. Majority Element (Easy)

摩尔投票法：快速的计算出一个数组中出现次数过半的数，应用同加异减的思想。设置一个计数器，在遍历数组的时候，如果是这个数，则计数器加 1，否则减 1，当计数器为 0 时，则重置 major 和 cnt。

def majorityElement(self, nums):
    major = nums[0]
    cnt = 1
    for i in range(1, len(nums)):
        if nums[i] == major:
            cnt += 1
        elif nums[i] != major:
            cnt -= 1
        if cnt == 0:
            major = nums[i]
            cnt = 1        
    return major

Majority Element II

Leetcode : 229. Majority Element II (Medium)

要求时间复杂度为 O(n)， 空间复杂度为 O(1)

出现次数超过 1/3 数组长的数，最多只有两个。改进摩尔投票法，设置两个计数器，和两个候选数字：

1. 若是两个候选数字之一，则将对应的计数器加一；
2. 不是两个候选数字任意一个，则两个计数器都减一；
3. 若某个计数器为 0， 则重置计数器和候选数字；
4. 最后得到两个候选数字，还需要检查出现的次数是否都超过了 1/3。

def majorityElement(self, nums):
    # if len(nums) <= 1:
    #     return nums
    cnt1, cnt2, can1, can2 = 0, 0, None, None
    for num in nums:
        if num == can1:
            cnt1 += 1
        elif num == can2:
            cnt2 += 1
        elif cnt1 == 0:
            can1, cnt1 = num, 1
        elif cnt2 == 0:
            can2, cnt2 = num, 1
        else:
            cnt1 -= 1
            cnt2 -= 1
    res = [n for n in (can1, can2) if nums.count(n) > len(nums)//3]
    return res

Product of Array Except Self

Leetcode : 238. Product of Array Except Self (Medium)

要求时间复杂度为 O(n)，并且不能使用除法。

思路： 先从左往右计算一次，再从右往左计算一次。

def productExceptSelf(self, nums):
    n = len(nums)
    product = [1] * n
    tmp = 1
    for i in range(n):
        product[i] = tmp
        tmp *= nums[i]
    tmp = 1
    for i in range(n-1, -1, -1):
        product[i] *= tmp
        tmp *= nums[i]
    return product

Move Zeroes

Leetcode : 283. Move Zeroes (Medium)

问题描述：题目要求 in-place 操作，即原位操作，不允许移动和使用临时变量，也就是要原地覆盖掉之前的值。
对于本题：只要遇到该数不等于 0，则直接从第一个数开始覆盖掉，遍历完一遍后，前面的数都是不为 0 的，再把后面的数全部填充为 0 即可。

def moveZeroes(nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    i = 0
    for x in nums:
        if x != 0:
            nums[i] = x
            i += 1
    while i < len(nums):
        nums[i] = 0
        i += 1

矩阵

Valid Sudoku

Leetcode : 36. Valid Sudoku (Medium)

验证数独板是否有效，每一行每一列，每个九宫格内都只能是 1-9 的数字，且不能重复。

思路：直接将每一行、每一列和每个九宫格进行验证。

class Solution(object):
    def isValidSudoku(self, board):
        for i in range(9):
            row = board[i]
            col = [r[i] for r in board]
            if not self.valid(row) or not self.valid(col):
                return False
        for i in [0, 3, 6]:
            for j in [0, 3, 6]:
                nine = [board[row][col] for row in [i, i+1, i+2] for col in [j, j+1, j+2]]
                if not self.valid(nine):
                    return False
        return True
        
    def valid(self, nums):
        dic = {}
        for char in nums:
            if char.isdigit():
                if char in dic:
                    return False
                else:
                    dic[char] = 1
        return True

旋转图像 Rotate Image

Leetcode : 48. Rotate Image (Medium)

矩阵的翻转方式有： 左右翻转、上下翻转、左上到右下的对角线（转置）翻转。

将矩阵翻转 90 度，相当于先转置数组，再左右翻转数组。

def rotate(self, matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i+1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for i in range(n):
        for j in range(n//2):
            matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]

螺旋矩阵 Spiral Matrix

Leetcode : 54. Spiral Matrix(Medium)

思路：向右，向下，向左，向上，四个方向遍历输出，但要注意终止条件，输出数组的大小等于矩阵所有元素数量则终止。

def spiralOrder(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """
    res = []
    if not matrix:
        return matrix
    left = 0
    right = len(matrix[0]) - 1
    up = 0
    down = len(matrix) - 1
    size = (right+1) * (down+1)
    while left <= right and up <= down:
        for i in range(left, right+1):
            if len(res)< size:
                res.append(matrix[up][i])
        up += 1
        for i in range(up, down+1):
            if len(res)< size:
                res.append(matrix[i][right])
        right -= 1
        for i in range(right, left-1, -1):
            if len(res)< size:
                res.append(matrix[down][i])
        down -= 1
        for i in range(down, up-1, -1):
            if len(res)< size:
                res.append(matrix[i][left])
        left += 1
    return res

螺旋矩阵 Spiral Matrix II

Leetcode : 59. Spiral Matrix II(Medium)

备注： 需要注意矩阵初始化的格式，可以用 matrix = [[0] * n for i in range(0, n)] 或 matrix = [[0 for col in range(n)] for row in range(n)]

def generateMatrix(self, n):
    """
    :type n: int
    :rtype: List[List[int]]
    """
    matrix = [[0 for col in range(n)] for row in range(n)]
    left = 0
    right = n-1
    up = 0
    down = n-1
    num = 1
    while left <= right and up <= down:
        for i in range(left, right+1):
            if num <= n*n:
                matrix[up][i] = num
                num += 1
        up += 1
        for i in range(up, down+1):
            if num <= n*n:
                matrix[i][right] = num
                num += 1
        right -= 1
        for i in range(right, left-1, -1):
            if num <= n*n:
                matrix[down][i] = num
                num += 1
        down -= 1
        for i in range(down, up-1, -1):
            if num <= n*n:
                matrix[i][left] = num
                num += 1
        left += 1
    return matrix

Set Matrix Zeroes

Leetocde : 73. Set Matrix Zeroes (Medium)

暴力法：两次遍历，第一次遍历存储需要置零的行和列，第二次遍历置零。此法时间复杂度为 O(n * m) , 空间复杂度为 O(n+m)。

def setZeroes(self, matrix):
        rows = []
        cols = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rows.append(i)
                    cols.append(j)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in rows or j in cols:
                    matrix[i][j] = 0

想要空间复杂度为 O(1)， 可以将需要置零的行号和列号记录在 第一列 和 第一行，但这会使第一行和第一列的原始元素丢失，因此只需要设置一个额外的变量来保存第一行或第一列是否需要置零。在更新 matrix 的时候，从下往上遍历，则不会破坏第一行或第一列的原始数据。

def setZeroes(self, matrix):
    m = len(matrix)
    n = len(matrix[0])
    flag = 0
    
    for i in range(m):
        if matrix[i][0] == 0:
            flag = 1 # 说明第 0 列中是有 0 的
        for j in range(1,n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    for i in range(m-1, -1, -1):
        for j in range(n-1, 0, -1): # 第 0 列额外判断
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0         
        if flag:
            matrix[i][0] = 0

有序矩阵的第k小元素 Kth Smallest Element in a Sorted Matrix

Leetcode : 378. Kth Smallest Element in a Sorted Matrix ((Medium))

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

思路：对于该有序矩阵，左上角元素最小，右下角元素最大，因此矩阵中的数一定处于这两者之间，可以用这两个数来做一个 range，二分查找出 kth Smallest。
对于数 mid，找到 matrix 中有多少个数小于 mid，然后与 k 进行比较，从而更新二分查找的上下界。

def kthSmallest(self, matrix, k):
    if not matrix:
        return None
    low = matrix[0][0]
    high = matrix[-1][-1]
    while(low < high - 1):  #1
        mid = low + (high - low) // 2
        cnt = self.count_num(matrix, mid)
        if cnt < k:
            low = mid  #2
        else:
            high = mid
    return low if self.count_num(matrix, low) >= k else high
        
def count_num(self, matrix, mid):
    n = len(matrix)
    row = 0
    col = n - 1
    cnt = 0
    while(row < n and col >= 0):
        if matrix[row][col] <= mid:
            cnt = cnt + col + 1
            row += 1
        else:
            col -= 1
    return cnt

备注：

1. 注意边界条件是 low < high - 1，最后有两个备选项。若是 low <= high，那么可能会出现死循环，因为前一个数字 low 的计数永远小于 cnt，low 就不会更新。
2. 注意此处 low = mid 和 high = mid

链表

单链表的定义：

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

快慢指针法

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动 2，慢指针每次向前移动 1 次。

应用一：判断环形链表
让快慢指针从链表头开始遍历，快指针向前移动两个位置，慢指针向前移动一个位置;如果快指针到达 NULL，说明链表以 NULL 为结尾，不是循环链表。如果 快指针追上慢指针，则表示出现了循环。

应用二：在有序链表中寻找中位数
该方法在不借助计数器变量实现寻找中位数的功能。原理是：快指针的移动速度是慢指针移动速度的 2 倍，因此当快指针到达链表尾时，慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素，当快指针移动 x 次后到达表尾（1+2x），说明链表有奇数个结点，直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以根据“规则”返回上中位数或下中位数或（上中位数+下中位数）的一半。

Add Two Numbers

Leetcode : 2. Add Two Numbers(Medium)

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        num1 = num2 = 0
        tens = 1
        while l1 or l2:
            if l1:
                num1 = num1 + l1.val * tens
                l1 = l1.next
            if l2:
                num2 = num2 + l2.val * tens
                l2 = l2.next
            tens = tens * 10
      
        sum = num1 + num2
        
        p = head = ListNode(sum%10)
        sum = sum // 10
        while sum:
            node = ListNode(sum%10)
            p.next = node
            p = node
            sum = sum // 10            
        return head

Remove Nth Node From End of List

Leetcode : 19. Remove Nth Node From End of List (Medium)

思路： 由于可能会改变链表表头，因此添加一个辅助节点 dummy。然后用两个指针，fast 先走 n 步，然后 slow 再和 fast 同步走，当 fast 走到终点时，slow 位于要删除的节点的前面。

def removeNthFromEnd(self, head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = head
    slow = dummy # 此处需要注意，slow不能是head，因为head有可能要被删除。
    for _ in range(n):
        fast = fast.next
    while fast: 
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

归并两个有序链表 Merge Two Sorted Lists

Leetcode : 21. Merge Two Sorted Lists (Easy)

思路：链表与树类似，可以用递归方式来定义，这与归并两颗二叉树类似。

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        if(l1.val < l2.val):
            p = l1
            p.next = self.mergeTwoLists(l1.next, l2)
        else:
            p = l2
            p.next = self.mergeTwoLists(l1, l2.next)
        return p

Swap Nodes in Pairs

Leetcode : 24. Swap Nodes in Pairs (Medium)

思路： 由于每次要交换相邻节点，因此可以两个节点作为一个单位进行处理。 用 cur 记录当前节点，pre 记录上一个节点，然后进行交换操作。

def swapPairs(self, head):
    if not head or not head.next:
        return head
    dummy = pre = ListNode(0)
    dummy.next = head.next
    cur = head
    while cur and cur.next:
        tmp = cur.next
        cur.next = tmp.next
        tmp.next = cur
        pre.next = tmp
        pre = cur
        cur = cur.next
    return dummy.next

旋转链表 Rotate List

Leetcode : 61. Rotate List (Medium)

思路： 先计算链表的长度，用 k%size 得到 rotate 的节点的数量，即 rotate 后面 k%size 个节点到前面去。
因此，用双指针， fast 先走 k 步，之后 slow 和 fast 同步，这时候 fast 已经走到最后，则将其指向 head，而此时 slow.next 是翻转之后的 head，并且要将 slow.next 置为 None，否则一直无法停止。

def rotateRight(self, head, k):
    if not head or not head.next or k == 0:
        return head
    
    node = head
    size = 0
    while node:
        size += 1 # 链表的长度
        node = node.next
    k = k % size # 将后面 k 个数 rotate 到前面
    
    if k == 0:
        return head
    
    slow, fast = head, head
    for _ in range(k):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    fast.next = head
    head = slow.next 
    slow.next = None
    return head

删除有序链表的重复节点 Remove Duplicates from Sorted List

Leetcode : 83. Remove Duplicates from Sorted List (Easy)

思路：由于链表是有序链表，则重复元素必定相邻

class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next:
            return head
        
        cur = head.next
        pre = head
        while cur:
            if pre.val == cur.val:
                cur = cur.next
            else:
                pre.next = cur
                pre = cur
                cur = pre.next
        pre.next = None
        return head

删除有序链表的重复节点II

Leetcode : 82. Remove Duplicates from Sorted List II (Medium)

思路：一般情况下，需要修改链表表头时，会用到辅助指针，即此处在表头添加一个节点 dummy。
使用 is_repeated 来标记是否有重复的节点，当存在重复节点时，则将 pre 指针指向 cur.next，这样就过滤掉了所有的重复节点。

class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head

        pre = dummy
        cur = dummy.next
        while cur:
            is_repeated = False
            while cur.next and pre.next.val == cur.next.val:
                cur = cur.next
                is_repeated = True
            if is_repeated:
                pre.next = cur.next
            else:
                pre = pre.next
            cur = cur.next
        return dummy.next

Partition List

Leetcode : 86. Partition List (Medium)

思路： 用到两个额外的链表，遍历一个原始链表，将比 x 小的节点构建 p1，比 x 大的节点构建 p2，这样能保证节点的相对位置不发生改变。 然后将两个链表相连。

def partition(self, head, x):
    dummy1, dummy2 = ListNode(0), ListNode(0)
    p1, p2 = dummy1, dummy2
    while head:
        if head.val < x:
            p1.next = head
            p1 = p1.next
        else:
            p2.next = head
            p2 = p2.next
        head = head.next
    p2.next = None
    p1.next = dummy2.next
    return dummy1.next

反转链表 Reverse Linked List

Leetcode : 92. Reverse Linked List II (Medium)

思路：将链表分成三部分，前面一部分，需要反转的部分，以及最后面一部分。需要注意的是当 m = 1 的时候，没有第一部分，因此需要额外进行讨论。

class Solution(object):
    def reverseBetween(self, head, m, n):
        while not head or not head.next or m == n:
            return head
        
        cur = head
        end = head
        for _ in range(m-1):
            end = cur
            cur = cur.next

        pre = None
        rend = end if m == 1 else cur
        
        for _ in range(n-m+1):
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
            
        if m != 1:
            end.next = pre            
        rend.next = cur 
        return head if m != 1 else pre

反转链表

Leetcode : 206. Reverse Linked List (Easy)

思路：采用循环方式，遍历一遍链表，并将当前元素的指针指向前一个元素，要注意的是必须先使用中间变量保存当前元素的下一个元素，否则在下一次循环时 cur.next 会是前一个元素，会造成死循环。

class Solution(object):
    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

Copy List with Random Pointer

Leetcode : 138. Copy List with Random Pointer (Medium)

思路：

1. 在原链表的每个节点后面都插入一个新节点，新节点的 label 与原节点一样
2. 用 tmp 指向原节点，则新节点指向的 random 为 tmp.next.random = tmp.random.next
3. 将新链表从下图的链表中拆分出来

def copyRandomList(self, head):
    if not head:
        return None
    tmp = head
    while tmp:
        new_node = RandomListNode(tmp.label)
        new_node.next = tmp.next
        tmp.next = new_node
        tmp = tmp.next.next
    tmp = head
    while tmp:
        if tmp.random:
            tmp.next.random = tmp.random.next
        tmp = tmp.next.next
    
    new_head = head.next
    pold = head
    pnew = new_head
    while pnew.next:
        pold.next = pnew.next
        pnew.next = pnew.next.next
        pold = pold.next
        pnew = pnew.next
    pold.next = None
    pnew.next = None
    return new_head

环形链表 Linked List Cycle

Leetcode : 141. Linked List Cycle (Easy)

class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Linked List Cycle II

Leetcode : 142. Linked List Cycle II (Medium)

问题描述： 如果链表存在环路，那么返回环路的起始节点。

思路: 利用快慢指针法来判断是否存在环路，假设两个指针 slow 和 fast 的路径如下图，在 Z 点相遇。

此时，fast 走过的路径为：a+b+c+b； slow 走过的路径为：a+b。 由于 fast 速度比 slow 快两倍，因此有： 2*(a+b) = a+b+c+b，则 a=c。 因此，当两个指针相遇后，令 slow 回到 head，fast 不变，然后两个指针同速度开始走，一次走一步，则两个指针会在 Y 点 相遇，也就是环路的起始节点。

def detectCycle(self, head):
    if not head or not head.next:
        return None
    slow = fast = head
    flag = 0
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            flag = 1
            break # 必须要break，否则死循环
    if not flag: # 不是环形就返回None，提高效率。
        return None 
    
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

Reorder List

Leetcode : 143. Reorder List (Medium)

思路： 将链表拆分为两个链表；再将第二个链表 reverse；最后交叉归并两个链表。
用快慢指针法找到需要拆分的地方。

def reorderList(self, head):
    if not head or not head.next or not head.next.next:
        return 
    # 快慢指针法拆分链表
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    head1 = head
    head2 = slow.next
    slow.next = None
    # 反转链表
    pre = None
    cur = head2
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    head2 = pre
    # 将第二个链表插入到第一个链表中
    p1 = head1
    p2 = head2
    while p2:
        tmp1 = p1.next
        p1.next = p2
        tmp2 = p2.next
        p2.next = tmp1
        p1 = tmp1
        p2 = tmp2

两个链表的交点 Intersection of Two Linked Lists

Leetcode : 160. Intersection of Two Linked Lists (Easy)

思路：对于链表 A 和 B，相交于公共部分 C，设两个链表的公共部分长度为 c，那么 A 的长度为 a + c，B 的长度为 b + c，那么有 a + c + b = b + c +a。

当链表 A 访问到尾部时，则从链表 B 的头部开始访问 B；
当链表 B 访问到尾部时，则从链表 A 的头部开始访问 A。
这样可以控制访问 A 和 B 的指针同时访问到交点，若 A 和 B 没有交点，则两个指针同时为空，返回 None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        p = headA
        q = headB
        if not p or not q:
            return None
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

回文链表 Palindrome Linked List

Leetcode : 234. Palindrome Linked List (Easy)

方法一：
将链表的值存到数组中，然后再判断是否为回文数组。
时间复杂度 o(n), 空间复杂度 o(n)

class Solution(object):
    def isPalindrome(self, head):
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        for i in range(len(arr)//2):
            if arr[i] != arr[len(arr)-1-i]:
                return False
        return True

方法二：
将后半段链表反转，再与前半段进行比较从而判断。
时间复杂度 o(n), 空间复杂度 o(1)

利用快慢指针法找到单链表的中点，注意边界条件。

class Solution(object):
    def isPalindrome(self, head):
        if not head or not head.next:
            return True
        
        fast = slow = head
        rhead = None
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        rhead = self.reverseList(slow.next)
        
        while rhead:
            if rhead.val != head.val:
                return False
            rhead = rhead.next
            head = head.next
        return True
    
    def reverseList(self, head):
        cur = head
        pre = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

Delete Node in a Linked List

Leetcode : 237. Delete Node in a Linked List (Easy)

本题需要删除链表中的一个节点 node，一般删除一个节点会通过保留上一个节点来操作，但该题中只给了当前节点，因此可以将下一个节点的值赋给当前节点，然后将当前节点指向下下个节点，这样就相当于删除了当前节点。

def deleteNode(self, node):
    node.val = node.next.val
    node.next = node.next.next

奇偶链表 Odd Even Linked List

Leetcode : 328. Odd Even Linked List (Medium)

class Solution(object):
    def oddEvenList(self, head):
        if not head:
            return head
        even_head = head.next
        odd = head
        even = even_head
        while even and even.next:
            odd.next = odd.next.next
            odd = odd.next
            even.next = even.next.next
            even = even.next
        odd.next = even_head
        return head