27. 二叉樹的鏡像

求一棵樹的鏡像的過程：先前序遍歷這棵樹的每個(gè)節(jié)點(diǎn)仅孩，如果遍歷到的節(jié)點(diǎn)有子節(jié)點(diǎn)托猩，就交換它的兩個(gè)子節(jié)點(diǎn)。當(dāng)交換完所有非葉節(jié)點(diǎn)的左杠氢、右子節(jié)點(diǎn)之后站刑，就得到了這棵樹的鏡像。

# 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 mirror(self, root):
        """
        :type root: TreeNode
        :rtype: void
        """
        stack = root and [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack += node.right, node.left # 列表的“+”相當(dāng)于append

28. 對稱的二叉樹

• 思路：用兩個(gè)指針去遍歷樹鼻百，第一個(gè)指針進(jìn)行前序遍歷绞旅，第二個(gè)指針和前序遍歷對稱著去遍歷。只要這兩個(gè)指針遍歷得到的結(jié)果是一樣的温艇，那么這個(gè)二叉樹就是對稱的因悲。

• 具體操作流程：用循環(huán)，用一個(gè) stack 勺爱，每次都鏡像地將樹中的節(jié)點(diǎn) append 到 stack 中晃琳，然后再成對地比較就可以了。

# 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 isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack = root and [(root.left, root.right)]
        while stack:
            p1, p2 = stack.pop()
            if not p1 and not p2:
                continue
            if not p1 or not p2:
                return False
            if p1.val != p2.val:
                return False
            stack.append((p1.left, p2.right)) # p1用的是前序遍歷
            stack.append((p1.right, p2.left)) # p2用的是和前序遍歷對稱的遍歷算法
        return True

29. 順時(shí)針打印矩陣

假設(shè)原始矩陣 如下所示：

            1   2   3   4
            5   6   7   8
            9   10  11  12
            13  14  15  16

本題其實(shí)是這樣的一個(gè)遞歸過程：

• 先取出原始矩陣的第一行，然后將第一行剔除掉卫旱，再將矩陣逆時(shí)針旋轉(zhuǎn) 90 ° 人灼，得到矩陣 ；
• 再將 的第一行取出來顾翼，然后將 的第一行剔除掉投放，再將矩陣 逆時(shí)針旋轉(zhuǎn) 90 ° ，得到矩陣 适贸；
• 如此直至矩陣被剔空灸芳。

而如何將矩陣逆時(shí)針旋轉(zhuǎn) 90 ° 呢？這一過程需要分兩步來完成：

• 首先將原始矩陣進(jìn)行轉(zhuǎn)置拜姿，用 zip 配合 * 可以實(shí)現(xiàn)：

  # 假設(shè)原始矩陣為a烙样，則a的轉(zhuǎn)置為：
  list(zip(*a))
  

• 然后，將矩陣上下顛倒：

  # 假設(shè)轉(zhuǎn)置后的矩陣為b蕊肥，則將b上下顛倒為：
  b[::-1]
  

根據(jù)以上分析谒获，不難寫出代碼：

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        return matrix and list(matrix.pop(0)) + self.spiralOrder(list(zip(*matrix))[::-1])

這里邊要注意三點(diǎn)：

• matrix and list(matrix.pop(0)) 中的 and 非常關(guān)鍵，它不能寫成 + 號晴埂，因?yàn)樗ＷC了 pop 的時(shí)候 matrix 不為空究反，所以它是后面進(jìn)行 pop 的一個(gè)先決條件；
• pop(0) 不是將第一個(gè)元素彈出來儒洛，由于 matrix 是一個(gè)二維的列表精耐，因此它這里是將第一行彈出來，這里一定要注意琅锻。
• 為什么 list(zip(*matrix))[::-1] 是進(jìn)行上下翻轉(zhuǎn)而不是左右翻轉(zhuǎn)：這里還是要用到整體思想卦停，先將matrix內(nèi)部視為一個(gè)個(gè)黑箱，則 [::-1] 將會(huì)把黑箱逆序恼蓬。然后再看黑箱是什么（在上述逆序的過程中惊完，黑箱內(nèi)部是不發(fā)生任何變化的），而這里黑箱恰好就是一行一行的列表处硬。因此綜合來看小槐，上述操作是對 matrix 進(jìn)行上下翻轉(zhuǎn)而不是左右翻轉(zhuǎn)。

本題的變形：要求逆時(shí)針從矩陣的第一行第一列的元素開始打印荷辕，如何編寫代碼凿跳？

假設(shè)原始矩陣 仍如下所示：

            1   2   3   4
            5   6   7   8
            9   10  11  12
            13  14  15  16

這個(gè)時(shí)候要打印出的是 1, 5, 9, 13, 14, 15, 16, ... 這樣的順序，那么此時(shí)我們就應(yīng)該順時(shí)針旋轉(zhuǎn)矩陣疮方，然后取出首行控嗜。注意這時(shí)候取出的首行是 13, 9, 5, 1 ，跟我們要打印的順序是相反的骡显，因此取出首行后還要再逆序一下疆栏。

而如何將矩陣順時(shí)針旋轉(zhuǎn) 90 ° 呢曾掂？這一過程也需要分兩步來完成：

• 首先將矩陣上下顛倒：

  # 假設(shè)原始矩陣為a，則將a上下顛倒為：
  a[::-1]
  

• 然后壁顶，將矩陣進(jìn)行轉(zhuǎn)置简识，用 zip 配合 * 可以實(shí)現(xiàn)：

  # 假設(shè)上下顛倒后的矩陣為b修档，則轉(zhuǎn)置操作為：
  list(zip(*b))
  

可以看到：將矩陣順時(shí)針旋轉(zhuǎn)90度和逆時(shí)針旋轉(zhuǎn)90度的區(qū)別是：順時(shí)針旋轉(zhuǎn)是先上下顛倒再進(jìn)行轉(zhuǎn)置庄岖，而逆時(shí)針旋轉(zhuǎn)是先進(jìn)行轉(zhuǎn)置再進(jìn)行上下顛倒猪瞬。

代碼如下：

def anti_clock_wise(self, matrix)
    if not matrix:
        return []
    clock_wise = list(zip(*(matrix[::-1])))
    a = list(clock_wise.pop(0))[::-1]
    b = self.anti_clock_wise(clock_wise)
    return a + b

以上代碼和順時(shí)針打印的區(qū)別是：

• 順時(shí)針打印是先取第一行然后再旋轉(zhuǎn)，而逆時(shí)針打印是先旋轉(zhuǎn)再取第一行富岳；
• 順時(shí)針打印取出第一行后不需要額外的操作，而逆時(shí)針旋轉(zhuǎn)取出第一行后還需要進(jìn)行逆序操作拯腮。

30. 包含 min 函數(shù)的棧

分析：要用一個(gè)輔助棧來保存當(dāng)前棧中的最小值窖式，它和當(dāng)前棧的長度是相同的，即當(dāng)前棧中有幾個(gè)元素动壤，輔助棧中就必須要有幾個(gè)元素萝喘。這樣就能夠保證當(dāng)當(dāng)前棧中最小的元素被彈出后，下一個(gè)最小的元素能夠輕而易舉地被找到琼懊。

總之阁簸，解決問題的關(guān)鍵在于不是用一個(gè)變量去保存當(dāng)前棧中的最小值，而是用一個(gè)輔助棧去存儲(chǔ)每壓入一個(gè)元素后當(dāng)前棧中的最小值哼丈。

而在具體的實(shí)現(xiàn)過程中启妹，我們真的要開辟兩個(gè)棧嗎？其實(shí)是不需要的醉旦。我們可以用一個(gè)“二元椚拿祝”來將當(dāng)前棧和輔助棧合并成一個(gè)棧：在最簡單的棧中，每一個(gè)單元里通常存儲(chǔ)的都是一個(gè)值车胡。而現(xiàn)在檬输，我們讓每個(gè)單元里都以 tuple 的形式存儲(chǔ)兩個(gè)值：(top_value, min_value) ，其中 top_value 是每一次被壓入到棧中的元素匈棘，min_value 是每一次壓入新的數(shù)值后當(dāng)前棧中對應(yīng)的最小元素丧慈。這樣我們可以通過索引 [0] 來得到棧中的元素，用索引 [1] 來得到棧中的最小值主卫，就避免了額外開辟一個(gè)棧逃默。

代碼如下：

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self._stack = []
        
    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        cur_min = self.getMin()
        if x < cur_min:
            cur_min = x
        self._stack.append((x, cur_min))
        
    def pop(self):
        """
        :rtype: None
        """
        if not self._stack:
            return None
        else:
            self._stack.pop()
        
    def top(self):
        """
        :rtype: int
        """
        if not self._stack:
            return None
        else:
            return self._stack[-1][0]
        
    def getMin(self):
        """
        :rtype: int
        """
        if not self._stack:
            return float('inf') # 這個(gè)地方只能return無窮，不能return其他值
        else:
            return self._stack[-1][1]

31. 棧的壓入队秩、彈出序列

劍指offer中的思路總結(jié)：
判斷一個(gè)序列是不是棧的彈出序列的規(guī)律：

• 如果下一個(gè)彈出的數(shù)字剛好是棧頂數(shù)字笑旺，那么直接彈出；
• 如果下一個(gè)彈出的數(shù)字不在棧頂馍资，則把壓棧序列中還沒有入棧的數(shù)字壓入棧中筒主，直到把下一個(gè)需要彈出的數(shù)字壓入棧頂為止关噪；
• 如果把所有數(shù)字都壓入棧后仍然沒有找到下一個(gè)彈出的數(shù)字，那么該序列不可能是一個(gè)彈出序列乌妙。

代碼如下：

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        stack = []
        j = 0
        for num in pushed:
            stack.append(num)
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1
        return j == len(popped)

注意：pop 的過去式和過去分詞是雙寫 p 加 ed ：popped 使兔。

32-1. 從上到下打印二叉樹

本題實(shí)質(zhì)考查的是二叉樹的層次遍歷（廣度優(yōu)先遍歷），要借助于一個(gè)雙端隊(duì)列來實(shí)現(xiàn)藤韵。

二叉樹的層次遍歷代碼如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        from collections import deque
        queue = deque([root])
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(node.val) # 這里append的是node.val而非node
                queue.append(node.left)
                queue.append(node.right)
        return res

不管是廣度優(yōu)先遍歷一幅有向圖還是一棵樹虐沥，都要用到隊(duì)列。首先把起始節(jié)點(diǎn)（對樹而言是根節(jié)點(diǎn)）放入隊(duì)列泽艘。接下來每次從隊(duì)列的頭部取出一個(gè)節(jié)點(diǎn)欲险，然后把它能到達(dá)的節(jié)點(diǎn)（對樹而言即為子節(jié)點(diǎn)）都依次放入隊(duì)列。重復(fù)這個(gè)過程匹涮，直到隊(duì)列中的節(jié)點(diǎn)全部被取出為止天试。

32-2. 分行從上到下打印二叉樹

# 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 levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res, nodes = [], root and [root]
        while nodes:
            res.append([node.val for node in nodes])
            nodes = [child for node in nodes for child in (node.left, node.right) if child]
        return res

32-3. 之字形打印二叉樹

加一個(gè)變量 order 用來控制每次是順序還是逆序?qū)⒔Y(jié)果 append 到 res 中。代碼如下：

# 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 zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res, nodes, order = [], root and [root], 1
        while nodes:
            res.append([node.val for node in nodes][::order])
            order *= -1
            nodes = [child for node in nodes for child in (node.left, node.right) if child]
        return res

33. 二叉搜索樹的后序遍歷序列

二叉搜索樹（BinarySearchTrees）是二叉樹的一種特例然低。在二叉搜索樹中喜每，每個(gè)節(jié)點(diǎn)的值都介于它的左子節(jié)點(diǎn)（如果有）和右子節(jié)點(diǎn)（如果有）的值中間，且大于左子節(jié)點(diǎn)的值雳攘，小于右子節(jié)點(diǎn)的值带兜。

二叉搜索樹的后序遍歷序列有如下特點(diǎn)：

• 在后序遍歷得到的序列中，最后一個(gè)數(shù)字是樹的根節(jié)點(diǎn)的值吨灭；
• 序列中除去最后一個(gè)數(shù)外刚照，剩余的序列可以分為兩部分：第一部分是左子樹節(jié)點(diǎn)的值，它們都比根節(jié)點(diǎn)的值行帧涩咖；第二部分是右子樹節(jié)點(diǎn)的值，它們都比根節(jié)點(diǎn)的值大繁莹。

二叉樹遍歷序列問題的通用方法：

• 先根據(jù)遍歷序列的類型檩互，找到二叉樹的根節(jié)點(diǎn)；
• 再基于根節(jié)點(diǎn)將整棵樹的遍歷序列分成左子序列（左子樹對應(yīng)的序列）和右子序列（右子樹對應(yīng)的序列）兩部分咨演，然后再遞歸地處理這兩個(gè)子序列闸昨。

