3-1.数组中重复的数字

思路分析：如果不考虑时间复杂度，则可以先对数组排序（需要 的时间），然后再从中找重复的数字。

如果不考虑空间复杂度，则可以额外使用一个字典，然后从头到尾遍历数组中的每个元素。每遍历到一个元素，就检查它是否已经在字典中，如果不在就把它添加到字典中，如果在就表示有重复。字典的查找时间复杂度是 ，遍历整个数组的时间复杂度是 ，因此算法的时间复杂度是 ，但它提高时间效率是以一个额外的空间复杂度 为代价的。

还有一种更优的考虑：注意到数组中的数字都在 的范围内，如果这个数组中没有重复的数字，那么当数组排序之后数字 将出现在下标为 的位置。而由于数组中有重复的数字，那么有些位置可能存在多个数字，同时有些位置可能没有数字。

基于这种考虑，我们从头到尾遍历数组中的每个数字。当遍历到下标为 的数字时，首先比较这个数字（用 表示）是不是等于 。如果是，就表明这个数字位于本来就属于它的位置；如果不是，那我们把它和第 个位置上的数字进行比较。如果它等于第 个位置上的数字，那就找到了一个重复的数字；如果不等，那就把 放到第 个位置上，同时原来在第 个位置上的数字放到第 个位置上（也就是把第 个数字和第 个数字交换）。然后继续比较这个下标 上的数字，直到这个位置上的数字等于 ，才进行下一个位置上的数字比较。对于每一个位置上的数字都是如此。也就是说，代码中会存在两个循环。代码如下：

def duplicate(nums):
    for i, num in enumerate(nums):
        while i != num:
            if num == nums[num]:
                return True, num
            else:
                nums[i], nums[num] = nums[num], nums[i]
                num = nums[i]
    return False, None

复杂度分析：

• 时间复杂度：代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它的位置，因此总的时间复杂度是 ；
• 空间复杂度：所有的操作都是在输入数组上进行的，不需要额外分配内存，因此空间复杂度是 。

3-2.不修改数组找出重复的数字

思路分析：假如没有重复的数字，那么在 1～n 的范围内最多只能有 n 个数字，而现在数组中有 n+1 个数字，就表明至少肯定是在某个范围内多了一个数字，那么我们就可以根据某个范围内数字的个数来判断是否有重复的数字。

把原数组从中间二分，假设中间数字是 m，那么左边一半即为 1～m，右边一半为 m+1～n。如果左边一半的数字个数超过了 m，就表明在这个区间里一定包含了重复的数字；否则，右边的一半区间里一定包含了重复的数字。然后，我们对包含重复数字的区间继续二分，如此进行下去，直到最终找到重复的数字。代码如下：

def find_duplicate(nums):
    def count_range(i, j):
        return sum(i<=num<=j for num in nums)
    lo = 1
    hi = len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        count = count_range(lo, mid)
        if lo == hi:
            if count > 1:
                return lo
            else:
                break
        if count > mid-lo+1:
            hi = mid
        else:
            lo = mid + 1
    return -1

复杂度分析：

• 时间复杂度：如果输入长度为 n 的数组，那么函数 count_range 将被调用 次，每次都需要 的时间，因此总的时间复杂度是 ；
• 空间复杂度：

算法的不足：该算法不能保证找出所有重复的数字，比如在 1～2 的范围内有 1 和 2 两个数字，这个范围内的数字也出现了两次，此时该算法无法判断是每个数字各出现一次还是某个数字出现了两次。

第4题：二维数组中的查找

思路分析：首先选取数组中右上角的数字，如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。如此，直到找到要查找的数字，或把整个数组剔空。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row, col = 0, len(array[0])-1 # 要从第0行最后一列开始
        while row < len(array) and col >= 0:
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                col -= 1
            else:
                row += 1
        return False

第5题：替换空格

分析：python中的join方法：将序列中的元素以指定的字符连接生成一个新的字符串。例子：

str = "-";
seq = ("a", "b", "c"); # 字符串序列
print(str.join( seq ))
# 输出：a-b-c

代码：

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        return ''.join(c if c!=' ' else '%20' for c in s)

6.从尾到头打印链表

