3-1.數(shù)組中重復(fù)的數(shù)字

思路分析：如果不考慮時(shí)間復(fù)雜度根盒，則可以先對(duì)數(shù)組排序（需要 的時(shí)間），然后再?gòu)闹姓抑貜?fù)的數(shù)字秉剑。

如果不考慮空間復(fù)雜度，則可以額外使用一個(gè)字典稠诲，然后從頭到尾遍歷數(shù)組中的每個(gè)元素侦鹏。每遍歷到一個(gè)元素，就檢查它是否已經(jīng)在字典中吕粹，如果不在就把它添加到字典中种柑，如果在就表示有重復(fù)。字典的查找時(shí)間復(fù)雜度是 匹耕，遍歷整個(gè)數(shù)組的時(shí)間復(fù)雜度是 聚请，因此算法的時(shí)間復(fù)雜度是 ，但它提高時(shí)間效率是以一個(gè)額外的空間復(fù)雜度 為代價(jià)的稳其。

還有一種更優(yōu)的考慮：注意到數(shù)組中的數(shù)字都在 的范圍內(nèi)驶赏，如果這個(gè)數(shù)組中沒(méi)有重復(fù)的數(shù)字，那么當(dāng)數(shù)組排序之后數(shù)字 將出現(xiàn)在下標(biāo)為 的位置既鞠。而由于數(shù)組中有重復(fù)的數(shù)字煤傍，那么有些位置可能存在多個(gè)數(shù)字，同時(shí)有些位置可能沒(méi)有數(shù)字嘱蛋。

基于這種考慮蚯姆，我們從頭到尾遍歷數(shù)組中的每個(gè)數(shù)字五续。當(dāng)遍歷到下標(biāo)為 的數(shù)字時(shí)，首先比較這個(gè)數(shù)字（用 表示）是不是等于 龄恋。如果是疙驾，就表明這個(gè)數(shù)字位于本來(lái)就屬于它的位置；如果不是郭毕，那我們把它和第 個(gè)位置上的數(shù)字進(jìn)行比較它碎。如果它等于第 個(gè)位置上的數(shù)字，那就找到了一個(gè)重復(fù)的數(shù)字显押；如果不等扳肛，那就把 放到第 個(gè)位置上，同時(shí)原來(lái)在第 個(gè)位置上的數(shù)字放到第 個(gè)位置上（也就是把第 個(gè)數(shù)字和第 個(gè)數(shù)字交換）乘碑。然后繼續(xù)比較這個(gè)下標(biāo) 上的數(shù)字挖息，直到這個(gè)位置上的數(shù)字等于 ，才進(jìn)行下一個(gè)位置上的數(shù)字比較兽肤。對(duì)于每一個(gè)位置上的數(shù)字都是如此旋讹。也就是說(shuō)，代碼中會(huì)存在兩個(gè)循環(huán)轿衔。代碼如下：

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

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：代碼中盡管有一個(gè)兩重循環(huán)，但每個(gè)數(shù)字最多只要交換兩次就能找到屬于它的位置睦疫，因此總的時(shí)間復(fù)雜度是 害驹；
• 空間復(fù)雜度：所有的操作都是在輸入數(shù)組上進(jìn)行的，不需要額外分配內(nèi)存宛官，因此空間復(fù)雜度是 底洗。

3-2.不修改數(shù)組找出重復(fù)的數(shù)字

思路分析：假如沒(méi)有重復(fù)的數(shù)字亥揖，那么在 1～n 的范圍內(nèi)最多只能有 n 個(gè)數(shù)字费变，而現(xiàn)在數(shù)組中有 n+1 個(gè)數(shù)字吁峻，就表明至少肯定是在某個(gè)范圍內(nèi)多了一個(gè)數(shù)字帮匾，那么我們就可以根據(jù)某個(gè)范圍內(nèi)數(shù)字的個(gè)數(shù)來(lái)判斷是否有重復(fù)的數(shù)字夏跷。

把原數(shù)組從中間二分，假設(shè)中間數(shù)字是 m亲雪，那么左邊一半即為 1～m，右邊一半為 m+1～n。如果左邊一半的數(shù)字個(gè)數(shù)超過(guò)了 m撩幽，就表明在這個(gè)區(qū)間里一定包含了重復(fù)的數(shù)字酱虎；否則撒妈，右邊的一半?yún)^(qū)間里一定包含了重復(fù)的數(shù)字棋蚌。然后盛垦，我們對(duì)包含重復(fù)數(shù)字的區(qū)間繼續(xù)二分蝶俱，如此進(jìn)行下去，直到最終找到重復(fù)的數(shù)字浅侨。代碼如下：

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

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：如果輸入長(zhǎng)度為 n 的數(shù)組不见，那么函數(shù) count_range 將被調(diào)用 次灶似，每次都需要 的時(shí)間春感，因此總的時(shí)間復(fù)雜度是 ；
• 空間復(fù)雜度：

算法的不足：該算法不能保證找出所有重復(fù)的數(shù)字谦秧，比如在 1～2 的范圍內(nèi)有 1 和 2 兩個(gè)數(shù)字集歇，這個(gè)范圍內(nèi)的數(shù)字也出現(xiàn)了兩次姑蓝，此時(shí)該算法無(wú)法判斷是每個(gè)數(shù)字各出現(xiàn)一次還是某個(gè)數(shù)字出現(xiàn)了兩次宙暇。

第4題：二維數(shù)組中的查找

思路分析：首先選取數(shù)組中右上角的數(shù)字型奥，如果該數(shù)字等于要查找的數(shù)字收夸，則查找過(guò)程結(jié)束咽瓷；如果該數(shù)字大于要查找的數(shù)字钻洒，則剔除這個(gè)數(shù)字所在的列头遭；如果該數(shù)字小于要查找的數(shù)字，則剔除這個(gè)數(shù)字所在的行疾就。如此盒延，直到找到要查找的數(shù)字计露，或把整個(gè)數(shù)組剔空该押。

# -*- coding:utf-8 -*-
class Solution:
    # array 二維列表
    def Find(self, target, array):
        # write code here
        row, col = 0, len(array[0])-1 # 要從第0行最后一列開(kāi)始
        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方法：將序列中的元素以指定的字符連接生成一個(gè)新的字符串净赴。例子：

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.從尾到頭打印鏈表

思路分析：按照從頭到尾的順序遍歷鏈表金度，將每一個(gè)節(jié)點(diǎn)的值保存到一個(gè)list中，最后再將list中的元素反過(guò)來(lái)就可以了。

# 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后面不能有小括號(hào)
            head = head.next  # next后面不能有小括號(hào)
        return stack[::-1]  # ::-1將list進(jìn)行反轉(zhuǎn)

7.重建二叉樹(shù)

知識(shí)拓展：

二叉樹(shù)的前序华望、中序建蹄、后序遍歷的遞歸旭绒、非遞歸實(shí)現(xiàn)及層次遍歷的實(shí)現(xiàn)：https://blog.csdn.net/weixin_45595437/article/details/100598886

二叉樹(shù)的遍歷代碼：

# 定義節(jié)點(diǎn)類
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:  # 表明此時(shí)樹(shù)還是空的
            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:  # 否則，就對(duì)右孩子賦值
                treeNode.rchild = node
                self.myQueue.append(treeNode.rchild)
                self.myQueue.pop(0) # 如果右孩子已經(jīng)賦上了值袋倔，就說(shuō)明這個(gè)二叉樹(shù)單元已經(jīng)完整了嚣艇，此時(shí)要彈出父節(jié)點(diǎn)
    
    # 前序遍歷遞歸實(shí)現(xiàn)
    def pre_order_recur(self, root): # 無(wú)論是樹(shù)還是鏈表慌洪，對(duì)它們操作傳入的都是根節(jié)點(diǎn)
        if root == None:
            return
        print(root.elem, end=' ')
        self.pre_order_recur(root.lchild) # 遞歸調(diào)用自身時(shí)必須要加self
        self.pre_order_recur(root.rchild)
    
    # 中序遍歷遞歸實(shí)現(xiàn)
    def in_order_recur(self, root):
        if root == None:
            return
        self.in_order_recur(root.lchild)  # 遞歸調(diào)用自身時(shí)必須要加self
        print(root.elem, end=' ')
        self.in_order_recur(root.rchild)  # 遞歸調(diào)用自身時(shí)必須要加self
    
    # 后序遍歷遞歸實(shí)現(xiàn)
    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=' ')
    
    # 前序遍歷非遞歸實(shí)現(xiàn)（非遞歸寫(xiě)法是用棧來(lái)實(shí)現(xiàn)的）
    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
    
    # 中序遍歷非遞歸實(shí)現(xiàn)（也是用棧芝此，思路和前序遍歷一模一樣怎炊，只是print的位置發(fā)生了變化）
    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
    
    # 后序遍歷非遞歸實(shí)現(xiàn)（用棧，而且要用兩個(gè)棧）
    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:  # 這個(gè)棧中保存的是后序遍歷的逆序
            node = myStack2.pop()
            print(node.elem, end=' ')

"""這部分刪掉剥汤，層次遍歷見(jiàn)后面的最新代碼
    # 層次遍歷/廣度優(yōu)先遍歷（用隊(duì)列實(shí)現(xiàn)）
    # 前序、中序和后序遍歷都屬于深度優(yōu)先遍歷
    def broad_first_search(self, root):
        if root == None:
            return
        node = root 
        myQueue = []
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0) # 棧和隊(duì)列表面上看起來(lái)都是一個(gè)列表瑞筐，但它們之間的區(qū)別就在于：棧是myStack.pop()峭范，即彈出最后一個(gè)元素（棧頂元素），從而體現(xiàn)了后進(jìn)先出纱控；而隊(duì)列則是myQueue.pop(0)辆毡，即彈出最前邊的元素甜害，從而體現(xiàn)了先進(jìn)先出舶掖。
            print(node.elem, end=' ')
            if node.lchild:
                myQueue.append(node.lchild)
            if node.rchild:
                myQueue.append(node.rchild)
"""

    # 更新于2019.12.28
    # 層次遍歷/廣度優(yōu)先遍歷（用隊(duì)列實(shí)現(xiàn)）
    # 前序、中序和后序遍歷都屬于深度優(yōu)先遍歷
    def broad_first_search(self, root):
        from collections import deque
        queue = deque([root])
        # res = []
        while queue:
            node = queue.popleft() # 棧和隊(duì)列表面上看起來(lái)都是一個(gè)列表尔店，但它們之間的區(qū)別就在于：棧是myStack.pop()访锻，即彈出最后一個(gè)元素（棧頂元素），從而體現(xiàn)了后進(jìn)先出闹获；而隊(duì)列則是myQueue.pop(0)期犬，即彈出最前邊的元素，從而體現(xiàn)了先進(jìn)先出避诽。
            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()