python itertools 模塊的 takewhile(condition, iterable) 函數(shù)：返回一連串的數(shù)字，直到 condition 不滿足時(shí)為止薄风，如：

takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4

代碼如下：

class Solution:
    def verifySequenceOfBST(self, sequence):
        """
        :type sequence: List[int]
        :rtype: bool
        """
        from itertools import takewhile
        if not sequence:
            return False  # [注]
        root = sequence[-1]
        left_seq = list(takewhile(lambda x: x < root, sequence[:-1]))
        right_seq = sequence[len(left_seq):-1]
        if not all(num>root for num in right_seq):
            return False
        left = right = True
        if left_seq:
            left = self.verifySequenceOfBST(left_seq)
        if right_seq:
            right = self.verifySequenceOfBST(right_seq)
        return left and right

【注】：劍指offer上認(rèn)為饵较，如果輸入的 sequence 為空，則應(yīng)返回 False 遭赂。而 AcWing 上認(rèn)為循诉，空序列是空二叉搜索樹的后序遍歷序列，因此應(yīng)該返回 True 撇他。這里采取和劍指offer上一樣的處理方法茄猫。

拓展：如果將題目改成“判斷該數(shù)組是不是某二叉搜索樹的前序遍歷結(jié)果”狈蚤，則解決方法和上面類似。只是在前序遍歷得到的序列中划纽，根節(jié)點(diǎn)的值是序列的第一個(gè)數(shù)字脆侮。

34. 二叉樹中和為某一值的路徑

在樹的前序、中序勇劣、后序 3 種遍歷方式中靖避，只有前序遍歷是首先訪問根節(jié)點(diǎn)的。

本題的本質(zhì)還是樹的遍歷比默。

書中對本題的分析：

• 用前序遍歷的方式來訪問樹幻捏。當(dāng)訪問到某一節(jié)點(diǎn)時(shí)，把該節(jié)點(diǎn)添加到路徑上（用棧來保存路徑）命咐，并累加該節(jié)點(diǎn)的值粘咖。如果該節(jié)點(diǎn)為葉節(jié)點(diǎn)，并且路徑中所有節(jié)點(diǎn)值之和剛好等于輸入的整數(shù)侈百，則當(dāng)前路徑符合要求，我們把它打印出來翰铡；如果當(dāng)前節(jié)點(diǎn)不是葉節(jié)點(diǎn)钝域，則繼續(xù)訪問它的子節(jié)點(diǎn)。
• 當(dāng)前節(jié)點(diǎn)訪問結(jié)束后锭魔，遞歸函數(shù)將自動(dòng)回到它的父節(jié)點(diǎn)例证。因此在函數(shù)返回上一級調(diào)用之前，必須要在路徑中刪除當(dāng)前節(jié)點(diǎn)并減去當(dāng)前節(jié)點(diǎn)的值迷捧，從而為遍歷其他節(jié)點(diǎn)做準(zhǔn)備织咧。
• 以上遞歸調(diào)用的本質(zhì)就是一個(gè)壓棧和出棧的過程。

代碼：

# 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 pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        stack = root and [(root, [root.val], sum)]
        result = []
        while stack:
            cur_node, cur_path, target_sum = stack.pop()
            if not cur_node.left and not cur_node.right and cur_node.val == target_sum:
                result.append(cur_path)
            # if cur_node.left: # 必須要先添加右子節(jié)點(diǎn)漠秋，否則不是前序遍歷
            #     stack.append((cur_node.left, cur_path+))
            if cur_node.right:
                stack.append((cur_node.right, cur_path+[cur_node.right.val], target_sum-cur_node.val))
            if cur_node.left:
                stack.append((cur_node.left, cur_path+[cur_node.left.val], target_sum-cur_node.val))
        return result

注意：利用棧實(shí)現(xiàn)前序遍歷時(shí)笙蒙，必須要先 append 右子節(jié)點(diǎn)再 append 左子節(jié)點(diǎn)，否則不是前序遍歷庆锦，本題的代碼就會(huì)出問題捅位。

35. 復(fù)雜鏈表的復(fù)制

通常分治法都可以用遞歸的代碼實(shí)現(xiàn)。

網(wǎng)站上的方法采用的是書中的第二種方法：用空間換時(shí)間

• 對于有 個(gè)節(jié)點(diǎn)的鏈表搂抒，需要用到一個(gè)大小為 的哈希表艇搀，這樣就可以把時(shí)間復(fù)雜度降到 。

代碼：

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        hash_table = {None: None}  # [注]
        p1 = p2 = head
        
        while p1:
            hash_table[p1] = Node(p1.val, None, None)
            p1 = p1.next
        
        while p2:
            hash_table[p2].next = hash_table[p2.next]
            hash_table[p2].random = hash_table[p2.random]
            p2 = p2.next
        
        return hash_table[head]

【注】：這個(gè)地方不能寫成 hash_table = {} 求晶，否則可能會(huì)報(bào) KeyError 為 None 的錯(cuò)誤焰雕。之所以要寫成 hash_table = {None: None} ，實(shí)際上是為這個(gè) hash_tabel 提供了一個(gè)原始的鍵值對芳杏，即當(dāng)要取 hash_tabel 中鍵為 None 的值時(shí)矩屁，將返回 None 辟宗。由于 None 的特殊性，如果不聲明在 hash_table 中有這樣一個(gè)鍵值對档插，則在 hash_table 中取 None 這個(gè)鍵的值時(shí)就會(huì)報(bào)錯(cuò)慢蜓。

36. 二叉搜索樹與雙向鏈表

書中的分析：

• 為什么能夠進(jìn)行二叉搜索樹和雙向鏈表的轉(zhuǎn)換：在二叉樹中，每個(gè)節(jié)點(diǎn)都有兩個(gè)指向子節(jié)點(diǎn)的指針郭膛。在雙向鏈表中晨抡，每個(gè)節(jié)點(diǎn)也有兩個(gè)指針，分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)则剃。由于這兩種節(jié)點(diǎn)的結(jié)構(gòu)相似耘柱，同時(shí)二叉搜索樹也是一種排序的數(shù)據(jù)結(jié)構(gòu)，因此棍现，在理論上有可能實(shí)現(xiàn)二叉搜索樹和排序雙向鏈表的轉(zhuǎn)換调煎。
• 轉(zhuǎn)換的思路：在二叉搜索樹中，左子節(jié)點(diǎn)的值總是小于父節(jié)點(diǎn)的值己肮，右子節(jié)點(diǎn)的值總是大于父節(jié)點(diǎn)的值士袄。因此，我們在將二叉搜索樹轉(zhuǎn)換成排序雙向鏈表時(shí)谎僻，原先指向左子節(jié)點(diǎn)的指針調(diào)整為鏈表中指向前一個(gè)節(jié)點(diǎn)的指針娄柳，原先指向右子節(jié)點(diǎn)的指針調(diào)整為鏈表中指向后一個(gè)節(jié)點(diǎn)的指針。
• 可以使用中序遍歷的方法來遍歷樹中的每個(gè)節(jié)點(diǎn)艘绍，這樣就可以按照從小到大的順序遍歷二叉樹的每個(gè)節(jié)點(diǎn)赤拒。
• 在節(jié)點(diǎn)之間進(jìn)行連接的時(shí)候，根節(jié)點(diǎn)向左總是和左子樹中值最大的一個(gè)節(jié)點(diǎn)進(jìn)行連接（注意诱鞠，左子樹中值最大的節(jié)點(diǎn)并不是根節(jié)點(diǎn)挎挖，而是根節(jié)點(diǎn)的右子節(jié)點(diǎn)），根節(jié)點(diǎn)向右總是和右子樹中值最小的一個(gè)節(jié)點(diǎn)進(jìn)行連接（右子樹中值最小的節(jié)點(diǎn)是根節(jié)點(diǎn)的左子節(jié)點(diǎn)）航夺。
• 按照中序遍歷的順序蕉朵，當(dāng)我們遍歷轉(zhuǎn)換到整棵樹的根節(jié)點(diǎn)時(shí)，左子樹已經(jīng)轉(zhuǎn)換成一個(gè)排序的鏈表了阳掐，并且處在鏈表中的最后一個(gè)節(jié)點(diǎn)是它當(dāng)前值最大的節(jié)點(diǎn)墓造，我們把這個(gè)節(jié)點(diǎn)和樹的根節(jié)點(diǎn)連接起來，此時(shí)左半部分便已經(jīng)排序完畢锚烦。然后再讓根節(jié)點(diǎn)和右半部分中最小的節(jié)點(diǎn)連接起來即可觅闽。整個(gè)過程很顯然可以用遞歸實(shí)現(xiàn)。

Morris Traversal:

參考：https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html

通常涮俄，實(shí)現(xiàn)二叉樹的前序（preorder）蛉拙、中序（inorder）、后序（postorder）遍歷有兩個(gè)常用的方法：一是遞歸(recursive)彻亲，二是使用棧實(shí)現(xiàn)的迭代版本(stack+iterative)孕锄。這兩種方法都是O(n)的空間復(fù)雜度（遞歸本身占用stack空間或者用戶自定義的stack）吮廉，所以不滿足要求。

Morris Traversal方法可以做到這兩點(diǎn)畸肆，與前兩種方法的不同在于該方法只需要O(1)空間宦芦，而且同樣可以在O(n)時(shí)間內(nèi)完成。

要使用O(1)空間進(jìn)行遍歷轴脐，最大的難點(diǎn)在于调卑，遍歷到子節(jié)點(diǎn)的時(shí)候怎樣重新返回到父節(jié)點(diǎn)（假設(shè)節(jié)點(diǎn)中沒有指向父節(jié)點(diǎn)的p指針），由于不能用棧作為輔助空間大咱。為了解決這個(gè)問題恬涧，Morris方法用到了線索二叉樹（threaded binary tree）的概念。在Morris方法中不需要為每個(gè)節(jié)點(diǎn)額外分配指針指向其前驅(qū)（predecessor）和后繼節(jié)點(diǎn)（successor）碴巾，只需要利用葉子節(jié)點(diǎn)中的左右空指針指向某種順序遍歷下的前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)就可以了溯捆。

用Morris Traversal實(shí)現(xiàn)中序遍歷的流程如下：

• 最開始時(shí)，將整棵樹的根節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)厦瓢；
• 然后開始判斷：
  • 如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空提揍，則在當(dāng)前節(jié)點(diǎn)的左子樹中找到在中序遍歷條件下的前驅(qū)節(jié)點(diǎn)（即最右最下方的節(jié)點(diǎn)），然后對前驅(qū)節(jié)點(diǎn)進(jìn)行判斷：
    • 如果前驅(qū)節(jié)點(diǎn)的右子節(jié)點(diǎn)為空（表明Morris Traversal處在查找過程）煮仇，則讓前驅(qū)節(jié)點(diǎn)的右子節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)劳跃，同時(shí)斷開當(dāng)前節(jié)點(diǎn)和其左子節(jié)點(diǎn)之間的連接（即讓當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)指向None），然后讓當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)（這里的左子節(jié)點(diǎn)指的是斷開之前的左子節(jié)點(diǎn)）欺抗；
    • 如果前驅(qū)節(jié)點(diǎn)的右孩子就是當(dāng)前節(jié)點(diǎn)（表明Morris Traversal處在回溯過程），則輸出當(dāng)前節(jié)點(diǎn)强重，然后將它的右孩子重新設(shè)為空（恢復(fù)樹的形狀）绞呈，同時(shí)將當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)（設(shè)為空之前的右子節(jié)點(diǎn)）。
  • 如果當(dāng)前節(jié)點(diǎn)的左孩子為空间景，則輸出當(dāng)前節(jié)點(diǎn)并將其右孩子設(shè)為當(dāng)前節(jié)點(diǎn)佃声。
  • 重復(fù)以上兩個(gè)大步驟，直至當(dāng)前節(jié)點(diǎn)為空倘要。

使用Morris Traversal解決本題的代碼如下：

（方法一需要用到python自帶的工具圾亏，這里只用方法三：Morris Traversal。）

# 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 convert(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        cur = root
        pre = res = None
        while cur:
            while cur.left:
                q = cur.left
                while q.right:
                    q = q.right
                q.right = cur
                cur.left, cur = None, cur.left # 斷開左指針
            cur.left = pre # 當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)為空后封拧，第一件事就是讓當(dāng)前節(jié)點(diǎn)的左指針指向pre
            if pre is None:
                res = cur # 這里是為了找到鏈表的頭志鹃，只執(zhí)行一次
            else:
                pre.right = cur
            pre, cur = cur, cur.right
        return res

37. 序列化二叉樹

序列化就是指將樹結(jié)構(gòu)的數(shù)據(jù)類型轉(zhuǎn)換成一個(gè)字符串，如何轉(zhuǎn)換以及轉(zhuǎn)換成一個(gè)什么樣的字符串泽西，就是序列化的過程要考慮的問題曹铃。
反序列化就是從序列化后的字符串中恢復(fù)出樹結(jié)構(gòu)。

書中的分析：