思路分析：按照从头到尾的顺序遍历链表，将每一个节点的值保存到一个list中，最后再将list中的元素反过来就可以了。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def printListReversingly(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        stack= []
        while head:
            stack.append(head.val)  # val后面不能有小括号
            head = head.next  # next后面不能有小括号
        return stack[::-1]  # ::-1将list进行反转

7.重建二叉树

知识拓展：

二叉树的前序、中序、后序遍历的递归、非递归实现及层次遍历的实现：https://blog.csdn.net/weixin_45595437/article/details/100598886

二叉树的遍历代码：

# 定义节点类
class Node(object):
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

class Tree(object):
    def __init__(self):
        self.root = Node()
        self.myQueue = []
    
    def addNode(self, elem):
        node = Node(elem)
        if self.root.elem == -1:  # 表明此时树还是空的
            self.root = node
            self.myQueue.append(self.root)
        else:
            treeNode = self.myQueue[0]
            if treeNode.lchild == None:
                treeNode.lchild = node
                self.myQueue.append(treeNode.lchild)
            else:  # 否则，就对右孩子赋值
                treeNode.rchild = node
                self.myQueue.append(treeNode.rchild)
                self.myQueue.pop(0) # 如果右孩子已经赋上了值，就说明这个二叉树单元已经完整了，此时要弹出父节点
    
    # 前序遍历递归实现
    def pre_order_recur(self, root): # 无论是树还是链表，对它们操作传入的都是根节点
        if root == None:
            return
        print(root.elem, end=' ')
        self.pre_order_recur(root.lchild) # 递归调用自身时必须要加self
        self.pre_order_recur(root.rchild)
    
    # 中序遍历递归实现
    def in_order_recur(self, root):
        if root == None:
            return
        self.in_order_recur(root.lchild)  # 递归调用自身时必须要加self
        print(root.elem, end=' ')
        self.in_order_recur(root.rchild)  # 递归调用自身时必须要加self
    
    # 后序遍历递归实现
    def post_order_recur(self, root):
        if root == None:
            return
        self.post_order_recur(root.lchild)
        self.post_order_recur(root.rchild)
        print(root.elem, end=' ')
    
    # 前序遍历非递归实现（非递归写法是用栈来实现的）
    def pre_order_traversal(self, root):
        if root == None:
            return
        node = root
        myStack = []
        while node or myStack:
            while node:
                print(node.elem, end=' ')
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()
            node = node.rchild
    
    # 中序遍历非递归实现（也是用栈，思路和前序遍历一模一样，只是print的位置发生了变化）
    def in_order_traversal(self, root):
        if root == None:
            return
        node = root 
        myStack = []
        while node or myStack:
            while node:
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()
            print(node.elem, end=' ')
            node = node.rchild
    
    # 后序遍历非递归实现（用栈，而且要用两个栈）
    def post_order_traversal(self, root):
        if root == None:
            return
        myStack1, myStack2 = [], []
        node = root
        myStack1.append(node)
        while myStack1:
            node = myStack1.pop()
            if node.lchild:
                myStack1.append(node.lchild)
            if node.rchild:
                myStack1.append(node.rchild)
            myStack2.append(node)
        while myStack2:  # 这个栈中保存的是后序遍历的逆序
            node = myStack2.pop()
            print(node.elem, end=' ')

"""这部分删掉，层次遍历见后面的最新代码
    # 层次遍历/广度优先遍历（用队列实现）
    # 前序、中序和后序遍历都属于深度优先遍历
    def broad_first_search(self, root):
        if root == None:
            return
        node = root 
        myQueue = []
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0) # 栈和队列表面上看起来都是一个列表，但它们之间的区别就在于：栈是myStack.pop()，即弹出最后一个元素（栈顶元素），从而体现了后进先出；而队列则是myQueue.pop(0)，即弹出最前边的元素，从而体现了先进先出。
            print(node.elem, end=' ')
            if node.lchild:
                myQueue.append(node.lchild)
            if node.rchild:
                myQueue.append(node.rchild)
"""

    # 更新于2019.12.28
    # 层次遍历/广度优先遍历（用队列实现）
    # 前序、中序和后序遍历都属于深度优先遍历
    def broad_first_search(self, root):
        from collections import deque
        queue = deque([root])
        # res = []
        while queue:
            node = queue.popleft() # 栈和队列表面上看起来都是一个列表，但它们之间的区别就在于：栈是myStack.pop()，即弹出最后一个元素（栈顶元素），从而体现了后进先出；而队列则是myQueue.pop(0)，即弹出最前边的元素，从而体现了先进先出。
            if node:
                print(node.elem, end=' ')
                # res.append(node.elem)
                queue.append(node.lchild)
                queue.append(node.rchild)
            # return res


if __name__ == '__main__':
    my_tree = Tree()
    my_tree.addNode(10)
    my_tree.addNode(6)
    my_tree.addNode(14)
    my_tree.addNode(4)
    my_tree.addNode(8)
    my_tree.addNode(12)
    my_tree.addNode(16)

    print('递归先序遍历', end=' ')
    my_tree.pre_order_recur(my_tree.root)
    print()

    print('递归中序遍历', end=' ')
    my_tree.in_order_recur(my_tree.root)
    print()

    print('递归后序遍历', end=' ')
    my_tree.post_order_recur(my_tree.root)
    print()

    print('非递归先序遍历', end=' ')
    my_tree.pre_order_traversal(my_tree.root)
    print()

    print('非递归中序遍历', end=' ')
    my_tree.in_order_traversal(my_tree.root)
    print()

    print('非递归后序遍历', end=' ')
    my_tree.post_order_traversal(my_tree.root)
    print()

    print('层次遍历', end=' ')
    my_tree.broad_first_search(my_tree.root)
    print()

思路分析：前序遍历序列的第一个数必是整个二叉树的根节点。在找到这个根节点之后，在中序遍历序列中找到该根节点所在的位置（这里要假设树中没有重复的元素），那么在这个根节点左侧的所有元素就构成了整个二叉树的左子树，右侧的所有元素构成整个二叉树的右子树。假设左子树中元素的总个数为 ，那么前序遍历序列中，位于根节点右边的连续 个元素都将是左子树中的元素，它和中序遍历序列中根节点左边的所有元素是完全对应的。如果把这部分元素取出来，递归地把它们再分成左、右子树，那么整个问题就可以用递归的方法去解决：就是一个不断划分左右子树的过程，递归的边界是用于划分的列表为空。

根节点、左右子树在先序遍历和中序遍历中的位置分别如下所示：

先序遍历：根节点 | 左子树 | 右子树
中序遍历：左子树 | 根节点 | 右子树

需要特别注意的是它们之间的边界到底应该取到哪里。

Python的 index 方法：在给定字符串中查找是否包含目标字符串，如果包含，则返回索引的起始位置；否则，抛出异常。e.g.

# 默认查找范围是从索引为0处查找到给定字符串的末尾
source_str.index(target_str, begin=0, end=len(source_str))

代码：

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

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if preorder == []:
            return
        root_val = preorder[0]
        root = TreeNode(root_val)
        cut = inorder.index(root_val) # 因为索引是从0开始的，所以cut是几，cut前面就会有几个元素，这个数字用于后面处理边界
        root.left = self.buildTree(preorder[1:cut+1], inorder[:cut]) # 从1后面（包括1）取cut个元素，inorder取前面cut个元素
        root.right = self.buildTree(preorder[cut+1:], inorder[cut+1:])
        return root

8.二叉树的下一个节点

分析：

• 如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点；
• 如果一个节点是它父节点的左子节点，那么它的下一个节点就是就是它的父节点；
• 如果一个节点既没有右子树，并且它还是它的父节点的右子节点，那么我们就沿着指向父节点的指针一直向上找，直到找到这样一个节点：它是它父节点的左子节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。如果找不到这样的节点，那么此时要寻找的下一个节点不存在。

代码：

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        # 如果该节点有右子树
        if pNode.right:  
            node = pNode.right
            while node.left:
                node = node.left
            return node
        # 如果该节点是它父节点的左子节点
        # 或者如果该节点既没有右子树，又不是它父节点的左子节点
        # 这两个合并起来写
        while pNode.next:
            parent_node = pNode.next
            if parent_node.left == pNode:
                return parent_node
            pNode = parent_node
        
        return None

9-1.用两个栈实现队列

分析：通常栈是一个不考虑排序的数据结构，需要在 时间内才能找到栈中最大或最小的元素。

考虑一个栈stack1，将三个元素a, b, c依次压入栈中，则c将位于栈顶。此时如果想模拟队列的弹出操作，则应该a最先被弹出，但事实情况是c将最先被弹出。

如果每新来一个元素，我们都把它放在栈底而不是栈顶，那么最新来的元素将最后被弹出，便实现了队列的操作。如何做到这一点呢？这时需要一个额外的栈stack2来辅助这一操作：每新来一个元素，我们都把stack1中原有的元素全部搬到stack2中，然后将新来的元素append到stack1中，最后再把原来的元素再搬回来，这样新来的元素将总是会出现在栈底。代码如下：

class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.s1, self.s2 = [], []
        

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())
        

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        return self.s1.pop()
        

    def peek(self):  # 这里的peek取的是栈顶的元素
        """
        Get the front element.
        :rtype: int
        """
        return self.s1[-1] # s1中栈顶的元素是最先进来的元素
        

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.s1 == []

9-2.用两个队列实现栈

思路分析：用deque（双向队列）实现。假设对于一个deque来说，最左边是队首，最右边是队尾。

对于一个队列来说，新来的元素只能添加到队尾。而如果把这个队列想象成栈的话，那么最左边应该是栈顶，最右边应该是栈底（这样的话出栈操作和出队操作就可以保持一致了——都是从最左边出来）。我们现在需要做的是：每新来一个元素，我们都把它添加到最左边而不是最右边。如何实现这一操作呢？用一个额外的队列就可以实现。假设q1是主体队列，q2是辅助队列。我们现在想把一个新的元素 添加到q1的队首，此时我们这样做：先把 添加到空的q2中，然后让q1中的元素逐个出队，并逐个进入q2，这样 在q2中的位置便是在最左边，此时再把q1和q2交换一下，便可以达到目标。代码如下：

class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        from collections import deque
        self.q1, self.q2 = deque(), deque()
        
    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
        
    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.q1.popleft()
         
    def top(self):  # 这里的top指的是排在队列最前面的元素
        """
        Get the top element.
        :rtype: int
        """
        return self.q1[0]
        
    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return not self.q1

要注意的是栈的top是栈顶元素，队列的top是队首元素。

下列语句即使是用在判断或循环语句里，也会实际执行一次 pop() 操作，因此尽量不要使用这样的判断语句：

if self.q1.pop(0) != target

while self.q1.pop(0) != target

拓展：

仅用一个deque就可以实现和上述代码同样的效果：

class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        from collections import deque
        self.q = deque()
        
    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.q.append(x)
        for i in range(len(self.q)-1):
            self.q.append(self.q.popleft())
        
    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.q.popleft()
        
    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.q[0]

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return not self.q

10.斐波那契数列

拓展：通常运用动态规划解决问题时都是用递归的思路分析问题，但由于递归分解的子问题中存在大量的重复，因此我们总是采用自下而上的循环来实现代码。一句话总结即：用递归分析问题并基于循环编写代码。

思路分析：关键是要避免重复运算（即避免递归）。递归算法可以看做是”从顶到底“的方法，可以改为”从底到顶“的循环来实现：

"""这个代码不是最精简的，更精简的代码参考后续分析"""
class Solution(object):
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        fn1, fn2 = 1, 0
        n = 2
        if N == 0:
            return fn2
        if N == 1:
            return fn1
        for i in range(N-1): # 只有当N>=2时才会进入这个循环体
            fn1, fn2 = fn1+fn2, fn1 # 只需要保存fn1, fn2这两个中间变量即可
        return fn1

以上代码可以进一步改进： N == 1 的情形可以合并到for循环中。Python的 range 其实返回的是一个列表，如 range(5) 返回 [0, 1, 2, 3, 4] 。如果 range 里面的数字是0，那么返回一个空列表： [] ，此时再用for去遍历这个列表时将会直接跳过，即for循环不执行。因此以上代码可以进一步简化为：

class Solution(object):
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        fn1, fn2 = 1, 0
        if not N:
            return fn2
        for i in range(N-1):
            fn1, fn2 = fn1+fn2, fn1
        return fn1

