《剑指offer》刷题笔记（二）

27. 二叉树的镜像

求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左、右子节点之后，就得到了这棵树的镜像。

# 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 # 列表的“+”相当于append

28. 对称的二叉树

• 思路：用两个指针去遍历树，第一个指针进行前序遍历，第二个指针和前序遍历对称着去遍历。只要这两个指针遍历得到的结果是一样的，那么这个二叉树就是对称的。

• 具体操作流程：用循环，用一个 stack ，每次都镜像地将树中的节点 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. 顺时针打印矩阵

假设原始矩阵 如下所示：

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

本题其实是这样的一个递归过程：

• 先取出原始矩阵的第一行，然后将第一行剔除掉，再将矩阵逆时针旋转 90 ° ，得到矩阵 ；
• 再将 的第一行取出来，然后将 的第一行剔除掉，再将矩阵 逆时针旋转 90 ° ，得到矩阵 ；
• 如此直至矩阵被剔空。

而如何将矩阵逆时针旋转 90 ° 呢？这一过程需要分两步来完成：

• 首先将原始矩阵进行转置，用 zip 配合 * 可以实现：

  # 假设原始矩阵为a，则a的转置为：
  list(zip(*a))
  

• 然后，将矩阵上下颠倒：

  # 假设转置后的矩阵为b，则将b上下颠倒为：
  b[::-1]
  

根据以上分析，不难写出代码：

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])

这里边要注意三点：

• matrix and list(matrix.pop(0)) 中的 and 非常关键，它不能写成 + 号，因为它保证了 pop 的时候 matrix 不为空，所以它是后面进行 pop 的一个先决条件；
• pop(0) 不是将第一个元素弹出来，由于 matrix 是一个二维的列表，因此它这里是将第一行弹出来，这里一定要注意。
• 为什么 list(zip(*matrix))[::-1] 是进行上下翻转而不是左右翻转：这里还是要用到整体思想，先将matrix内部视为一个个黑箱，则 [::-1] 将会把黑箱逆序。然后再看黑箱是什么（在上述逆序的过程中，黑箱内部是不发生任何变化的），而这里黑箱恰好就是一行一行的列表。因此综合来看，上述操作是对 matrix 进行上下翻转而不是左右翻转。

本题的变形：要求逆时针从矩阵的第一行第一列的元素开始打印，如何编写代码？

假设原始矩阵 仍如下所示：

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

这个时候要打印出的是 1, 5, 9, 13, 14, 15, 16, ... 这样的顺序，那么此时我们就应该顺时针旋转矩阵，然后取出首行。注意这时候取出的首行是 13, 9, 5, 1 ，跟我们要打印的顺序是相反的，因此取出首行后还要再逆序一下。

而如何将矩阵顺时针旋转 90 ° 呢？这一过程也需要分两步来完成：

• 首先将矩阵上下颠倒：

  # 假设原始矩阵为a，则将a上下颠倒为：
  a[::-1]
  

• 然后，将矩阵进行转置，用 zip 配合 * 可以实现：

  # 假设上下颠倒后的矩阵为b，则转置操作为：
  list(zip(*b))
  

可以看到：将矩阵顺时针旋转90度和逆时针旋转90度的区别是：顺时针旋转是先上下颠倒再进行转置，而逆时针旋转是先进行转置再进行上下颠倒。

代码如下：

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

以上代码和顺时针打印的区别是：

• 顺时针打印是先取第一行然后再旋转，而逆时针打印是先旋转再取第一行；
• 顺时针打印取出第一行后不需要额外的操作，而逆时针旋转取出第一行后还需要进行逆序操作。

30. 包含 min 函数的栈

分析：要用一个辅助栈来保存当前栈中的最小值，它和当前栈的长度是相同的，即当前栈中有几个元素，辅助栈中就必须要有几个元素。这样就能够保证当当前栈中最小的元素被弹出后，下一个最小的元素能够轻而易举地被找到。

总之，解决问题的关键在于不是用一个变量去保存当前栈中的最小值，而是用一个辅助栈去存储每压入一个元素后当前栈中的最小值。

而在具体的实现过程中，我们真的要开辟两个栈吗？其实是不需要的。我们可以用一个“二元栈”来将当前栈和辅助栈合并成一个栈：在最简单的栈中，每一个单元里通常存储的都是一个值。而现在，我们让每个单元里都以 tuple 的形式存储两个值：(top_value, min_value) ，其中 top_value 是每一次被压入到栈中的元素，min_value 是每一次压入新的数值后当前栈中对应的最小元素。这样我们可以通过索引 [0] 来得到栈中的元素，用索引 [1] 来得到栈中的最小值，就避免了额外开辟一个栈。

代码如下：

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') # 这个地方只能return无穷，不能return其他值
        else:
            return self._stack[-1][1]

31. 栈的压入、弹出序列

剑指offer中的思路总结：
判断一个序列是不是栈的弹出序列的规律：

• 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；
• 如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入栈中，直到把下一个需要弹出的数字压入栈顶为止；
• 如果把所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

代码如下：

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. 从上到下打印二叉树

本题实质考查的是二叉树的层次遍历（广度优先遍历），要借助于一个双端队列来实现。

二叉树的层次遍历代码如下：

# 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

不管是广度优先遍历一幅有向图还是一棵树，都要用到队列。首先把起始节点（对树而言是根节点）放入队列。接下来每次从队列的头部取出一个节点，然后把它能到达的节点（对树而言即为子节点）都依次放入队列。重复这个过程，直到队列中的节点全部被取出为止。

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. 之字形打印二叉树

加一个变量 order 用来控制每次是顺序还是逆序将结果 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）是二叉树的一种特例。在二叉搜索树中，每个节点的值都介于它的左子节点（如果有）和右子节点（如果有）的值中间，且大于左子节点的值，小于右子节点的值。

二叉搜索树的后序遍历序列有如下特点：

• 在后序遍历得到的序列中，最后一个数字是树的根节点的值；
• 序列中除去最后一个数外，剩余的序列可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。

二叉树遍历序列问题的通用方法：