可以先把一棵二叉樹序列化成一個(gè)前序遍歷序列捧杉，然后再將這個(gè)前序遍歷序列通過反序列化重建出原二叉樹陕见。

如果二叉樹的序列化是從根節(jié)點(diǎn)開始的秘血，那么相應(yīng)的反序列化在根節(jié)點(diǎn)的數(shù)值讀出來的時(shí)候就可以開始了。因此评甜，可以根據(jù)前序遍歷的順序來序列化二叉樹（因?yàn)榍靶虮闅v正好是從根節(jié)點(diǎn)開始的）灰粮。當(dāng)遍歷的過程中碰到空指針時(shí)，這些空指針要被序列化為一個(gè)特殊的字符（如 $ ）忍坷。此外粘舟，節(jié)點(diǎn)的數(shù)值之間要用一個(gè)特殊的字符（如 , ）隔開。

總結(jié)前面序列化和反序列化的過程承匣，可以發(fā)現(xiàn)都是把二叉樹分解成三部分：根節(jié)點(diǎn)蓖乘、左子樹和右子樹。在處理根節(jié)點(diǎn)之后再分別處理它的左韧骗、右子樹嘉抒。因此這個(gè)問題可以用遞歸解決。

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return '$'
        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def deserialize_tree(nodes):
            val = next(nodes)
            if val == '$':
                return None
            root = TreeNode(val)
            root.left = deserialize_tree(nodes)
            root.right = deserialize_tree(nodes)
            return root
            
        nodes = iter(data.split(','))
        return deserialize_tree(nodes)
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

38. 字符串的排列

書中的分析：
可以把一個(gè)字符串看成由兩部分組成：第一部分是它的第一個(gè)字符袍暴；第二部分是后面的所有字符些侍。
這樣求整個(gè)字符串的排列就可以看成兩步。第一步求所有可能出現(xiàn)在第一個(gè)位置的字符政模，即把第一個(gè)字符和后面所有的字符交換岗宣。第二步固定第一個(gè)字符，求后面所有字符的排列淋样。這時(shí)候仍把后面的所有字符分成兩部分：后面字符的第一個(gè)字符耗式，以及這個(gè)字符之后的所有字符。然后把第一個(gè)字符逐一和它后面的字符交換趁猴。這顯然是一個(gè)遞歸的過程刊咳。

網(wǎng)站實(shí)現(xiàn)（循環(huán)）：

def Permutation(self, ss):
    ans = ['']
    for s in ss:
        ans = [p[:i] + s + p[i:]
               for p in ans for i in range((p+s).index(s)+1)]
    return sorted(ans) if ss else []

實(shí)現(xiàn)思路：自底向上。假設(shè) ss = 'abc' 儡司，則：

• step 1：假設(shè)原始結(jié)果為 [''] 娱挨，先取 ss 中的第一個(gè)字符 a ，此時(shí)這個(gè)字符和原始的結(jié)果之間只可能有一種排列方式捕犬，即：ans = ['a'] 跷坝；

• step 2：再取 ss 中的第二個(gè)字符 b，此時(shí) b 和上一步中的結(jié)果 ['a'] 可能構(gòu)成兩種排列：將 b 插在 a 的前面和將 b 插在 a 的后面碉碉，即： ans = ['ba', 'ab'] 柴钻；

• step 3：最后取 ss 中的第三個(gè)字符 c ，此時(shí) c 和上一步的結(jié)果 ['ba', 'ab'] 將會(huì)有多種組合方式垢粮，應(yīng)該分別將 ans 中的兩個(gè)字符串取出來顿颅，和 c 進(jìn)行排列，此即 for p in ans 的含義。將 c 插入到 ba 中粱腻，等價(jià)于將 ba 拆開庇配，然后將 c 放到拆開的位置。如何拆呢绍些？這里用切片實(shí)現(xiàn)：

  • 'cba' = 'c' + 'ba' = 'ba'[:0] + 'c' + 'ba'[0:]
  • 'bca' = 'b' + 'c' + 'a' = 'ba'[:1] + 'c' + 'ba'[1:]
  • 'bac' = 'ba' + 'c'= 'ba'[:2] + 'c' + 'ba'[2:]

  因此第二個(gè)循環(huán)中 i 的作用就是確定如何對 p 進(jìn)行拆分捞慌。這樣當(dāng) p 遍歷完 ans 后，ans 中的所有結(jié)果便都和字符 s 進(jìn)行了所有的排列柬批。

這里用 range((p+s).index(s)+1) 而不用 range(len(p+s)-1) 是因?yàn)樾ピ瑁绻?p 和 s 中有重復(fù)的字符，前者可以避免重復(fù)進(jìn)行排列氮帐，而后者無法做到這一點(diǎn)嗅虏。（如 'ba' + 'a' ）。

如果是要求對整數(shù)做排列上沐，則代碼為：

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [[]]
        for num in nums:
            res = [p[:i] + [num] + p[i:]
                  for p in res for i in range((p+[num]).index(num)+1)]
        return sorted(res) if nums else []

注意 int 型的數(shù)字和列表是不能相加的皮服，必須要在數(shù)字外面包上中括號，然后才能和 list 相加参咙。

39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

絕大部分動(dòng)態(tài)規(guī)劃算法的分析和代碼實(shí)現(xiàn)都是分兩個(gè)步驟來完成的：

• 用遞歸的思路來分析問題龄广；
• 基于循環(huán)用數(shù)組來保存中間結(jié)果從而實(shí)現(xiàn)代碼。

波義耳摩爾投票算法：https://darktiantian.github.io/%E6%B3%A2%E4%B9%89%E5%B0%94%E6%91%A9%E5%B0%94%E6%8A%95%E7%A5%A8%E7%AE%97%E6%B3%95%EF%BC%88Boyer-Moore-Voting-Algorithm%EF%BC%89/

算法描述：

遍歷數(shù)組的時(shí)候保存兩個(gè)值：一個(gè)是數(shù)組中的數(shù)字蕴侧，另一個(gè)是次數(shù)择同。當(dāng)我們遍歷到下一個(gè)數(shù)字的時(shí)候，如果下一個(gè)數(shù)字和我們之前保存的數(shù)字相同净宵，則次數(shù)加1敲才；如果下一個(gè)數(shù)字和我們之前保存的數(shù)字不同，則次數(shù)減1择葡。如果次數(shù)為零紧武，那么需要保存下一個(gè)數(shù)字，并把次數(shù)設(shè)為1.由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多刁岸，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為1時(shí)的對應(yīng)數(shù)字脏里。

優(yōu)點(diǎn)：通過這種算法她我，在線性時(shí)間復(fù)雜度和常數(shù)空間復(fù)雜度的情況下即可找到數(shù)組的主要元素（即出現(xiàn)次數(shù)超過一半的元素）虹曙。

代碼實(shí)現(xiàn)：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)
        
        return candidate

40. 最小的 k 個(gè)數(shù)

用一個(gè)最大堆來存儲(chǔ)最小的 k 個(gè)數(shù)字，然后從剩余的數(shù)據(jù)中每次讀入一個(gè)數(shù)番舆。如果這個(gè)數(shù)比堆中最大的數(shù)還大酝碳，那么可以不用管這個(gè)數(shù)字虎锚；如果這個(gè)數(shù)比堆中最大的數(shù)字小野揪，那么就用這個(gè)數(shù)來替換堆中最大的數(shù)秤朗。

在最大堆中通铲，根節(jié)點(diǎn)的值總是大于它的子樹中任意節(jié)點(diǎn)的值吻谋。因此，每次都可以在 的時(shí)間內(nèi)從堆中找到最大值尤蒿，但需要 的時(shí)間來完成刪除及插入操作必逆。

因此，用最大堆的方法總的時(shí)間復(fù)雜度為 芽偏，而且這種方法適合處理海量的輸入數(shù)據(jù)雷逆。

代碼：

def GetLeastNumbers_Solution(self, tinput, k):
    import heapq as hq
    if k > len(tinput) or k <= 0: return []
    heap = [-x for x in tinput[:k]] # 因?yàn)楹竺嬗玫亩际亲钚≈担赃@里提前將它們轉(zhuǎn)成負(fù)數(shù)
    hq.heapify(heap)
    for num in tinput[k:]:
        if -heap[0] > num: # heap[0]是堆中的最小值
            hq.heapreplace(heap, -num)
    return sorted(-x for x in heap)

點(diǎn)評：當(dāng)需要在某個(gè)數(shù)據(jù)容器內(nèi)頻繁查找及替換最大值時(shí)污尉，二叉樹是一個(gè)合適的選擇膀哲，而且此時(shí)用堆或者紅黑樹等特殊的二叉樹來實(shí)現(xiàn)比較合適。

41. 數(shù)據(jù)流中的中位數(shù)

書中的分析：

假設(shè)將整個(gè)數(shù)據(jù)流進(jìn)行排序被碗，然后用一個(gè)分界線將數(shù)據(jù)分為兩部分：分界線左側(cè)的數(shù)據(jù)均不大于中位數(shù)某宪，分界線右側(cè)的數(shù)據(jù)均不小于中位數(shù)。

然后锐朴，用一個(gè)最大堆去裝載分界線左側(cè)的數(shù)據(jù)兴喂，用一個(gè)最小堆去裝載分界線右側(cè)的數(shù)據(jù)。這樣如果整個(gè)數(shù)據(jù)流的個(gè)數(shù)為奇數(shù)個(gè)包颁，則最大堆堆頂或最小堆堆頂?shù)臄?shù)據(jù)即為中位數(shù)瞻想；如果整個(gè)數(shù)據(jù)流的個(gè)數(shù)為偶數(shù)個(gè)，則最大堆堆頂和最小堆堆頂數(shù)據(jù)的平均數(shù)即為中位數(shù)娩嚼。

而不管是最大堆還是最小堆蘑险，獲取堆頂數(shù)據(jù)的時(shí)間復(fù)雜度均為 。

其次岳悟，往堆中插入一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是 佃迄。為了保證數(shù)據(jù)平均分配到兩個(gè)堆中（即兩個(gè)堆中數(shù)據(jù)的個(gè)數(shù)相差不能超過1），可以在堆中現(xiàn)有數(shù)據(jù)的總數(shù)目是偶數(shù)時(shí)將新來的數(shù)據(jù)插入到最小堆中贵少，否則將其插入到最大堆中呵俏。

此外，還要保證最大堆中的所有數(shù)據(jù)都要小于最小堆中的所有數(shù)據(jù)滔灶。如果新來的數(shù)據(jù)大于最小堆中的一些數(shù)據(jù)但是卻被插入到最大堆中了普碎，則此時(shí)還是先將其插入到最大堆（可能是為了維持?jǐn)?shù)據(jù)平衡的需要），然后將最大堆中最大的數(shù)字拿出來并將其插入到最小堆录平。新來的數(shù)據(jù)小于最大堆中的某些數(shù)但卻被插入到最小堆的情形也是如此麻车。

網(wǎng)站上的分析：

使用兩個(gè)堆，最大堆存儲(chǔ)較小的數(shù)據(jù)斗这，最小堆存儲(chǔ)較大的數(shù)據(jù)动猬。添加數(shù)字時(shí)，先添加到最大堆表箭，然后最大堆返回一個(gè)最大的數(shù)字給最小堆赁咙，最后為了平衡，可能需要最小堆還給最大堆一個(gè)最小值彼水，以保證最大堆的長度>=最小堆的長度握童。由于headpq是最小堆，所以使用取反實(shí)現(xiàn)最大堆随闪。添加數(shù)字：Time-O(logn)畜吊，取出中位數(shù)：Time-O(1)延窜。

代碼：

import heapq as hq

class MedianFinder:

    def __init__(self):
        self.lo, self.hi = [], []  # lo is max_heap, hi is min_heap
        
    def addNum(self, num):
        hq.heappush(self.lo, -num) # 新來的數(shù)據(jù)總是先放到最大堆
        hq.heappush(self.hi, -hq.heappop(self.lo)) # 然后從最大堆中彈出最大值到最小堆
        
        if len(self.lo) < len(self.hi): # 最后維持?jǐn)?shù)據(jù)間的平衡
            hq.heappush(self.lo, -hq.heappop(self.hi))       

    def findMedian(self):
        if len(self.lo) == len(self.hi):
            return (-self.lo[0]+self.hi[0]) / 2.0
        else:
            return float(-self.lo[0])

42. 連續(xù)子數(shù)組的最大和

書中的方法：

將第一個(gè)數(shù)字加到第二個(gè)數(shù)字上，如果和小于0吻育，那么不管第三個(gè)數(shù)字為幾侨糟，這一小于0的和如果加到第三個(gè)數(shù)上面，將只會(huì)使第三個(gè)數(shù)更小藻治。因此應(yīng)該拋棄前兩個(gè)數(shù)的和碘勉，從第三個(gè)數(shù)字開始重新和后面的數(shù)進(jìn)行累加。

即：只有當(dāng)前面的累加和為正值時(shí)桩卵，才讓它和后面的數(shù)繼續(xù)相加验靡，否則從后面的數(shù)開始重新進(jìn)行累加倍宾。