11-1.排序问题

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度无法突破 ，因此也称为非线性时间比较类排序。它主要包括：

• 交换排序：包括冒泡排序和快速排序；
• 插入排序：包括简单插入排序和希尔排序；
• 选择排序：包括简单选择排序和堆排序；
• 归并排序：包括二路归并排序和多路归并排序。

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。它主要包括：

• 计数排序；
• 桶排序；
• 基数排序。

它们的复杂度及稳定性如下：（时间复杂度不是说跑完这个算法需要花费多少时间，而是随着n的增加，算法的操作次数将以什么样的趋势增加。空间复杂度反映的是随着n的增加，算法消耗的空间资源将以什么样的趋势增加。稳定性：假设排序前a=b且a在b的前面，如果排序后a仍然在b的前面，则说这个算法是稳定的。如果排序后a不一定是在b的前面，则说这个算法是不稳定的。）

排序方法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序					稳定
快速排序					可以稳定
简单插入排序					稳定
希尔排序					不稳定
简单选择排序					不稳定
堆排序					不稳定
归并排序					稳定
计数排序					稳定
桶排序					稳定
基数排序					稳定

（1）冒泡排序：

• 一句话总结：冒泡排序的核心思想就是比较和交换。

• 具体操作过程：比较相邻的元素，如果后面的元素比前面的大，就交换它们两个（或者反过来也可以）。这样经过一轮比较和交换，最大（或最小）的元素就会出现在序列的末尾。然后再进行第二轮比较和交换......如此进行下去，直到最后一轮比较和交换完成（最后一轮将只剩下两个元素进行比较和交换）。
  整个过程中，数值较小的数字将会像水里的泡泡一样逐渐“浮”到水面，这便是冒泡排序名字的由来。

• Python实现：

  def bubbleSort(nums):
      if len(nums) <= 1:
          return nums
      for i in range(len(nums)-1):
          for j in range(len(nums)-1-i):
              if nums[j] > nums[j+1]:
                  nums[j], nums[j+1] = nums[j+1], nums[j]
      return nums
  

• 时间复杂度：假设有 个数，则比较和交换的过程总共需要进行 轮。这 轮的比较和交换过程无论是在最好的情况（即序列本来就是有序序列）还是在最坏的情况（即数组完全逆序）下都是少不了的，因此它决定了冒泡排序时间复杂度的下限（即最好时间复杂度）（注意这里的比较操作不算在时间复杂度之内）。在最坏情况下，在每一轮比较过程中，每两个相邻的元素都需要交换，两两交换的时间复杂度是 ，因此最坏情况下的时间复杂度为 。
  综上，冒泡排序最好情况下的时间复杂度是 (发生在序列原本就已经有序的情况下)，最坏情况下的时间复杂度为 (发生在序列完全逆序的情况下)，平均时间复杂度仍为 。

• 空间复杂度：由于是 in-place 操作，所以空间复杂度是 。

• 稳定性：由于当相邻的数字相等时不发生交换，因此冒泡排序是稳定的。

• Python实现：

  def bubbleSort(nums):
      if len(nums) <= 1:
          return nums
      for i in range(len(nums)-1): # 总共需要遍历n-1轮
          for j in range(len(nums)-1-i):
              if nums[j] > nums[j+1]:
                  nums[j], nums[j+1] = nums[j+1], nums[j]
      return nums
  

（2）快速排序：

• 一句话总结：快速排序就是不断地将序列分为一个数值较大的序列和一个数值较小的序列。

• 快速排序是一种递归的方法，采用的是分治策略（分治不一定是二分）；

• 具体操作过程：从序列中挑出一个元素（比如序列末尾的元素），将其称之为“基准”。然后遍历序列中剩余的元素，将所有小于基准值的元素都放到基准的左边，大于基准值的元素都放到基准的右边，等于基准值的元素理论上可以放到任何一边（但如果要想使快速排序算法是稳定的，则当基准值每次都取序列的首个元素时，应将等于基准值的元素放到基准的右边；当基准值每次都取序列的末尾元素时，应将等于基准值的元素放到基准的左边。）这样就把原序列分成了两部分，然后递归地将这两部分再不断地分成更小的两部分，直到两部分序列中的元素个数都不超过1。

• 时间复杂度：最好的情况是每次都能将序列二分（即左右两边序列的长度相等，这个时候基准值不一定是整个序列的中位数），这样不断地二分是最节省时间的，此时的时间复杂度为 ，可以通过数学式子推倒出来：
  假设对一个长度为 的序列，我们需要用 的时间对它进行排序。由于每次都要遍历一遍序列，因此每次都要花费 的时间来将原序列划分为两个长度减半的序列，由此可得到递推公式：
  
  其中， 。因此最好情况下的时间复杂度是 。
  在最坏的情况下，每次左右两边的序列都有一个是空的，相当于原序列每次只减少了一个元素，这样一个长度为 的序列就需要 次才能使序列的长度减少到 1 ，而每次又都需要花费 的时间来进行划分，因此最坏情况下的时间复杂度为 。

• 空间复杂度：在每一轮都需要花费 的额外空间来存储原序列中的元素，最好情况下需要 轮，最坏情况下需要 轮，因此空间复杂度为 ～ 。

• 稳定性：前已述及，要看基准数怎么选，可以将快速排序设计成稳定的。

• python实现：

  def quickSort(nums):
      if len(nums) <= 1:  # 递归算法先写递归基
          return nums
      base = nums.pop()
      left, right = [], []
      for num in nums:
          if num <= base:
              left.append(num)
          else:
              right.append(num)
      return quickSort(left) + [base] + quickSort(right)
  

（3）简单插入排序

• 一句话总结：在已排序序列中从后向前扫描，不断地找新来元素对应的位置并插入。

• 具体操作过程：从原始序列的第2个元素开始，每次取出一个元素，这个元素左边的序列是已经排好序的。我们要在这个排好序的序列中找到这个新来的元素对应的位置，方法是在已排序的序列中从后向前扫描，如果当前扫描到的元素大于新来的元素，就把这个扫描到的元素向后挪一位；否则，就把这个新来的元素放到当前扫描到的元素的后面。
  由此可见，简单插入排序是 in-place 的，因此空间复杂度为 。而且简单插入排序是稳定的。

• 时间复杂度：平均时间复杂度为 。
  在最好的情况下，每次新来的元素都比已排序序列中任何一个元素都大，即每次都不需要挪动元素，只需要把新来的元素放到已排序序列的末尾即可，这个过程在 的时间内即可完成。而遍历整个序列需要花费 的时间，因此最好情况下的时间复杂度为 。
  在最坏的情况下，每次新来的元素都比已排序序列中任何一个元素都小，此时每次都要将已排序序列中所有元素向后挪一位，这将花费 的时间。而遍历操作也需要花费 的时间，因此最坏情况下的时间复杂度为 。

• 空间复杂度：前已述及，为 。

• 稳定性：前已述及，是稳定的。

• python实现：

  def insertionSort(nums):
      for i in range(1, len(nums)):
          num = nums[i]
          sorted_p = i - 1
          while sorted_p >= 0 and nums[sorted_p] > num:
              nums[sorted_p+1] = nums[sorted_p]
              sorted_p -= 1
          nums[sorted_p+1] = num
      return nums
  

（4）希尔排序

• 一句话总结：通过一个增量序列将原序列划分成若干个子序列，然后分别对这些子序列进行简单插入排序。希尔排序也叫递减增量排序。

• 具体实现过程：

  • 首先选择一个逐渐较小的增量序列 ，其中 ，且 ；（在实际的操作过程中，通常取 且对其进行取整。）
  • 增量序列中的每一个 都将原序列划分成 个子序列，我们要对这 个子序列分别进行简单插入排序；
  • 增量序列中总共有 个值，因此第二步总共需要进行 轮，且最后一轮的增量为 1，即为简单插入排序。因此希尔排序中前面的所有轮都可以看做是为最后一轮做准备的，待最后一轮结束，整个排序工作也就完成了。

• 需要注意的地方：
  希尔排序最后一趟的增量因子必须为 1（即最后一趟即为简单插入排序）；
  在每一趟排序结束之后，都将增量因子减小为原来的一半，直到最终减小到 1。