• 先根据遍历序列的类型，找到二叉树的根节点；
• 再基于根节点将整棵树的遍历序列分成左子序列（左子树对应的序列）和右子序列（右子树对应的序列）两部分，然后再递归地处理这两个子序列。

python itertools 模块的 takewhile(condition, iterable) 函数：返回一连串的数字，直到 condition 不满足时为止，如：

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上认为，如果输入的 sequence 为空，则应返回 False 。而 AcWing 上认为，空序列是空二叉搜索树的后序遍历序列，因此应该返回 True 。这里采取和剑指offer上一样的处理方法。

拓展：如果将题目改成“判断该数组是不是某二叉搜索树的前序遍历结果”，则解决方法和上面类似。只是在前序遍历得到的序列中，根节点的值是序列的第一个数字。

34. 二叉树中和为某一值的路径

在树的前序、中序、后序 3 种遍历方式中，只有前序遍历是首先访问根节点的。

本题的本质还是树的遍历。

书中对本题的分析：

• 用前序遍历的方式来访问树。当访问到某一节点时，把该节点添加到路径上（用栈来保存路径），并累加该节点的值。如果该节点为叶节点，并且路径中所有节点值之和刚好等于输入的整数，则当前路径符合要求，我们把它打印出来；如果当前节点不是叶节点，则继续访问它的子节点。
• 当前节点访问结束后，递归函数将自动回到它的父节点。因此在函数返回上一级调用之前，必须要在路径中删除当前节点并减去当前节点的值，从而为遍历其他节点做准备。
• 以上递归调用的本质就是一个压栈和出栈的过程。

代码：

# 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: # 必须要先添加右子节点，否则不是前序遍历
            #     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

注意：利用栈实现前序遍历时，必须要先 append 右子节点再 append 左子节点，否则不是前序遍历，本题的代码就会出问题。

35. 复杂链表的复制

通常分治法都可以用递归的代码实现。

网站上的方法采用的是书中的第二种方法：用空间换时间

• 对于有 个节点的链表，需要用到一个大小为 的哈希表，这样就可以把时间复杂度降到 。

代码：