代碼實(shí)現(xiàn)：

def maxSubArray(self, nums):
    cp_nums = nums[:]
    for i in range(1, len(nums)):
        if cp_nums[i-1] > 0:
            cp_nums[i] += cp_nums[i-1]
    return max(cp_nums)

為了避免對原始數(shù)組的修改，這個(gè)代碼先將原始數(shù)組復(fù)制了一份胜嗓，因此會(huì)有額外的 的空間復(fù)雜度高职。然后，從復(fù)制數(shù)組的第2項(xiàng)開始辞州，判斷并累加前面的結(jié)果怔锌。

43. 1～n 整數(shù)中 1 出現(xiàn)的次數(shù)

先給出代碼：

def countDigitOne(self, n):    
    countr, i = 0, 1
    while i <= n:
        divider = i * 10
        countr += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
        i *= 10
    return countr

然后再來分析代碼是如何執(zhí)行的。debug 代碼如下：

def countDigitOne(n):    
    countr, i = 0, 1
    while i <= n:
        divider = i * 10
        print('divider = {}, i = {}, cur_sum = {}, // = {}, % = {}'.format(divider, i, (n // divider) * i + min(max(n % divider - i + 1, 0), i), (n // divider) * i, min(max(n % divider - i + 1, 0), i)))
        countr += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
        i *= 10
    return countr


if __name__ == '__main__':
    y = countDigitOne(21345)
    print(y)

這里讓輸入的數(shù)字 n=21345变过，運(yùn)行結(jié)果如下：

divider = 10, i = 1, cur_sum = 2135, // = 2134, % = 1
divider = 100, i = 10, cur_sum = 2140, // = 2130, % = 10
divider = 1000, i = 100, cur_sum = 2200, // = 2100, % = 100
divider = 10000, i = 1000, cur_sum = 2346, // = 2000, % = 346
divider = 100000, i = 10000, cur_sum = 10000, // = 0, % = 10000
18821

程序是按位（從最高位到最低位）埃元、分區(qū)（整區(qū)和零區(qū)）來統(tǒng)計(jì)1出現(xiàn)的次數(shù)的。不妨倒著來看：

（1）首先固定萬位數(shù)字為1媚狰，先來看整區(qū)亚情，整區(qū)即以10w為單位，看n最大能達(dá)到多少哈雏。顯然n不夠10w楞件，因此整區(qū)的數(shù)字范圍不存在。顯然裳瘪，此時(shí)一種可能的情況都沒有土浸；

然后再來看零區(qū)（零區(qū)即在整區(qū)數(shù)字范圍之外的數(shù)字），零區(qū)的數(shù)字范圍為 0 ~ 21345 彭羹，固定萬位為1黄伊，則所有可能的情況為：

10000 ~ 19999

總共有 種可能的情況。

（2）然后固定千位為1派殷，還是先來看整區(qū)的情況还最。此時(shí)的整區(qū)為以1w為單位，看n最大能取多少毡惜。顯然拓轻，以1w為單位的話，n最大只能取到20000经伙，因此整區(qū)的數(shù)字范圍為 0 ~ 20000 扶叉。固定千位為1，則所有可能的情況為：

11000 ~ 11999
 1000  ~ 1999

最高位可以取0和1兩個(gè)數(shù)字帕膜，后三位每一位都可以取0~9這10個(gè)數(shù)字枣氧，因此總共有 種可能的情況。

再來看零區(qū)垮刹，此時(shí)零區(qū)的數(shù)字分布在 20000 ~ 21345 之間达吞，固定千位為1，則所有可能的情況為：

21000 ~ 21345

此時(shí)后三位的數(shù)字不能隨便取荒典，因?yàn)樗幸粋€(gè)上限 345 酪劫，因此零區(qū)所有可能的情況為 種吞鸭。

（3）接著固定百位為1，則整區(qū)應(yīng)該以千計(jì)契耿，最大只能達(dá)到21000，因此整區(qū)數(shù)字范圍為 0 ~ 21000 螃征，固定百位數(shù)字為1搪桂，則所有可能的情況為：

20100 ~ 20199
19100 ~ 19199
......
100   ~   199

顯然，總共包括21大種情況盯滚，每一大種情況內(nèi)部由于個(gè)位和十位數(shù)字都可以從0到9任取踢械，因此所有可能的情況為 種。

然后看零區(qū)魄藕，除整區(qū)外内列，零區(qū)剩余的數(shù)字范圍為 21001 ~ 21345 ，然后固定百位數(shù)字為1背率，則所有可能的情況為：

21100 ~ 21199

總共是 種情況话瞧。

（4）固定十位數(shù)字為1，則整區(qū)以百計(jì)寝姿，最大21300交排，則整區(qū)共有 種情況；

零區(qū)為 21301 ~ 21345 饵筑，固定十位數(shù)字為1埃篓，則共有 種情況。

（5）最后固定個(gè)位數(shù)字為1根资，整區(qū)以十計(jì)架专，最大21340，固定個(gè)位數(shù)字為1玄帕，共有 種情況部脚；

零區(qū)：21341 ~ 21345 ，固定個(gè)位數(shù)字為1裤纹，只有一種情況：21341睛低。

以上代碼就是按照這一思路來編寫的， i 代表的是固定哪一位數(shù)字為1服傍， divider 代表的是整區(qū)以多少計(jì)钱雷，注意到 divider 總是 i 的10倍。

(n // divider) * i 代表的是整區(qū)總共有多少種情況吹零；

min(max(n % divider - i + 1, 0), i) 代表的是零區(qū)有多少種情況罩抗。最外層的 min 代表的是零區(qū)的情況最多不超過 i ，如 i 在萬位時(shí)最多不超過10000灿椅， i 在千位時(shí)最多不超過 1000套蒂。注意到钞支，只要 i 所在的數(shù)字大于1，則總有：

max(n % divider - i + 1, 0) > i

成立操刀，稱此種情況為“飽和”烁挟，即當(dāng) i 所在的數(shù)字大于1時(shí)，零區(qū)范圍內(nèi) i 后面的數(shù)字總能取滿（即能取盡0~9的所有情況）骨坑，因此零區(qū)總的情況數(shù)總是10的冪次撼嗓，即由外層 min 函數(shù)中的 i 決定。
而當(dāng) i 所在的數(shù)字小于或等于1時(shí)欢唾，總有：

max(n % divider - i + 1, 0) < i

成立且警，稱此種情況為“不足”，即如果 i 所在的數(shù)字小于或等于1礁遣，則零區(qū)范圍內(nèi) i 后面的數(shù)字就不能取盡0~9的所有情況斑芜，此時(shí)零區(qū)的所有情況將受限于 i 后面的數(shù)字最大能達(dá)到多大（當(dāng) i=1 時(shí)）或干脆直接就等于0（當(dāng) i=0 時(shí)）。

以上就是對整個(gè)代碼運(yùn)行過程的分析祟霍。由于是按位進(jìn)行循環(huán)的杏头，因此時(shí)間復(fù)雜度為 。推導(dǎo)過程如下：

假設(shè) 為輸入的數(shù)字沸呐， 為需要循環(huán)的次數(shù)大州，則有：

因此，時(shí)間復(fù)雜度為 垂谢。

44. 數(shù)字序列中某一位的數(shù)字

書中的分析如下：

假設(shè) n=1001厦画，則：

• 序列的前 10 位是 0~9 這 10 個(gè)只有一位的數(shù)字。顯然第 1001 位在這 10 個(gè)數(shù)字之后滥朱，因此這 10 個(gè)數(shù)字可以直接跳過根暑。然后再從后面緊跟著的序列中找第 991 （991=1001-1-1x9）位的數(shù)字；
• 接下來 180 位數(shù)字是 90 個(gè) 10~99 的兩位數(shù)徙邻。由于 991>180排嫌，所以第 991 位在所有的兩位數(shù)之后。我們再跳過 90 個(gè)兩位數(shù)缰犁，繼續(xù)從后面找 811 （811=991-2x90）位淳地；
• 接下來的 2700 位是 900 個(gè) 100~999 的三位數(shù)。由于 811<2700帅容，所以第 811 位是某個(gè)三位數(shù)中的一位颇象。由于 811//3 = 270，因此第811位是從100開始的第270個(gè)數(shù)字并徘，即 100+270=370遣钳。然后再判斷是屬于370的第幾位：811%3=1，因此是屬于370的第1位（索引從0開始）麦乞，即數(shù)字7蕴茴。

代碼：

class Solution(object):
    def digitAtIndex(self, n):
        """
        :type n: int
        :rtype: int
        """
        base = 1   # base是基數(shù)劝评，它的取值分別為1, 10, 100, 1000, ...
        width = 1  # width是對應(yīng)的位寬，取值分別為1, 2, 3, 4, ...
        basecount = 9  # basecount是在某個(gè)位寬范圍內(nèi)總共有多少個(gè)數(shù)倦淀，取值分別為9, 90, 900, ...
        nleft = n - 1  # nleft是當(dāng)前還剩多少位蒋畜，取值為n-1, n-1-1*9, n-1-2*90, n-1-3*900, ..., n-1-width*basecount
        while nleft > basecount * width:
            nleft -= basecount * width
            base *= 10 # 基數(shù)每次擴(kuò)大10倍
            width += 1 # 位寬每次增加一位
            basecount *= 10
        
        num = base + nleft//width  # 確定該數(shù)字是幾，必須要加上基數(shù)
        bit = nleft % width  # 確定該數(shù)字屬于num的第幾位
        
        return int(str(num)[bit])  

這里要注意的是 nleft 的初始值是 n-1 撞叽。

45. 把數(shù)組排成最小的數(shù)

n 個(gè)數(shù)字總共有 種排列方式姻成。

書中的分析：這道題其實(shí)是希望我們能找到一個(gè)排序規(guī)則，即給出兩個(gè)數(shù)字 和 能扒，我們需要確定一個(gè)規(guī)則判斷 和 哪個(gè)應(yīng)該排在前面佣渴，而不僅僅是比較這兩個(gè)數(shù)字的值哪個(gè)更大辫狼。

根據(jù)題目的要求初斑，兩個(gè)數(shù)字 和 能拼接成數(shù)字 和 。如果 膨处，那么我們應(yīng)該打印出 见秤，即 應(yīng)該排在 的前面，我們定義此時(shí) 小于 真椿；反之鹃答，如果 ，則我們定義 小于 突硝；如果 测摔，則 等于 。自定義比較方法可以通過python的 functools.cmp_to_key() 函數(shù)實(shí)現(xiàn)解恰。

在比較時(shí)锋八，應(yīng)該先將 int 型的數(shù)字轉(zhuǎn)換成字符串。

from functools import cmp_to_key
def PrintMinNumber(self, numbers):
    # write code here
    nums = list(map(str, numbers))
    nums.sort(key=cmp_to_key(lambda x, y: ((x+y)>(y+x)) - ((y+x)>(x+y))))
    return ''.join(nums)

上述代碼中护盈，以下部分：

lambda x, y: ((x+y)>(y+x)) - ((y+x)>(x+y))

字符串的比較返回的是 bool 型的結(jié)果挟纱，因此上述代碼等價(jià)于以下三種情況：

if (x+y)>(y+x): True - False = 1 - 0 = 1
if (y+x)>(x+y): False - True = 0 - 1 = -1
if (x+y)=(y+x): False - False = 0 - 0 = 0

46. 把數(shù)字翻譯成字符串

書中的分析：如果用自上而下的遞歸來解決問題，則會(huì)造成重復(fù)的計(jì)算（就和計(jì)算斐波那契數(shù)是一樣的）腐宋，因此可以從最小的子問題開始紊服，用自下而上的循環(huán)解決問題。也就是說胸竞，我們可以從數(shù)字的末尾開始欺嗤，然后從右到左翻譯并計(jì)算不同翻譯的數(shù)目。（如果從數(shù)字的開頭開始卫枝，從左到右翻譯則是遞歸的方法剂府。）

代碼如下：

ef numDecodings(self, s: str) -> int:
    # w tells the number of ways
    # v tells the previous number of ways
    # d is the current digit
    # p is the previous digit
    v, w, p = 0, int(s>''), ''
    for d in s:
        v, w, p = w, int(d>'0')*w + (9<int(p+d)<27)*v, d
    return w

對這個(gè)代碼的分析如下：

假設(shè)給定一個(gè)字符串 x ，我們將其視為一個(gè)黑箱剃盾，假設(shè)它有 w 種翻譯方法腺占。同時(shí)淤袜，如果將 x 的最后一個(gè)字符去掉，剩余的字符有 v 種翻譯方法衰伯。

現(xiàn)在又來了一個(gè)新字符 d 铡羡，那么 x 和 d 放在一塊會(huì)有多少種翻譯方法呢？根據(jù)我們已經(jīng)直到的信息意鲸，我們不妨將其分為兩種情況：

• 第一種情況：如果 d 本身能夠翻譯成字符烦周，那么 d 自己只會(huì)有一種翻譯方法，而前面的 x 有 w 種翻譯方法怎顾，則此時(shí)總共會(huì)有 1 * w 種翻譯方法读慎，亦即代碼中的 int(d>'0')*w ；
• 第二種情況：將 d 和 x 的最后一個(gè)字符 p 配對槐雾，如果 p 和 d 放一起后也能翻譯成字符夭委，那么這也將提供一種翻譯方法，而 x 去掉 p 后總共有 v 種翻譯方法募强，因此此時(shí)總的翻譯方法數(shù)為：1 * v 株灸，亦即代碼中的 (9<int(p+d)<27)*v 。

值得注意的是擎值，這種基于循環(huán)的自下而上的方法雖然可以避免重復(fù)的計(jì)算慌烧，但是它要保存中間結(jié)果。根據(jù)前面的分析鸠儿，這里要保存的中間結(jié)果有三個(gè)：

• 上一輪總的翻譯方法數(shù)屹蚊，即代碼中的 w ；
• 上一輪去掉最后一個(gè)字母的方法數(shù)进每，亦即上上一輪的方法數(shù)汹粤，在代碼中表示為 v ；
• 上一輪的最后一個(gè)字母品追，即代碼中的 p 玄括，代碼中的 d 是當(dāng)前這一輪新來的字母。

debug代碼如下：

class Solution(object):
    def numDecodings(self, s: str) -> int:
        # w tells the number of ways
        # v tells the previous number of ways
        # d is the current digit
        # p is the previous digit
        v, w, p = 0, int(s>''), ''
        print('initial: v = {}, w = {}, p = {}'.format(v, w, p))
        for d in s:
            print('d = {}, left = {}, p+d = {}, right = {}'.format(d, int(d>'0')*w, p+d, (9<int(p+d)<27)*v))
            v, w, p = w, int(d>'0')*w + (9<int(p+d)<27)*v, d
            print('in loop: v = {}, w = {}, p = {}'.format(v, w, p))
            print()
        return w

輸出為：

initial: v = 0, w = 1, p = 
d = 1, left = 1, p+d = 1, right = 0
in loop: v = 1, w = 1, p = 1

d = 2, left = 1, p+d = 12, right = 1
in loop: v = 1, w = 2, p = 2

d = 2, left = 2, p+d = 22, right = 1
in loop: v = 2, w = 3, p = 2

d = 5, left = 3, p+d = 25, right = 2
in loop: v = 3, w = 5, p = 5

d = 8, left = 5, p+d = 58, right = 0
in loop: v = 5, w = 5, p = 8

5

47. 禮物的最大價(jià)值

書中的分析：

本題用到的方法是動(dòng)態(tài)規(guī)劃肉瓦。先用遞歸的思路來分析問題遭京，再用循環(huán)的方式來編寫代碼。

先定義一個(gè)函數(shù) 表示到達(dá)坐標(biāo)為 的格子時(shí)能拿到的禮物總和的最大值泞莉。根據(jù)題目要求哪雕，有兩種可能的途徑到達(dá)坐標(biāo)為 的格子：通過格子 或者 。所以 鲫趁。其中 表示坐標(biāo)為 的格子里禮物的價(jià)值斯嚎。

代碼：

def get_max_value(g: 'List[List[int]]') -> int:
    R, C = len(g), len(g[0])
    cur = list(itertools.accumulate(g[0]))
    for i in range(1, R):
        tmp = []
        for j in range(C):
            left = tmp[-1] if j > 0 else float('-inf')
            tmp.append(max(cur[j], left) + g[i][j])
        cur = tmp
    return cur[-1]

代碼分析：

這里用到了兩個(gè)列表來存儲(chǔ)臨時(shí)值。cur 代表的是上一行中走到各個(gè)位置時(shí)能獲得的禮物的最大值。tmp 中存儲(chǔ)的是走到當(dāng)前行的各個(gè)位置時(shí)能獲得的禮物的最大值堡僻，在每一行最開始時(shí)都要重置 tmp 糠惫，left 是 tmp 中上一次被添加進(jìn)去的禮物的最大值，如果要獲得下一次獲得禮物的最大值钉疫，則要將 left 取出來硼讽，然后和 cur 中對應(yīng)列處的值進(jìn)行比較。這是兩種不同的走法：

• 如果是 left + g[i][j] 牲阁，則表明是先往下走再往右走固阁；
• 如果是 cur[j] + g[i][j] ，則表明是先往右走再往下走城菊。

在每一行計(jì)算完成后备燃，cur 都要及時(shí)更新為上一行的值，即 cur = tmp 凌唬。然后在下一行開始時(shí)并齐，重新將 tmp 清空。

當(dāng)所有循環(huán)都結(jié)束時(shí)法瑟，cur[-1] 中保存的即為整個(gè)矩陣中可獲得禮物的最大值冀膝。

debug 過程如下：

import itertools
def get_max_value(g: 'List[List[int]]') -> int:
    R, C = len(g), len(g[0])
    cur = list(itertools.accumulate(g[0]))
    print('cur = {}'.format(cur))
    for i in range(1, R):
        tmp = []
        for j in range(C):
            print('j = {}, tmp = {}'.format(j, tmp))
            left = tmp[-1] if j > 0 else float('-inf')
            tmp.append(max(cur[j], left) + g[i][j])
            print('left = {}, tmp = {}'.format(left, tmp))
        cur = tmp
    return cur[-1]


if __name__ == '__main__':
    g = [
        [1, 10, 3, 8],
        [12, 2, 9, 6],
        [5, 7, 4, 11],
        [3, 7, 16, 5]
    ]
    y = get_max_value(g)
    print(y)

輸出結(jié)果為：

cur = [1, 11, 14, 22]
j = 0, tmp = []
left = -inf, tmp = [13]
j = 1, tmp = [13]
left = 13, tmp = [13, 15]
j = 2, tmp = [13, 15]
left = 15, tmp = [13, 15, 24]
j = 3, tmp = [13, 15, 24]
left = 24, tmp = [13, 15, 24, 30]
j = 0, tmp = []
left = -inf, tmp = [18]
j = 1, tmp = [18]
left = 18, tmp = [18, 25]
j = 2, tmp = [18, 25]
left = 25, tmp = [18, 25, 29]
j = 3, tmp = [18, 25, 29]
left = 29, tmp = [18, 25, 29, 41]
j = 0, tmp = []
left = -inf, tmp = [21]
j = 1, tmp = [21]
left = 21, tmp = [21, 32]
j = 2, tmp = [21, 32]
left = 32, tmp = [21, 32, 48]
j = 3, tmp = [21, 32, 48]
left = 48, tmp = [21, 32, 48, 53]
53

48. 最長不含重復(fù)字符的子字符串

書中的分析：本題要用動(dòng)態(tài)規(guī)劃來解決唁奢。

代碼：

def lengthOfLongestSubstring(self, s):
    ans = start = 0
    pos = {}    # last index of element
    for end, c in enumerate(s):
        if c in pos:
            start = max(start, pos[c]+1)
        pos[c] = end
        ans = max(ans, end-start+1)
    return ans

pos 保存的是字符串中每個(gè)字符最后一次在字符串中出現(xiàn)的位置霎挟，每遍歷到一個(gè)字符，都要先判斷一下該字符是否已經(jīng)在 pos 中出現(xiàn)過麻掸，如果出現(xiàn)過酥夭，就表明遇到重復(fù)字符了，此時(shí)要更新 start 的值脊奋。 pos[c] 有可能出現(xiàn)在 start 的后面熬北，也有可能出現(xiàn)在它的前面，為了保證 start 總是取最右邊的值诚隙，這里要取上一次的 start 和 pos[c] 中的最大值讶隐。

pos[c] 的值每次都要更新。

最終返回的結(jié)果就是上一次的結(jié)果和 end 與 start 之間距離的最大者久又。

49. 丑數(shù)

[書]：根據(jù)丑數(shù)的定義巫延，丑數(shù)只能被 2 、 3 和 5 整除地消。也就是說炉峰，如果一個(gè)數(shù)能被 2 整除，就連續(xù)除以 2 脉执，如果最后得到的是 1 疼阔，那么這個(gè)數(shù)就是丑數(shù)，否則不是；同樣婆廊，如果一個(gè)數(shù)能被 3 整除 （或者被 5 整除）迅细，就連續(xù)除以 3 （或者 5）摆霉，如果最后得到的是 1 熊榛，那么這個(gè)數(shù)就是丑數(shù)，否則不是澡罚。

本題的高效解法是只計(jì)算丑數(shù)列荔，不管非丑數(shù)敬尺。根據(jù)丑數(shù)的定義，丑數(shù)應(yīng)該是另一個(gè)丑數(shù)（1除外）乘以 2贴浙、 3 或 5 的結(jié)果砂吞。因此我們可以以空間換時(shí)間：創(chuàng)建一個(gè)數(shù)組，里面的數(shù)字是排好序的丑數(shù)崎溃，每個(gè)丑數(shù)都是前面的丑數(shù)乘以 2蜻直、 3 或 5 得到的。
這種思路的關(guān)鍵在于怎樣確保數(shù)組里面的丑數(shù)是排好序的袁串。假設(shè)數(shù)組中已經(jīng)有若干個(gè)排好序的丑數(shù)概而，并且把已有最大的丑數(shù)記作 M。如果將已有的丑數(shù)中所有的數(shù)字都乘以 2 囱修，并把得到的第一個(gè)乘以 2 以后大于 M 的結(jié)果記為 赎瑰。同樣，我們把已有的每個(gè)丑數(shù)乘以 3 和 5破镰，能得到第一個(gè)大于 M 的結(jié)果 和 餐曼。那么下一個(gè)丑數(shù)應(yīng)該是 。

因?yàn)橐延械某髷?shù)是按順序存放在數(shù)組中的鲜漩。對于乘以 2 而言源譬，肯定存在某一個(gè)丑數(shù) ，排在它之前的每個(gè)丑數(shù)乘以 2 得到的結(jié)果都會(huì)小于已有的最大丑數(shù)孕似，在它之后的每個(gè)丑數(shù)乘以 2 得到的結(jié)果都會(huì)太大踩娘。我們只需記下這個(gè)丑數(shù)的位置，同時(shí)每次生成新的丑數(shù)的時(shí)候去更新這個(gè) 即可喉祭。對于乘以 3 和 5 而言养渴，也存在同樣的 和 。

def nthUglyNumber(self, n: int) -> int:
    q = [1]
    t2 = t3 = t5 = 0
    for _ in range(n-1): # 這里是挖掉第一個(gè)默認(rèn)的丑數(shù)1
        a2, a3, a5 = q[t2]*2, q[t3]*3, q[t5]*5
        to_add = min(a2, a3, a5)
        q.append(to_add)
        if a2 == to_add:
            t2 += 1
        if a3 == to_add:
            t3 += 1
        if a5 == to_add:
            t5 += 1
    return q[-1]

50. 第一個(gè)只出現(xiàn)一次的字符

[書]：定義哈希表的 Key 是字符臂拓，Value 是該字符出現(xiàn)的次數(shù)厚脉。我們需要從頭開始掃描字符串兩次。第一次掃描字符串時(shí)胶惰，每掃到一個(gè)字符傻工，就在哈希表的對應(yīng)項(xiàng)中把次數(shù)加 1 。接下來第二次掃描時(shí)，每掃到一個(gè)字符中捆，就從哈希表中得到該字符出現(xiàn)的次數(shù)鸯匹。這樣，第一個(gè)只出現(xiàn)一次的字符就是符合要求的輸出泄伪。

def firstUniqChar(self, s):
    from collections import Counter
    c = Counter(s) # Counter是dict的一個(gè)子類殴蓬，因此這里本質(zhì)上返回的是一個(gè)dict
    for i, ch in enumerate(s):
        if c[ch] == 1:
            return i
    return -1

總結(jié)：有關(guān)字符及其出現(xiàn)次數(shù)的問題，通常都會(huì)借助一個(gè)輔助的哈希表來換取時(shí)間效率蟋滴。

如果字符是一個(gè)接一個(gè)從字符流中讀出來的染厅，則上述代碼中 c 就不能用 Counter 來實(shí)現(xiàn)了。此時(shí)只能構(gòu)建一個(gè)哈希表津函，然后每來一個(gè)字符肖粮，都在哈希表中查找一下，如果已經(jīng)存在尔苦，只就加1涩馆；如果不存在，就把它添加到哈希表中允坚。

通常要更加關(guān)注時(shí)間復(fù)雜度魂那。
降低時(shí)間復(fù)雜度的第一種方法是改用更加高效的算法。
降低時(shí)間復(fù)雜度的第二種方法是用空間換取時(shí)間稠项。

51. 數(shù)組中的逆序?qū)?/h4>