思路分析：前序遍歷序列的第一個(gè)數(shù)必是整個(gè)二叉樹(shù)的根節(jié)點(diǎn)龟虎。在找到這個(gè)根節(jié)點(diǎn)之后，在中序遍歷序列中找到該根節(jié)點(diǎn)所在的位置（這里要假設(shè)樹(shù)中沒(méi)有重復(fù)的元素）沙庐，那么在這個(gè)根節(jié)點(diǎn)左側(cè)的所有元素就構(gòu)成了整個(gè)二叉樹(shù)的左子樹(shù)鲤妥，右側(cè)的所有元素構(gòu)成整個(gè)二叉樹(shù)的右子樹(shù)。假設(shè)左子樹(shù)中元素的總個(gè)數(shù)為 拱雏，那么前序遍歷序列中棉安，位于根節(jié)點(diǎn)右邊的連續(xù) 個(gè)元素都將是左子樹(shù)中的元素，它和中序遍歷序列中根節(jié)點(diǎn)左邊的所有元素是完全對(duì)應(yīng)的铸抑。如果把這部分元素取出來(lái)贡耽，遞歸地把它們?cè)俜殖勺蟆⒂易訕?shù)鹊汛，那么整個(gè)問(wèn)題就可以用遞歸的方法去解決：就是一個(gè)不斷劃分左右子樹(shù)的過(guò)程蒲赂，遞歸的邊界是用于劃分的列表為空。

根節(jié)點(diǎn)刁憋、左右子樹(shù)在先序遍歷和中序遍歷中的位置分別如下所示：

先序遍歷：根節(jié)點(diǎn) | 左子樹(shù) | 右子樹(shù)
中序遍歷：左子樹(shù) | 根節(jié)點(diǎn) | 右子樹(shù)

需要特別注意的是它們之間的邊界到底應(yīng)該取到哪里滥嘴。

Python的 index 方法：在給定字符串中查找是否包含目標(biāo)字符串，如果包含至耻，則返回索引的起始位置若皱；否則镊叁，拋出異常。e.g.

# 默認(rèn)查找范圍是從索引為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) # 因?yàn)樗饕菑?開(kāi)始的走触，所以cut是幾意系，cut前面就會(huì)有幾個(gè)元素，這個(gè)數(shù)字用于后面處理邊界
        root.left = self.buildTree(preorder[1:cut+1], inorder[:cut]) # 從1后面（包括1）取cut個(gè)元素饺汹，inorder取前面cut個(gè)元素
        root.right = self.buildTree(preorder[cut+1:], inorder[cut+1:])
        return root

8.二叉樹(shù)的下一個(gè)節(jié)點(diǎn)

分析：

• 如果一個(gè)節(jié)點(diǎn)有右子樹(shù)，那么它的下一個(gè)節(jié)點(diǎn)就是它的右子樹(shù)中的最左子節(jié)點(diǎn)痰催；
• 如果一個(gè)節(jié)點(diǎn)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)兜辞，那么它的下一個(gè)節(jié)點(diǎn)就是就是它的父節(jié)點(diǎn)；
• 如果一個(gè)節(jié)點(diǎn)既沒(méi)有右子樹(shù)夸溶，并且它還是它的父節(jié)點(diǎn)的右子節(jié)點(diǎn)逸吵，那么我們就沿著指向父節(jié)點(diǎn)的指針一直向上找，直到找到這樣一個(gè)節(jié)點(diǎn)：它是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)缝裁。如果這樣的節(jié)點(diǎn)存在扫皱，那么這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就是我們要找的下一個(gè)節(jié)點(diǎn)。如果找不到這樣的節(jié)點(diǎn)捷绑，那么此時(shí)要尋找的下一個(gè)節(jié)點(diǎn)不存在韩脑。

代碼：

# -*- 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
        # 如果該節(jié)點(diǎn)有右子樹(shù)
        if pNode.right:  
            node = pNode.right
            while node.left:
                node = node.left
            return node
        # 如果該節(jié)點(diǎn)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)
        # 或者如果該節(jié)點(diǎn)既沒(méi)有右子樹(shù)，又不是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)
        # 這兩個(gè)合并起來(lái)寫(xiě)
        while pNode.next:
            parent_node = pNode.next
            if parent_node.left == pNode:
                return parent_node
            pNode = parent_node
        
        return None

9-1.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

分析：通常棧是一個(gè)不考慮排序的數(shù)據(jù)結(jié)構(gòu)粹污，需要在 時(shí)間內(nèi)才能找到棧中最大或最小的元素段多。

考慮一個(gè)棧stack1，將三個(gè)元素a, b, c依次壓入棧中壮吩，則c將位于棧頂进苍。此時(shí)如果想模擬隊(duì)列的彈出操作，則應(yīng)該a最先被彈出鸭叙，但事實(shí)情況是c將最先被彈出觉啊。

如果每新來(lái)一個(gè)元素，我們都把它放在棧底而不是棧頂沈贝，那么最新來(lái)的元素將最后被彈出杠人，便實(shí)現(xiàn)了隊(duì)列的操作。如何做到這一點(diǎn)呢宋下？這時(shí)需要一個(gè)額外的棧stack2來(lái)輔助這一操作：每新來(lái)一個(gè)元素搜吧，我們都把stack1中原有的元素全部搬到stack2中，然后將新來(lái)的元素append到stack1中杨凑，最后再把原來(lái)的元素再搬回來(lái)滤奈，這樣新來(lái)的元素將總是會(huì)出現(xiàn)在棧底。代碼如下：

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取的是棧頂?shù)脑?        """
        Get the front element.
        :rtype: int
        """
        return self.s1[-1] # s1中棧頂?shù)脑厥亲钕冗M(jìn)來(lái)的元素
        

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

9-2.用兩個(gè)隊(duì)列實(shí)現(xiàn)棧

思路分析：用deque（雙向隊(duì)列）實(shí)現(xiàn)撩满。假設(shè)對(duì)于一個(gè)deque來(lái)說(shuō)蜒程，最左邊是隊(duì)首绅你，最右邊是隊(duì)尾。