• 时间复杂度分析：希尔排序的时间复杂度与增量（即步长gap）的选取有关。通常认为，希尔排序的平均时间复杂度为 。
  当增量为1时，希尔排序退化成了简单插入排序，因此希尔排序在最好情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。

• 空间复杂度分析：希尔排序是 in-place 的，因此空间复杂度为 。

• 稳定性：希尔排序是不稳定的。对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。

• python实现：

  def shellSort(nums):
      gap = len(nums) // 2
      while gap > 0:
          for i in range(gap, len(nums)):
              num = nums[i]
              sorted_p = i - gap
              while sorted_p >= 0 and nums[sorted_p] > num:
                  nums[sorted_p+gap] = nums[sorted_p]
                  sorted_p -= gap
              nums[sorted_p+gap] = num
          gap //= 2
      return nums
  

（5）简单选择排序

• 一句话总结：不断地寻找未排序序列的最值，将其逐个添加到已排序序列的末尾。

• 具体操作过程：以寻找未排序序列的最小值为例。首先寻找整个序列的最小值，然后，为了减小空间复杂度，采取 in-place 操作——将其和序列的首个元素进行交换，这样便排好了第一个元素。当第一个元素排好序之后，未排序序列就是从第二个元素起直到序列结束。我们需要做的就是在这一未排序序列中找到最小值，然后将其和未排序序列的首个元素进行交换（这一操作等价于是将这个最小值添加到已排序序列的末尾）。然后在剩余的未排序序列中重复上述过程，直至未排序序列的长度减小到1。

• 时间复杂度分析：无论原始序列是否是有序的，选择排序的两趟遍历是少不了的，因此不管是最好还是最坏情况，简单选择排序的时间复杂度均为 ，平均时间复杂度也为 。

• 空间复杂度分析：in-place 操作，空间复杂度为 。

• 稳定性分析：由于简单选择排序涉及到交换过程，假设有两个相等的元素，如果左边那个相等的元素先被交换到后面，那么最终排序的结果可能会打乱这两个相等的元素在原序列中的顺序。因此简单选择排序是不稳定的。

• python实现：

  def selectionSort(nums):
      for i in range(len(nums)):
          min_idx = i
          for j in range(i+1, len(nums)):
              if nums[j] < nums[min_idx]:
                  min_idx = j
          nums[i], nums[min_idx] = nums[min_idx], nums[i]
      return nums
  

（6）堆排序

• 前置知识：

  • 二叉树：每个节点至多拥有两棵子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，其次序不能任意颠倒。
  • 完全二叉树：除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干节点，并且所有的叶子节点都向左对齐（即孩子节点在进行填充时必须满足如下优先级：当前节点的左孩子节点 当前节点的右孩子节点，当前节点的孩子节点 后续节点的孩子节点。若违背这一优先级，则这棵树就不是完全二叉树）。（参考：https://blog.csdn.net/qq_30650153/article/details/82024648）（参考：https://www.jianshu.com/p/d174f1862601）
  • 满二叉树是完全二叉树的一种，它的所有层上的节点数均达到最大值。
  • 堆是一种特殊的完全二叉树，堆中某个节点的值总是不大于或不小于其父节点（若存在）的值。
  • 大根堆：每个节点的值都大于或等于其左右孩子节点（若存在）的值，根节点的值是所有节点值中的最大者。
  • 小根堆：每个节点的值都小于或等于其左右孩子节点（若存在）的值，根节点的值是所有节点值中的最小者。
  • 堆排序就是利用堆这种数据结构来进行排序。

• 一句话总结：先构造大根堆，然后不断交换未排序部分的首尾元素并重新构造大根堆。

• 具体操作过程（以大根堆为例）：

  • 首先将待排序的数组构造成一个大根堆；
  • 然后取出这个大根堆的堆顶节点（最大值），将其与堆的未排序部分的最后一个元素进行交换，然后将未排序部分除最后一个元素之外的部分重新构造成一个大根堆（交换之后，未排序部分的最后一个元素相当于已经排过序了，因此它不需要再参与大根堆的构建）；
  • 重复第二步，直到未排序部分的长度为1，此时即完成排序。

• 时间复杂度分析：平均时间复杂度： 。堆排序的时间复杂度分析类似于选择排序，不管原始序列是已经排好序的还是完全逆序的，堆排序总是要花费 的时间来遍历堆中的 个元素，来进行元素交换。每次交换元素后，又必须要花费 的时间来将堆中剩余部分重新构造成一个大根堆（这里 是因为索引值是以 2 的指数的方式来遍历堆中剩余的元素的），因此无论是在最好情况下还是在最坏情况下，时间复杂度均为 。

• 空间复杂度分析：由于是 in-place 操作，因此空间复杂度为 。

• 稳定性分析：由于涉及到元素交换，因此不能保证排序后相同元素的顺序保持不变，所以堆排序是不稳定的。

• python实现：

  from collections import deque
  
  def generate_max_heap(nums, parent_position, last_position):
      parent_val = nums[parent_position]
      max_child_position = 2 * parent_position
      while max_child_position <= last_position:
          if max_child_position < last_position and nums[max_child_position] < nums[max_child_position+1]:
              max_child_position += 1
          if parent_val < nums[max_child_position]:
              nums[parent_position] = nums[max_child_position]
              parent_position = max_child_position
              max_child_position = 2 * parent_position
          else:
              break
      nums[parent_position] = parent_val
      return nums
  
  def heapSort(nums):
      nums = deque(nums)
      nums.appendleft(0)
      first_parent_position = (len(nums)-1) // 2
      for i in range(first_parent_position):
          nums = generate_max_heap(nums, first_parent_position-i, len(nums)-1)
      for i in range(len(nums)-2):
          nums[1], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[1]
          nums = generate_max_heap(nums, 1, len(nums)-2-i)
      return [nums[i] for i in range(1, len(nums))]
  

（7）二路归并排序

• 归并排序是一种递归算法，用到的思想是分而治之。

• 将两个有序子序列合并成一个有序序列的过程称为二路归并。

• 一句话总结：先使每个子序列有序，然后再将有序的子序列合并。

• 具体操作过程：

  • 将原始序列从中间位置分成两个序列；
  • 将得到的两个子序列按照第一步继续二分下去；
  • 直到所有子序列的长度都为 1，即无法再继续二分为止。此时再两两合并成一个有序序列即可。

• 时间复杂度分析：平均时间复杂度： 。划分序列的过程每次都是二分的，因此用 的时间就可以完成序列的划分（划分子序列的形式类似于一棵二叉树，划分的次数其实就是二叉树的深度）。每次归并都要遍历整个被划分出来的两个序列，因此归并操作的时间复杂度是 。并且，无论原始序列是否有序，二分的过程和归并的过程都是少不了的。因此无论是在最好的情况下还是在最坏的情况下，归并排序的时间复杂度均为 。

• 空间复杂度分析：由于要用到一个额外的辅助数组，因此归并排序的空间复杂度是 。

• 稳定性分析：整个划分和归并的过程不涉及到元素位置的交换，因此归并排序是稳定的。

• python实现：

  def merge(left, right):
      extra = []
      i = j = 0
      while i < len(left) and j < len(right):  # 这里是and关系
          if left[i] < right[j]:
              extra.append(left[i])
              i += 1
          else:
              extra.append(right[j])
              j += 1
      if i == len(left):
          extra += right[j:]
      else:
          extra += left[i:]
      return extra
  
  def mergeSort(nums):
      if len(nums) < 2:  # 递归方法一定要先写递归基
          return nums
      middle = len(nums) // 2
      left = mergeSort(nums[:middle])
      right = mergeSort(nums[middle:])
      return merge(left, right)
  

（8）计数排序

• 前置知识：

  • 计数排序、桶排序和基数排序都属于非比较排序，它们的时间复杂度都是线性的，优于比较排序类方法。但它们也有弊端：会多占用一些空间，相当于是用空间换时间。
  • 计数排序的核心思想是将原始序列转化为键值对存储在额外开辟的数组空间中，它要求原始序列必须是有确定范围的整数。（最大值最好不要太大，否则会占用很多的额外空间。）

• 一句话总结：将原始序列转化为键值对存储在额外开辟的数组空间中。

• 具体操作过程：用一个额外的数组来记录原始序列中每个元素对应的位置以及它出现的次数，然后再把它们按顺序一个一个地取出来。