[書]：先把數(shù)組分隔成子數(shù)組涯雅，統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)?shù)目皿渗。在統(tǒng)計(jì)逆序?qū)Φ倪^程中斩芭，還需要對數(shù)組進(jìn)行排序轻腺。這個(gè)排序過程實(shí)際上就是歸并排序乐疆。具體過程如下：

先用兩個(gè)指針分別指向兩個(gè)子數(shù)組的末尾，并每次比較兩個(gè)指針指向的數(shù)字贬养。如果第一個(gè)子數(shù)組中的數(shù)字大于第二個(gè)子數(shù)組中的數(shù)字則構(gòu)成逆序?qū)吠粒⑶夷嫘驅(qū)Φ臄?shù)目等于第二個(gè)子數(shù)組中剩余數(shù)字的個(gè)數(shù)。而如果第一個(gè)數(shù)組中的數(shù)字小于或等于第二個(gè)數(shù)組中的數(shù)字误算，則不構(gòu)成逆序?qū)ρ雒馈Ｃ看伪容^的時(shí)候，我們都把較大的數(shù)字從后往前復(fù)制到一個(gè)輔助數(shù)組儿礼，確保輔助數(shù)組中的數(shù)字是遞增排序的咖杂。在把較大的數(shù)字復(fù)制到輔助數(shù)組之后，把對應(yīng)的指針向前移動(dòng)一位蚊夫，接下來進(jìn)行下一輪比較诉字。