"""
# 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]

【注】：这个地方不能写成 hash_table = {} ，否则可能会报 KeyError 为 None 的错误。之所以要写成 hash_table = {None: None} ，实际上是为这个 hash_tabel 提供了一个原始的键值对，即当要取 hash_tabel 中键为 None 的值时，将返回 None 。由于 None 的特殊性，如果不声明在 hash_table 中有这样一个键值对，则在 hash_table 中取 None 这个键的值时就会报错。

36. 二叉搜索树与双向链表

书中的分析：

• 为什么能够进行二叉搜索树和双向链表的转换：在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点也有两个指针，分别指向前一个节点和后一个节点。由于这两种节点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此，在理论上有可能实现二叉搜索树和排序双向链表的转换。
• 转换的思路：在二叉搜索树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。
• 可以使用中序遍历的方法来遍历树中的每个节点，这样就可以按照从小到大的顺序遍历二叉树的每个节点。
• 在节点之间进行连接的时候，根节点向左总是和左子树中值最大的一个节点进行连接（注意，左子树中值最大的节点并不是根节点，而是根节点的右子节点），根节点向右总是和右子树中值最小的一个节点进行连接（右子树中值最小的节点是根节点的左子节点）。
• 按照中序遍历的顺序，当我们遍历转换到整棵树的根节点时，左子树已经转换成一个排序的链表了，并且处在链表中的最后一个节点是它当前值最大的节点，我们把这个节点和树的根节点连接起来，此时左半部分便已经排序完毕。然后再让根节点和右半部分中最小的节点连接起来即可。整个过程很显然可以用递归实现。

Morris Traversal:

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

通常，实现二叉树的前序（preorder）、中序（inorder）、后序（postorder）遍历有两个常用的方法：一是递归(recursive)，二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度（递归本身占用stack空间或者用户自定义的stack），所以不满足要求。

Morris Traversal方法可以做到这两点，与前两种方法的不同在于该方法只需要O(1)空间，而且同样可以在O(n)时间内完成。

要使用O(1)空间进行遍历，最大的难点在于，遍历到子节点的时候怎样重新返回到父节点（假设节点中没有指向父节点的p指针），由于不能用栈作为辅助空间。为了解决这个问题，Morris方法用到了线索二叉树（threaded binary tree）的概念。在Morris方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。

用Morris Traversal实现中序遍历的流程如下：

• 最开始时，将整棵树的根节点设为当前节点；
• 然后开始判断：
  • 如果当前节点的左子节点不为空，则在当前节点的左子树中找到在中序遍历条件下的前驱节点（即最右最下方的节点），然后对前驱节点进行判断：
    • 如果前驱节点的右子节点为空（表明Morris Traversal处在查找过程），则让前驱节点的右子节点指向当前节点，同时断开当前节点和其左子节点之间的连接（即让当前节点的左子节点指向None），然后让当前节点的左子节点成为当前节点（这里的左子节点指的是断开之前的左子节点）；
    • 如果前驱节点的右孩子就是当前节点（表明Morris Traversal处在回溯过程），则输出当前节点，然后将它的右孩子重新设为空（恢复树的形状），同时将当前节点更新为当前节点的右子节点（设为空之前的右子节点）。
  • 如果当前节点的左孩子为空，则输出当前节点并将其右孩子设为当前节点。
  • 重复以上两个大步骤，直至当前节点为空。

使用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 # 当前节点的左子节点为空后，第一件事就是让当前节点的左指针指向pre
            if pre is None:
                res = cur # 这里是为了找到链表的头，只执行一次
            else:
                pre.right = cur
            pre, cur = cur, cur.right
        return res

37. 序列化二叉树

序列化就是指将树结构的数据类型转换成一个字符串，如何转换以及转换成一个什么样的字符串，就是序列化的过程要考虑的问题。
反序列化就是从序列化后的字符串中恢复出树结构。

书中的分析：

可以先把一棵二叉树序列化成一个前序遍历序列，然后再将这个前序遍历序列通过反序列化重建出原二叉树。

如果二叉树的序列化是从根节点开始的，那么相应的反序列化在根节点的数值读出来的时候就可以开始了。因此，可以根据前序遍历的顺序来序列化二叉树（因为前序遍历正好是从根节点开始的）。当遍历的过程中碰到空指针时，这些空指针要被序列化为一个特殊的字符（如 $ ）。此外，节点的数值之间要用一个特殊的字符（如 , ）隔开。

总结前面序列化和反序列化的过程，可以发现都是把二叉树分解成三部分：根节点、左子树和右子树。在处理根节点之后再分别处理它的左、右子树。因此这个问题可以用递归解决。

# 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. 字符串的排列

书中的分析：
可以把一个字符串看成由两部分组成：第一部分是它的第一个字符；第二部分是后面的所有字符。
这样求整个字符串的排列就可以看成两步。第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面所有字符的排列。这时候仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。这显然是一个递归的过程。

网站实现（循环）：

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 []

实现思路：自底向上。假设 ss = 'abc' ，则：

• step 1：假设原始结果为 [''] ，先取 ss 中的第一个字符 a ，此时这个字符和原始的结果之间只可能有一种排列方式，即：ans = ['a'] ；

• step 2：再取 ss 中的第二个字符 b，此时 b 和上一步中的结果 ['a'] 可能构成两种排列：将 b 插在 a 的前面和将 b 插在 a 的后面，即： ans = ['ba', 'ab'] ；

• step 3：最后取 ss 中的第三个字符 c ，此时 c 和上一步的结果 ['ba', 'ab'] 将会有多种组合方式，应该分别将 ans 中的两个字符串取出来，和 c 进行排列，此即 for p in ans 的含义。将 c 插入到 ba 中，等价于将 ba 拆开，然后将 c 放到拆开的位置。如何拆呢？这里用切片实现：

  • '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:]

  因此第二个循环中 i 的作用就是确定如何对 p 进行拆分。这样当 p 遍历完 ans 后，ans 中的所有结果便都和字符 s 进行了所有的排列。

这里用 range((p+s).index(s)+1) 而不用 range(len(p+s)-1) 是因为，如果 p 和 s 中有重复的字符，前者可以避免重复进行排列，而后者无法做到这一点。（如 'ba' + 'a' ）。

如果是要求对整数做排列，则代码为：

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 型的数字和列表是不能相加的，必须要在数字外面包上中括号，然后才能和 list 相加。

39. 数组中出现次数超过一半的数字

绝大部分动态规划算法的分析和代码实现都是分两个步骤来完成的：

• 用递归的思路来分析问题；
• 基于循环用数组来保存中间结果从而实现代码。

波义耳摩尔投票算法：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/

算法描述：

遍历数组的时候保存两个值：一个是数组中的数字，另一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，那么需要保存下一个数字，并把次数设为1.由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时的对应数字。

优点：通过这种算法，在线性时间复杂度和常数空间复杂度的情况下即可找到数组的主要元素（即出现次数超过一半的元素）。

代码实现：

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 个数

用一个最大堆来存储最小的 k 个数字，然后从剩余的数据中每次读入一个数。如果这个数比堆中最大的数还大，那么可以不用管这个数字；如果这个数比堆中最大的数字小，那么就用这个数来替换堆中最大的数。

在最大堆中，根节点的值总是大于它的子树中任意节点的值。因此，每次都可以在 的时间内从堆中找到最大值，但需要 的时间来完成删除及插入操作。

因此，用最大堆的方法总的时间复杂度为 ，而且这种方法适合处理海量的输入数据。

代码：

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]] # 因为后面用的都是最小值，所以这里提前将它们转成负数
    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)

点评：当需要在某个数据容器内频繁查找及替换最大值时，二叉树是一个合适的选择，而且此时用堆或者红黑树等特殊的二叉树来实现比较合适。

41. 数据流中的中位数

书中的分析：

假设将整个数据流进行排序，然后用一个分界线将数据分为两部分：分界线左侧的数据均不大于中位数，分界线右侧的数据均不小于中位数。

然后，用一个最大堆去装载分界线左侧的数据，用一个最小堆去装载分界线右侧的数据。这样如果整个数据流的个数为奇数个，则最大堆堆顶或最小堆堆顶的数据即为中位数；如果整个数据流的个数为偶数个，则最大堆堆顶和最小堆堆顶数据的平均数即为中位数。

而不管是最大堆还是最小堆，获取堆顶数据的时间复杂度均为 。

其次，往堆中插入一个数据的时间复杂度是 。为了保证数据平均分配到两个堆中（即两个堆中数据的个数相差不能超过1），可以在堆中现有数据的总数目是偶数时将新来的数据插入到最小堆中，否则将其插入到最大堆中。

此外，还要保证最大堆中的所有数据都要小于最小堆中的所有数据。如果新来的数据大于最小堆中的一些数据但是却被插入到最大堆中了，则此时还是先将其插入到最大堆（可能是为了维持数据平衡的需要），然后将最大堆中最大的数字拿出来并将其插入到最小堆。新来的数据小于最大堆中的某些数但却被插入到最小堆的情形也是如此。

网站上的分析：

使用两个堆，最大堆存储较小的数据，最小堆存储较大的数据。添加数字时，先添加到最大堆，然后最大堆返回一个最大的数字给最小堆，最后为了平衡，可能需要最小堆还给最大堆一个最小值，以保证最大堆的长度>=最小堆的长度。由于headpq是最小堆，所以使用取反实现最大堆。添加数字：Time-O(logn)，取出中位数：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) # 新来的数据总是先放到最大堆
        hq.heappush(self.hi, -hq.heappop(self.lo)) # 然后从最大堆中弹出最大值到最小堆
        
        if len(self.lo) < len(self.hi): # 最后维持数据间的平衡
            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. 连续子数组的最大和

书中的方法：

将第一个数字加到第二个数字上，如果和小于0，那么不管第三个数字为几，这一小于0的和如果加到第三个数上面，将只会使第三个数更小。因此应该抛弃前两个数的和，从第三个数字开始重新和后面的数进行累加。

即：只有当前面的累加和为正值时，才让它和后面的数继续相加，否则从后面的数开始重新进行累加。

代码实现：

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)

为了避免对原始数组的修改，这个代码先将原始数组复制了一份，因此会有额外的 的空间复杂度。然后，从复制数组的第2项开始，判断并累加前面的结果。

43. 1～n 整数中 1 出现的次数

先给出代码：

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

然后再来分析代码是如何执行的。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)

这里让输入的数字 n=21345，运行结果如下：

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

程序是按位（从最高位到最低位）、分区（整区和零区）来统计1出现的次数的。不妨倒着来看：

（1）首先固定万位数字为1，先来看整区，整区即以10w为单位，看n最大能达到多少。显然n不够10w，因此整区的数字范围不存在。显然，此时一种可能的情况都没有；

然后再来看零区（零区即在整区数字范围之外的数字），零区的数字范围为 0 ~ 21345 ，固定万位为1，则所有可能的情况为：

10000 ~ 19999

总共有 种可能的情况。

（2）然后固定千位为1，还是先来看整区的情况。此时的整区为以1w为单位，看n最大能取多少。显然，以1w为单位的话，n最大只能取到20000，因此整区的数字范围为 0 ~ 20000 。固定千位为1，则所有可能的情况为：

11000 ~ 11999
 1000  ~ 1999

最高位可以取0和1两个数字，后三位每一位都可以取0~9这10个数字，因此总共有 种可能的情况。

再来看零区，此时零区的数字分布在 20000 ~ 21345 之间，固定千位为1，则所有可能的情况为：

21000 ~ 21345

此时后三位的数字不能随便取，因为它有一个上限 345 ，因此零区所有可能的情况为 种。

（3）接着固定百位为1，则整区应该以千计，最大只能达到21000，因此整区数字范围为 0 ~ 21000 ，固定百位数字为1，则所有可能的情况为：

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

显然，总共包括21大种情况，每一大种情况内部由于个位和十位数字都可以从0到9任取，因此所有可能的情况为 种。

然后看零区，除整区外，零区剩余的数字范围为 21001 ~ 21345 ，然后固定百位数字为1，则所有可能的情况为：

21100 ~ 21199

总共是 种情况。

（4）固定十位数字为1，则整区以百计，最大21300，则整区共有 种情况；

零区为 21301 ~ 21345 ，固定十位数字为1，则共有 种情况。

（5）最后固定个位数字为1，整区以十计，最大21340，固定个位数字为1，共有 种情况；

零区：21341 ~ 21345 ，固定个位数字为1，只有一种情况：21341。

以上代码就是按照这一思路来编写的， i 代表的是固定哪一位数字为1， divider 代表的是整区以多少计，注意到 divider 总是 i 的10倍。

(n // divider) * i 代表的是整区总共有多少种情况；

min(max(n % divider - i + 1, 0), i) 代表的是零区有多少种情况。最外层的 min 代表的是零区的情况最多不超过 i ，如 i 在万位时最多不超过10000， i 在千位时最多不超过 1000。注意到，只要 i 所在的数字大于1，则总有：

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

成立，称此种情况为“饱和”，即当 i 所在的数字大于1时，零区范围内 i 后面的数字总能取满（即能取尽0~9的所有情况），因此零区总的情况数总是10的幂次，即由外层 min 函数中的 i 决定。
而当 i 所在的数字小于或等于1时，总有：

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

成立，称此种情况为“不足”，即如果 i 所在的数字小于或等于1，则零区范围内 i 后面的数字就不能取尽0~9的所有情况，此时零区的所有情况将受限于 i 后面的数字最大能达到多大（当 i=1 时）或干脆直接就等于0（当 i=0 时）。

以上就是对整个代码运行过程的分析。由于是按位进行循环的，因此时间复杂度为 。推导过程如下：

假设 为输入的数字， 为需要循环的次数，则有：

因此，时间复杂度为 。

44. 数字序列中某一位的数字

书中的分析如下：

假设 n=1001，则：

• 序列的前 10 位是 0~9 这 10 个只有一位的数字。显然第 1001 位在这 10 个数字之后，因此这 10 个数字可以直接跳过。然后再从后面紧跟着的序列中找第 991 （991=1001-1-1x9）位的数字；
• 接下来 180 位数字是 90 个 10~99 的两位数。由于 991>180，所以第 991 位在所有的两位数之后。我们再跳过 90 个两位数，继续从后面找 811 （811=991-2x90）位；
• 接下来的 2700 位是 900 个 100~999 的三位数。由于 811<2700，所以第 811 位是某个三位数中的一位。由于 811//3 = 270，因此第811位是从100开始的第270个数字，即 100+270=370。然后再判断是属于370的第几位：811%3=1，因此是属于370的第1位（索引从0开始），即数字7。

代码：

class Solution(object):
    def digitAtIndex(self, n):
        """
        :type n: int
        :rtype: int
        """
        base = 1   # base是基数，它的取值分别为1, 10, 100, 1000, ...
        width = 1  # width是对应的位宽，取值分别为1, 2, 3, 4, ...
        basecount = 9  # basecount是在某个位宽范围内总共有多少个数，取值分别为9, 90, 900, ...
        nleft = n - 1  # nleft是当前还剩多少位，取值为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 # 基数每次扩大10倍
            width += 1 # 位宽每次增加一位
            basecount *= 10
        
        num = base + nleft//width  # 确定该数字是几，必须要加上基数
        bit = nleft % width  # 确定该数字属于num的第几位
        
        return int(str(num)[bit])  

这里要注意的是 nleft 的初始值是 n-1 。

45. 把数组排成最小的数

n 个数字总共有 种排列方式。

书中的分析：这道题其实是希望我们能找到一个排序规则，即给出两个数字 和 ，我们需要确定一个规则判断 和 哪个应该排在前面，而不仅仅是比较这两个数字的值哪个更大。

根据题目的要求，两个数字 和 能拼接成数字 和 。如果 ，那么我们应该打印出 ，即 应该排在 的前面，我们定义此时 小于 ；反之，如果 ，则我们定义 小于 ；如果 ，则 等于 。自定义比较方法可以通过python的 functools.cmp_to_key() 函数实现。

在比较时，应该先将 int 型的数字转换成字符串。

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 型的结果，因此上述代码等价于以下三种情况：

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. 把数字翻译成字符串

书中的分析：如果用自上而下的递归来解决问题，则会造成重复的计算（就和计算斐波那契数是一样的），因此可以从最小的子问题开始，用自下而上的循环解决问题。也就是说，我们可以从数字的末尾开始，然后从右到左翻译并计算不同翻译的数目。（如果从数字的开头开始，从左到右翻译则是递归的方法。）

代码如下：

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

对这个代码的分析如下：

假设给定一个字符串 x ，我们将其视为一个黑箱，假设它有 w 种翻译方法。同时，如果将 x 的最后一个字符去掉，剩余的字符有 v 种翻译方法。

现在又来了一个新字符 d ，那么 x 和 d 放在一块会有多少种翻译方法呢？根据我们已经直到的信息，我们不妨将其分为两种情况：

• 第一种情况：如果 d 本身能够翻译成字符，那么 d 自己只会有一种翻译方法，而前面的 x 有 w 种翻译方法，则此时总共会有 1 * w 种翻译方法，亦即代码中的 int(d>'0')*w ；
• 第二种情况：将 d 和 x 的最后一个字符 p 配对，如果 p 和 d 放一起后也能翻译成字符，那么这也将提供一种翻译方法，而 x 去掉 p 后总共有 v 种翻译方法，因此此时总的翻译方法数为：1 * v ，亦即代码中的 (9<int(p+d)<27)*v 。

值得注意的是，这种基于循环的自下而上的方法虽然可以避免重复的计算，但是它要保存中间结果。根据前面的分析，这里要保存的中间结果有三个：

• 上一轮总的翻译方法数，即代码中的 w ；
• 上一轮去掉最后一个字母的方法数，亦即上上一轮的方法数，在代码中表示为 v ；
• 上一轮的最后一个字母，即代码中的 p ，代码中的 d 是当前这一轮新来的字母。

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. 礼物的最大价值

书中的分析：

本题用到的方法是动态规划。先用递归的思路来分析问题，再用循环的方式来编写代码。

先定义一个函数 表示到达坐标为 的格子时能拿到的礼物总和的最大值。根据题目要求，有两种可能的途径到达坐标为 的格子：通过格子 或者 。所以 。其中 表示坐标为 的格子里礼物的价值。

代码：

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]

代码分析：

这里用到了两个列表来存储临时值。cur 代表的是上一行中走到各个位置时能获得的礼物的最大值。tmp 中存储的是走到当前行的各个位置时能获得的礼物的最大值，在每一行最开始时都要重置 tmp ，left 是 tmp 中上一次被添加进去的礼物的最大值，如果要获得下一次获得礼物的最大值，则要将 left 取出来，然后和 cur 中对应列处的值进行比较。这是两种不同的走法：

• 如果是 left + g[i][j] ，则表明是先往下走再往右走；
• 如果是 cur[j] + g[i][j] ，则表明是先往右走再往下走。

在每一行计算完成后，cur 都要及时更新为上一行的值，即 cur = tmp 。然后在下一行开始时，重新将 tmp 清空。

当所有循环都结束时，cur[-1] 中保存的即为整个矩阵中可获得礼物的最大值。

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)

输出结果为：

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. 最长不含重复字符的子字符串

书中的分析：本题要用动态规划来解决。

代码：

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 保存的是字符串中每个字符最后一次在字符串中出现的位置，每遍历到一个字符，都要先判断一下该字符是否已经在 pos 中出现过，如果出现过，就表明遇到重复字符了，此时要更新 start 的值。 pos[c] 有可能出现在 start 的后面，也有可能出现在它的前面，为了保证 start 总是取最右边的值，这里要取上一次的 start 和 pos[c] 中的最大值。

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

最终返回的结果就是上一次的结果和 end 与 start 之间距离的最大者。

49. 丑数

[书]：根据丑数的定义，丑数只能被 2 、 3 和 5 整除。也就是说，如果一个数能被 2 整除，就连续除以 2 ，如果最后得到的是 1 ，那么这个数就是丑数，否则不是；同样，如果一个数能被 3 整除 （或者被 5 整除），就连续除以 3 （或者 5），如果最后得到的是 1 ，那么这个数就是丑数，否则不是。

本题的高效解法是只计算丑数，不管非丑数。根据丑数的定义，丑数应该是另一个丑数（1除外）乘以 2、 3 或 5 的结果。因此我们可以以空间换时间：创建一个数组，里面的数字是排好序的丑数，每个丑数都是前面的丑数乘以 2、 3 或 5 得到的。
这种思路的关键在于怎样确保数组里面的丑数是排好序的。假设数组中已经有若干个排好序的丑数，并且把已有最大的丑数记作 M。如果将已有的丑数中所有的数字都乘以 2 ，并把得到的第一个乘以 2 以后大于 M 的结果记为 。同样，我们把已有的每个丑数乘以 3 和 5，能得到第一个大于 M 的结果 和 。那么下一个丑数应该是 。

因为已有的丑数是按顺序存放在数组中的。对于乘以 2 而言，肯定存在某一个丑数 ，排在它之前的每个丑数乘以 2 得到的结果都会小于已有的最大丑数，在它之后的每个丑数乘以 2 得到的结果都会太大。我们只需记下这个丑数的位置，同时每次生成新的丑数的时候去更新这个 即可。对于乘以 3 和 5 而言，也存在同样的 和 。

def nthUglyNumber(self, n: int) -> int:
    q = [1]
    t2 = t3 = t5 = 0
    for _ in range(n-1): # 这里是挖掉第一个默认的丑数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. 第一个只出现一次的字符

[书]：定义哈希表的 Key 是字符，Value 是该字符出现的次数。我们需要从头开始扫描字符串两次。第一次扫描字符串时，每扫到一个字符，就在哈希表的对应项中把次数加 1 。接下来第二次扫描时，每扫到一个字符，就从哈希表中得到该字符出现的次数。这样，第一个只出现一次的字符就是符合要求的输出。

def firstUniqChar(self, s):
    from collections import Counter
    c = Counter(s) # Counter是dict的一个子类，因此这里本质上返回的是一个dict
    for i, ch in enumerate(s):
        if c[ch] == 1:
            return i
    return -1

总结：有关字符及其出现次数的问题，通常都会借助一个辅助的哈希表来换取时间效率。

如果字符是一个接一个从字符流中读出来的，则上述代码中 c 就不能用 Counter 来实现了。此时只能构建一个哈希表，然后每来一个字符，都在哈希表中查找一下，如果已经存在，只就加1；如果不存在，就把它添加到哈希表中。

通常要更加关注时间复杂度。
降低时间复杂度的第一种方法是改用更加高效的算法。
降低时间复杂度的第二种方法是用空间换取时间。

51. 数组中的逆序对

[书]：先把数组分隔成子数组，统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对数目。在统计逆序对的过程中，还需要对数组进行排序。这个排序过程实际上就是归并排序。具体过程如下：

先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个子数组中的数字则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数。而如果第一个数组中的数字小于或等于第二个数组中的数字，则不构成逆序对。每次比较的时候，我们都把较大的数字从后往前复制到一个辅助数组，确保辅助数组中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。

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. 两个链表的第一个公共节点

[书]：如果两个单向链表有公共的节点，那么这两个链表从某一节点开始，它们的 next 指针都指向同一个节点。但由于是单向链表的节点，每个节点只有一个 next 指针，因此从第一个公共节点开始，之后它们所有的节点都是重合的，不可能再出现分叉。所以两个有公共节点的单向链表，其拓扑形状看起来像一个 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

代码分析：

• 第一个指针走到头之后返回来从 B 继续开始走；
• 第二个指针走到头之后返回来从 A 继续开始走；
• 这样最终相遇时，两个指针走的路程是一样的。

53-1. 在排序数组中查找数字

[书]：既然输入的数组是排序的，那么我们就能很自然地想到用二分查找算法。

二分查找算法总是先拿数组中间的数字和 k 作比较。如果中间的数字比 k 大，那么 k 只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。如果中间的数字比 k 小，那么 k 只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。

如果中间的数字和 k 相等，那么我们首先要判断这个数字是不是第一个 k 。如果中间数字的前面一个数字不是 k ，那么此时中间的数字刚好就是第一个 k ；如果中间数字的前面一个数字也是 k ，那么第一个 k 肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。

同样，我们可以在排序数组中找到最后一个 k 。如果中间数字等于 k ，我们需要判断这个 k 是不是最后一个 k ，也就是中间数字的下一个数字是不是也等于 k 。如果下一个数字不是 k ，则中间数字就是最后一个 k ；否则下一轮我们还是要在数组的后半段中去查找。

以上查找第一个 k 和最后一个 k 的过程都是通过二分查找进行的，它们的时间复杂度均为 ，因此总的时间复杂度也为 。

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 函数如何保证最终返回的就是最左边的 target 的索引：在 if 判断语句中，当 nums[mid] = n 时，hi 还是要不断往前移，这就保证了最终它会移到最左边的 target 所在的位置。

在寻找 target 在最右边的索引时，为了能够利用已有的 search 函数而不再专门定义一个新的查找最右边 target 的函数，这里改为先查找比 target 大 1 的数在最左边位置的索引，将这个索引减 1，即可得到 target 在最右边的索引。这里值得注意的是，即使数组中不存在比 target 大 1 的数，查找 target+1 也能够正确的返回最右边的 target 右边紧邻的那个数字的索引。如果最右边的 target 已经是整个数组的最后一个数字，则依然能够返回正确的值，因为 hi 的初始值被设成了 len(nums) 而非 len(nums)-1 ，在这种情况下，查找 target+1 将返回 len(nums) 。

53-2. 0～n-1 中缺失的数字

[书]：首先将问题进行转换：因为 0～n-1 这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同。如果不在数组中的那个数字记为 m ，那么所有比 m 小的数字的下标都与它们的值相同。由于 m 不在数组中，那么 m+1 处在下标为 m 的位置，m+2 处在下标为 m+1 的位置，以此类推。可见 m 正好是数组中第一个数值和下标不相等的元素的下标，因此这个问题转换成在排序数组中找出第一个值和下标不相等的元素。

方法：基于二分查找的过程如下：(时间复杂度：)

• 如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；
• 如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，则意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；
• 如果中间元素的值和下标不相等，并且它前面一个元素和它的下标也不相等，则意味着下一轮查找我们只需要在左半边查找即可。

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

如果数组是未排序的，则可以先计算出 0~n-1 的所有数字的和，再减去数组中所有数字的和，即可得到缺失的数字。但这种方法需要 的时间求数组中所有数字的和。

53-3. 数组中数值和下标相等的元素

[书]：由于数组是单调递增排序的，因此可以选择用二分查找法。

由于数组中的所有数字都唯一并且单调递增，因此如果一个数字大于它的下标，那么这个数字右边的所有数字都将大于它的下标，在下一轮查找时在这个数字左边的部分进行查找即可。同样，如果一个数字小于它的下标，那么它左边的数字也都会小于它的下标，下一轮查找时只需要在它的右边进行查找即可。

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

总结：二分查找法非常适合在排序的数组中进行查找。

54. 二叉搜索树的第 k 大节点

[书]：本题实际上考查的是对中序遍历的理解：如果按照中序遍历的顺序遍历一棵二叉搜索树，则遍历序列的数值是递增排序的，从中序遍历序列中便很容易找到第 k 大节点。

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 # 这里先一直到达二叉搜索树的最大节点
            root = stack.pop()
            k -= 1
            ans = root
            root = root.left
            if k == 0:
                return ans

注意这里最终返回的是节点而非节点的值。

55-1. 二叉树的深度

定义：从根节点到叶节点依次经过的节点形成树的一条路径，最长路径的长度（即节点的个数）为树的深度。

这里用到了用 deque 实现的 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. 平衡二叉树

[书]：本题实质考查树的后序遍历。如果用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之前我们就已经遍历了它的左、右子树。在遍历该节点的左、右子节点之后，我们就可以根据它的左、右子节点的深度（某一节点的深度等于它到叶节点的路径的长度）判断它是不是平衡的，并得到当前节点的深度。当最后遍历到树的根节点的时候，也就判断了整棵二叉树是不是平衡二叉树。

但是用后序遍历的代码比较复杂，这里用了一种更简单且不会重复遍历节点的方法：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 会先深入到最左下方的节点，然后从这个节点开始，逐个节点进行判断，逐个节点返回，逐个遍历剩余节点，而且总是优先遍历纵深处的节点，直至最终到达根节点。

56-1. 数组中只出现一次的两个数字

[书]：异或运算的一个性质：任何一个数字异或它自己都等于 0 。假如一个数组中只有一个数字只出现了一次，其他数字都出现了两次，那么当我们从头到尾依次异或数组中的每个数字时，最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。

现在数组中有两个数字只出现了一次，如果我们能想办法把原数组分成两个子数组，使得每个子数组均只包含一个只出现一次的数字，而其他数字都成对出现两次，那我们就可以按照前面的方法分别找出这两个数组中只出现一次的那个数字。

用什么方法（或按什么样的标准）才能做到将这两个不同的数字分到两个不同的数组里，而且每个数组里的其他值均是成对出现的呢？我们首先从头到尾依次异或数组中的每个数字，那么最终得到的结果就是那两个只出现一次的数字异或得到的结果（其他数字因为成对出现所以全部被抵消），而且最终的结果肯定不为 0 ，也就是说，最终结果的二进制表示中至少有一位为 1 。我们在结果数字中找到第一个为 1 的位的位置，记为第 n 位。现在我们就得到了将原数组划分成两个子数组的标准：看它的二进制表示中第 n 位是不是 1 。如果是 1 ，则分到第一个子数组中；如果是 0 ，则分到第二个子数组中。（因为异或是“相同为 1 ，不同为 0”，所以这两个只出现一次的数肯定会被分到不同的子数组中去。）这样我们就完成了数组的划分，然后再运用前面的方法，即可找到这两个数字。

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: # 找到第一个为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. 数组中唯一只出现一次的数字

[书]：本题的两种直观的解法：

• 先将数组排序，然后从排序的数组中就可以很容易找到只出现一次的数字，但排序需要 的时间；
• 也可以用一个哈希表来记录数组中每个数字出现的次数，但这个哈希表需要 的空间。

以上两种方法都不是最优的解法，最优的解法仍然要用到位运算，这里就要考查二进制表示的一些性质：

如果一个数字出现三次，那么它的二进制表示的每一位（0或者1）也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被 3 整除。如此，我们便可以通过二进制表示来确定那个只出现一次的数字都会出现在哪一位：我们先把数组中所有数字的二进制表示的每一位都加起来，如果某一位的和能被 3 整除，那么那个只出现一次的数字二进制表示中对应的那一位就是 0 ；否则就是 1 。这种解法的时间效率是 ，空间效率是 。

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的个数。假设count%3!=0为True，说明该元素i位为1，然后是用|=更新ans在第i个位置的值，这里也可以使用+=，但是效率稍慢。convert的作用是因为python中的int是个对象，且没有最大限制，不是在第32位使用1来表示负数。

57-1. 和为 s 的两个数字

[书]：首先定义两个指针，第一个指针指向数组的第一个数字，第二个指针指向数组的最后一个数字。如果两指针指向的数字大于 s ，则向前移动后一个指针；如果两指针指向的数字小于 s ，则向后移动前一个指针。如此，直至两指针指向的数字等于 s ，或直至左指针的下标不再小于右指针，表明数组中不存在和为 s 的两个数字，此时返回空列表。

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 的连续正数序列

[书]：考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1 ，big 初始化为 2 。如果从 small 到 big 的序列的和大于s ，则可以从序列中去掉较小的值，也就是增大 small 的值。如果从 small 到 big 的序列的和小于 s ，则可以增大 big ，让这个序列包含更多的数字。因为这个序列至少要有两个数字，所以 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. 翻转单词顺序

[书]：通过两次翻转来解决。第一步先翻转句子中所有的字符，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。第二步再翻转每个单词中字符的顺序，就可以实现要求的翻转。

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

        def hp_reversed(s): # 这个函数返回完全逆序的结果
            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) # 先对整个字符串进行翻转
        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==' '是判断除最后一个字符之外的其他字符，r==len(s)-1是判断最后一个字符
                ans += hp_reversed(word) + ' ' # 这里是对每一个单词进行翻转
                word = ''
        return ans[:-1] # 最后一个字符不要是因为ans每次在添加的时候多加了一个空格

如果可以使用 python 的 split() 函数，则以上代码可以简化为：

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() 函数，则以上代码可以进一步简化为只有一行：

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

58-2. 左旋转字符串

[书]：可以借鉴前面的翻转单词顺序的思想：假如给定字符串 "abcdefg" ，我们想把它的前两个字符进行左旋转操作，那么我们首先可以将它分成两部分：把前两个字符分到第一部分，把后面的所有字符分到第二部分。第一步先翻转整个字符串，得到 "gfedcba" ，第二步再翻转单词内部的顺序，得到 "cdefgab" 。此外，本题还要注意非法输入及越界等问题。

但是darktiantian认为书中的方法并不适用于 python，因此他用了如下切片的方法进行解决：

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

59-1. 滑动窗口的最大值

[书]：一个滑动窗口可以看成一个队列，当窗口滑动时，处于窗口的第一个数字被删除，同时在窗口的末尾添加一个新的数字，这符合队列“先进先出”的特性。

我们并不把滑动窗口的每个数值都存入队列，而是只把有可能成为滑动窗口最大值的数值存入一个两端开口的队列。

但是，为了确定某个数字是否已经滑出了滑动窗口，应该在队列中存入数字在数组里的下标，而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时，这个数字已经从窗口中滑出，可以从队列中删除了。

注意到滑动窗口的最大值总是位于队列的头部。

综上，我们需要一个双端队列，用来保存有可能是滑动窗口最大值数字的下标。在存入一个新的数字的下标之前，首先要判断队列里已有的数字是否小于待存入的数字。如果已有的数字小于待存入的数字，那么这些数字已经不可能是滑动窗口的最大值，因此它们将会被依次从队列的尾部删除。同时，如果队列头部的数字已经从窗口里滑出，那么滑出的数字也需要从队列的头部删除。

darktiantain：得益于python的切片，有一种很简洁的方法（其实本质上是蛮力法），时间复杂度为 ， 为滑动窗的大小：

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

另一种方法就是和书中的方法一样，用双端队列，时间复杂度为 ：

def maxInWindows(self, nums, size):
    from collections import deque
    q = deque()
    ans = []
    def pop_less(i):
        # nums[i] 索引和值都比队列尾的元素大，队列尾的元素就没有必要存在了
        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循环中每一轮添加的其实是上一轮的最大值，因此循环退出后必须补一个append操作
    return ans

59-2. 队列的最大值

[书]：可以借鉴上题中找滑动窗口的最大值。这一次要找的是整个队列的最大值，相当于是把滑动窗口设置为整个队列。

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: # 先要判断队列是否为空
            return
        data = self.dequeData.popleft()
        if data == self.dequeMax[0]:
            self.dequeMax.popleft()
    
    def max(self):
        return self.dequeMax[0]

注意 push_back 中的 while 循环，如果 number 大于 dequeMax 中的所有元素，则该循环将会把 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])

有一点必须要明确，那就是当队列中的某个数被弹出时，此时队列的最大值只可能在这个数的右边出现，因为“后进先出”的原则，这个数左边的数字早就被弹出了。

60. n 个骰子的点数

[书]：考虑用两个数组来存储骰子点数的每个总数出现的次数。在一轮循环中，第一个数组中的第 n 个数字表示骰子和为 n 出现的次数。在下一轮循环中，我们加上一个新的骰子，此时和为 n 的骰子出现的次数应该等于上一轮循环中骰子点数和为 n-1 、n-2、 n-3、 n-4、 n-5、 n-6 的次数的总和，所以我们把另一个数组的第 n 个数字设为前一个数组对应的第 n-1 、n-2、 n-3、 n-4、 n-5、 n-6 个数字之和。

def dice_probability(n, val=6):
    dp = [[0]*val*n for _ in range(n)]
    dp[0][:val] = [1] * val  # 初始化第一个骰子
    
    for i in range(n-1):  # 根据第i个骰子更新第i+1个骰子
        for j in range(i, len(dp[i+1])):
            # 第i+1个骰子和为j（实际为j+1，因为数组下标从0开始）的次数，等于第i个
            # 骰子j-1 ~ j-6次数的总和
            dp[i+1][j] = sum([dp[i][j-k] for k in range(1, val+1)])
            
    # 整理数据成为dict，key表示和，value表示出现的次数
    # count = {i+1: times for i, times in enumerate(dp[-1])}
    # 计算概率
    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表示第一个骰子和为j+1的次数为1，因为数组下标从0开始。

61. 扑克牌中的顺子

[书]：由于大、小王可以看成任意数字，我们不妨把它们都定义为 0 。

首先，如果一副牌里含有对子，则不可能是顺子。

为了判断 5 个数字是不是连续的，我们需要首先把数组排序；其次统计数组中 0 的个数；最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于 0 的个数，那么这个数组就是连续的；反之则不连续。

def IsContinuous(self, numbers): # numbers是随机抽到的5张牌
    if not numbers:
        return False
    joker_count = numbers.count(0) # count用于统计字符串里某个字符出现的次数
    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]: # 如果有对子出现，肯定不会连续
            return False
        need_joker += (left_cards[i+1]-left_cards[i]-1)
    return need_joker <= joker_count

62. 圆圈中最后剩下的数字

圆圈报数问题的本质是约瑟夫环问题。详见：https://oldj.net/blog/2010/05/27/joseph-ring/

假设当环中还剩下最后一个人时，这个人的编号是 ，则约瑟夫环递推公式为：

其中， mod 是取余运算， 是总共有多少个人， 是报到第 个人出局。

在本题中， ，因此代码如下：

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 # 这里应该是last_num+A，因为A=0，所以省略掉了

63. 股票的最大利润

卡登算法：属于动态规划的一种，用于求连续子数组的最大和。详见：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

本题在此基础上稍微做了变形：

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

【注】如果价格比之前小，则舍弃，否则一起计算连续子数组的和。

卡登算法的时间复杂度为 。

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

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

65. 不用加减乘除做加法

python 的 int 是没有范围限制的，因此在进行位运算时，负数取补码将会变成一个非常大的数字。因此 python 在进行位运算时可能存在非常多的坑。参考：https://darktiantian.github.io/371-Sum-of-Two-Integers-Python/

如果不做任何限制，本题的原始代码为：

def get_sum(a, b):
    res, carry = 0, 0
    while b != 0: # step3: 不断循环直至最终进位为0
        res = a ^ b # step1: 相加但不进位
        carry = (a & b) << 1 # step2: 计算进位
        a, b = res, carry
    return res

在上述过程中，carry 右边第 2 位上的 1 将会不断往左移。正常情况下，当移到第33位时，由于数字范围的限制，这个 1 将会被舍弃从而使 b=0 ，使循环退出。但 python 的 int 没有限制，这样 carry 中的这个 1 就会一直不停地往前移，永远也不会消失，从而导致 b 永远不为 0 ，循环永远不会停止，造成死循环。

解决上述问题的关键就是我们要把数据范围限制在32位，为此，可以用一个32位全为1的 mask 来和数字进行相与从而得到一个32位的数字：mask = 0xFFFFFFFF 。但是这样改完以后还有一个问题：有时候负数和这个 mask 相与会变成一个很大的数字，为此darktiantian的看法是：

当负数与mask进行与运算时，比如-2，此时-2的补码变为11…10，一个33-bit的数字，然后和32位的mask与操作后，变为了一个33位的正数。

有一个公式可以帮我们还原a，如果一个负数n，它的无符号的32位补码是m，那么m=~(n ^ mask) 或者n=~(m ^ mask)

因此最终还有可能要做一个还原操作，所以最终的代码为：

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，因为numpy提供了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)

需要注意的是最后要再转回int，否则是没法通过测试用例的。