• 时间复杂度分析：平均时间复杂度、最好情况下的时间复杂度、最坏情况下的时间复杂度均为 ，快于任何比较排序算法。当 不是很大且序列比较集中时，计数排序是一个很有效的排序算法。但是计数排序对于输入的数据有要求，并不是所有情况下都能使用这种排序算法。（计数排序也只需要用到最大值，不需要用到最小值，因此如果 比输入数据的规模小的多，计数排序将会非常高效。）

• 空间复杂度分析：

  • 把原序列当做输出序列： ；
  • 用额外的空间来存放输出序列： 。

• 稳定性分析：稳定。

• python实现：

  def countingSort(nums, maxValue):
      counter = [0] * (maxValue+1)
      for num in nums:
          counter[num] += 1
      ndx = 0
      for i in range(maxValue+1):
          while counter[i] > 0:
              nums[ndx] = i
              ndx += 1
              counter[i] -= 1
      return nums
  

（9）桶排序（参考：https://cppsecrets.com/users/17211410511511610510710997106117109100971144964103109971051084699111109/Python-program-for-bucket-sort-algorithm.php）

• 一句话总结：分桶 -> 排序 -> 合并。

• 计数排序和桶排序的区别与联系：它们都用到了“桶”的概念，只不过计数排序中每个桶里只有一个键值，而桶排序中每个桶里存放的是一定范围内的键值。

• 具体操作过程：

  • 将待排元素划分到不同的桶。假设原始序列的最大值和最小值分别为 max(nums) 和 min(nums) ，设桶的个数为 k，则把区间 [min(nums), max(nums)] 均匀划分成 k 个区间，每个区间就是一个桶。然后将序列中的元素分配到各自的桶。
  • 接着对每个桶内的元素分别进行排序。可以选择任意一种排序算法，或者递归地用桶排序继续进行划分。
  • 然后将各个桶中的元素合并成一个大的有序序列。

• 复杂度分析：桶排序的计算复杂度依赖于每个桶用到的排序算法、要使用的桶的个数以及输入数据是否是均匀分布的。当输入数据均匀地分布在某个范围内时，桶排序非常有效。但是当输入数据中某些数字非常集中时，这时各个桶中的数据分布将会非常不均匀（一些桶中的数据非常多而另一些桶中的非常少）。一种极端的情形是所有的数据都分布在同一个桶里，桶排序最坏情况下的时间复杂度就发生在这种情形：因为此时桶排序的性能将完全取决于对每个桶所使用的排序算法的好坏。如果使用的是诸如冒泡排序、简单选择排序、简单插入排序这样的算法，那么桶排序的时间复杂度将达到 。在最好的情况下，每个桶里都分得一个元素，这样整体所花费的时间就是分桶操作所花费的时间，为 平均时间复杂度为 。空间复杂度：假设用到了 k 个桶，那么空间复杂度就是 。

• 稳定性分析：分桶操作不涉及交换，因此桶排序是稳定的。

• python实现：

  • 代码中只需要用到最大值，不需要用到最小值。这一点非常巧妙：即使输入数据中包含负数，代码也能够正常进行排序，因为负数的索引进过映射后就变成了 -len(nums) ，正好被分到前面的桶中。
  • 桶排序在对每个桶中的元素分别进行排序时，需要额外使用其他的排序算法，这里以快速排序为例。
  • 程序中必须要有 bucket_index 和 len(nums) 的判断，否则需要额外分配一个桶，造成空间的浪费。
  • bucket_index 的数据类型必须要转换为 int 型，/ 操作得到的是 float 型。

  def quickSort(nums): # 桶排序中要额外用到的其他排序算法
      if len(nums) <= 1:
          return nums
      base = nums.pop()
      left, right = [], []
      for num in nums:
          if num <= base:
              left.append(num)
          else:
              right.append(num)
      return quickSort(left) + [base] + quickSort(right)
  
  def bucketSort(self, nums):
          bucket_size = max(nums) / len(nums)
          buckets = [[] for i in range(len(nums))]
          for i in range(len(nums)):
              bucket_index = int(nums[i] / bucket_size)
              if bucket_index != len(nums):
                  buckets[bucket_index].append(nums[i])
              else:
                  buckets[bucket_index-1].append(nums[i])
          res = []
          for i in range(len(nums)):
              buckets[i] = quickSort(buckets[i])
              res += buckets[i]
          
          return res
  

（10）基数排序

• 一句话总结：先排元素的最后一位，再排倒数第二位，直到所有的位数都排完。

• 对于正整数序列之外的序列，如果要使用基数排序，需要调整元素放入桶中的方式。

• 和计数排序一样，基数排序也是一种特殊的桶排序。桶排序是按区间来划分桶，而基数排序则是按数位来划分桶。基数排序可以看做是多轮桶排序，在每个数位上都进行一轮桶排序。

• 基数排序要求元素是非负整数。

• 时间复杂度分析：假设原序列中最大值的位数为 ，则总共将进行 轮桶排序。每一轮桶排序都要遍历整个序列，需要花 的时间。因此平均时间复杂度为 。而且，无论初始序列是否有序， 轮桶排序是少不了的，每一轮桶排序中对整个序列的遍历也是少不了的。因此，无论是在最好情况下还是在最坏情况下，时间复杂度均为 。

• 空间复杂度分析：基数排序的内层循环实际上是一个计数排序，整个基数排序过程实际上是跑了 遍计数排序。计数排序的空间复杂度为 ，而在基数排序的过程中这些空间在每一轮的计数排序中都是重复利用的，因此基数排序的空间复杂度和计数排序是一样的，均为 ，其中 为桶的数量。

• 稳定性分析：基数排序不涉及到元素交换，因此是稳定的。

• python实现：

  def radixSort(nums):
          k = len(str(max(nums))) # 得到最大值的位数
          for i in range(k): # O(k)
              bucktes = [[] for j in range(10)]
              for num in nums: # O(n)
                  bucktes[int(num/(10**i)) % 10].append(num) # 新来的元素一定要放到末尾，这直接决定了基数排序的稳定性
              nums.clear()  # clear函数用于清空列表，例如：list.clear()
              for bucket in bucktes:
                  nums += bucket
          
          return nums
  

11-2. 旋转数组中的最小数字

如果数组中不存在重复的元素，则代码为：

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums)-1
        if nums[left] < nums[right]: # 数组中不存在重复的元素，所以这个地方不能写等于
            return nums[left]
        while left <= right:
            mid = (left+right) // 2
            if nums[left] < nums[mid]:
                left = mid
            elif nums[mid] < nums[right]:
                right = mid
            else:
                return nums[right]

如果数组中存在重复的元素，则以上方法失效，此时只能遍历一遍数组来查找最小值。

12. 矩阵中的路径

回溯法适用于这样的问题：

• 这个问题可能要分很多步才能完成；
• 每一步都有很多种可能，而且这一步一旦确定，下一步还是会有很多种可能，下下一步也还是会有很多种可能，问题看起来非常复杂。

矩阵中的路径问题是典型的可以用回溯法解决的问题，通常回溯法适合用递归实现代码。当我们到达某一个节点时，尝试所有可能的选项并在满足条件的前提下递归地抵达下一个节点。

代码如下：

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def explore(i, j, word):
        if not word: # 递归算法先写递归基
            return True
        temp, board[i][j] = board[i][j], '*' # 因为矩阵中的元素只能用一次，所以一旦用过就得把它抹掉（这里用 * 将它覆盖）
        success = False # 回溯法都是用一个标志来记录探索成功与否的，而不是直接return
        for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
            if 0<=x<rows and 0<=y<cols and board[x][y]==word[0] and explore(x, y, word[1:]):
                success = True # 如果探索成功，就把当前这一步标记为成功
                break # 这里即使是break，代码也会把所有可能的情况找完，不会漏，
                      # 因为如果没有成功，那么if条件不成立，for循环将继续进行下一个值
                      # 而如果成功之后不及时break的话，success的值就可能被下一轮循环改变
        board[i][j] = temp # for循环结束，表明当前的所有情况都探索完了，此时要把抹掉的值复原，以便其他轮的探索能够正常使用这些值
        return success
    
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == word[0] and explore(i, j, word[1:]):
                return True
    return False