def InversePairs(self, data):
    self.count = 0
    
    def merge(left, right):
        q = deque()
        l, r = len(left)-1, len(right)-1
        while l >= 0 and r >= 0:
            if left[l] > right[r]:
                self.count += r + 1
                q.appendleft(left[l])
                l -= 1
            else:
                q.appendleft(right[r])
                r -= 1
        q = left[:l+1] + right[:r+1] + list(q)
        return q
        
    def merge_sort(ary):
        if len(ary) <= 1: return ary
        mid = len(ary) // 2
        left = merge_sort(ary[:mid])
        right = merge_sort(ary[mid:])
        return merge(left, right)
    
    merge_sort(data)
    return self.count

52. 兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)

[書]：如果兩個(gè)單向鏈表有公共的節(jié)點(diǎn)，那么這兩個(gè)鏈表從某一節(jié)點(diǎn)開始，它們的 next 指針都指向同一個(gè)節(jié)點(diǎn)壤圃。但由于是單向鏈表的節(jié)點(diǎn)陵霉，每個(gè)節(jié)點(diǎn)只有一個(gè) next 指針，因此從第一個(gè)公共節(jié)點(diǎn)開始伍绳，之后它們所有的節(jié)點(diǎn)都是重合的踊挠，不可能再出現(xiàn)分叉。所以兩個(gè)有公共節(jié)點(diǎn)的單向鏈表冲杀，其拓?fù)湫螤羁雌饋硐褚粋€(gè) Y 效床，而不可能像 X 。

def getIntersectionNode(self, headA, headB):
    p1, p2 = headA, headB
    while p1 is not p2:
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA
    return p1

代碼分析：

• 第一個(gè)指針走到頭之后返回來從 B 繼續(xù)開始走权谁；
• 第二個(gè)指針走到頭之后返回來從 A 繼續(xù)開始走扁凛；
• 這樣最終相遇時(shí)，兩個(gè)指針走的路程是一樣的闯传。

53-1. 在排序數(shù)組中查找數(shù)字

[書]：既然輸入的數(shù)組是排序的谨朝，那么我們就能很自然地想到用二分查找算法。

二分查找算法總是先拿數(shù)組中間的數(shù)字和 k 作比較甥绿。如果中間的數(shù)字比 k 大字币，那么 k 只有可能出現(xiàn)在數(shù)組的前半段，下一輪我們只在數(shù)組的前半段查找就可以了共缕。如果中間的數(shù)字比 k 小洗出，那么 k 只有可能出現(xiàn)在數(shù)組的后半段，下一輪我們只在數(shù)組的后半段查找就可以了图谷。

如果中間的數(shù)字和 k 相等翩活，那么我們首先要判斷這個(gè)數(shù)字是不是第一個(gè) k 。如果中間數(shù)字的前面一個(gè)數(shù)字不是 k 便贵，那么此時(shí)中間的數(shù)字剛好就是第一個(gè) k 菠镇；如果中間數(shù)字的前面一個(gè)數(shù)字也是 k ，那么第一個(gè) k 肯定在數(shù)組的前半段承璃，下一輪我們?nèi)匀恍枰跀?shù)組的前半段查找利耍。

同樣，我們可以在排序數(shù)組中找到最后一個(gè) k 盔粹。如果中間數(shù)字等于 k 隘梨，我們需要判斷這個(gè) k 是不是最后一個(gè) k ，也就是中間數(shù)字的下一個(gè)數(shù)字是不是也等于 k 舷嗡。如果下一個(gè)數(shù)字不是 k 轴猎，則中間數(shù)字就是最后一個(gè) k ；否則下一輪我們還是要在數(shù)組的后半段中去查找进萄。

以上查找第一個(gè) k 和最后一個(gè) k 的過程都是通過二分查找進(jìn)行的捻脖，它們的時(shí)間復(fù)雜度均為 烦秩，因此總的時(shí)間復(fù)雜度也為 。

def searchRange(self, nums: List[int], target: int) -> List[int]:

    def search(n): # 定義二分查找
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] >= n:
                hi = mid
            else:
                lo = mid + 1
        return lo
    lo = search(target)
    if target in nums[lo:lo+1]:
        return lo, search(target+1)-1
    else:
        return -1, -1

search 函數(shù)如何保證最終返回的就是最左邊的 target 的索引：在 if 判斷語句中郎仆，當(dāng) nums[mid] = n 時(shí)只祠，hi 還是要不斷往前移，這就保證了最終它會(huì)移到最左邊的 target 所在的位置扰肌。

在尋找 target 在最右邊的索引時(shí)抛寝，為了能夠利用已有的 search 函數(shù)而不再專門定義一個(gè)新的查找最右邊 target 的函數(shù)，這里改為先查找比 target 大 1 的數(shù)在最左邊位置的索引曙旭，將這個(gè)索引減 1盗舰，即可得到 target 在最右邊的索引。這里值得注意的是桂躏，即使數(shù)組中不存在比 target 大 1 的數(shù)钻趋，查找 target+1 也能夠正確的返回最右邊的 target 右邊緊鄰的那個(gè)數(shù)字的索引。如果最右邊的 target 已經(jīng)是整個(gè)數(shù)組的最后一個(gè)數(shù)字剂习，則依然能夠返回正確的值蛮位，因?yàn)?hi 的初始值被設(shè)成了 len(nums) 而非 len(nums)-1 ，在這種情況下鳞绕，查找 target+1 將返回 len(nums) 失仁。

53-2. 0～n-1 中缺失的數(shù)字

[書]：首先將問題進(jìn)行轉(zhuǎn)換：因?yàn)?0～n-1 這些數(shù)字在數(shù)組中是排序的，因此數(shù)組中開始的一些數(shù)字與它們的下標(biāo)相同们何。如果不在數(shù)組中的那個(gè)數(shù)字記為 m 萄焦，那么所有比 m 小的數(shù)字的下標(biāo)都與它們的值相同。由于 m 不在數(shù)組中冤竹，那么 m+1 處在下標(biāo)為 m 的位置拂封，m+2 處在下標(biāo)為 m+1 的位置，以此類推鹦蠕∶扒可見 m 正好是數(shù)組中第一個(gè)數(shù)值和下標(biāo)不相等的元素的下標(biāo)，因此這個(gè)問題轉(zhuǎn)換成在排序數(shù)組中找出第一個(gè)值和下標(biāo)不相等的元素片部。

方法：基于二分查找的過程如下：(時(shí)間復(fù)雜度：)

• 如果中間元素的值和下標(biāo)相等镣衡，那么下一輪查找只需要查找右半邊；
• 如果中間元素的值和下標(biāo)不相等档悠，并且它前面一個(gè)元素和它的下標(biāo)相等，則意味著這個(gè)中間的數(shù)字正好是第一個(gè)值和下標(biāo)不相等的元素望浩，它的下標(biāo)就是在數(shù)組中不存在的數(shù)字辖所；
• 如果中間元素的值和下標(biāo)不相等，并且它前面一個(gè)元素和它的下標(biāo)也不相等磨德，則意味著下一輪查找我們只需要在左半邊查找即可缘回。

def getMissingNumber(self, nums):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo + hi) >> 1
        if nums[mid] != mid:
            if mid==0 or nums[mid-1]==mid-1:
                return mid
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

如果數(shù)組是未排序的吆视，則可以先計(jì)算出 0~n-1 的所有數(shù)字的和，再減去數(shù)組中所有數(shù)字的和酥宴，即可得到缺失的數(shù)字啦吧。但這種方法需要 的時(shí)間求數(shù)組中所有數(shù)字的和。

53-3. 數(shù)組中數(shù)值和下標(biāo)相等的元素

[書]：由于數(shù)組是單調(diào)遞增排序的拙寡，因此可以選擇用二分查找法授滓。

由于數(shù)組中的所有數(shù)字都唯一并且單調(diào)遞增，因此如果一個(gè)數(shù)字大于它的下標(biāo)肆糕，那么這個(gè)數(shù)字右邊的所有數(shù)字都將大于它的下標(biāo)般堆，在下一輪查找時(shí)在這個(gè)數(shù)字左邊的部分進(jìn)行查找即可。同樣诚啃，如果一個(gè)數(shù)字小于它的下標(biāo)淮摔，那么它左邊的數(shù)字也都會(huì)小于它的下標(biāo)，下一輪查找時(shí)只需要在它的右邊進(jìn)行查找即可始赎。

def getNumberSameAsIndex(self, nums):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo + hi) >> 1
        if nums[mid] < mid:
            lo = mid + 1
        elif nums[mid] > mid:
            hi = mid - 1
        else:
            return mid
    return -1

總結(jié)：二分查找法非常適合在排序的數(shù)組中進(jìn)行查找和橙。

54. 二叉搜索樹的第 k 大節(jié)點(diǎn)

[書]：本題實(shí)際上考查的是對中序遍歷的理解：如果按照中序遍歷的順序遍歷一棵二叉搜索樹，則遍歷序列的數(shù)值是遞增排序的造垛，從中序遍歷序列中便很容易找到第 k 大節(jié)點(diǎn)胃碾。

class Solution(object):
    def kth_largest(self, root: TreeNode, k: int) -> int:
        stack, ans = [], None
        while stack or root:
            while root:
                stack.append(root)
                root = root.right # 這里先一直到達(dá)二叉搜索樹的最大節(jié)點(diǎn)
            root = stack.pop()
            k -= 1
            ans = root
            root = root.left
            if k == 0:
                return ans

注意這里最終返回的是節(jié)點(diǎn)而非節(jié)點(diǎn)的值。

55-1. 二叉樹的深度

定義：從根節(jié)點(diǎn)到葉節(jié)點(diǎn)依次經(jīng)過的節(jié)點(diǎn)形成樹的一條路徑筋搏，最長路徑的長度（即節(jié)點(diǎn)的個(gè)數(shù)）為樹的深度仆百。

這里用到了用 deque 實(shí)現(xiàn)的 BFS：

class Solution(object):
    def maxDepth(self, root: 'TreeNode') -> 'int':
        q = root and collections.deque([(root, 1)])
        d = 0
        while q:
            node, d = q.popleft() # popleft()表明是BFS
            if node.right:
                q.append((node.right, d+1))
            if node.left:
                q.append((node.left, d+1))
        return d

55-2. 平衡二叉樹

[書]：本題實(shí)質(zhì)考查樹的后序遍歷。如果用后序遍歷的方式遍歷二叉樹的每個(gè)節(jié)點(diǎn)奔脐，那么在遍歷到一個(gè)節(jié)點(diǎn)之前我們就已經(jīng)遍歷了它的左俄周、右子樹。在遍歷該節(jié)點(diǎn)的左髓迎、右子節(jié)點(diǎn)之后峦朗，我們就可以根據(jù)它的左、右子節(jié)點(diǎn)的深度（某一節(jié)點(diǎn)的深度等于它到葉節(jié)點(diǎn)的路徑的長度）判斷它是不是平衡的排龄，并得到當(dāng)前節(jié)點(diǎn)的深度波势。當(dāng)最后遍歷到樹的根節(jié)點(diǎn)的時(shí)候，也就判斷了整棵二叉樹是不是平衡二叉樹橄维。

但是用后序遍歷的代碼比較復(fù)雜尺铣，這里用了一種更簡單且不會(huì)重復(fù)遍歷節(jié)點(diǎn)的方法：DFS。

def isBalanced(self, root: 'TreeNode') -> 'bool':
    self.balanced = True
    
    def dfs(node):
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        if abs(left-right) > 1 and self.balanced:
            self.balanced = False
        return max(left, right) + 1
    
    dfs(root)
    return self.balanced