對(duì)于一個(gè)隊(duì)列來(lái)說(shuō)昭躺，新來(lái)的元素只能添加到隊(duì)尾忌锯。而如果把這個(gè)隊(duì)列想象成棧的話，那么最左邊應(yīng)該是棧頂领炫，最右邊應(yīng)該是棧底（這樣的話出棧操作和出隊(duì)操作就可以保持一致了——都是從最左邊出來(lái)）偶垮。我們現(xiàn)在需要做的是：每新來(lái)一個(gè)元素，我們都把它添加到最左邊而不是最右邊帝洪。如何實(shí)現(xiàn)這一操作呢似舵？用一個(gè)額外的隊(duì)列就可以實(shí)現(xiàn)。假設(shè)q1是主體隊(duì)列葱峡，q2是輔助隊(duì)列砚哗。我們現(xiàn)在想把一個(gè)新的元素 添加到q1的隊(duì)首，此時(shí)我們這樣做：先把 添加到空的q2中砰奕，然后讓q1中的元素逐個(gè)出隊(duì)蛛芥，并逐個(gè)進(jìn)入q2，這樣 在q2中的位置便是在最左邊军援，此時(shí)再把q1和q2交換一下仅淑，便可以達(dá)到目標(biāo)。代碼如下：

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指的是排在隊(duì)列最前面的元素
        """
        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是棧頂元素胸哥，隊(duì)列的top是隊(duì)首元素漓糙。

下列語(yǔ)句即使是用在判斷或循環(huán)語(yǔ)句里，也會(huì)實(shí)際執(zhí)行一次 pop() 操作烘嘱，因此盡量不要使用這樣的判斷語(yǔ)句：

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

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

拓展：

僅用一個(gè)deque就可以實(shí)現(xiàn)和上述代碼同樣的效果：

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.斐波那契數(shù)列

拓展：通常運(yùn)用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)都是用遞歸的思路分析問(wèn)題昆禽，但由于遞歸分解的子問(wèn)題中存在大量的重復(fù)，因此我們總是采用自下而上的循環(huán)來(lái)實(shí)現(xiàn)代碼蝇庭。一句話總結(jié)即：用遞歸分析問(wèn)題并基于循環(huán)編寫(xiě)代碼醉鳖。

思路分析：關(guān)鍵是要避免重復(fù)運(yùn)算（即避免遞歸）。遞歸算法可以看做是”從頂?shù)降住暗姆椒ㄏ冢梢愿臑椤睆牡椎巾敗暗难h(huán)來(lái)實(shí)現(xiàn)：

"""這個(gè)代碼不是最精簡(jiǎn)的盗棵，更精簡(jiǎn)的代碼參考后續(xù)分析"""
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): # 只有當(dāng)N>=2時(shí)才會(huì)進(jìn)入這個(gè)循環(huán)體
            fn1, fn2 = fn1+fn2, fn1 # 只需要保存fn1, fn2這兩個(gè)中間變量即可
        return fn1

以上代碼可以進(jìn)一步改進(jìn)： N == 1 的情形可以合并到for循環(huán)中。Python的 range 其實(shí)返回的是一個(gè)列表北发，如 range(5) 返回 [0, 1, 2, 3, 4] 纹因。如果 range 里面的數(shù)字是0，那么返回一個(gè)空列表： [] 琳拨，此時(shí)再用for去遍歷這個(gè)列表時(shí)將會(huì)直接跳過(guò)瞭恰，即for循環(huán)不執(zhí)行。因此以上代碼可以進(jìn)一步簡(jiǎn)化為：

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.排序問(wèn)題

比較類排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序狱庇，由于其時(shí)間復(fù)雜度無(wú)法突破 惊畏，因此也稱為非線性時(shí)間比較類排序恶耽。它主要包括：

• 交換排序：包括冒泡排序和快速排序；
• 插入排序：包括簡(jiǎn)單插入排序和希爾排序颜启；
• 選擇排序：包括簡(jiǎn)單選擇排序和堆排序偷俭；
• 歸并排序：包括二路歸并排序和多路歸并排序。

非比較類排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序缰盏，它可以突破基于比較排序的時(shí)間下界涌萤，以線性時(shí)間運(yùn)行，因此也稱為線性時(shí)間非比較類排序口猜。它主要包括：

• 計(jì)數(shù)排序负溪；
• 桶排序；
• 基數(shù)排序暮的。

它們的復(fù)雜度及穩(wěn)定性如下：（時(shí)間復(fù)雜度不是說(shuō)跑完這個(gè)算法需要花費(fèi)多少時(shí)間，而是隨著n的增加淌实，算法的操作次數(shù)將以什么樣的趨勢(shì)增加冻辩。空間復(fù)雜度反映的是隨著n的增加拆祈，算法消耗的空間資源將以什么樣的趨勢(shì)增加恨闪。穩(wěn)定性：假設(shè)排序前a=b且a在b的前面，如果排序后a仍然在b的前面放坏，則說(shuō)這個(gè)算法是穩(wěn)定的咙咽。如果排序后a不一定是在b的前面，則說(shuō)這個(gè)算法是不穩(wěn)定的淤年。）

排序方法	平均時(shí)間復(fù)雜度	最好時(shí)間復(fù)雜度	最壞時(shí)間復(fù)雜度	空間復(fù)雜度	穩(wěn)定性
冒泡排序					穩(wěn)定
快速排序					可以穩(wěn)定
簡(jiǎn)單插入排序					穩(wěn)定
希爾排序					不穩(wěn)定
簡(jiǎn)單選擇排序					不穩(wěn)定
堆排序					不穩(wěn)定
歸并排序					穩(wěn)定
計(jì)數(shù)排序					穩(wěn)定
桶排序					穩(wěn)定
基數(shù)排序					穩(wěn)定

（1）冒泡排序：

• 一句話總結(jié)：冒泡排序的核心思想就是比較和交換钧敞。

• 具體操作過(guò)程：比較相鄰的元素，如果后面的元素比前面的大麸粮，就交換它們兩個(gè)（或者反過(guò)來(lái)也可以）溉苛。這樣經(jīng)過(guò)一輪比較和交換，最大（或最信濉）的元素就會(huì)出現(xiàn)在序列的末尾愚战。然后再進(jìn)行第二輪比較和交換......如此進(jìn)行下去，直到最后一輪比較和交換完成（最后一輪將只剩下兩個(gè)元素進(jìn)行比較和交換）齐遵。
  整個(gè)過(guò)程中寂玲，數(shù)值較小的數(shù)字將會(huì)像水里的泡泡一樣逐漸“浮”到水面，這便是冒泡排序名字的由來(lái)梗摇。

• Python實(shí)現(xiàn)：

  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
  

• 時(shí)間復(fù)雜度：假設(shè)有 個(gè)數(shù)拓哟，則比較和交換的過(guò)程總共需要進(jìn)行 輪。這 輪的比較和交換過(guò)程無(wú)論是在最好的情況（即序列本來(lái)就是有序序列）還是在最壞的情況（即數(shù)組完全逆序）下都是少不了的伶授，因此它決定了冒泡排序時(shí)間復(fù)雜度的下限（即最好時(shí)間復(fù)雜度）（注意這里的比較操作不算在時(shí)間復(fù)雜度之內(nèi)）彰檬。在最壞情況下伸刃，在每一輪比較過(guò)程中，每?jī)蓚€(gè)相鄰的元素都需要交換逢倍，兩兩交換的時(shí)間復(fù)雜度是 捧颅，因此最壞情況下的時(shí)間復(fù)雜度為 。
  綜上较雕，冒泡排序最好情況下的時(shí)間復(fù)雜度是 (發(fā)生在序列原本就已經(jīng)有序的情況下)碉哑，最壞情況下的時(shí)間復(fù)雜度為 (發(fā)生在序列完全逆序的情況下)，平均時(shí)間復(fù)雜度仍為 亮蒋。

• 空間復(fù)雜度：由于是 in-place 操作扣典，所以空間復(fù)雜度是 。

• 穩(wěn)定性：由于當(dāng)相鄰的數(shù)字相等時(shí)不發(fā)生交換慎玖，因此冒泡排序是穩(wěn)定的贮尖。

• Python實(shí)現(xiàn)：

  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）快速排序：

• 一句話總結(jié)：快速排序就是不斷地將序列分為一個(gè)數(shù)值較大的序列和一個(gè)數(shù)值較小的序列。

• 快速排序是一種遞歸的方法趁怔，采用的是分治策略（分治不一定是二分）湿硝；

• 具體操作過(guò)程：從序列中挑出一個(gè)元素（比如序列末尾的元素），將其稱之為“基準(zhǔn)”润努。然后遍歷序列中剩余的元素关斜，將所有小于基準(zhǔn)值的元素都放到基準(zhǔn)的左邊，大于基準(zhǔn)值的元素都放到基準(zhǔn)的右邊铺浇，等于基準(zhǔn)值的元素理論上可以放到任何一邊（但如果要想使快速排序算法是穩(wěn)定的痢畜，則當(dāng)基準(zhǔn)值每次都取序列的首個(gè)元素時(shí)，應(yīng)將等于基準(zhǔn)值的元素放到基準(zhǔn)的右邊鳍侣；當(dāng)基準(zhǔn)值每次都取序列的末尾元素時(shí)丁稀，應(yīng)將等于基準(zhǔn)值的元素放到基準(zhǔn)的左邊。）這樣就把原序列分成了兩部分倚聚，然后遞歸地將這兩部分再不斷地分成更小的兩部分二驰，直到兩部分序列中的元素個(gè)數(shù)都不超過(guò)1。

• 時(shí)間復(fù)雜度：最好的情況是每次都能將序列二分（即左右兩邊序列的長(zhǎng)度相等秉沼，這個(gè)時(shí)候基準(zhǔn)值不一定是整個(gè)序列的中位數(shù)）桶雀，這樣不斷地二分是最節(jié)省時(shí)間的，此時(shí)的時(shí)間復(fù)雜度為 唬复，可以通過(guò)數(shù)學(xué)式子推倒出來(lái)：
  假設(shè)對(duì)一個(gè)長(zhǎng)度為 的序列矗积，我們需要用 的時(shí)間對(duì)它進(jìn)行排序。由于每次都要遍歷一遍序列敞咧，因此每次都要花費(fèi) 的時(shí)間來(lái)將原序列劃分為兩個(gè)長(zhǎng)度減半的序列棘捣，由此可得到遞推公式：
  
  其中， 休建。因此最好情況下的時(shí)間復(fù)雜度是 乍恐。
  在最壞的情況下评疗，每次左右兩邊的序列都有一個(gè)是空的，相當(dāng)于原序列每次只減少了一個(gè)元素茵烈，這樣一個(gè)長(zhǎng)度為 的序列就需要 次才能使序列的長(zhǎng)度減少到 1 百匆，而每次又都需要花費(fèi) 的時(shí)間來(lái)進(jìn)行劃分，因此最壞情況下的時(shí)間復(fù)雜度為 呜投。

• 空間復(fù)雜度：在每一輪都需要花費(fèi) 的額外空間來(lái)存儲(chǔ)原序列中的元素加匈，最好情況下需要 輪，最壞情況下需要 輪仑荐，因此空間復(fù)雜度為 ～ 雕拼。

• 穩(wěn)定性：前已述及，要看基準(zhǔn)數(shù)怎么選粘招，可以將快速排序設(shè)計(jì)成穩(wěn)定的啥寇。

• python實(shí)現(xiàn)：

  def quickSort(nums):
      if len(nums) <= 1:  # 遞歸算法先寫(xiě)遞歸基
          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）簡(jiǎn)單插入排序

• 一句話總結(jié)：在已排序序列中從后向前掃描战秋，不斷地找新來(lái)元素對(duì)應(yīng)的位置并插入谆构。

• 具體操作過(guò)程：從原始序列的第2個(gè)元素開(kāi)始们衙，每次取出一個(gè)元素耍铜，這個(gè)元素左邊的序列是已經(jīng)排好序的。我們要在這個(gè)排好序的序列中找到這個(gè)新來(lái)的元素對(duì)應(yīng)的位置谋减，方法是在已排序的序列中從后向前掃描，如果當(dāng)前掃描到的元素大于新來(lái)的元素，就把這個(gè)掃描到的元素向后挪一位难裆；否則，就把這個(gè)新來(lái)的元素放到當(dāng)前掃描到的元素的后面镊掖。
  由此可見(jiàn)乃戈，簡(jiǎn)單插入排序是 in-place 的，因此空間復(fù)雜度為 亩进。而且簡(jiǎn)單插入排序是穩(wěn)定的症虑。

• 時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度為 。
  在最好的情況下归薛，每次新來(lái)的元素都比已排序序列中任何一個(gè)元素都大谍憔，即每次都不需要挪動(dòng)元素，只需要把新來(lái)的元素放到已排序序列的末尾即可主籍，這個(gè)過(guò)程在 的時(shí)間內(nèi)即可完成习贫。而遍歷整個(gè)序列需要花費(fèi) 的時(shí)間，因此最好情況下的時(shí)間復(fù)雜度為 千元。
  在最壞的情況下苫昌，每次新來(lái)的元素都比已排序序列中任何一個(gè)元素都小，此時(shí)每次都要將已排序序列中所有元素向后挪一位幸海，這將花費(fèi) 的時(shí)間祟身。而遍歷操作也需要花費(fèi) 的時(shí)間奥务，因此最壞情況下的時(shí)間復(fù)雜度為 。

• 空間復(fù)雜度：前已述及袜硫，為 氯葬。

• 穩(wěn)定性：前已述及，是穩(wěn)定的父款。

• python實(shí)現(xiàn)：

  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）希爾排序

• 一句話總結(jié)：通過(guò)一個(gè)增量序列將原序列劃分成若干個(gè)子序列溢谤，然后分別對(duì)這些子序列進(jìn)行簡(jiǎn)單插入排序。希爾排序也叫遞減增量排序憨攒。

• 具體實(shí)現(xiàn)過(guò)程：

  • 首先選擇一個(gè)逐漸較小的增量序列 世杀，其中 ，且 肝集；（在實(shí)際的操作過(guò)程中瞻坝，通常取 且對(duì)其進(jìn)行取整。）
  • 增量序列中的每一個(gè) 都將原序列劃分成 個(gè)子序列杏瞻，我們要對(duì)這 個(gè)子序列分別進(jìn)行簡(jiǎn)單插入排序所刀；
  • 增量序列中總共有 個(gè)值，因此第二步總共需要進(jìn)行 輪捞挥，且最后一輪的增量為 1浮创，即為簡(jiǎn)單插入排序。因此希爾排序中前面的所有輪都可以看做是為最后一輪做準(zhǔn)備的砌函，待最后一輪結(jié)束斩披，整個(gè)排序工作也就完成了。

• 需要注意的地方：
  希爾排序最后一趟的增量因子必須為 1（即最后一趟即為簡(jiǎn)單插入排序）讹俊；
  在每一趟排序結(jié)束之后垦沉，都將增量因子減小為原來(lái)的一半，直到最終減小到 1仍劈。

• 時(shí)間復(fù)雜度分析：希爾排序的時(shí)間復(fù)雜度與增量（即步長(zhǎng)gap）的選取有關(guān)厕倍。通常認(rèn)為，希爾排序的平均時(shí)間復(fù)雜度為 贩疙。
  當(dāng)增量為1時(shí)讹弯，希爾排序退化成了簡(jiǎn)單插入排序，因此希爾排序在最好情況下的時(shí)間復(fù)雜度為 这溅，在最壞情況下的時(shí)間復(fù)雜度為 组民。

• 空間復(fù)雜度分析：希爾排序是 in-place 的，因此空間復(fù)雜度為 芍躏。

• 穩(wěn)定性：希爾排序是不穩(wěn)定的邪乍。對(duì)于相同的兩個(gè)數(shù)，可能由于分在不同的組中而導(dǎo)致它們的順序發(fā)生變化。

• python實(shí)現(xiàn)：

  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）簡(jiǎn)單選擇排序

• 一句話總結(jié)：不斷地尋找未排序序列的最值庇楞，將其逐個(gè)添加到已排序序列的末尾榜配。

• 具體操作過(guò)程：以尋找未排序序列的最小值為例。首先尋找整個(gè)序列的最小值吕晌，然后蛋褥，為了減小空間復(fù)雜度，采取 in-place 操作——將其和序列的首個(gè)元素進(jìn)行交換睛驳，這樣便排好了第一個(gè)元素烙心。當(dāng)?shù)谝粋€(gè)元素排好序之后，未排序序列就是從第二個(gè)元素起直到序列結(jié)束乏沸。我們需要做的就是在這一未排序序列中找到最小值淫茵，然后將其和未排序序列的首個(gè)元素進(jìn)行交換（這一操作等價(jià)于是將這個(gè)最小值添加到已排序序列的末尾）。然后在剩余的未排序序列中重復(fù)上述過(guò)程蹬跃，直至未排序序列的長(zhǎng)度減小到1匙瘪。

• 時(shí)間復(fù)雜度分析：無(wú)論原始序列是否是有序的，選擇排序的兩趟遍歷是少不了的蝶缀，因此不管是最好還是最壞情況丹喻，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度均為 ，平均時(shí)間復(fù)雜度也為 翁都。

• 空間復(fù)雜度分析：in-place 操作碍论，空間復(fù)雜度為 。

• 穩(wěn)定性分析：由于簡(jiǎn)單選擇排序涉及到交換過(guò)程柄慰，假設(shè)有兩個(gè)相等的元素鳍悠，如果左邊那個(gè)相等的元素先被交換到后面，那么最終排序的結(jié)果可能會(huì)打亂這兩個(gè)相等的元素在原序列中的順序先煎。因此簡(jiǎn)單選擇排序是不穩(wěn)定的贼涩。

• python實(shí)現(xiàn)：

  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）堆排序

• 前置知識(shí)：

  • 二叉樹(shù)：每個(gè)節(jié)點(diǎn)至多擁有兩棵子樹(shù)（即二叉樹(shù)中不存在度大于2的節(jié)點(diǎn)）巧涧，并且二叉樹(shù)的子樹(shù)有左右之分薯蝎，其次序不能任意顛倒。
  • 完全二叉樹(shù)：除最后一層外谤绳，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值占锯，在最后一層上只缺少右邊的若干節(jié)點(diǎn)，并且所有的葉子節(jié)點(diǎn)都向左對(duì)齊（即孩子節(jié)點(diǎn)在進(jìn)行填充時(shí)必須滿足如下優(yōu)先級(jí)：當(dāng)前節(jié)點(diǎn)的左孩子節(jié)點(diǎn) 當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)缩筛，當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn) 后續(xù)節(jié)點(diǎn)的孩子節(jié)點(diǎn)消略。若違背這一優(yōu)先級(jí)，則這棵樹(shù)就不是完全二叉樹(shù)）瞎抛。（參考：https://blog.csdn.net/qq_30650153/article/details/82024648）（參考：http://www.reibang.com/p/d174f1862601）
  • 滿二叉樹(shù)是完全二叉樹(shù)的一種艺演，它的所有層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值。
  • 堆是一種特殊的完全二叉樹(shù)，堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)（若存在）的值胎撤。
  • 大根堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)（若存在）的值晓殊，根節(jié)點(diǎn)的值是所有節(jié)點(diǎn)值中的最大者。
  • 小根堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子節(jié)點(diǎn)（若存在）的值伤提，根節(jié)點(diǎn)的值是所有節(jié)點(diǎn)值中的最小者巫俺。
  • 堆排序就是利用堆這種數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行排序。

• 一句話總結(jié)：先構(gòu)造大根堆肿男，然后不斷交換未排序部分的首尾元素并重新構(gòu)造大根堆介汹。

• 具體操作過(guò)程（以大根堆為例）：

  • 首先將待排序的數(shù)組構(gòu)造成一個(gè)大根堆；
  • 然后取出這個(gè)大根堆的堆頂節(jié)點(diǎn)（最大值）舶沛，將其與堆的未排序部分的最后一個(gè)元素進(jìn)行交換嘹承，然后將未排序部分除最后一個(gè)元素之外的部分重新構(gòu)造成一個(gè)大根堆（交換之后，未排序部分的最后一個(gè)元素相當(dāng)于已經(jīng)排過(guò)序了如庭，因此它不需要再參與大根堆的構(gòu)建）赶撰；
  • 重復(fù)第二步，直到未排序部分的長(zhǎng)度為1柱彻，此時(shí)即完成排序豪娜。

• 時(shí)間復(fù)雜度分析：平均時(shí)間復(fù)雜度： 。堆排序的時(shí)間復(fù)雜度分析類似于選擇排序哟楷，不管原始序列是已經(jīng)排好序的還是完全逆序的瘤载，堆排序總是要花費(fèi) 的時(shí)間來(lái)遍歷堆中的 個(gè)元素，來(lái)進(jìn)行元素交換卖擅。每次交換元素后鸣奔，又必須要花費(fèi) 的時(shí)間來(lái)將堆中剩余部分重新構(gòu)造成一個(gè)大根堆（這里 是因?yàn)樗饕凳且?2 的指數(shù)的方式來(lái)遍歷堆中剩余的元素的），因此無(wú)論是在最好情況下還是在最壞情況下惩阶，時(shí)間復(fù)雜度均為 挎狸。

• 空間復(fù)雜度分析：由于是 in-place 操作，因此空間復(fù)雜度為 断楷。

• 穩(wěn)定性分析：由于涉及到元素交換锨匆，因此不能保證排序后相同元素的順序保持不變，所以堆排序是不穩(wěn)定的冬筒。

• python實(shí)現(xiàn)：

  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）二路歸并排序

• 歸并排序是一種遞歸算法恐锣，用到的思想是分而治之。

• 將兩個(gè)有序子序列合并成一個(gè)有序序列的過(guò)程稱為二路歸并舞痰。

• 一句話總結(jié)：先使每個(gè)子序列有序土榴，然后再將有序的子序列合并。

• 具體操作過(guò)程：

  • 將原始序列從中間位置分成兩個(gè)序列响牛；
  • 將得到的兩個(gè)子序列按照第一步繼續(xù)二分下去玷禽；
  • 直到所有子序列的長(zhǎng)度都為 1赫段，即無(wú)法再繼續(xù)二分為止。此時(shí)再兩兩合并成一個(gè)有序序列即可矢赁。

• 時(shí)間復(fù)雜度分析：平均時(shí)間復(fù)雜度： 瑞佩。劃分序列的過(guò)程每次都是二分的，因此用 的時(shí)間就可以完成序列的劃分（劃分子序列的形式類似于一棵二叉樹(shù)坯台，劃分的次數(shù)其實(shí)就是二叉樹(shù)的深度）炬丸。每次歸并都要遍歷整個(gè)被劃分出來(lái)的兩個(gè)序列，因此歸并操作的時(shí)間復(fù)雜度是 蜒蕾。并且稠炬，無(wú)論原始序列是否有序，二分的過(guò)程和歸并的過(guò)程都是少不了的咪啡。因此無(wú)論是在最好的情況下還是在最壞的情況下首启，歸并排序的時(shí)間復(fù)雜度均為 。

• 空間復(fù)雜度分析：由于要用到一個(gè)額外的輔助數(shù)組撤摸，因此歸并排序的空間復(fù)雜度是 毅桃。

• 穩(wěn)定性分析：整個(gè)劃分和歸并的過(guò)程不涉及到元素位置的交換，因此歸并排序是穩(wěn)定的准夷。

• python實(shí)現(xiàn)：

  def merge(left, right):
      extra = []
      i = j = 0
      while i < len(left) and j < len(right):  # 這里是and關(guān)系
          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:  # 遞歸方法一定要先寫(xiě)遞歸基
          return nums
      middle = len(nums) // 2
      left = mergeSort(nums[:middle])
      right = mergeSort(nums[middle:])
      return merge(left, right)
  

（8）計(jì)數(shù)排序

• 前置知識(shí)：

  • 計(jì)數(shù)排序钥飞、桶排序和基數(shù)排序都屬于非比較排序，它們的時(shí)間復(fù)雜度都是線性的衫嵌，優(yōu)于比較排序類方法读宙。但它們也有弊端：會(huì)多占用一些空間，相當(dāng)于是用空間換時(shí)間楔绞。
  • 計(jì)數(shù)排序的核心思想是將原始序列轉(zhuǎn)化為鍵值對(duì)存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中结闸，它要求原始序列必須是有確定范圍的整數(shù)。（最大值最好不要太大酒朵，否則會(huì)占用很多的額外空間桦锄。）

• 一句話總結(jié)：將原始序列轉(zhuǎn)化為鍵值對(duì)存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。

• 具體操作過(guò)程：用一個(gè)額外的數(shù)組來(lái)記錄原始序列中每個(gè)元素對(duì)應(yīng)的位置以及它出現(xiàn)的次數(shù)蔫耽，然后再把它們按順序一個(gè)一個(gè)地取出來(lái)结耀。

• 時(shí)間復(fù)雜度分析：平均時(shí)間復(fù)雜度、最好情況下的時(shí)間復(fù)雜度针肥、最壞情況下的時(shí)間復(fù)雜度均為 饼记，快于任何比較排序算法香伴。當(dāng) 不是很大且序列比較集中時(shí)慰枕，計(jì)數(shù)排序是一個(gè)很有效的排序算法。但是計(jì)數(shù)排序?qū)τ谳斎氲臄?shù)據(jù)有要求即纲，并不是所有情況下都能使用這種排序算法具帮。（計(jì)數(shù)排序也只需要用到最大值，不需要用到最小值，因此如果 比輸入數(shù)據(jù)的規(guī)模小的多蜂厅，計(jì)數(shù)排序?qū)?huì)非常高效匪凡。）

• 空間復(fù)雜度分析：

  • 把原序列當(dāng)做輸出序列： ；
  • 用額外的空間來(lái)存放輸出序列： 掘猿。

• 穩(wěn)定性分析：穩(wěn)定病游。

• python實(shí)現(xiàn)：

  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）

• 一句話總結(jié)：分桶 -> 排序 -> 合并。

• 計(jì)數(shù)排序和桶排序的區(qū)別與聯(lián)系：它們都用到了“桶”的概念稠通，只不過(guò)計(jì)數(shù)排序中每個(gè)桶里只有一個(gè)鍵值衬衬，而桶排序中每個(gè)桶里存放的是一定范圍內(nèi)的鍵值。

• 具體操作過(guò)程：

  • 將待排元素劃分到不同的桶改橘。假設(shè)原始序列的最大值和最小值分別為 max(nums) 和 min(nums) 滋尉，設(shè)桶的個(gè)數(shù)為 k，則把區(qū)間 [min(nums), max(nums)] 均勻劃分成 k 個(gè)區(qū)間飞主，每個(gè)區(qū)間就是一個(gè)桶狮惜。然后將序列中的元素分配到各自的桶。
  • 接著對(duì)每個(gè)桶內(nèi)的元素分別進(jìn)行排序碌识∧氪郏可以選擇任意一種排序算法，或者遞歸地用桶排序繼續(xù)進(jìn)行劃分筏餐。
  • 然后將各個(gè)桶中的元素合并成一個(gè)大的有序序列耽梅。

• 復(fù)雜度分析：桶排序的計(jì)算復(fù)雜度依賴于每個(gè)桶用到的排序算法、要使用的桶的個(gè)數(shù)以及輸入數(shù)據(jù)是否是均勻分布的胖烛。當(dāng)輸入數(shù)據(jù)均勻地分布在某個(gè)范圍內(nèi)時(shí)眼姐，桶排序非常有效。但是當(dāng)輸入數(shù)據(jù)中某些數(shù)字非常集中時(shí)佩番，這時(shí)各個(gè)桶中的數(shù)據(jù)分布將會(huì)非常不均勻（一些桶中的數(shù)據(jù)非常多而另一些桶中的非常少）众旗。一種極端的情形是所有的數(shù)據(jù)都分布在同一個(gè)桶里，桶排序最壞情況下的時(shí)間復(fù)雜度就發(fā)生在這種情形：因?yàn)榇藭r(shí)桶排序的性能將完全取決于對(duì)每個(gè)桶所使用的排序算法的好壞趟畏。如果使用的是諸如冒泡排序贡歧、簡(jiǎn)單選擇排序、簡(jiǎn)單插入排序這樣的算法赋秀，那么桶排序的時(shí)間復(fù)雜度將達(dá)到 利朵。在最好的情況下，每個(gè)桶里都分得一個(gè)元素猎莲，這樣整體所花費(fèi)的時(shí)間就是分桶操作所花費(fèi)的時(shí)間绍弟，為 平均時(shí)間復(fù)雜度為 ≈荩空間復(fù)雜度：假設(shè)用到了 k 個(gè)桶樟遣，那么空間復(fù)雜度就是 而叼。

• 穩(wěn)定性分析：分桶操作不涉及交換，因此桶排序是穩(wěn)定的豹悬。

• python實(shí)現(xiàn)：

  • 代碼中只需要用到最大值葵陵，不需要用到最小值。這一點(diǎn)非常巧妙：即使輸入數(shù)據(jù)中包含負(fù)數(shù)瞻佛，代碼也能夠正常進(jìn)行排序脱篙，因?yàn)樨?fù)數(shù)的索引進(jìn)過(guò)映射后就變成了 -len(nums) ，正好被分到前面的桶中伤柄。
  • 桶排序在對(duì)每個(gè)桶中的元素分別進(jìn)行排序時(shí)涡尘，需要額外使用其他的排序算法，這里以快速排序?yàn)槔?/li>
  • 程序中必須要有 bucket_index 和 len(nums) 的判斷响迂，否則需要額外分配一個(gè)桶考抄，造成空間的浪費(fèi)。
  • bucket_index 的數(shù)據(jù)類型必須要轉(zhuǎn)換為 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）基數(shù)排序

• 一句話總結(jié)：先排元素的最后一位，再排倒數(shù)第二位然遏，直到所有的位數(shù)都排完贫途。

• 對(duì)于正整數(shù)序列之外的序列，如果要使用基數(shù)排序待侵，需要調(diào)整元素放入桶中的方式丢早。

• 和計(jì)數(shù)排序一樣，基數(shù)排序也是一種特殊的桶排序秧倾。桶排序是按區(qū)間來(lái)劃分桶怨酝，而基數(shù)排序則是按數(shù)位來(lái)劃分桶∧窍龋基數(shù)排序可以看做是多輪桶排序农猬，在每個(gè)數(shù)位上都進(jìn)行一輪桶排序。

• 基數(shù)排序要求元素是非負(fù)整數(shù)售淡。

• 時(shí)間復(fù)雜度分析：假設(shè)原序列中最大值的位數(shù)為 斤葱，則總共將進(jìn)行 輪桶排序。每一輪桶排序都要遍歷整個(gè)序列揖闸，需要花 的時(shí)間揍堕。因此平均時(shí)間復(fù)雜度為 。而且汤纸，無(wú)論初始序列是否有序衩茸， 輪桶排序是少不了的，每一輪桶排序中對(duì)整個(gè)序列的遍歷也是少不了的。因此汁雷，無(wú)論是在最好情況下還是在最壞情況下，時(shí)間復(fù)雜度均為 。

• 空間復(fù)雜度分析：基數(shù)排序的內(nèi)層循環(huán)實(shí)際上是一個(gè)計(jì)數(shù)排序抖部，整個(gè)基數(shù)排序過(guò)程實(shí)際上是跑了 遍計(jì)數(shù)排序。計(jì)數(shù)排序的空間復(fù)雜度為 议惰，而在基數(shù)排序的過(guò)程中這些空間在每一輪的計(jì)數(shù)排序中都是重復(fù)利用的慎颗，因此基數(shù)排序的空間復(fù)雜度和計(jì)數(shù)排序是一樣的，均為 言询，其中 為桶的數(shù)量俯萎。

• 穩(wěn)定性分析：基數(shù)排序不涉及到元素交換，因此是穩(wěn)定的运杭。

• python實(shí)現(xiàn)：

  def radixSort(nums):
          k = len(str(max(nums))) # 得到最大值的位數(shù)
          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) # 新來(lái)的元素一定要放到末尾夫啊，這直接決定了基數(shù)排序的穩(wěn)定性
              nums.clear()  # clear函數(shù)用于清空列表，例如：list.clear()
              for bucket in bucktes:
                  nums += bucket
          
          return nums
  

11-2. 旋轉(zhuǎn)數(shù)組中的最小數(shù)字

如果數(shù)組中不存在重復(fù)的元素辆憔，則代碼為：

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums)-1
        if nums[left] < nums[right]: # 數(shù)組中不存在重復(fù)的元素撇眯，所以這個(gè)地方不能寫(xiě)等于
            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]

如果數(shù)組中存在重復(fù)的元素，則以上方法失效虱咧，此時(shí)只能遍歷一遍數(shù)組來(lái)查找最小值熊榛。

12. 矩陣中的路徑

回溯法適用于這樣的問(wèn)題：

• 這個(gè)問(wèn)題可能要分很多步才能完成；
• 每一步都有很多種可能腕巡，而且這一步一旦確定玄坦，下一步還是會(huì)有很多種可能，下下一步也還是會(huì)有很多種可能绘沉，問(wèn)題看起來(lái)非常復(fù)雜煎楣。

矩陣中的路徑問(wèn)題是典型的可以用回溯法解決的問(wèn)題，通吵瞪。回溯法適合用遞歸實(shí)現(xiàn)代碼转质。當(dāng)我們到達(dá)某一個(gè)節(jié)點(diǎn)時(shí)，嘗試所有可能的選項(xiàng)并在滿足條件的前提下遞歸地抵達(dá)下一個(gè)節(jié)點(diǎn)帖世。

代碼如下：

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def explore(i, j, word):
        if not word: # 遞歸算法先寫(xiě)遞歸基
            return True
        temp, board[i][j] = board[i][j], '*' # 因?yàn)榫仃囍械脑刂荒苡靡淮涡菪罚砸坏┯眠^(guò)就得把它抹掉（這里用 * 將它覆蓋）
        success = False # 回溯法都是用一個(gè)標(biāo)志來(lái)記錄探索成功與否的，而不是直接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 # 如果探索成功日矫，就把當(dāng)前這一步標(biāo)記為成功
                break # 這里即使是break赂弓，代碼也會(huì)把所有可能的情況找完，不會(huì)漏哪轿，
                      # 因?yàn)槿绻麤](méi)有成功盈魁，那么if條件不成立，for循環(huán)將繼續(xù)進(jìn)行下一個(gè)值
                      # 而如果成功之后不及時(shí)break的話窃诉，success的值就可能被下一輪循環(huán)改變
        board[i][j] = temp # for循環(huán)結(jié)束杨耙，表明當(dāng)前的所有情況都探索完了赤套，此時(shí)要把抹掉的值復(fù)原，以便其他輪的探索能夠正常使用這些值
        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矩陣中的路徑：出錯(cuò)了兩次珊膜，出錯(cuò)代碼如下：

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

錯(cuò)誤的地方在于：

• 首先容握，在 explore 函數(shù)中，if 語(yǔ)句進(jìn)行判斷時(shí)车柠，不能把 board[x][y] == word[0] 這一條件放在最前面剔氏。因?yàn)槿绻?x 和 y 越界，那么這個(gè)地方代碼就會(huì)報(bào) List index out of range 的錯(cuò)誤竹祷。 if 語(yǔ)句在進(jìn)行判斷的時(shí)候谈跛，是從前往后一個(gè)一個(gè)進(jìn)行判斷，如果前面的天劍就不通過(guò)塑陵，那么后面的條件根本就不會(huì)看感憾。因此為了保證判斷到 board[x][y] == word[0] 時(shí)索引不會(huì)越界，必須要把這一條件放到 0<=x<rows-1 and 0<=y<cols-1 這兩個(gè)條件的后面令花；
• 其次阻桅，0<=x<rows-1 and 0<=y<cols-1 這兩個(gè)條件本身就沒(méi)寫(xiě)對(duì)，要么改成 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. 機(jī)器人的運(yùn)動(dòng)范圍

通常物體或者人在二維方格運(yùn)動(dòng)之類的問(wèn)題都可以用回溯法解決。

網(wǎng)站上提供的答案不能應(yīng)對(duì) threshold=0 或 rows=0 或 cols=0 的情況俯抖，因此要額外加上一個(gè)判斷：

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

threshold = 0 時(shí)输瓜，表示一步都沒(méi)走，但機(jī)器人初始時(shí)就占據(jù)了一個(gè)格子芬萍，所以此時(shí)答案為 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. 剪繩子

什么樣的問(wèn)題可以用動(dòng)態(tài)規(guī)劃解決？

• 第一柬祠，問(wèn)題的目標(biāo)是要求得一個(gè)最優(yōu)解（通常是最大值或最小值）北戏；
• 第二，原問(wèn)題可以遞歸地分解成很多個(gè)子問(wèn)題漫蛔，而且這些子問(wèn)題也都存在各自的最優(yōu)解嗜愈；
• 第三，原問(wèn)題似乎可以用遞歸的方法解決莽龟，但這樣做可能會(huì)造成大量的重復(fù)蠕嫁。因此通常采用從上往下的方法分析問(wèn)題，再?gòu)南峦锨蠼鈫?wèn)題毯盈，即先計(jì)算小問(wèn)題的最優(yōu)解并存儲(chǔ)下來(lái)剃毒，再以此為基礎(chǔ)求解大問(wèn)題的最優(yōu)解。
• 用自上而下的遞歸思路分析問(wèn)題，基于自下而上的循環(huán)實(shí)現(xiàn)代碼赘阀。

貪婪算法：

• 每一步都可以做出一個(gè)貪婪的選擇益缠，基于這個(gè)選擇，我們確定能夠得到最優(yōu)解基公；
• 但是為什么我們做出這樣貪婪的選擇就能夠得到問(wèn)題的最優(yōu)解幅慌？這是需要通過(guò)數(shù)學(xué)的方式來(lái)證明的。

回溯法與動(dòng)態(tài)規(guī)劃：

• 回溯法很適合解決迷宮及其類似問(wèn)題酌媒；
• 如果是求一個(gè)問(wèn)題的最優(yōu)解欠痴，那么可以嘗試使用動(dòng)態(tài)規(guī)劃迄靠。如果在用動(dòng)態(tài)規(guī)劃分析問(wèn)題時(shí)發(fā)現(xiàn)每一步都存在一個(gè)能得到最優(yōu)解的選擇秒咨，那么可以嘗試使用貪婪算法。

時(shí)間復(fù)雜度為 掌挚、空間復(fù)雜度為 的通用方法：

class Solution(object):
    def maxProductAfterCutting(self,length):
        """
        :type length: int
        :rtype: int
        """
        # 長(zhǎng)度至少為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]

這里要說(shuō)明的是：

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

并不是繩長(zhǎng)分別為 1，2吠式，3 時(shí)剪到的乘積的最大值陡厘，而是一些乘積項(xiàng)，即當(dāng)剪斷之后特占，如果繩長(zhǎng)為 1 就乘以 1糙置，繩長(zhǎng)為 2 就乘以 2 ，繩長(zhǎng)為 3 就乘以 3是目。從 product_mat[4] 開(kāi)始谤饭，這個(gè)矩陣中存儲(chǔ)的才是乘積的最大值：

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

時(shí)間復(fù)雜度和空間復(fù)雜度均為 的貪婪算法：

• 當(dāng) 時(shí)，盡可能多地剪長(zhǎng)度為 3 的繩子懊纳；
• 當(dāng)剩下的繩子長(zhǎng)度為 4 時(shí)揉抵，把繩子剪成長(zhǎng)度為 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  # 余數(shù)為1或2
        # 如果余數(shù)為1嗤疯，則少剪一段3冤今，把4剪成兩個(gè)2
        if length % 3 == 1:
            count3 -= 1
        count2 = (length - count3*3) // 2
        
        return (3**count3) * (2**count2)

15. 二進(jìn)制中 1 的個(gè)數(shù)

• 左移運(yùn)算符有可能會(huì)把左邊的數(shù)位丟棄，右移運(yùn)算符有可能會(huì)把右邊的數(shù)位丟棄茂缚。
• 右移時(shí)如果是正數(shù)則左邊補(bǔ) 0 戏罢，如果是負(fù)數(shù)則左邊補(bǔ) 1。
• 乘除法的效率比移位運(yùn)算要低得多脚囊，因此要盡可能地用移位運(yùn)算代替乘除法龟糕。
• 把一個(gè)整數(shù)減去 1 之后再和原來(lái)的整數(shù)做與運(yùn)算，得到的結(jié)果相當(dāng)于把整數(shù)的二進(jìn)制表示中最右邊的 1 變成 0 凑术。
• 二進(jìn)制表示中數(shù)字位數(shù)為 1 的個(gè)數(shù)也被稱為漢明重量翩蘸。

代碼實(shí)現(xiàn)：(依據(jù)是：一個(gè)數(shù) n 和 n-1 做與運(yùn)算，相當(dāng)于去掉了最右面的 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.數(shù)值的整數(shù)次方：

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是不是奇數(shù)
                ans *= x
            return ans
            
        if n < 0:
            return 1 / cal_unsigned_pow(x, -n)
        else:
            return cal_unsigned_pow(x, n)

需要注意的地方：

• 在計(jì)算冪次時(shí)催首，不是用 for 循環(huán)的方法每次去乘 x 扶踊，而是用遞歸的方法不斷地計(jì)算平方，這樣效率更高郎任；
• 0 的 0 次方是沒(méi)有意義的秧耗，這里將它的值定為 1 。

17.打印從 1 到最大的 n 位數(shù)

python 的 int 沒(méi)有長(zhǎng)度限制舶治，所以直接打臃志：

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

18-1. 刪除鏈表的節(jié)點(diǎn)

• 在單向鏈表中刪除一個(gè)節(jié)點(diǎn)的常規(guī)做法是從鏈表的頭結(jié)點(diǎn)開(kāi)始，順序遍歷查找要?jiǎng)h除的節(jié)點(diǎn)霉猛，并在鏈表中刪除該節(jié)點(diǎn)尺锚。（刪除某個(gè)節(jié)點(diǎn)就是讓它上一個(gè)節(jié)點(diǎn)的指針跳過(guò)當(dāng)前節(jié)點(diǎn)直接指向下一個(gè)節(jié)點(diǎn)。）
  由于這種做法需要順序查找惜浅，因此它的時(shí)間復(fù)雜度是 瘫辩。
• 在單向鏈表中，節(jié)點(diǎn)中沒(méi)有指向前一個(gè)節(jié)點(diǎn)的指針坛悉。
• 一種創(chuàng)新性的思考方法：當(dāng)我們想刪除一個(gè)節(jié)點(diǎn)時(shí)伐厌，并不一定要?jiǎng)h除這個(gè)節(jié)點(diǎn)本身÷阌埃可以先把下一個(gè)節(jié)點(diǎn)的內(nèi)容復(fù)制出來(lái)覆蓋想被刪除的節(jié)點(diǎn)的內(nèi)容挣轨，然后把下一個(gè)節(jié)點(diǎn)刪除，這樣就等價(jià)于刪除了這個(gè)節(jié)點(diǎn)本身轩猩。
  如果想要?jiǎng)h除的這個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)存在（即當(dāng)前節(jié)點(diǎn)不是鏈表的最后一個(gè)節(jié)點(diǎn)）卷扮，那么我們就可以在 的時(shí)間內(nèi)把下一個(gè)節(jié)點(diǎn)的內(nèi)容復(fù)制覆蓋要?jiǎng)h除的節(jié)點(diǎn)，并刪除下一個(gè)節(jié)點(diǎn)界轩。
  如果要?jiǎng)h除的節(jié)點(diǎn)就是鏈表的尾節(jié)點(diǎn)画饥，那么這種方法失效，此時(shí)只能采用常規(guī)方法浊猾，按順序查找當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)抖甘，這樣時(shí)間復(fù)雜度依舊是 。
• 綜合考慮以上兩種情況葫慎，總的平均時(shí)間復(fù)雜度為 衔彻。
• 此外還要考慮兩種特殊情況：
  • 一是初始鏈表中只有一個(gè)節(jié)點(diǎn)，此時(shí)刪除時(shí)候鏈表為空偷办，則鏈表的頭節(jié)點(diǎn)應(yīng)該指向 None 艰额；
  • 二是想要?jiǎng)h除的節(jié)點(diǎn)不在鏈表中。（這種情況可以看成是非法輸入椒涯。）

# 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. 正則表達(dá)式匹配

如果 pattern 中沒(méi)有 * 柄沮，則問(wèn)題可以通過(guò)如下的遞歸來(lái)解決：

def match(text, pattern):
    if not pattern: return not text # 先寫(xiě)遞歸基
    match_res = bool(text) and pattern[0] in {text[0], '.'} # text只要不空，轉(zhuǎn)化為bool均返回True
    return match_res and match(text[1:], pattern[1:])

當(dāng) * 出現(xiàn)時(shí)，前面一定會(huì)跟一個(gè)其他字符祖搓，所以每一次對(duì) pattern 切片后狱意，* 一定會(huì)出現(xiàn)在 pattern[1] 的位置。如何應(yīng)對(duì) * 出現(xiàn)時(shí)的情況呢拯欧？有如下兩種解決方案：

• 其一详囤，因?yàn)?* 代表它前面的字符可以出現(xiàn) 0 次，所以跳過(guò) * 和它前面的那個(gè)字符镐作，從 * 后面的字符開(kāi)始重新對(duì)當(dāng)前的 text[0] 進(jìn)行匹配藏姐，即 match(text, pattern[2:])；
• 其二该贾，因?yàn)?* 代表它前面的字符可以出現(xiàn)任意次羔杨，所以 * 和它前面的那個(gè)字符可以重復(fù)使用。如果當(dāng)前這一輪 text[0] 和 pattern[0] 匹配成功靶庙，那么在下一輪遞歸時(shí)问畅，text 要匹配的是 text[1:] 娃属，而 pattern 則可以重復(fù)使用六荒，不使用的情況已經(jīng)在上面那一條說(shuō)過(guò)了，重復(fù)使用的情況就是 pattern 不進(jìn)行切片矾端，仍然將當(dāng)前 pattern 的全部?jī)?nèi)容傳入下一輪遞歸中掏击，即 match(text[1:], pattern) 。

可以看到秩铆，如果 pattern 中有 * 砚亭，則每一輪遞歸都有兩條路可以選，而且在進(jìn)入到下一輪遞歸后仍然有兩條路可以選殴玛。

整個(gè)代碼的思路是：

• 首先捅膘，不管哪種情況，由于 * 不可能出現(xiàn)在 pattern[0] 的位置滚粟，因此每次都要先判斷第 0 個(gè)字符是否能匹配寻仗，判斷的方法是：

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

• 當(dāng)前 pattern 的長(zhǎng)度大于 1 而且 pattern[1] == * 嗎？

  • 如果上述條件滿足凡壤，則又分為兩條路：

    • match(text, pattern[2:])

    • match(text[1:], pattern)

      以上這兩條路是并行執(zhí)行的署尤，而且只要有一條路滿足就可以，所以要用 or 連接亚侠。

  • 如果上述條件不滿足曹体，就可以認(rèn)為 pattern[0] 和 pattern[1] 里面均不包含 * （至少在當(dāng)前 pattern 的前兩個(gè)位置是沒(méi)有 * 的，后面的位置有 * 的情況先不管硝烂。因?yàn)榇a是遞歸進(jìn)行的箕别，所以后面的位置如果有 * ，早晚有一天這個(gè) * 肯定會(huì)挪到 pattern[1] 的位置，到那時(shí)再對(duì)它進(jìn)行處理也不遲串稀。）啥酱。那么這種情況退化為最開(kāi)始的那種沒(méi)有 * 的情況，此時(shí)在進(jìn)行下一輪遞歸時(shí)厨诸，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]不會(huì)發(fā)生索引越界的情況（因?yàn)閠ext有可能為空）
        
        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:])

測(cè)試樣例及測(cè)試結(jié)果如下：

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)


"""輸出結(jié)果"""
text = mississippi, pattern = mis*is*ip*.

text[1:], pattern[1:] :                   # 第一輪循環(huán)微酬，各自去一個(gè)
text = ississippi, pattern = is*is*ip*.

text[1:], pattern[1:] :                   # 第二輪循環(huán)绘趋，仍然各自去一個(gè)
text = ssissippi, pattern = s*is*ip*.

text, pattern[2:] or text[1:], pattern :  # 第三輪循環(huán)，要進(jìn)行抉擇：
text = ssissippi, pattern = is*ip*.       # 程序先選的跳過(guò)當(dāng)前pattern颗管，但是這條路走不通陷遮，所以也就沒(méi)有后序輸出了

text[1:], pattern[1:] :                   # 然后返回抉擇的地方，
text = sissippi, pattern = s*is*ip*.      # 選擇第二條路垦江，發(fā)現(xiàn)這條路可以走通

text, pattern[2:] or text[1:], pattern :  # 第四輪循環(huán)帽馋，再次面臨抉擇：
text = sissippi, pattern = is*ip*.        # 仍然先選第一條路，發(fā)現(xiàn)仍然走不通

text[1:], pattern[1:] :                   
text = issippi, pattern = s*is*ip*.       # 轉(zhuǎn)而選第二條路

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. 表示數(shù)值的字符串

這道題和 19 題一樣比吭，都是狀態(tài)機(jī)問(wèn)題（這類字符串匹配問(wèn)題其實(shí)都是狀態(tài)機(jī)問(wèn)題）绽族，只不過(guò)第 19 題是無(wú)限狀態(tài)機(jī)，而這一題是有限狀態(tài)機(jī)衩藤。

代碼：

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

代碼解析：

這是一個(gè)有限狀態(tài)機(jī)問(wèn)題吧慢。有限狀態(tài)機(jī)也叫有窮自動(dòng)機(jī)，即給定某個(gè)狀態(tài)赏表，它在接受某個(gè)輸入之后會(huì)轉(zhuǎn)到下一個(gè)狀態(tài)检诗，且總的狀態(tài)數(shù)是有限的。

假設(shè)原始字符串為 s 瓢剿，且假設(shè)有限狀態(tài)機(jī)的初始狀態(tài)為 1 狀態(tài)逢慌，在這個(gè)狀態(tài)時(shí)，有限狀態(tài)機(jī)尚未接收到任何字符信息间狂。當(dāng) s 中的第 0 個(gè)字符輸入到初始狀態(tài)時(shí)攻泼，可能會(huì)有以下五種情況：

• ，即 1 狀態(tài)接收一個(gè)空格時(shí)前标，仍然保留 1 狀態(tài)不變坠韩；
• ，即 1 狀態(tài)接收一個(gè) + 號(hào)或 - 號(hào)時(shí)炼列，將轉(zhuǎn)移到 2 狀態(tài)只搁；
• ，即 1 狀態(tài)接收一個(gè)數(shù)字時(shí)俭尖，將轉(zhuǎn)移到 3 狀態(tài)氢惋；
• 洞翩，即 1 狀態(tài)接收一個(gè)小數(shù)點(diǎn)時(shí)，將轉(zhuǎn)移到 4 狀態(tài)焰望。
• 骚亿，即如果 1 狀態(tài)接收到的字符不是以上 4 種，則程序?qū)⒅苯?return False 熊赖。

當(dāng)狀態(tài)機(jī)位于 2 狀態(tài)時(shí)来屠，表明狀態(tài)機(jī)第一次接收到了一個(gè) + 號(hào)或 - 號(hào)，此時(shí)欲使輸入字符串是一個(gè)有效的數(shù)字震鹉，則 s[1] 只能是數(shù)字或小數(shù)點(diǎn)俱笛，即 2 狀態(tài)只有兩個(gè)后繼狀態(tài)：

• ，即 2 狀態(tài)接收一個(gè)數(shù)字時(shí)传趾，將轉(zhuǎn)移到 3 狀態(tài)迎膜；
• ，即 2 狀態(tài)接收一個(gè)小數(shù)點(diǎn)時(shí)浆兰，將轉(zhuǎn)移到 4 狀態(tài)磕仅。

當(dāng)狀態(tài)機(jī)位于 3 狀態(tài)時(shí)，表明狀態(tài)機(jī)已經(jīng)接收到了至少一個(gè)數(shù)字簸呈。而數(shù)字對(duì)后續(xù)字符的要求比較低榕订，因此 3 狀態(tài)存在四個(gè)后繼狀態(tài)：

• ，即 3 狀態(tài)接收一個(gè)數(shù)字時(shí)蝶棋，仍然返回到 3 狀態(tài)卸亮。因?yàn)?3 狀態(tài)接收一個(gè)數(shù)字后轉(zhuǎn)移到的新?tīng)顟B(tài)仍然存在四個(gè)后繼狀態(tài)，而且這四個(gè)后繼狀態(tài)和 3 狀態(tài)的后繼狀態(tài)是一樣的玩裙，因此這個(gè)新?tīng)顟B(tài)就等效于 3 狀態(tài)本身，所以 3 狀態(tài)接收一個(gè)數(shù)字后仍然回到 3 狀態(tài)段直；
• 吃溅，即 3 狀態(tài)接收到一個(gè)小數(shù)點(diǎn)后，將進(jìn)入到 5 狀態(tài)鸯檬；
• 决侈，即 3 狀態(tài)接收到字母 e 時(shí)，將進(jìn)入到 6 狀態(tài)喧务；
• 赖歌，即 3 狀態(tài)接收到一個(gè)空格時(shí)，將進(jìn)入到 9 狀態(tài)功茴。

當(dāng)狀態(tài)機(jī)位于 4 狀態(tài)時(shí)庐冯，表明狀態(tài)機(jī)第一次接收到一個(gè)小數(shù)點(diǎn)，因?yàn)樾?shù)點(diǎn)對(duì)后續(xù)字符的要求比較苛刻坎穿，所以 4 狀態(tài)只有一個(gè)后繼狀態(tài)：

• 展父，即 4 狀態(tài)只能接收一個(gè)數(shù)字返回到 3 狀態(tài)返劲；

當(dāng)狀態(tài)機(jī)位于 5 狀態(tài)時(shí)，由于 5 狀態(tài)是由 3 狀態(tài)接收一個(gè)小數(shù)點(diǎn)得來(lái)的栖茉，因此 5 狀態(tài)有 3 種可行的后繼狀態(tài)：

• 篮绿，即 5 狀態(tài)接收一個(gè)數(shù)字后重新返回 5 狀態(tài)（原因和前面 3 狀態(tài)接收一個(gè)數(shù)字后返回 3 狀態(tài)是一樣的）。注意這里不能返回 3 狀態(tài)吕漂，因?yàn)楫?dāng)狀態(tài)機(jī)位于 5 狀態(tài)時(shí)亲配，表明此時(shí)字符串中已經(jīng)有了一個(gè)小數(shù)點(diǎn)。3 狀態(tài)是可以接收小數(shù)點(diǎn)的惶凝，而 5 狀態(tài)不能再接收小數(shù)點(diǎn)弃榨，因此 5 狀態(tài)和 3 狀態(tài)是不等價(jià)的，所以這里只能返回 5 狀態(tài)梨睁；
• 鲸睛，即 5 狀態(tài)接收到字母 e 時(shí)，將進(jìn)入到 6 狀態(tài)坡贺；
• 官辈，即 5 狀態(tài)接收到一個(gè)空格時(shí)，將進(jìn)入到 9 狀態(tài)遍坟。

當(dāng)狀態(tài)機(jī)位于 6 狀態(tài)時(shí)摊阀，由于 6 狀態(tài)是狀態(tài)機(jī)第一次接收到字母 e 后轉(zhuǎn)移到的狀態(tài)，而字母 e 后的指數(shù)部分只能接數(shù)字或正負(fù)號(hào)恃慧，因此 6 狀態(tài)只有兩種后繼狀態(tài)：

• 呵扛，即 6 狀態(tài)接收一個(gè) + 號(hào)或 - 號(hào)時(shí)，將轉(zhuǎn)移到 7狀態(tài)隔节；
• 鹅经，即 6 狀態(tài)接收一個(gè)數(shù)字時(shí)，將轉(zhuǎn)移到 8 狀態(tài)怎诫；

當(dāng)狀態(tài)機(jī)位于 7 狀態(tài)時(shí)瘾晃，由于 7 狀態(tài)是由 6 狀態(tài)接收一個(gè)正號(hào)或負(fù)號(hào)得來(lái)的，也就是說(shuō) 7 狀態(tài)只能接收數(shù)字幻妓，因此 7 狀態(tài)只有一個(gè)后繼狀態(tài)：

• 蹦误，即 7 狀態(tài)接收一個(gè)數(shù)字時(shí)，將轉(zhuǎn)移到 8 狀態(tài)肉津。

當(dāng)狀態(tài)機(jī)位于 8 狀態(tài)時(shí)强胰，由于此時(shí)狀態(tài)機(jī)中正負(fù)號(hào)、小數(shù)點(diǎn)妹沙、字母 e 都已經(jīng)有了偶洋，所以 8 狀態(tài)能接收的負(fù)號(hào)僅剩兩種，即只有兩個(gè)后繼狀態(tài)：

• 初烘，即 8 狀態(tài)接收一個(gè)數(shù)字后重新返回 8 狀態(tài)涡真；
• 分俯，即 8 狀態(tài)接收到一個(gè)空格時(shí)，將進(jìn)入到 9 狀態(tài)哆料。

當(dāng)狀態(tài)機(jī)位于 9 狀態(tài)時(shí)缸剪，這是狀態(tài)機(jī)的最后一個(gè)狀態(tài)，它是由其他狀態(tài)接收空格轉(zhuǎn)移而來(lái)的东亦。當(dāng)狀態(tài)機(jī)進(jìn)入 9 狀態(tài)時(shí)杏节，欲使原始字符串表示的是一個(gè)有效的數(shù)字，那么不管這個(gè)空格前面的字符是什么典阵，這個(gè)空格后面的字符必須全部是空格奋渔，直到字符串結(jié)尾。因此 9 狀態(tài)只有一個(gè)后繼狀態(tài)：

• 壮啊，即 9 狀態(tài)接收一個(gè)空格時(shí)嫉鲸，仍然返回 9 狀態(tài)。

狀態(tài)轉(zhuǎn)移圖如下：

狀態(tài)轉(zhuǎn)移圖

21. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

不穩(wěn)定的解法（調(diào)整之后奇數(shù)之間或偶數(shù)之間的相對(duì)位置可能會(huì)發(fā)生變化）：

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: # 從前往后找偶數(shù)
                left += 1
            while left < right and array[right] & 1 == 0: # 從后往前找奇數(shù)
                right -= 1
            array[left], array[right] = array[right], array[left]

穩(wěn)定但非 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:  # 從后找奇數(shù)
            q.appendleft(array[-i-1])
        if array[i] & 1 == 0:  #從前找偶數(shù)
            q.append(array[i])
    return q

22. 鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)

程序的魯棒性（也叫健壯性）指的是程序能夠判斷輸入是否合乎規(guī)范要求玄渗，并對(duì)不符合要求的輸入予以合理的處理。

以后在編寫(xiě)代碼時(shí)一定要特別注意這一點(diǎn)狸眼，即如果有人惡意輸入一些非法值藤树，程序應(yīng)該如何應(yīng)對(duì)，必須在代碼中體現(xiàn)出這些方面拓萌。

此外岁钓，這道題目給了我們一個(gè)啟示：當(dāng)我們用一個(gè)指針遍歷鏈表不能解決問(wèn)題的時(shí)候，可以嘗試用兩個(gè)指針來(lái)遍歷鏈表微王÷畔蓿可以讓其中一個(gè)指針走的速度快一些（比如一次在鏈表中走上兩步，或者讓它先在鏈表中走上若干步）骂远，另外一個(gè)指針走的慢一些囚霸。這樣就可以拿這兩個(gè)指針之間的距離來(lái)做文章。比如另外一道題目：

求鏈表的中間節(jié)點(diǎn)激才。如果鏈表的節(jié)點(diǎn)總數(shù)為奇數(shù)，則返回中間節(jié)點(diǎn)额嘿；如果節(jié)點(diǎn)總數(shù)是偶數(shù)瘸恼，則返回中間兩個(gè)節(jié)點(diǎn)的任意一個(gè)。

為了解決這個(gè)問(wèn)題册养，我們可以定義兩個(gè)指針东帅，讓它們同時(shí)從鏈表的頭結(jié)點(diǎn)出發(fā)。其中一個(gè)指針一次走一步球拦，另一個(gè)指針一次走兩步靠闭。則當(dāng)走得快的指針到達(dá)鏈表的末尾時(shí)帐我，走得慢的指針正好在鏈表的中間。

本題的代碼：（用了兩個(gè)指針愧膀，快指針先走 k-1 步拦键，然后兩個(gè)一起走。當(dāng)快指針走到尾節(jié)點(diǎn)時(shí)檩淋，慢指針正好在倒數(shù)第 k 個(gè)節(jié)點(diǎn)芬为。這里要注意代碼的魯棒性：k=0、輸入空鏈表蟀悦、k 大于鏈表的總長(zhǎng)度媚朦。）

# 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(鏈表)的情形已經(jīng)包含在這里面了
            if fast:
                fast = fast.next
            else:
                return None
        while fast:
            slow, fast = slow.next, fast.next
        return slow

23. 鏈表中環(huán)的入口節(jié)點(diǎn)

這個(gè)問(wèn)題要分三步來(lái)做：

• step 1：判斷鏈表中是否有環(huán)，可以用一快一慢兩個(gè)指針來(lái)判斷日戈；
• step 2：如果鏈表中有換询张，要得到環(huán)中節(jié)點(diǎn)的數(shù)目；
• step 3：用兩個(gè)速度相同的指針 和 來(lái)找環(huán)的入口節(jié)點(diǎn)浙炼。初始時(shí)讓兩個(gè)指針都指向鏈表的頭結(jié)點(diǎn)份氧，假設(shè)鏈表中的環(huán)有 個(gè)節(jié)點(diǎn)，則讓指針 先在鏈表上向前移動(dòng) 步鼓拧，然后兩個(gè)指針以相同的速度向前移動(dòng)半火。當(dāng)?shù)诙€(gè)指針走到環(huán)的入口節(jié)點(diǎn)時(shí)，第一個(gè)指針已經(jīng)繞著環(huán)走了一圈季俩，重新返回到了入口節(jié)點(diǎn)钮糖。

上述步驟中的 step 1 和 step 2 可以合并起來(lái)做：快指針一次走兩步，慢指針一次走一步酌住，則當(dāng)快指針和慢指針相遇時(shí)店归，快指針剛好比慢指針多走了 步（ 為環(huán)中的節(jié)點(diǎn)個(gè)數(shù)）。

又由于慢指針是從頭結(jié)點(diǎn)出發(fā)的酪我，因此上述過(guò)程中的慢指針可以直接用在 step 3 中：這個(gè)慢指針可以視為 step 3 中的 —— 它已經(jīng)從頭結(jié)點(diǎn)出發(fā)多走了 步消痛。此時(shí)只要引入第三個(gè)慢指針（初始時(shí)讓它指向鏈表的頭結(jié)點(diǎn)）或者直接把頭節(jié)點(diǎn)當(dāng)做第三個(gè)慢指針。然后讓它和 一起移動(dòng)都哭，當(dāng)它們?cè)俅蜗嘤鰰r(shí)秩伞，第三個(gè)慢指針?biāo)赶虻奈恢镁褪黔h(huán)的入口節(jié)點(diǎn)。

代碼如下：

# 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  # 可以這樣寫(xiě)連等號(hào)
        # 檢測(cè)是否有環(huán)
        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. 反轉(zhuǎn)鏈表

解決與鏈表相關(guān)的問(wèn)題總是有大量的指針操作欺矫。

指針在等號(hào)左邊時(shí)相當(dāng)于指針的搬移纱新，只有調(diào)用 next 方法才是修改節(jié)點(diǎn)的指向。

本題要用三個(gè)指針穆趴，從鏈表的頭結(jié)點(diǎn)開(kāi)始脸爱，一直遍歷到最后一個(gè)節(jié)點(diǎn)：

• 第一個(gè)指針：指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，用于修改節(jié)點(diǎn)的指向未妹；
• 第二個(gè)指針：指向要修改指向的當(dāng)前節(jié)點(diǎn)簿废；
• 第三個(gè)指針：指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)空入，用于保存下一個(gè)節(jié)點(diǎn)的值，以防在修改當(dāng)前節(jié)點(diǎn)的指向時(shí)鏈表斷裂族檬。

# 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 # 初始時(shí)歪赢，將頭結(jié)點(diǎn)前面的那個(gè)節(jié)點(diǎn)置為None
        while head:
            head.next, previous, head = previous, head, head.next
        return previous # 最終previous指向尾節(jié)點(diǎn)，head指向尾節(jié)點(diǎn)后面的None

25. 合并兩個(gè)排序的鏈表

循環(huán)的方法：

# 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) # 開(kāi)辟一個(gè)新鏈表實(shí)際上就是開(kāi)辟一個(gè)新的頭結(jié)點(diǎn)
        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. 樹(shù)的子結(jié)構(gòu)

與二叉樹(shù)相關(guān)的代碼通常都會(huì)有大量的指針操作导梆。而且與鏈表相比轨淌，樹(shù)中的指針操作更多也更復(fù)雜。

但是不管是鏈表還是二叉樹(shù)看尼，每次在使用指針的時(shí)候递鹉，我們都要問(wèn)自己這個(gè)指針有沒(méi)有可能是空指針，如果是空指針我們要如何應(yīng)對(duì)藏斩。

劍指offer中題目對(duì)應(yīng)的代碼（只需要考慮有沒(méi)有子結(jié)構(gòu)躏结，不需要考慮子結(jié)構(gòu)下面的其他部分）：

# 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: # 如果沒(méi)有左右子樹(shù)，就直接退出
                    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] # ***見(jiàn)備注***
        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 是一個(gè)布爾值媳拴，要么為 True ，要么為 False 兆览，下面分析這兩種情況：

• 如果 s 為 True 屈溉，則 True 和任何數(shù)相與，都等于這個(gè)數(shù)本身抬探，因此此時(shí)上述代碼等價(jià)于：

  stack = [s]
  

• 如果 s 為 False 子巾，則 False 和任何數(shù)相與，結(jié)果都為 False 小压，因此此時(shí)上面的代碼等價(jià)于：

  stack = False
  

leetcode 中題目對(duì)應(yīng)的代碼（不僅需要考慮有沒(méi)有子結(jié)構(gòu)线梗，還需要考慮子結(jié)構(gòu)下面的其他部分，條件更苛刻）：

# 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上的一個(gè)知識(shí)點(diǎn)：如果樹(shù)中的數(shù)包含浮點(diǎn)數(shù)怠益，則 s.val == t.val 是非法的仪搔，因?yàn)閮蓚€(gè)浮點(diǎn)數(shù)不能直接比較大小，此時(shí)判斷它們相等的方法是它們差的絕對(duì)值小于某個(gè)足夠小的數(shù)蜻牢，比如 0.0000001 烤咧。