review矩阵中的路径：出错了两次，出错代码如下：

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        rows, cols = len(board), len(board[0])

        def explore(i, j, word):
            if not word:
                return True
            temp, board[i][j] = board[i][j], '*'
            success = False
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if board[x][y] == word[0] and 0<=x<rows-1 and 0<=y<cols-1 and explore(x, y, word[1:]):
                    success = True
                    break
            board[i][j] = temp
            return success

        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and explore(i, j, word[1:]):
                    return True
        return False

错误的地方在于：

• 首先，在 explore 函数中，if 语句进行判断时，不能把 board[x][y] == word[0] 这一条件放在最前面。因为如果 x 和 y 越界，那么这个地方代码就会报 List index out of range 的错误。 if 语句在进行判断的时候，是从前往后一个一个进行判断，如果前面的天剑就不通过，那么后面的条件根本就不会看。因此为了保证判断到 board[x][y] == word[0] 时索引不会越界，必须要把这一条件放到 0<=x<rows-1 and 0<=y<cols-1 这两个条件的后面；
• 其次，0<=x<rows-1 and 0<=y<cols-1 这两个条件本身就没写对，要么改成 0<=x<rows and 0<=y<cols ，要么改成 0<=x<=rows-1 and 0<=y<=cols-1 。

正确代码如下：

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        rows, cols = len(board), len(board[0])

        def explore(i, j, word):
            if not word:
                return True
            temp, board[i][j] = board[i][j], '*'
            success = False
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0<=x<rows and 0<=y<cols and board[x][y] == word[0] and explore(x, y, word[1:]):
                    success = True
                    break
            board[i][j] = temp
            return success

        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and explore(i, j, word[1:]):
                    return True
        return False

13. 机器人的运动范围

通常物体或者人在二维方格运动之类的问题都可以用回溯法解决。

网站上提供的答案不能应对 threshold=0 或 rows=0 或 cols=0 的情况，因此要额外加上一个判断：

if threshold < 0 or rows <= 0 or cols <= 0:
    return 0

threshold = 0 时，表示一步都没走，但机器人初始时就占据了一个格子，所以此时答案为 1 。

完整代码：