DFS 會(huì)先深入到最左下方的節(jié)點(diǎn)争舞，然后從這個(gè)節(jié)點(diǎn)開始凛忿，逐個(gè)節(jié)點(diǎn)進(jìn)行判斷，逐個(gè)節(jié)點(diǎn)返回竞川，逐個(gè)遍歷剩余節(jié)點(diǎn)店溢，而且總是優(yōu)先遍歷縱深處的節(jié)點(diǎn)叁熔，直至最終到達(dá)根節(jié)點(diǎn)。

56-1. 數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字

[書]：異或運(yùn)算的一個(gè)性質(zhì)：任何一個(gè)數(shù)字異或它自己都等于 0 床牧。假如一個(gè)數(shù)組中只有一個(gè)數(shù)字只出現(xiàn)了一次荣回，其他數(shù)字都出現(xiàn)了兩次，那么當(dāng)我們從頭到尾依次異或數(shù)組中的每個(gè)數(shù)字時(shí)戈咳，最終的結(jié)果剛好是那個(gè)只出現(xiàn)一次的數(shù)字心软，因?yàn)槟切┏蓪Τ霈F(xiàn)兩次的數(shù)字全部在異或中抵消了。

現(xiàn)在數(shù)組中有兩個(gè)數(shù)字只出現(xiàn)了一次除秀，如果我們能想辦法把原數(shù)組分成兩個(gè)子數(shù)組糯累，使得每個(gè)子數(shù)組均只包含一個(gè)只出現(xiàn)一次的數(shù)字，而其他數(shù)字都成對出現(xiàn)兩次册踩，那我們就可以按照前面的方法分別找出這兩個(gè)數(shù)組中只出現(xiàn)一次的那個(gè)數(shù)字泳姐。

用什么方法（或按什么樣的標(biāo)準(zhǔn)）才能做到將這兩個(gè)不同的數(shù)字分到兩個(gè)不同的數(shù)組里，而且每個(gè)數(shù)組里的其他值均是成對出現(xiàn)的呢暂吉？我們首先從頭到尾依次異或數(shù)組中的每個(gè)數(shù)字胖秒，那么最終得到的結(jié)果就是那兩個(gè)只出現(xiàn)一次的數(shù)字異或得到的結(jié)果（其他數(shù)字因?yàn)槌蓪Τ霈F(xiàn)所以全部被抵消），而且最終的結(jié)果肯定不為 0 慕的，也就是說阎肝，最終結(jié)果的二進(jìn)制表示中至少有一位為 1 。我們在結(jié)果數(shù)字中找到第一個(gè)為 1 的位的位置肮街，記為第 n 位》缣猓現(xiàn)在我們就得到了將原數(shù)組劃分成兩個(gè)子數(shù)組的標(biāo)準(zhǔn)：看它的二進(jìn)制表示中第 n 位是不是 1 。如果是 1 嫉父，則分到第一個(gè)子數(shù)組中沛硅；如果是 0 ，則分到第二個(gè)子數(shù)組中绕辖。（因?yàn)楫惢蚴恰跋嗤瑸?1 摇肌，不同為 0”，所以這兩個(gè)只出現(xiàn)一次的數(shù)肯定會(huì)被分到不同的子數(shù)組中去仪际。）這樣我們就完成了數(shù)組的劃分围小，然后再運(yùn)用前面的方法，即可找到這兩個(gè)數(shù)字树碱。

class Solution(object):
    def singleNumber(self, nums: List[int]) -> List[int]:
        from functools import reduce
        def get_single(nums):
            return reduce(operator.xor, nums)
        
        total_xor = get_single(nums)
        mask = 1
        while total_xor&mask == 0: # 找到第一個(gè)為1的位的位置
            mask <<= 1
        n1 = [num for num in nums if num&mask==0]
        n2 = [num for num in nums if num&mask!=0]
        return get_single(n1), get_single(n2)

56-2. 數(shù)組中唯一只出現(xiàn)一次的數(shù)字

[書]：本題的兩種直觀的解法：

• 先將數(shù)組排序肯适，然后從排序的數(shù)組中就可以很容易找到只出現(xiàn)一次的數(shù)字，但排序需要 的時(shí)間赴恨；
• 也可以用一個(gè)哈希表來記錄數(shù)組中每個(gè)數(shù)字出現(xiàn)的次數(shù)疹娶，但這個(gè)哈希表需要 的空間。

以上兩種方法都不是最優(yōu)的解法伦连，最優(yōu)的解法仍然要用到位運(yùn)算雨饺，這里就要考查二進(jìn)制表示的一些性質(zhì)：

如果一個(gè)數(shù)字出現(xiàn)三次，那么它的二進(jìn)制表示的每一位（0或者1）也出現(xiàn)三次惑淳。如果把所有出現(xiàn)三次的數(shù)字的二進(jìn)制表示的每一位都分別加起來额港，那么每一位的和都能被 3 整除。如此歧焦，我們便可以通過二進(jìn)制表示來確定那個(gè)只出現(xiàn)一次的數(shù)字都會(huì)出現(xiàn)在哪一位：我們先把數(shù)組中所有數(shù)字的二進(jìn)制表示的每一位都加起來移斩，如果某一位的和能被 3 整除，那么那個(gè)只出現(xiàn)一次的數(shù)字二進(jìn)制表示中對應(yīng)的那一位就是 0 绢馍；否則就是 1 向瓷。這種解法的時(shí)間效率是 ，空間效率是 舰涌。

class Solution(object):
    def singleNumber(self, nums, n=3):
        ans = 0
        for i in range(32):
            count = 0
            for num in nums:
                if ((num >> i) & 1):
                    count += 1
            ans |= ((count%n!=0) << i)
        return self.convert(ans)

    def convert(self, x):
        if x >= 2**31:
            x -= 2**32
        return x

上述代碼中使用count來表示每一位1的個(gè)數(shù)猖任。假設(shè)count%3!=0為True，說明該元素i位為1瓷耙，然后是用|=更新ans在第i個(gè)位置的值朱躺，這里也可以使用+=，但是效率稍慢搁痛。convert的作用是因?yàn)閜ython中的int是個(gè)對象长搀，且沒有最大限制，不是在第32位使用1來表示負(fù)數(shù)鸡典。

57-1. 和為 s 的兩個(gè)數(shù)字

[書]：首先定義兩個(gè)指針源请，第一個(gè)指針指向數(shù)組的第一個(gè)數(shù)字，第二個(gè)指針指向數(shù)組的最后一個(gè)數(shù)字彻况。如果兩指針指向的數(shù)字大于 s 谁尸，則向前移動(dòng)后一個(gè)指針；如果兩指針指向的數(shù)字小于 s 疗垛，則向后移動(dòng)前一個(gè)指針症汹。如此，直至兩指針指向的數(shù)字等于 s 贷腕，或直至左指針的下標(biāo)不再小于右指針背镇，表明數(shù)組中不存在和為 s 的兩個(gè)數(shù)字，此時(shí)返回空列表泽裳。

def FindNumbersWithSum(self, array, tsum):
    l, r = 0, len(array)-1
    while l < r:
        if array[l] + array[r] < tsum:
            l += 1
        elif array[l]+array[r] > tsum:
            r -= 1
        else:
            return array[l], array[r]
    return []

57-2. 和為 s 的連續(xù)正數(shù)序列

[書]：考慮用兩個(gè)數(shù) small 和 big 分別表示序列的最小值和最大值瞒斩。首先把 small 初始化為 1 ，big 初始化為 2 涮总。如果從 small 到 big 的序列的和大于s 胸囱，則可以從序列中去掉較小的值，也就是增大 small 的值瀑梗。如果從 small 到 big 的序列的和小于 s 烹笔，則可以增大 big 裳扯，讓這個(gè)序列包含更多的數(shù)字。因?yàn)檫@個(gè)序列至少要有兩個(gè)數(shù)字谤职，所以 small 是有上限的饰豺，它不能超過 。

class Solution(object):
    def findContinuousSequence(self, tsum):
        end = (tsum + 1) // 2
        lo, hi, cur_sum = 1, 2, 3
        ans = []
        while lo < end:
            if cur_sum < tsum:
                hi += 1
                cur_sum += hi
            else:
                if cur_sum == tsum:
                    ans.append(list(range(lo, hi+1)))
                cur_sum -= lo
                lo += 1
        return ans

58-1. 翻轉(zhuǎn)單詞順序

[書]：通過兩次翻轉(zhuǎn)來解決允蜈。第一步先翻轉(zhuǎn)句子中所有的字符冤吨，此時(shí)不但翻轉(zhuǎn)了句子中單詞的順序，連單詞內(nèi)的字符順序也被翻轉(zhuǎn)了饶套。第二步再翻轉(zhuǎn)每個(gè)單詞中字符的順序漩蟆，就可以實(shí)現(xiàn)要求的翻轉(zhuǎn)。