class Solution(object):
    def movingCount(self, threshold, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        if threshold < 0 or rows <= 0 or cols <= 0:
            return 0
        visited = [[False]*cols for _ in range(rows)]
        def get_sum(x, y):
            return sum(map(int, str(x)+str(y)))
    
        def movingCore(threshold, rows, cols, i, j):
            if get_sum(i, j) <= threshold:
                visited[i][j] = True
                for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
                    if 0<=x<rows and 0<=y<cols and not visited[x][y]:
                        movingCore(threshold, rows, cols, x, y)
    
        movingCore(threshold, rows, cols, 0, 0)
        return sum(sum(visited, []))

14. 剪绳子

什么样的问题可以用动态规划解决？

• 第一，问题的目标是要求得一个最优解（通常是最大值或最小值）；
• 第二，原问题可以递归地分解成很多个子问题，而且这些子问题也都存在各自的最优解；
• 第三，原问题似乎可以用递归的方法解决，但这样做可能会造成大量的重复。因此通常采用从上往下的方法分析问题，再从下往上求解问题，即先计算小问题的最优解并存储下来，再以此为基础求解大问题的最优解。
• 用自上而下的递归思路分析问题，基于自下而上的循环实现代码。

贪婪算法：

• 每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解；
• 但是为什么我们做出这样贪婪的选择就能够得到问题的最优解？这是需要通过数学的方式来证明的。

回溯法与动态规划：

• 回溯法很适合解决迷宫及其类似问题；
• 如果是求一个问题的最优解，那么可以尝试使用动态规划。如果在用动态规划分析问题时发现每一步都存在一个能得到最优解的选择，那么可以尝试使用贪婪算法。

时间复杂度为 、空间复杂度为 的通用方法：

class Solution(object):
    def maxProductAfterCutting(self,length):
        """
        :type length: int
        :rtype: int
        """
        # 长度至少为2，至少要剪两段
        if length == 2:
            return 1
        if length == 3:
            return 2
        
        product_mat = [0] * (length+1)
        product_mat[1] = 1
        product_mat[2] = 2
        product_mat[3] = 3
        
        for i in range(4, length+1):
            max_product = 0
            for j in range(1, int(i/2)+1):
                product = product_mat[j] * product_mat[i-j]
                if product > max_product:
                    max_product = product 
            product_mat[i] = max_product
        
        return product_mat[length]

这里要说明的是：

product_mat[1] = 1
product_mat[2] = 2
product_mat[3] = 3

并不是绳长分别为 1，2，3 时剪到的乘积的最大值，而是一些乘积项，即当剪断之后，如果绳长为 1 就乘以 1，绳长为 2 就乘以 2 ，绳长为 3 就乘以 3。从 product_mat[4] 开始，这个矩阵中存储的才是乘积的最大值：

product_mat[4] = product_mat[2] * product_mat[2] = 2 * 2 = 4

时间复杂度和空间复杂度均为 的贪婪算法：

• 当 时，尽可能多地剪长度为 3 的绳子；
• 当剩下的绳子长度为 4 时，把绳子剪成长度为 2 的两段绳子。

class Solution(object):
    def maxProductAfterCutting(self,length):
        """
        :type length: int
        :rtype: int
        """
        if length == 2:
            return 1
        if length == 3:
            return 2
        
        # 尽可能多地剪出3
        count3 = length // 3  # 余数为1或2
        # 如果余数为1，则少剪一段3，把4剪成两个2
        if length % 3 == 1:
            count3 -= 1
        count2 = (length - count3*3) // 2
        
        return (3**count3) * (2**count2)

15. 二进制中 1 的个数

• 左移运算符有可能会把左边的数位丢弃，右移运算符有可能会把右边的数位丢弃。
• 右移时如果是正数则左边补 0 ，如果是负数则左边补 1。
• 乘除法的效率比移位运算要低得多，因此要尽可能地用移位运算代替乘除法。
• 把一个整数减去 1 之后再和原来的整数做与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0 。
• 二进制表示中数字位数为 1 的个数也被称为汉明重量。

代码实现：(依据是：一个数 n 和 n-1 做与运算，相当于去掉了最右面的 1 。)

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n:
            count += 1
            n = n & (n-1)
        return count

16.数值的整数次方：

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        def cal_unsigned_pow(x, n):
            if n == 0:
                return 1
            if n == 1:
                return x
            ans = cal_unsigned_pow(x, n>>1)
            ans *= ans
            if n & 1 == 1: # 判断n是不是奇数
                ans *= x
            return ans
            
        if n < 0:
            return 1 / cal_unsigned_pow(x, -n)
        else:
            return cal_unsigned_pow(x, n)

需要注意的地方：

• 在计算幂次时，不是用 for 循环的方法每次去乘 x ，而是用递归的方法不断地计算平方，这样效率更高；
• 0 的 0 次方是没有意义的，这里将它的值定为 1 。

17.打印从 1 到最大的 n 位数

python 的 int 没有长度限制，所以直接打印：

def print_max_n_bit(n):
    for i in range(1, 10**n):
        print i

18-1. 删除链表的节点

• 在单向链表中删除一个节点的常规做法是从链表的头结点开始，顺序遍历查找要删除的节点，并在链表中删除该节点。（删除某个节点就是让它上一个节点的指针跳过当前节点直接指向下一个节点。）
  由于这种做法需要顺序查找，因此它的时间复杂度是 。
• 在单向链表中，节点中没有指向前一个节点的指针。
• 一种创新性的思考方法：当我们想删除一个节点时，并不一定要删除这个节点本身。可以先把下一个节点的内容复制出来覆盖想被删除的节点的内容，然后把下一个节点删除，这样就等价于删除了这个节点本身。
  如果想要删除的这个节点的下一个节点存在（即当前节点不是链表的最后一个节点），那么我们就可以在 的时间内把下一个节点的内容复制覆盖要删除的节点，并删除下一个节点。
  如果要删除的节点就是链表的尾节点，那么这种方法失效，此时只能采用常规方法，按顺序查找当前节点的上一个节点，这样时间复杂度依旧是 。
• 综合考虑以上两种情况，总的平均时间复杂度为 。
• 此外还要考虑两种特殊情况：
  • 一是初始链表中只有一个节点，此时删除时候链表为空，则链表的头节点应该指向 None ；
  • 二是想要删除的节点不在链表中。（这种情况可以看成是非法输入。）

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

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

19. 正则表达式匹配

如果 pattern 中没有 * ，则问题可以通过如下的递归来解决：

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

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

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

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

整个代码的思路是：

• 首先，不管哪种情况，由于 * 不可能出现在 pattern[0] 的位置，因此每次都要先判断第 0 个字符是否能匹配，判断的方法是：

  match_res = bool(text) and pattern[0] in {text[0], '.'}
  

• 当前 pattern 的长度大于 1 而且 pattern[1] == * 吗？

  • 如果上述条件满足，则又分为两条路：

    • match(text, pattern[2:])

    • match(text[1:], pattern)

      以上这两条路是并行执行的，而且只要有一条路满足就可以，所以要用 or 连接。

  • 如果上述条件不满足，就可以认为 pattern[0] 和 pattern[1] 里面均不包含 * （至少在当前 pattern 的前两个位置是没有 * 的，后面的位置有 * 的情况先不管。因为代码是递归进行的，所以后面的位置如果有 * ，早晚有一天这个 * 肯定会挪到 pattern[1] 的位置，到那时再对它进行处理也不迟。）。那么这种情况退化为最开始的那种没有 * 的情况，此时在进行下一轮递归时，text 和 pattern 都要往后挪一位，即 match(text[1:], pattern[1:]) 。

完整的代码如下：

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

测试样例及测试结果如下：

class Solution(object):
    def isMatch(self, text, pattern):
        print('text = {}, pattern = {}'.format(text, pattern))
        print()
        if not pattern: return not text
        match_res = bool(text) and pattern[0] in {text[0], '.'}
        
        if len(pattern) > 1 and pattern[1] == '*':
            print('text, pattern[2:] or text[1:], pattern :')
            return self.isMatch(text, pattern[2:]) or \
                   (match_res and self.isMatch(text[1:], pattern))                  
        else:
            print('text[1:], pattern[1:] :')
            return match_res and self.isMatch(text[1:], pattern[1:])

if __name__ == '__main__':
    sol = Solution()
    y = sol.isMatch("mississippi", "mis*is*ip*.")
    print(y)


"""输出结果"""
text = mississippi, pattern = mis*is*ip*.

text[1:], pattern[1:] :                   # 第一轮循环，各自去一个
text = ississippi, pattern = is*is*ip*.

text[1:], pattern[1:] :                   # 第二轮循环，仍然各自去一个
text = ssissippi, pattern = s*is*ip*.

text, pattern[2:] or text[1:], pattern :  # 第三轮循环，要进行抉择：
text = ssissippi, pattern = is*ip*.       # 程序先选的跳过当前pattern，但是这条路走不通，所以也就没有后序输出了

text[1:], pattern[1:] :                   # 然后返回抉择的地方，
text = sissippi, pattern = s*is*ip*.      # 选择第二条路，发现这条路可以走通

text, pattern[2:] or text[1:], pattern :  # 第四轮循环，再次面临抉择：
text = sissippi, pattern = is*ip*.        # 仍然先选第一条路，发现仍然走不通

text[1:], pattern[1:] :                   
text = issippi, pattern = s*is*ip*.       # 转而选第二条路

text, pattern[2:] or text[1:], pattern :
text = issippi, pattern = is*ip*.

text[1:], pattern[1:] :
text = ssippi, pattern = s*ip*.

text, pattern[2:] or text[1:], pattern :
text = ssippi, pattern = ip*.

text[1:], pattern[1:] :
text = sippi, pattern = s*ip*.

text, pattern[2:] or text[1:], pattern :
text = sippi, pattern = ip*.

text[1:], pattern[1:] :
text = ippi, pattern = s*ip*.

text, pattern[2:] or text[1:], pattern :
text = ippi, pattern = ip*.

text[1:], pattern[1:] :
text = ppi, pattern = p*.

text, pattern[2:] or text[1:], pattern :
text = ppi, pattern = .

text[1:], pattern[1:] :
text = pi, pattern = 

text = pi, pattern = p*.

text, pattern[2:] or text[1:], pattern :
text = pi, pattern = .

text[1:], pattern[1:] :
text = i, pattern = 

text = i, pattern = p*.

text, pattern[2:] or text[1:], pattern :
text = i, pattern = .

text[1:], pattern[1:] :
text = , pattern = 

True

20. 表示数值的字符串

这道题和 19 题一样，都是状态机问题（这类字符串匹配问题其实都是状态机问题），只不过第 19 题是无限状态机，而这一题是有限状态机。

代码：

class Solution(object):
  def isNumber(self, s):
      """
      :type s: str
      :rtype: bool
      """
      #define a DFA
      state = [{}, 
              {'blank': 1, 'sign': 2, 'digit':3, '.':4}, 
              {'digit':3, '.':4},
              {'digit':3, '.':5, 'e':6, 'blank':9},
              {'digit':5},
              {'digit':5, 'e':6, 'blank':9},
              {'sign':7, 'digit':8},
              {'digit':8},
              {'digit':8, 'blank':9},
              {'blank':9}]
      currentState = 1
      for c in s:
          if c >= '0' and c <= '9':
              c = 'digit'
          if c == ' ':
              c = 'blank'
          if c in ['+', '-']:
              c = 'sign'
          if c not in state[currentState].keys():
              return False
          currentState = state[currentState][c]
      if currentState not in [3,5,8,9]:
          return False
      return True

代码解析：

这是一个有限状态机问题。有限状态机也叫有穷自动机，即给定某个状态，它在接受某个输入之后会转到下一个状态，且总的状态数是有限的。

假设原始字符串为 s ，且假设有限状态机的初始状态为 1 状态，在这个状态时，有限状态机尚未接收到任何字符信息。当 s 中的第 0 个字符输入到初始状态时，可能会有以下五种情况：

• ，即 1 状态接收一个空格时，仍然保留 1 状态不变；
• ，即 1 状态接收一个 + 号或 - 号时，将转移到 2 状态；
• ，即 1 状态接收一个数字时，将转移到 3 状态；
• ，即 1 状态接收一个小数点时，将转移到 4 状态。
• ，即如果 1 状态接收到的字符不是以上 4 种，则程序将直接 return False 。

当状态机位于 2 状态时，表明状态机第一次接收到了一个 + 号或 - 号，此时欲使输入字符串是一个有效的数字，则 s[1] 只能是数字或小数点，即 2 状态只有两个后继状态：

• ，即 2 状态接收一个数字时，将转移到 3 状态；
• ，即 2 状态接收一个小数点时，将转移到 4 状态。

当状态机位于 3 状态时，表明状态机已经接收到了至少一个数字。而数字对后续字符的要求比较低，因此 3 状态存在四个后继状态：

• ，即 3 状态接收一个数字时，仍然返回到 3 状态。因为 3 状态接收一个数字后转移到的新状态仍然存在四个后继状态，而且这四个后继状态和 3 状态的后继状态是一样的，因此这个新状态就等效于 3 状态本身，所以 3 状态接收一个数字后仍然回到 3 状态；
• ，即 3 状态接收到一个小数点后，将进入到 5 状态；
• ，即 3 状态接收到字母 e 时，将进入到 6 状态；
• ，即 3 状态接收到一个空格时，将进入到 9 状态。

当状态机位于 4 状态时，表明状态机第一次接收到一个小数点，因为小数点对后续字符的要求比较苛刻，所以 4 状态只有一个后继状态：

• ，即 4 状态只能接收一个数字返回到 3 状态；

当状态机位于 5 状态时，由于 5 状态是由 3 状态接收一个小数点得来的，因此 5 状态有 3 种可行的后继状态：

• ，即 5 状态接收一个数字后重新返回 5 状态（原因和前面 3 状态接收一个数字后返回 3 状态是一样的）。注意这里不能返回 3 状态，因为当状态机位于 5 状态时，表明此时字符串中已经有了一个小数点。3 状态是可以接收小数点的，而 5 状态不能再接收小数点，因此 5 状态和 3 状态是不等价的，所以这里只能返回 5 状态；
• ，即 5 状态接收到字母 e 时，将进入到 6 状态；
• ，即 5 状态接收到一个空格时，将进入到 9 状态。

当状态机位于 6 状态时，由于 6 状态是状态机第一次接收到字母 e 后转移到的状态，而字母 e 后的指数部分只能接数字或正负号，因此 6 状态只有两种后继状态：

• ，即 6 状态接收一个 + 号或 - 号时，将转移到 7状态；
• ，即 6 状态接收一个数字时，将转移到 8 状态；

当状态机位于 7 状态时，由于 7 状态是由 6 状态接收一个正号或负号得来的，也就是说 7 状态只能接收数字，因此 7 状态只有一个后继状态：

• ，即 7 状态接收一个数字时，将转移到 8 状态。

当状态机位于 8 状态时，由于此时状态机中正负号、小数点、字母 e 都已经有了，所以 8 状态能接收的负号仅剩两种，即只有两个后继状态：

• ，即 8 状态接收一个数字后重新返回 8 状态；
• ，即 8 状态接收到一个空格时，将进入到 9 状态。

当状态机位于 9 状态时，这是状态机的最后一个状态，它是由其他状态接收空格转移而来的。当状态机进入 9 状态时，欲使原始字符串表示的是一个有效的数字，那么不管这个空格前面的字符是什么，这个空格后面的字符必须全部是空格，直到字符串结尾。因此 9 状态只有一个后继状态：

• ，即 9 状态接收一个空格时，仍然返回 9 状态。

状态转移图如下：

状态转移图

21. 调整数组顺序使奇数位于偶数前面

不稳定的解法（调整之后奇数之间或偶数之间的相对位置可能会发生变化）：

class Solution(object):
    def reOrderArray(self, array):
        """
        :type array: List[int]
        :rtype: void
        """
        left, right = 0, len(array)-1
        while left < right:
            while left < right and array[left] & 1 == 1: # 从前往后找偶数
                left += 1
            while left < right and array[right] & 1 == 0: # 从后往前找奇数
                right -= 1
            array[left], array[right] = array[right], array[left]

稳定但非 in-place 的解法：使用 deque 。

def reOrderArray(self, array):
    # write code here
    from collections import deque
    q = deque()
    n = len(array)
    for i in range(n):
        if array[-i-1] & 1 == 1:  # 从后找奇数
            q.appendleft(array[-i-1])
        if array[i] & 1 == 0:  #从前找偶数
            q.append(array[i])
    return q

22. 链表中倒数第 k 个节点

程序的鲁棒性（也叫健壮性）指的是程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。

以后在编写代码时一定要特别注意这一点，即如果有人恶意输入一些非法值，程序应该如何应对，必须在代码中体现出这些方面。

此外，这道题目给了我们一个启示：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针走的速度快一些（比如一次在链表中走上两步，或者让它先在链表中走上若干步），另外一个指针走的慢一些。这样就可以拿这两个指针之间的距离来做文章。比如另外一道题目：

求链表的中间节点。如果链表的节点总数为奇数，则返回中间节点；如果节点总数是偶数，则返回中间两个节点的任意一个。

为了解决这个问题，我们可以定义两个指针，让它们同时从链表的头结点出发。其中一个指针一次走一步，另一个指针一次走两步。则当走得快的指针到达链表的末尾时，走得慢的指针正好在链表的中间。

本题的代码：（用了两个指针，快指针先走 k-1 步，然后两个一起走。当快指针走到尾节点时，慢指针正好在倒数第 k 个节点。这里要注意代码的鲁棒性：k=0、输入空链表、k 大于链表的总长度。）

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

class Solution(object):
    def findKthToTail(self, pListHead, k):
        """
        :type pListHead: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not k: # 三种非鲁棒情形中唯一需要特别指出的是k=0的情形
            return None
        slow = fast = pListHead
        for i in range(k): # 输入空链表和k>len(链表)的情形已经包含在这里面了
            if fast:
                fast = fast.next
            else:
                return None
        while fast:
            slow, fast = slow.next, fast.next
        return slow

23. 链表中环的入口节点

这个问题要分三步来做：

• step 1：判断链表中是否有环，可以用一快一慢两个指针来判断；
• step 2：如果链表中有换，要得到环中节点的数目；
• step 3：用两个速度相同的指针 和 来找环的入口节点。初始时让两个指针都指向链表的头结点，假设链表中的环有 个节点，则让指针 先在链表上向前移动 步，然后两个指针以相同的速度向前移动。当第二个指针走到环的入口节点时，第一个指针已经绕着环走了一圈，重新返回到了入口节点。

上述步骤中的 step 1 和 step 2 可以合并起来做：快指针一次走两步，慢指针一次走一步，则当快指针和慢指针相遇时，快指针刚好比慢指针多走了 步（ 为环中的节点个数）。

又由于慢指针是从头结点出发的，因此上述过程中的慢指针可以直接用在 step 3 中：这个慢指针可以视为 step 3 中的 —— 它已经从头结点出发多走了 步。此时只要引入第三个慢指针（初始时让它指向链表的头结点）或者直接把头节点当做第三个慢指针。然后让它和 一起移动，当它们再次相遇时，第三个慢指针所指向的位置就是环的入口节点。

代码如下：

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = slow = head  # 可以这样写连等号
        # 检测是否有环
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if slow is fast:
                break
        else:
            return None
        while head is not slow:
            head, slow = head.next, slow.next
        return head

24. 反转链表

解决与链表相关的问题总是有大量的指针操作。

指针在等号左边时相当于指针的搬移，只有调用 next 方法才是修改节点的指向。

本题要用三个指针，从链表的头结点开始，一直遍历到最后一个节点：

• 第一个指针：指向当前节点的前一个节点，用于修改节点的指向；
• 第二个指针：指向要修改指向的当前节点；
• 第三个指针：指向当前节点的下一个节点，用于保存下一个节点的值，以防在修改当前节点的指向时链表断裂。

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        previous = None # 初始时，将头结点前面的那个节点置为None
        while head:
            head.next, previous, head = previous, head, head.next
        return previous # 最终previous指向尾节点，head指向尾节点后面的None

25. 合并两个排序的链表

循环的方法：

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l = head = ListNode(0) # 开辟一个新链表实际上就是开辟一个新的头结点
        while l1 and l2:
            if l1.val <= l2.val:
                l.next, l1 = l1, l1.next
            else:
                l.next, l2 = l2, l2.next
            l = l.next
        l.next = l1 or l2
        
        return head.next

26. 树的子结构

与二叉树相关的代码通常都会有大量的指针操作。而且与链表相比，树中的指针操作更多也更复杂。

但是不管是链表还是二叉树，每次在使用指针的时候，我们都要问自己这个指针有没有可能是空指针，如果是空指针我们要如何应对。

剑指offer中题目对应的代码（只需要考虑有没有子结构，不需要考虑子结构下面的其他部分）：

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

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        def is_same(s, t):
            if s and t:
                equal = s.val == t.val
                if not t.left and not t.right: # 如果没有左右子树，就直接退出
                    return equal
                else:
                    return equal and is_same(s.left, t.left) and is_same(s.right, t.right)
            else:
                return s is t
        stack = s and [s] # ***见备注***
        while stack:
            node = stack.pop()
            if node:
                if is_same(node, t):
                    return True
                stack.append(node.right)
                stack.append(node.left)

        return False

上面的代码中有一句很神奇的代码：

stack = s and [s]

这里的 and 类似与集合中的“与”操作， s 是一个布尔值，要么为 True ，要么为 False ，下面分析这两种情况：

• 如果 s 为 True ，则 True 和任何数相与，都等于这个数本身，因此此时上述代码等价于：

  stack = [s]
  

• 如果 s 为 False ，则 False 和任何数相与，结果都为 False ，因此此时上面的代码等价于：

  stack = False
  

leetcode 中题目对应的代码（不仅需要考虑有没有子结构，还需要考虑子结构下面的其他部分，条件更苛刻）：

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

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        def is_same(s, t):
            if s and t:
                return s.val == t.val and is_same(s.left, t.left) and is_same(s.right, t.right)
            else:
                return s is t
        stack = s and [s]
        while stack:
            node = stack.pop()
            if node:
                if is_same(node, t):
                    return True
                stack.append(node.right)
                stack.append(node.left)

        return False

上述代码中删掉了剑指offer上的一个知识点：如果树中的数包含浮点数，则 s.val == t.val 是非法的，因为两个浮点数不能直接比较大小，此时判断它们相等的方法是它们差的绝对值小于某个足够小的数，比如 0.0000001 。