class Solution(object):
    def reverseWords(self, s: str) -> str:

        def hp_reversed(s): # 這個(gè)函數(shù)返回完全逆序的結(jié)果
            s = list(s)
            for i in range(len(s)//2):
                s[i], s[~i] = s[~i], s[i]
            return ''.join(s)

        s = hp_reversed(s) # 先對整個(gè)字符串進(jìn)行翻轉(zhuǎn)
        print('hp_reversed(s) = {}'.format(s))
        ans = word = ''
        for r, c in enumerate(s):
            if c != ' ':
                word += c
            if (c== ' ' or r==len(s)-1) and word: # c==' '是判斷除最后一個(gè)字符之外的其他字符妓蛮，r==len(s)-1是判斷最后一個(gè)字符
                ans += hp_reversed(word) + ' ' # 這里是對每一個(gè)單詞進(jìn)行翻轉(zhuǎn)
                word = ''
        return ans[:-1] # 最后一個(gè)字符不要是因?yàn)閍ns每次在添加的時(shí)候多加了一個(gè)空格

如果可以使用 python 的 split() 函數(shù)怠李，則以上代碼可以簡化為：

def reverseWords(self, s: str) -> str:

    def hp_reversed(s):
        s = list(s)
        for i in range(len(s)//2):
            # s[i], s[-i-1] = s[-i-1], s[i]
            s[i], s[~i] = s[~i], s[i]
        return ''.join(s)
    s = hp_reversed(s)
    return ' '.join(hp_reversed(word) for word in s.split())

如果可以使用 python 的 reversed() 函數(shù)，則以上代碼可以進(jìn)一步簡化為只有一行：

def reverse_words(s):
    return ' '.join(reversed(s.split()))

58-2. 左旋轉(zhuǎn)字符串

[書]：可以借鑒前面的翻轉(zhuǎn)單詞順序的思想：假如給定字符串 "abcdefg" 仔引，我們想把它的前兩個(gè)字符進(jìn)行左旋轉(zhuǎn)操作扔仓，那么我們首先可以將它分成兩部分：把前兩個(gè)字符分到第一部分，把后面的所有字符分到第二部分咖耘。第一步先翻轉(zhuǎn)整個(gè)字符串翘簇，得到 "gfedcba" ，第二步再翻轉(zhuǎn)單詞內(nèi)部的順序儿倒，得到 "cdefgab" 版保。此外，本題還要注意非法輸入及越界等問題夫否。

但是darktiantian認(rèn)為書中的方法并不適用于 python彻犁，因此他用了如下切片的方法進(jìn)行解決：

class Solution(object):
    def LeftRotateString(self, s, n):
        if not s:
            return ''
        n = n % len(s)
        return s[n:] + s[:n]

59-1. 滑動(dòng)窗口的最大值

[書]：一個(gè)滑動(dòng)窗口可以看成一個(gè)隊(duì)列，當(dāng)窗口滑動(dòng)時(shí)凰慈，處于窗口的第一個(gè)數(shù)字被刪除汞幢，同時(shí)在窗口的末尾添加一個(gè)新的數(shù)字，這符合隊(duì)列“先進(jìn)先出”的特性微谓。

我們并不把滑動(dòng)窗口的每個(gè)數(shù)值都存入隊(duì)列森篷，而是只把有可能成為滑動(dòng)窗口最大值的數(shù)值存入一個(gè)兩端開口的隊(duì)列。

但是豺型，為了確定某個(gè)數(shù)字是否已經(jīng)滑出了滑動(dòng)窗口仲智，應(yīng)該在隊(duì)列中存入數(shù)字在數(shù)組里的下標(biāo)，而不是數(shù)值姻氨。當(dāng)一個(gè)數(shù)字的下標(biāo)與當(dāng)前處理的數(shù)字的下標(biāo)之差大于或者等于滑動(dòng)窗口的大小時(shí)钓辆，這個(gè)數(shù)字已經(jīng)從窗口中滑出，可以從隊(duì)列中刪除了。

注意到滑動(dòng)窗口的最大值總是位于隊(duì)列的頭部前联。

綜上功戚，我們需要一個(gè)雙端隊(duì)列，用來保存有可能是滑動(dòng)窗口最大值數(shù)字的下標(biāo)蛀恩。在存入一個(gè)新的數(shù)字的下標(biāo)之前疫铜，首先要判斷隊(duì)列里已有的數(shù)字是否小于待存入的數(shù)字茂浮。如果已有的數(shù)字小于待存入的數(shù)字双谆，那么這些數(shù)字已經(jīng)不可能是滑動(dòng)窗口的最大值，因此它們將會(huì)被依次從隊(duì)列的尾部刪除席揽。同時(shí)顽馋，如果隊(duì)列頭部的數(shù)字已經(jīng)從窗口里滑出，那么滑出的數(shù)字也需要從隊(duì)列的頭部刪除幌羞。

darktiantain：得益于python的切片寸谜，有一種很簡潔的方法（其實(shí)本質(zhì)上是蠻力法），時(shí)間復(fù)雜度為 属桦， 為滑動(dòng)窗的大行艹铡：

def maxInWindows(self, nums, size):
    return [max(nums[i:i+size])
            for i in range(len(nums)-size+1) if size!=0 ]

另一種方法就是和書中的方法一樣，用雙端隊(duì)列聂宾，時(shí)間復(fù)雜度為 ：

def maxInWindows(self, nums, size):
    from collections import deque
    q = deque()
    ans = []
    def pop_less(i):
        # nums[i] 索引和值都比隊(duì)列尾的元素大果善，隊(duì)列尾的元素就沒有必要存在了
        while q and nums[i]>=nums[q[-1]]:
            q.pop()
        q.append(i)

    for i in range(size):
        pop_less(i)

    for i in range(size, len(nums)):
        ans.append(nums[q[0]])
        pop_less(i)
        while q and q[0]<= i-size:
            q.popleft()
    ans.append(nums[q[0]]) # 在for循環(huán)中每一輪添加的其實(shí)是上一輪的最大值，因此循環(huán)退出后必須補(bǔ)一個(gè)append操作
    return ans

59-2. 隊(duì)列的最大值

[書]：可以借鑒上題中找滑動(dòng)窗口的最大值系谐。這一次要找的是整個(gè)隊(duì)列的最大值巾陕，相當(dāng)于是把滑動(dòng)窗口設(shè)置為整個(gè)隊(duì)列。

from collections import deque
class queueWithMax(object):
    def __init__(self):
        self.dequeData = deque()
        self.dequeMax = deque()
    
    def push_back(self, num):
        self.dequeData.append(num)
        while self.dequeMax and num > self.dequeMax[-1]: # 這里不能有等號
            self.dequeMax.pop()
        self.dequeMax.append(num)
    
    def pop_front(self):
        if not self.dequeData: # 先要判斷隊(duì)列是否為空
            return
        data = self.dequeData.popleft()
        if data == self.dequeMax[0]:
            self.dequeMax.popleft()
    
    def max(self):
        return self.dequeMax[0]

注意 push_back 中的 while 循環(huán)纪他，如果 number 大于 dequeMax 中的所有元素鄙煤，則該循環(huán)將會(huì)把 dequeMax 彈空。一組 debug 代碼如下所示：

self.dequeData = deque([2]), self.dequeMax = deque([2])
self.dequeData = deque([2, 3]), self.dequeMax = deque([3])
self.dequeData = deque([2, 3, 4]), self.dequeMax = deque([4])
self.dequeData = deque([2, 3, 4, 2]), self.dequeMax = deque([4, 2])
self.dequeData = deque([2, 3, 4, 2, 6]), self.dequeMax = deque([6])
self.dequeData = deque([2, 3, 4, 2, 6, 6]), self.dequeMax = deque([6, 6])
self.dequeData = deque([2, 3, 4, 2, 6, 6, 5]), self.dequeMax = deque([6, 6, 5])
self.dequeData = deque([2, 3, 4, 2, 6, 6, 5, 1]), self.dequeMax = deque([6, 6, 5, 1])

有一點(diǎn)必須要明確茶袒，那就是當(dāng)隊(duì)列中的某個(gè)數(shù)被彈出時(shí)梯刚，此時(shí)隊(duì)列的最大值只可能在這個(gè)數(shù)的右邊出現(xiàn)，因?yàn)椤昂筮M(jìn)先出”的原則，這個(gè)數(shù)左邊的數(shù)字早就被彈出了。

60. n 個(gè)骰子的點(diǎn)數(shù)

[書]：考慮用兩個(gè)數(shù)組來存儲(chǔ)骰子點(diǎn)數(shù)的每個(gè)總數(shù)出現(xiàn)的次數(shù)灰蛙。在一輪循環(huán)中召夹，第一個(gè)數(shù)組中的第 n 個(gè)數(shù)字表示骰子和為 n 出現(xiàn)的次數(shù)。在下一輪循環(huán)中尸折，我們加上一個(gè)新的骰子，此時(shí)和為 n 的骰子出現(xiàn)的次數(shù)應(yīng)該等于上一輪循環(huán)中骰子點(diǎn)數(shù)和為 n-1 、n-2旷太、 n-3、 n-4、 n-5供璧、 n-6 的次數(shù)的總和存崖，所以我們把另一個(gè)數(shù)組的第 n 個(gè)數(shù)字設(shè)為前一個(gè)數(shù)組對應(yīng)的第 n-1 、n-2睡毒、 n-3来惧、 n-4、 n-5演顾、 n-6 個(gè)數(shù)字之和供搀。

def dice_probability(n, val=6):
    dp = [[0]*val*n for _ in range(n)]
    dp[0][:val] = [1] * val  # 初始化第一個(gè)骰子
    
    for i in range(n-1):  # 根據(jù)第i個(gè)骰子更新第i+1個(gè)骰子
        for j in range(i, len(dp[i+1])):
            # 第i+1個(gè)骰子和為j（實(shí)際為j+1，因?yàn)閿?shù)組下標(biāo)從0開始）的次數(shù)钠至，等于第i個(gè)
            # 骰子j-1 ~ j-6次數(shù)的總和
            dp[i+1][j] = sum([dp[i][j-k] for k in range(1, val+1)])
            
    # 整理數(shù)據(jù)成為dict葛虐，key表示和，value表示出現(xiàn)的次數(shù)
    # count = {i+1: times for i, times in enumerate(dp[-1])}
    # 計(jì)算概率
    count = {i+1: round(float(times / (val**n)), 5)
             for i, times in enumerate(dp[-1]) if times!=0}
    return count

其中棉钧，dp[0][j]==1表示第一個(gè)骰子和為j+1的次數(shù)為1屿脐，因?yàn)閿?shù)組下標(biāo)從0開始。

61. 撲克牌中的順子

[書]：由于大宪卿、小王可以看成任意數(shù)字的诵，我們不妨把它們都定義為 0 。

首先佑钾，如果一副牌里含有對子西疤，則不可能是順子。

為了判斷 5 個(gè)數(shù)字是不是連續(xù)的次绘，我們需要首先把數(shù)組排序瘪阁；其次統(tǒng)計(jì)數(shù)組中 0 的個(gè)數(shù)；最后統(tǒng)計(jì)排序之后的數(shù)組中相鄰數(shù)字之間的空缺總數(shù)邮偎。如果空缺的總數(shù)小于或者等于 0 的個(gè)數(shù)管跺，那么這個(gè)數(shù)組就是連續(xù)的；反之則不連續(xù)禾进。

def IsContinuous(self, numbers): # numbers是隨機(jī)抽到的5張牌
    if not numbers:
        return False
    joker_count = numbers.count(0) # count用于統(tǒng)計(jì)字符串里某個(gè)字符出現(xiàn)的次數(shù)
    left_cards = sorted(numbers)[joker_count:]
    need_joker = 0
    for i in range(len(left_cards)-1):
        if left_cards[i+1] == left_cards[i]: # 如果有對子出現(xiàn)豁跑，肯定不會(huì)連續(xù)
            return False
        need_joker += (left_cards[i+1]-left_cards[i]-1)
    return need_joker <= joker_count

62. 圓圈中最后剩下的數(shù)字

圓圈報(bào)數(shù)問題的本質(zhì)是約瑟夫環(huán)問題。詳見：https://oldj.net/blog/2010/05/27/joseph-ring/

假設(shè)當(dāng)環(huán)中還剩下最后一個(gè)人時(shí)泻云，這個(gè)人的編號是 艇拍，則約瑟夫環(huán)遞推公式為：

其中， mod 是取余運(yùn)算宠纯， 是總共有多少個(gè)人卸夕， 是報(bào)到第 個(gè)人出局。

在本題中婆瓜， 快集，因此代碼如下：

def LastRemaining_Solution(self, n, m):
    if n<=0 or m<=0:
        return -1
    last_num = 0
    for i in range(2, n+1):
        last_num = (last_num+m) % i
    return last_num # 這里應(yīng)該是last_num+A贡羔，因?yàn)锳=0，所以省略掉了

63. 股票的最大利潤

卡登算法：屬于動(dòng)態(tài)規(guī)劃的一種个初，用于求連續(xù)子數(shù)組的最大和乖寒。詳見：https://blog.csdn.net/lishichengyan/article/details/77150133

原始算法描述：

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

本題在此基礎(chǔ)上稍微做了變形：

def maxProfit(self, prices: List[int]) -> int:
    cur = sofar = 0
    for i in range(1, len(prices)):
        cur += prices[i] - prices[i-1]
        cur = max(0, cur) # [注]
        sofar = max(cur, sofar)
    return sofar

【注】如果價(jià)格比之前小，則舍棄院溺，否則一起計(jì)算連續(xù)子數(shù)組的和楣嘁。

卡登算法的時(shí)間復(fù)雜度為 。

64. 求 1+2+...+n

def Sum_Solution(self, n):
    # write code here
    return n and (n+self.Sum_Solution(n-1))

65. 不用加減乘除做加法

python 的 int 是沒有范圍限制的珍逸，因此在進(jìn)行位運(yùn)算時(shí)逐虚，負(fù)數(shù)取補(bǔ)碼將會(huì)變成一個(gè)非常大的數(shù)字。因此 python 在進(jìn)行位運(yùn)算時(shí)可能存在非常多的坑弄息。參考：https://darktiantian.github.io/371-Sum-of-Two-Integers-Python/

如果不做任何限制痊班，本題的原始代碼為：

def get_sum(a, b):
    res, carry = 0, 0
    while b != 0: # step3: 不斷循環(huán)直至最終進(jìn)位為0
        res = a ^ b # step1: 相加但不進(jìn)位
        carry = (a & b) << 1 # step2: 計(jì)算進(jìn)位
        a, b = res, carry
    return res

在上述過程中，carry 右邊第 2 位上的 1 將會(huì)不斷往左移摹量。正常情況下，當(dāng)移到第33位時(shí)馒胆，由于數(shù)字范圍的限制缨称，這個(gè) 1 將會(huì)被舍棄從而使 b=0 ，使循環(huán)退出祝迂。但 python 的 int 沒有限制睦尽，這樣 carry 中的這個(gè) 1 就會(huì)一直不停地往前移，永遠(yuǎn)也不會(huì)消失型雳，從而導(dǎo)致 b 永遠(yuǎn)不為 0 当凡，循環(huán)永遠(yuǎn)不會(huì)停止，造成死循環(huán)纠俭。

解決上述問題的關(guān)鍵就是我們要把數(shù)據(jù)范圍限制在32位沿量，為此，可以用一個(gè)32位全為1的 mask 來和數(shù)字進(jìn)行相與從而得到一個(gè)32位的數(shù)字：mask = 0xFFFFFFFF 冤荆。但是這樣改完以后還有一個(gè)問題：有時(shí)候負(fù)數(shù)和這個(gè) mask 相與會(huì)變成一個(gè)很大的數(shù)字朴则，為此darktiantian的看法是：

當(dāng)負(fù)數(shù)與mask進(jìn)行與運(yùn)算時(shí)，比如-2钓简，此時(shí)-2的補(bǔ)碼變?yōu)?code>11…10乌妒，一個(gè)33-bit的數(shù)字，然后和32位的mask與操作后外邓，變?yōu)榱艘粋€(gè)33位的正數(shù)撤蚊。

有一個(gè)公式可以幫我們還原a，如果一個(gè)負(fù)數(shù)n损话，它的無符號的32位補(bǔ)碼是m侦啸，那么m=~(n ^ mask) 或者n=~(m ^ mask)

因此最終還有可能要做一個(gè)還原操作，所以最終的代碼為：

def getSum(self, a, b):
    # 32 bits integer max
    MAX = 0x7FFFFFFF  # 2**31-1
    # 32 bits interger min  
    MIN = 0x80000000  # -2**31
    # mask to get last 32 bits
    mask = 0xFFFFFFFF  # 2*32-1
    while b != 0:
        # ^ get different bits and & gets double 1s, << moves carry
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    # if a is negative, get a's 32 bits complement positive first
    # then get 32-bit positive's Python complement negative
    return a if a <= MAX else ~(a ^ mask)

或者我們可以借助 numpy，因?yàn)閚umpy提供了32位的整型：np.int32 匹中，代碼如下：

import numpy as np

class Solution(object):
    def getSum(self, a, b):
        while b != 0:
            a, b = np.int32(a ^ b), np.int32((a & b) << 1)
        return int(a)

需要注意的是最后要再轉(zhuǎn)回int夏漱，否則是沒法通過測試用例的。