《剑指offer》所有习题python解法

Posted on | In | Visitors: 
1
《剑指offer》第二版python版总结。

动机

个人觉得在准备找工作要刷题前，先刷一遍这本书的问题，再去刷LeetCode这类的OJ比较合适。难度循序渐进，亦有理论支撑。

阅读流程：按照目录去索引问题，找到问题后，先看问题描述，思考问题解决思路；然后看思路，获取提示；然后阅读优点和复杂度，检查和自己想的是否一致。

用到的数据结构

数据结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
"""Self-defined data structures and some tool functions."""
from __future__ import print_function
from __future__ import absolute_import
from __future__ import division


class ListNode:
    """List node."""
    def __init__(self, x):
        self.val = x
        self.next = None


class TreeNode:
    """Tree node."""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class RandomListNode:
    """List node with a random field."""
    def __init__(self, x):
        self.val = x
        self.next = None
        self.random = None


class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None


def print_list(head_node):
    """Traverse a list and print."""
    vals = []
    while head_node:
        vals.append(head_node.val)
        head_node = head_node.next
    if len(vals) > 0:
        print(" ".join(map(str, vals)))
    else:
        print("This node list is empty!")

        
def print_random_list(head_node):
    """Traverse a random list and print."""
    while head_node:
        if head_node.next is not None:
            val_of_next = head_node.next.val
        else:
            val_of_next = None
        if head_node.random is not None:
            val_of_random = head_node.random.val
        else:
            val_of_random = None
        print("val: {}, val of next: {}, val of random: {} ".format(head_node.val, val_of_next, val_of_random))
        head_node = head_node.next
        

def print_tree(root_node):
    """Travers a tree by level and print."""
    travers = []
    queue = [root_node]
    while len(queue) > 0:
        farther = queue.pop()
        travers.append(farther.val)
        if farther:
            if farther.left:
                queue.insert(0, farther.left)
            if farther.right:
                queue.insert(0, farther.right)
    print(" ".join(map(str, travers)))


def init_nodes_by_list(l):
    """Initialize a List nodes with a given list of values."""
    head = last_node = ListNode(l[0])
    for one in l[1:]:
        node = ListNode(one)
        last_node.next = node
        last_node = node
    return head

NO.3 数组中重复的数字

  • 问题描述：在一个长度是n的数组里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3.
  • 思路：如果先排序，则时间复杂度是$O(logn)$。注意到数字的范围，所以如果将每个检查到的数，换到以这个数为下标的位置，则数组不会溢出。而且在交换的过程中，可以很快地检查是否有重复。
  • 优点：时间复杂度低。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isDuplicate(nums):
    l = len(nums)
    for i in range(l):
        cur_val = nums[i]
        # 当前值和不在这个值对应的下标上
        while cur_val != i:
            # 如果这个值对应的下标上已经是这个值，说明重复
            if nums[cur_val] == cur_val:
                return cur_val
            # 否则将当前值交换到这个值对应的下标上
            else:
                # swap in a pythonic way
                nums[cur_val], nums[i] = nums[i], nums[cur_val]
    return -1
1
2
test_nums = [2, 3, 1, 0, 2, 5, 3]
isDuplicate(test_nums)
1
2

NO.4 二维数组的查找

  • 问题描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
  • 思路：从右上角开始判断，若小于则在左边，大于则在下面。直到找完。
  • 优点：区域不会重合
  • 时间复杂度：$O(m+n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def Find(target, array):
    # 2-d array size: m * n
    m = len(array)
    n = len(array[0])
    j = n-1
    i = 0
    while i < m and j >= 0:
        if array[i][j] == target:
            return True
        elif array[i][j] < target:
            i += 1
        else:
            j -= 1
        
    return False
1
Find(7, [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]])
1
True

NO.6 从尾到头打印链表

  • 问题描述：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
  • 思路：使用一个栈，保存正序遍历的值。
  • 空间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
def printListFromTailToHead(listNode):
    values = []
    stack = []
    while listNode != None:
        stack.append(listNode.val)
        listNode = listNode.next
#     values = stack[::-1]
    for _ in range(len(stack)):
        values.append(stack.pop())
    return values
1
2
3
4
5
6
l1 = ListNode(1)
l2 = ListNode(2)
l3 = ListNode(3)
l1.next = l2
l2.next = l3
print(printListFromTailToHead(l1))
1
[3, 2, 1]

NO.7 重建二叉树

  • 问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出二叉树并输出它的头结点。
  • 思路：根据中序遍历和前序遍历可以很快找到（左子树，根，右子树）的分割，用递归实现。
  • 优点：思路简单清晰。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def reConstructBinaryTree(preorder, inorder, length):
    if not preorder or not inorder or length == 0:
        return 
    return constructCore(preorder, inorder, 0, length-1, 0, length-1)

def constructCore(preorder, inorder, p_s, p_e, i_s, i_e):
    root_val = preorder[p_s]
    root = TreeNode(root_val)
    if p_s == p_e or i_s == i_e:
        return root
    root_ind = inorder.index(root_val)
    left_len = root_ind - i_s 
    right_len = i_e - root_ind
    if left_len > 0: 
#         print "left", p_s+1, p_s+left_len, i_s, root_ind-1
        root.left = constructCore(preorder, inorder, p_s+1, p_s+left_len, i_s, root_ind-1)
    if right_len > 0:
#         print "right", p_s+left_len+1, p_e, root_ind+1, i_e
        root.right = constructCore(preorder, inorder, p_s+left_len+1, p_e, root_ind+1, i_e)
    return root
1
2
3
pre = [1,2,4,7,3,5,6,8]
tin = [4,7,2,1,5,3,8,6]
print_tree(reConstructBinaryTree(pre, tin, 8))
1
1 2 3 4 5 6 7 8

NO.8 二叉树的下一个节点

  • 问题描述：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
  • 思路：
  • 优点：

NO.9 用两个栈实现队列

  • 问题描述：用两个栈实现一个队列。请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
  • 思路：一个栈负责入队，另一个栈负责出队。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class CQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def appendTail(self, val):
        self.stack1.append(val)
    def deleteHead(self):
        if len(self.stack2) == 0:
            for _ in range(len(self.stack1)):
                self.stack2.append(self.stack1.pop())
            if len(self.stack2) == 0:
                print("Queue is empty!")
                return 
        return self.stack2.pop()
1
2
3
4
5
6
7
8
cqueue = CQueue()
cqueue.appendTail(1)
cqueue.appendTail(2)
cqueue.appendTail(3)
print(cqueue.deleteHead())
print(cqueue.deleteHead())
print(cqueue.deleteHead())
print(cqueue.deleteHead())
1
2
3
4
5
1
2
3
Queue is empty!
None

NO.10 斐波那契数列

  • 问题描述：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。
  • 思路：不用递归，用保存数组的方式。
  • 优点：时间复杂度比递归小。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
def Fibonacci(n):
    if n < 2:
        return 0
    minus_one = 1
    minus_two = 0
    res = 0
    for i in range(2, n+1):
        res = minus_one + minus_two
        minus_two = minus_one
        minus_one = res
    return res
1
2
for i in range(10):
    print((i, Fibonacci(i)), end=" ")
1
(0, 0) (1, 0) (2, 1) (3, 2) (4, 3) (5, 5) (6, 8) (7, 13) (8, 21) (9, 34)

快速排序

快排的整体思想就是每次执行一次partition，然后根据partition返回的位置将数组分成两段，再递归地对这两段子序列进行快排。

partition: 将当前第一个元素作为pivot，小的元素往前移到pivot的前面，大的元素往后移到pivot的后面。

1
2
3
4
5
6
7
8
9
def quickSort(data, l, s, e):
    if s == e:
        return 
    pivot_index = partition(data, l, s, e)
#     print(data)
    if pivot_index > s:
        quickSort(data, l, s, pivot_index - 1)
    if pivot_index < e:
        quickSort(data, l, pivot_index + 1, e)

不同的快排实现差别主要在partition的实现上。下面是《Problem Solving with Algorithms and Data Structures》上的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# def partition(data, l, s, e):
#     """双指针互换"""
#     pivot_index = s
#     pivot_value = data[pivot_index]
#     print("pivot_index: ", pivot_index, "pivot_value: ", pivot_value)
#     if s == e:
#         return pivot_index
#     # 双指针法
#     p1 = s + 1
#     p2 = e
#     done = False
#     while not done:
#         # 找到左边一个大的（待换）
#         while data[p1] <= pivot_value and p1 <= p2:
#             p1 += 1
#         #　找到右边一个小的（待换）
#         while data[p2] >= pivot_value and p1 <= p2:
#             p2 -= 1
#         if p1 > p2:
#             done = True
#         else:
#             data[p2], data[p1] = data[p1], data[p2] 
#     print("p1: ", p1, "p2: ", p2)
#     data[p2], data[pivot_index] = data[pivot_index], data[p2]
#     return p2

《剑指offer》的写法，倾向用这种。

1
2
3
4
5
6
7
8
9
10
11
12
13
def partition(data, l, s, e):
    """记录一个small指针和当前指针"""
    if s == e:
        return s
    small = s 
    pivot_index = s
    pivot_value = data[pivot_index]
    for i in range(s, e):
        if data[i] < pivot_value:
            small += 1
            data[i], data[small] = data[small], data[i]
    data[small], data[s] = data[s], data[small]
    return small
1
2
3
test_data = [11, 8, 15, 3, 2, 4, 6, 9, 7, 22]
quickSort(test_data, 10, 0, 9)
print(test_data)
1
[2, 3, 6, 4, 7, 8, 9, 11, 15, 22]

NO.11 旋转数组的最小数字

  • 问题描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
  • 思路：注意到最小的元素刚好是这两个子数组的分界线，用二分查找法的思路来寻找这个最小的元素。提示：１．第一个元素应该是大于或者等于最后一个元素的。２．前面子序列的元素都大于或者等于后面的子序列的元素。
  • 优点：时间复杂度低。
  • 时间复杂度：$O(logn)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findRotateMin1(data):
    """使用二分查找寻找最小值，初版"""
    l = len(data)
    if l == 0:
        print("Data is empty.")
        return
    s = 0
    e = l - 1
    while s < e:
        if e - s == 1:
            mid = e
            break
        mid = (s + e) // 2
        # 中间元素比起始元素小，所以中间元素属于属于第二个子序列
        if data[mid] < data[s]:
            e = mid
        # 中间元素不比其实元素小，所以中间元素属于第一个子序列
        else:
            s = mid
    return data[mid]
1
findRotateMin1([3,4,5,1,2])
1
1

正确

1
findRotateMin1([1,0,1,1,1])
1
1

错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def minInOrder(data, s, e):
    """顺序查找"""
    res = data[s]
    for i in range(s + 1, e + 1):
        if res > data[i]:
            res = data[i]
    return res


def findRotateMin2(data):
    """使用二分查找寻找最小值，完整版"""
    l = len(data)
    if l == 0:
        print("Data is empty.")
        return
    s = 0
    e = l - 1
    while s < e:
        if e - s == 1:
            mid = e
            break
        mid = (s + e) // 2
        # 如果s、e、mid指向的元素都相等，只能顺序查找
        if data[mid] == data[s] and data[mid] == data[e]:
            return minInOrder(data, s, e)
        # 中间元素比起始元素小，所以中间元素属于属于第二个子序列
        if data[mid] < data[s]:
            e = mid
        # 中间元素不比其实元素小，所以中间元素属于第一个子序列
        else:
            s = mid
    return data[mid]
1
findRotateMin2([3,4,5,1,2])
1
1
1
findRotateMin2([1,0,1,1,1])
1
0

都正确。

回溯

回溯法可以看成是蛮力法的升级版，它从解决问题每一步的所有可能选项里面系统地选择出一个可行的解决方案。回溯法非常适合由多个步骤组成，并且每个步骤都有多个选项。

下面两道题涉及回溯的思想，在解决回溯类的问题时，脑海中要想象一棵搜索树，树的每一层对应着一个步骤的搜索空间，如果在某层搜索失败，则需要回溯到上一步骤。

NO.12 矩阵中的路径

  • 问题描述：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如[["a", "b", "t", "g"], ["c", "f", "c", "s",], ["j", "d", "e", "h"]]矩阵中包含一条字符串”bfce”的路径，但是矩阵中不包含”abfb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
  • 思路：回溯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def hasPath(matrix, rows, columns, target_path):
    if len(target_path) == 0: 
        return True
    first_candidates = [] # [(r1, c1), (r2, c2), ...]
    # 搜索第一个点
    for i in range(rows):
        for j in range(columns):
            if matrix[i][j] == target_path[0]:
                first_candidates.append((i, j))
    # 第一个点搜索失败
    if len(first_candidates) == 0:
        return False
    # 搜索剩下所有点
    for r, c in first_candidates:
        if hasPathCore(matrix, rows, columns, target_path, [(r, c)]):
            return True
    return False
    
def hasPathCore(matrix, rows, columns, target_path, cur_path):
    # 已经搜索完毕
    if len(target_path) == len(cur_path):
        return True
    target_char = target_path[len(cur_path)]
    # 确定这步的搜索空间
    possible_points = []
    cur_point = cur_path[-1]
    if cur_point[0] > 0:
        possible_point = (cur_point[0] - 1, cur_point[1])
        if possible_point not in cur_path:   
            possible_points.append(possible_point)
    if cur_point[1] > 0:
        possible_point = (cur_point[0], cur_point[1] - 1)
        if possible_point not in cur_path:   
            possible_points.append(possible_point)
    if cur_point[0] < rows - 1:
        possible_point = (cur_point[0] + 1, cur_point[1])
        if possible_point not in cur_path:   
            possible_points.append(possible_point)
    if cur_point[1] < columns - 1:
        possible_point = (cur_point[0], cur_point[1] + 1)
        if possible_point not in cur_path:   
            possible_points.append(possible_point)
    # 搜索空间为空
    if len(possible_points) == 0:
        return False
    # 搜索一步
    for possible_point in possible_points:
        # 该步搜索成功
        if matrix[possible_point[0]][possible_point[1]] == target_char:
            # 搜索后续
            if hasPathCore(matrix, rows, columns, target_path, cur_path + [possible_point]):
                return True
    return False
1
2
3
test_matrix = [["a", "b", "t", "g"], ["c", "f", "c", "s",], ["j", "d", "e", "h"]]
print(hasPath(test_matrix, 3, 4, "bfce"))
print(hasPath(test_matrix, 3, 4, "abfb"))
1
2
True
False

NO.13 机器人的运动范围

  • 问题描述：地上有一个m行和n列的方格。一个机器人从坐标(0,0)的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够达到多少个格子？例如，当k为18时，机器人能够进入方格(35,37)，因为3+5+3+7=18。但是，它不能进入方格(35,38)，因为3+5+3+8=19。
  • 思路：回溯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def movingCount(threshold, rows, cols):
    if rows <=0 or cols <= 0:
        return 0
    # 如果没有访问过设为0，访问过设为1，不合法设为-1。
    reach_matrix = [[0 for j in range(cols)] for i in range(rows)]
    movingCountCore(reach_matrix, threshold, rows, cols, (0, 0))
    count = 0
    for i in range(rows):
        for j in range(cols):
            if reach_matrix[i][j] == 1:
                count += 1
    print("reach_matrix:", reach_matrix)
    return count

def movingCountCore(reach_matrix, threshold, rows, cols, cur_point):
    possible_next_points = getPossibleNextPoints(reach_matrix, rows, cols, cur_point)
    if len(possible_next_points) == 0:
        return
    for point in possible_next_points:
        if checkIsLegal(threshold, point):
            # 如果合法，记录记为1，且继续探索
            reach_matrix[point[0]][point[1]] = 1
            movingCountCore(reach_matrix, threshold, rows, cols, point)
        else:
            # 如果不合法，记录为-1，且停止改点后续的探索
            reach_matrix[point[0]][point[1]] = -1
    
def getPossibleNextPoints(reach_matrix, rows, cols, cur_point):
    r = cur_point[0]
    c = cur_point[1]
    possible_next_points = []
    if r > 0 and reach_matrix[r - 1][c] == 0:
        possible_next_points.append((r - 1, c))
    if c > 0 and reach_matrix[r][c - 1] == 0:
        possible_next_points.append((r, c - 1))
    if r < rows - 1 and reach_matrix[r + 1][c] == 0:
        possible_next_points.append((r + 1, c))
    if c < cols - 1 and reach_matrix[r][c + 1] == 0:
        possible_next_points.append((r, c + 1))
    return possible_next_points
    
def checkIsLegal(threshold, point):
    r = point[0]
    c = point[1]
    return getDigitSum(r) + getDigitSum(c) <= threshold
    
def getDigitSum(num):
    res = num % 10
    while num // 10 != 0:
        num = num // 10
        res += num % 10
    return res
1
movingCount(2, 3, 3)
1
2
3
reach_matrix: [[1, 1, 1], [1, 1, -1], [1, -1, 0]]

6

动态规划

使用动态规划的问题的三个特点：

  • 1.问题本身是求解一个最优解。
  • 2.这个最优解依赖于各个子问题的最优解。
  • 3.大问题可以分解成若干小问题，小问题之间还有相互重叠的更小的子问题。

贪婪算法

贪婪算法解决问题：每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。与此同时，我们必须要用数学方式证明贪婪选择是正确的。

NO.14 剪绳子

  • 问题描述：给定一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]* k[1] * … *k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
  • 思路：动态规划。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
def maxProductAfterCuttingDP(length):
    max_product = list(range(length + 1))
    for i in range(1, length + 1):
        for j in range(i):
            candidate = max_product[j] * max_product[i - j]
            if candidate > max_product[i]:
                max_product[i] = candidate
    print("max_product: ", max_product)
    return max_product[-1]
1
maxProductAfterCuttingDP(8)
1
2
3
max_product:  [0, 1, 2, 3, 4, 6, 9, 12, 18]

18

贪婪算法解法

  • 思路：贪婪算法。
  • 时间复杂度：$O(1)$
  • 策略：当$n\geq5$时，尽可能多地将剪绳子成长度为3；当剩下的绳子长度是4时，把绳子剪成两段长度是2的绳子。
  • 证明：当$n\geq 5$时，$2(n-2)\geq n$，$3(n-3)\geq n$且$3(n-3)\geq 2(n-2)$。但如果长度剪成其他大于3的长度，则一定可以用剪成两段2或者更多的3来替代。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxProductAfterCuttingGreedy(length):
    if length < 2:
        return 0
    if length == 2:
        return 1
    if length == 3:
        return 2
    # 尽可能多地剪成长度是3的绳子
    times_of_3 = length // 3
    # 此时的方案是将绳子剪成长度是2的两段，因为2*2 > 3*1
    if length - times_of_3 * 3 == 1:
        times_of_3 -= 1
    times_of_2 = (length - times_of_3 * 3) // 2
    
    print("times_of_3: ", times_of_3, "times_of_2: ", times_of_2)
    return pow(3, times_of_3) * pow(2, times_of_2)
1
maxProductAfterCuttingGreedy(8)
1
2
3
times_of_3:  2 times_of_2:  1

18

NO.15 二进制中1的个数

  • 问题描述：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。
  • 思路：设置一个对比的数，flag，从1开始，每次右移一位，每次与原数字做与运算。
  • 优点：简单，且能解决负数的情况。
1
2
3
4
5
6
7
8
9
10
11
def NumberOfOne(n):
    count = 0
    flag = 1
    i = 0
    while flag and i < 32:
        if n & flag:
            count += 1
        flag = flag << 1
#         print flag, count
        i += 1
    return count
1
NumberOfOne(5)
1
2

NO.16 数值的整数次方

  • 问题描述：实现函数double Power（double base, int exponent），求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
  • 思路：当$n$为奇数：$x^n=(x^2)^{n/2}×x$；当$n$为偶数：$x^n=(x^2)^{n/2}$
  • 优点：节省乘法的次数。
  • 时间复杂度：$O(logn)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def Power(x, n):
    """x^n"""
    if x == 0 and n < 0:  # 0的负数次方不合理
        return 0
    abs_n = abs(n)
    res = PowerWithAbsExponent(x, abs_n)
    if n < 0:
        res = 1.0/res
    return res

def PowerWithAbsExponent(x, abs_n):
    if abs_n == 0:
        return 1
    if abs_n == 1:
        return x
    res = PowerWithAbsExponent(x, abs_n>>1)
    res *= res
    if abs_n & 1 == 1:
        res *= x
    return res
1
Power(12, 3)
1
1728

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

  • 问题描述：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。
  • 陷阱：这个问题属于大数类的问题，即给定n过大，n位的整数肯定不能用长整型保存。
1
2
3
4
5
6
# 错误示范
def Print1ToMaxOfNDigitsWrong(n):
    end = pow(10, n)
    print(end)
#     for i in range(1, end):
#         print(i, end=" ")
1
Print1ToMaxOfNDigitsWrong(100)
1
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

但是这种题好像对python没有影响。。。

  • 思路：转换成全排列问题，使用递归完美解决。(有点像深度优先遍历)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def Print1ToMaxOfNDigits(n):
    if n <= 0:
        return 
    number = ["0" for _ in range(n)]
    for i in range(10):
        number[0] = str(i)
        Print1ToMaxOfNDigitsRecursively(number, n, 0)
        
def Print1ToMaxOfNDigitsRecursively(number, l, index):
    # 已经遍历到最后一位数字，则打印出该数字
    if index == l - 1:
        printNumber(number)
        return
    # 否则继续深度优先遍历
    for i in range(10):
        number[index + 1] = str(i)
        Print1ToMaxOfNDigitsRecursively(number, l, index + 1)
        
def printNumber(number):
    done = False
    while number[0] == "0" and len(number) > 1:
        number = number[1:]
    print("".join(number), end=" ")
1
Print1ToMaxOfNDigits(2)
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

NO.18 在O（1）时间删除链表结点

  • 问题描述：给定单向链表的头指针和一个结点指针，定义一个函数在$O(1)$时间删除该结点
  • 思路：普通思路：从头遍历，找到当前节点的前一个节点，将这个节点指向当前节点的下一个节点，时间复杂度$O(n)$。优秀思路：将当前节点的写一个节点的值拷贝到当前节点，删除下一个节点。
  • 陷阱：如果要删除的是最后一个节点，解决方案需要调整。
  • 优点：时间复杂度低。
  • 缺点：这种方式采用拷贝的形式，改变了之前节点的对象。
  • 时间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def deleteNode(list_head, node_to_delete):
    """删除链表中的指定节点。
    注意，这里判断两个节点是否相同的方式仅仅是判断两个节点的值是否相同。"""
    if list_head is None or node_to_delete is None:
        return list_head
    # 如果要删除的是最后一个节点，则需要从头开始找
    if node_to_delete.next is None:
        if node_to_delete.val == list_head.val:
            del node_to_delete, list_head
            list_head = None
            return list_head
        cur_node = list_head
        while cur_node.next is not None and cur_node.next.val != node_to_delete.val:
            cur_node = cur_node.next
        if cur_node.next is not None and cur_node.next.val == node_to_delete.val:
            cur_node.next = None
            del node_to_delete
        return list_head
    # 将当前节点的写一个节点的值拷贝到当前节点，删除下一个节点
    else:
        next_node = node_to_delete.next
        node_to_delete.next = next_node.next
        node_to_delete.val = next_node.val
        del next_node
        return list_head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n1 = ListNode(1)
new_head = deleteNode(n1, n1)
print_list(new_head)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
new_head = deleteNode(n1, n3)
print_list(new_head)
new_head = deleteNode(new_head, n5)
print_list(new_head)
1
2
3
This node list is empty!
1 2 4 5
1 2 4
1
2
3
new_node = ListNode(3)
new_node.next = n3.next
new_node == n3
1
False

NO.19 正则表达式匹配

  • 问题描述：请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式a.a和ab*ac*a匹配，但是与aa.a和ab*a均不匹配。
  • 思路：递归、非确定有限状态机。
  • 优点：思路清晰。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def match(string, pattern):
    if len(string) == 0 or len(pattern) == 0:
        return False
    return matchCore(string, pattern)

def matchCore(string, pattern):
    # 完整匹配结束
    if len(string) == 0 and len(pattern) == 0:
        return True
    # 模板匹配结束，还有剩余的字符串
    if len(string) != 0 and len(pattern) == 0:
        return False
    # 字符串匹配结束，只有pattern的长度既是2的整数倍，且是"a*b*"之类才可以匹配
    if len(string) == 0:
        if pattern[-1] != "*" or len(pattern) % 2 != 0:
            return False
        if len(pattern) == 2:
            return True
        return matchCore(string, pattern[2:])
        
    # 前两个字符没有*的情况
    if len(pattern) < 2 or pattern[1] != "*":
        if pattern[0] == string[0] or pattern[0] == ".":
            return matchCore(string[1:], pattern[1:])
        else:
            return False
    # 第二个字符是*的情况
    else:
        # 第一个字符也匹配上
        if pattern[0] == string[0] or (pattern[0] == "." and len(string) > 0):
            # 丢掉第一个匹配的字符，进入下一个状态
            if matchCore(string[1:], pattern[2:]):  
                return True
            # 继续保留第一个匹配的字符，进入下一个状态
            if matchCore(string, pattern[2:]):  
                return True
            # 或者继续停留在这个状态
            if matchCore(string[1:], pattern):
                return True
            return False
        else:
            # 第一个字符匹配不上，必须进入下一个状态
            return matchCore(string, pattern[2:])
1
2
3
4
5
print(match("aaa", "a.a"))
print(match("aaa", "ab*ac*a"))
print(match("aaa", "aa.a"))
print(match("aaa", "ab*a"))
print(match("a", "ab*a*"))
1
2
3
4
5
True
True
False
False
True

NO.20 表示数值的字符串

  • 问题描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
  • 思路：表示数字的字符串遵循模式A[.[B]][e|EC]或者.B[e|EC]，其中A为数值的整数部分，B紧跟着小数点为数值的小数部分，C紧跟e或者E是数值的指数部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def scanUnsignedInteger(string):
    if len(string) == 0:
        return False, 0
    i = 0
    while i < len(string) and string[i].isdigit():
        i += 1
    return i > 0, i

def scanInteger(string):
    if len(string) == 0:
        return False, 0
    if string[0] == "-" or string[0] == "+":
        found, index = scanUnsignedInteger(string[1:])
        return found, index + 1
    else:
        return scanUnsignedInteger(string)

def isNumeric(string):
    if len(string) == 0:
        return False
    found_1 = found_2 = found_3 = False
    found_1, index = scanInteger(string)
    string = string[index:]
    is_numeric = found_1
    
    # 如果出现'.'，则接下来是小数部分
    if len(string) > 0 and string[0] == ".":
        string = string[1:]
        found_2, index = scanUnsignedInteger(string)
        string = string[index:]
        # 使用'or'的原因：小数点前面或者后面都可以没有数字
        is_numeric = found_2 or is_numeric
        
    # 如果出现'e'或者'E'，则接下来的数字是指数部分
    if len(string) > 0 and (string[0] == 'e' or string[0] == 'E'):
        string = string[1:]
        found_3, index = scanInteger(string)
        string = string[index:]
        # 使用'and'的原因：e的前面或者后面没有数字，都不合法
        is_numeric = found_3 and is_numeric
    
#     print("found_1: ", found_1, ",found_2: ", found_2, ",found_3: ", found_3, "is_numeric: ", is_numeric)
    return is_numeric and len(string) == 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 正例
print(isNumeric("+100"))
print(isNumeric("123"))
print(isNumeric("5e2"))
print(isNumeric("-123"))
print(isNumeric("3.1416"))
print(isNumeric("-1E-16"))
print()
# 反例
print(isNumeric("12e"))
print(isNumeric("1a3.14"))
print(isNumeric("1.2.3"))
print(isNumeric("+-5"))
print(isNumeric("12e+4.3"))
1
2
3
4
5
6
7
8
9
10
11
12
True
True
True
True
True
True

False
False
False
False
False

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

  • 问题描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
  • 思路：看到这题想到了快排的partition，只不过一个标准是小的在前，大的在后面。提示：双指针。
  • 优点：可扩展性高。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def Reorder(data, reorder_func):
    l = len(data)
    if l == 0 or reorder_func is None:
        return
    s = 0
    e = l - 1
    
    while s < e:
        while s < e and not reorder_func(data[s]):
            s += 1
        while s < e and reorder_func(data[e]):
            e -= 1
        if s < e:
            data[s], data[e] = data[e], data[s]

def isEven(n):
    return (n % 2) == 0

def ReorderOddEven(data):
    Reorder(data, isEven)
1
2
3
test_data = [1,2,3,4,5]
ReorderOddEven(test_data)
print(test_data)
1
[1, 5, 3, 4, 2]

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

  • 问题描述：输入一个链表，输出该链表中倒数第k个结点。为符合计数习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。如：一个链表有6个节点，从头节点开始，它们的值一次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
  • 思路：两个指针。
  • 陷阱：如果链表长度小于k会不会有问题？
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findKthToTail(head_node, k):
    if head_node is None or k <= 0:
        return False, -1
    ahead = head_node
    behind = head_node
    for i in range(k - 1):
        if ahead.next != None:
            ahead = ahead.next
        else:
            return False, -1
    while ahead.next is not None:
        ahead = ahead.next
        behind = behind.next
    return True, behind.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
print(findKthToTail(n1, 3))
print(findKthToTail(n1, 0))
print(findKthToTail(n1, 7))
1
2
3
(True, 4)
(False, -1)
(False, -1)

NO.23 链表中环的入口节点

  • 问题描述：如果一个链表中包含环，请找出该链表的环的入口结点。如：在1->2->3->4->5->6->3的链表中，包含一个环，环的入口节点是3。
  • 思路：先确定环的长度$n$，再确定入口位置（用$k$表示从起点到入口的距离）。1：使用两个速度不一样的指针取遍历，当二者相遇时，说明被套圈了。套圈说明差距是$n$的整数倍，不能保证一定是$n$；但套圈还说明了相遇的点一定在环中，在这个节点上重新开始遍历，回到本身时，遍历次数即是长度。2：使用同样速度一前一后的两个指针，前面的指针先走$n$步，然后后面的指针和前面的指针一起走，当二者第一次相遇时，慢指针正好走了$k$步，快指针走了$n+k$步，都在环入口处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def meetingNode(headNode):
    """在存在环的前提下，找到一快一慢两个指针相遇的节点。"""
    if headNode is None:
        return
    slow = headNode.next
    if slow is None:
        return 
    fast = slow.next
    while fast is not None and slow is not None:
        if fast == slow:
            return fast
        slow = slow.next
        fast = fast.next
        if fast is not None:
            fast = fast.next
    return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def entryNodeOfLoop(headNode):
    meeting_node = MeetingNode(headNode)
    if meeting_node is None:
        return
    
    # 计算环的长度
    n = 1
    node = meeting_node
    while node.next != meeting_node:
        node = node.next
        n += 1
        
    # 先移动前面的指针n次
    ahead = headNode
    for i in range(n):
        ahead = ahead.next
        
    # 再同时移动两个指针，直到相遇
    behind = headNode
    while ahead != behind:
        ahead = ahead.next
        behind = behind.next
    return ahead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
n6.next = n3
entry = entryNodeOfLoop(n1)
print(entry.val)
1
3

NO.24 反转链表

  • 问题描述：输入一个链表的头节点，反转链表并输出反转链表的头节点。
  • 思路：递归。
  • 优点：思路简单。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
def reverseListRecursive(headNode):
    if headNode is None:
        return None, None
    if headNode.next is None:
        return headNode, headNode
    new_tail, new_head = reverseListRecursive(headNode.next)
    new_tail.next = headNode
    headNode.next = None
    return headNode, new_head
1
2
3
4
5
6
7
8
9
10
11
12
13
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
new_tail, new_head = reverseListRecursive(n1)
print_list(new_head)
1
6 5 4 3 2 1
  • 思路：也可以直接正向遍历。
  • 优点：运行开销没有递归大。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def reverseList(headNode):
    if headNode is None:
        return 
    if headNode.next is None:
        return headNode
    prevNode = headNode
    node = headNode.next
    headNode.next = None
    while node.next != None:
        nextNode = node.next
        node.next = prevNode
        prevNode = node
        node = nextNode
    node.next = prevNode
    return node
1
2
3
4
5
6
7
8
9
10
11
12
13
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
new_head = reverseList(n1)
print_list(new_head)
1
6 5 4 3 2 1

NO.25 合并两个排序的链表

  • 问题描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调递增规则。如：链表1：1->3->5；链表2：2->4->6；合并后为：1->2->3->4->5->6。
  • 思路：递归。
  • 优点：思路清晰。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
def mergeList(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.val < head2.val:
        new_head = mergeList(head1.next, head2)
        head1.next = new_head
        return head1
    else:
        new_head = mergeList(head1, head2.next)
        head2.next = new_head
        return head2
1
2
3
4
5
6
7
8
9
10
11
12
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n3
n3.next = n5
n2.next = n4
n4.next = n6
new_head = mergeList(n1, n2)
print_list(new_head)
1
1 2 3 4 5 6

NO.26 树的子结构

  • 问题描述：输入两棵二叉树A和B，判断B是不是A的子结构。
  • 思路：分成两步：1.在A中找到和B的根节点的值一样的节点R；2.判断A中以R为根节点的子树是不是包含和B一样的结构。
  • 时间复杂度：$O(n×m)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def hasSubtree(root1, root2):
    res = False
    if root1 is not None and root2 is not None:
        if root1.val == root2.val:
            res = doesTree1HasTree2(root1, root2)
        if not res:
            res = hasSubtree(root1.left, root2)
        if not res:
            res = hasSubtree(root1.right, root2)
    return res

def doesTree1HasTree2(root1, root2):
    if root2 is None:
        return True
    if root1 is None:
        return False
    if root1.val != root2.val:
        return False
    return doesTree1HasTree2(root1.left, root2.left) and doesTree1HasTree2(root1.right, root2.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n1 = TreeNode(8)
n2 = TreeNode(8)
n3 = TreeNode(7)
n4 = TreeNode(9)
n5 = TreeNode(2)
n6 = TreeNode(4)
n7 = TreeNode(7)

n8 = TreeNode(8)
n9 = TreeNode(9)
n10 = TreeNode(2)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n5.left = n6
n6.right = n7

print_tree(n1)

n8.left = n9
n8.right = n10

print_tree(n8)

hasSubtree(n1, n8)
1
2
3
4
8 8 7 9 2 4 7
8 9 2

True

NO.27 二叉树的镜像

  • 问题描述：输入一棵二叉树，输出它的镜像。
  • 思路：递归。
  • 优点：思路清晰。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
def mirrorRecursively(root):
    if root is None:
        return
    root.right, root.left = root.left, root.right
    mirrorRecursively(root.right)
    mirrorRecursively(root.left)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)

mirrorRecursively(n1)

print_tree(n1)
1
2
8 6 10 5 7 9 11
8 10 6 11 9 7 5

NO.28 对称的二叉树

  • 问题描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
  • 思路：递归。
  • 优点：思路清晰。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
def isTreeSymmetrical(root):
    return isTwoTreeSymmetrical(root, root)

def isTwoTreeSymmetrical(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    if root1.val != root2.val:
        return False
    return isTwoTreeSymmetrical(root1.left, root2.right) and isTwoTreeSymmetrical(root1.right, root2.left)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(6)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(7)
n7 = TreeNode(5)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)
print(isTreeSymmetrical(n1))

n3.val = 9

print_tree(n1)
print(isTreeSymmetrical(n1))

n3.val = 6
n3.right = None

print_tree(n1)
print(isTreeSymmetrical(n1))
1
2
3
4
5
6
8 6 6 5 7 7 5
True
8 6 9 5 7 7 5
False
8 6 6 5 7 7
False

NO.29 顺时针打印矩阵

  • 问题描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
  • 思路：此题没有复杂的思路，只需需注意每一步的条件判断，简单但易错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def PrintMatrixClockwisely(numbers, columns, rows):
    if not numbers or columns <= 0 or rows <= 0:
        return
    start = 0
    while columns > start * 2 and rows > start * 2:
        PrintMatrixInCircle(numbers, columns, rows, start);
        start += 1

def PrintMatrixInCircle(numbers, columns, rows, start):
    endX = columns - 1 - start
    endY = rows - 1 - start

    # 从做到右打印一行
    for i in range(start, endX+1):
        number = numbers[start][i]
        print(number, end=" ")
    # 从上到下打印一行
    if start < endY:
        for i in range(start+1, endY+1):
            number = numbers[i][endX]
            print(number, end=" ")
    # 从右到左打印一行
    if start < endX and start < endY:
        for i in range(endX-1, start-1, -1):
            number = numbers[endY][i]
            print(number, end=" ")
    # 从下到上打印一行
    if start < endX and start < endY - 1:
        for i in range(endY-1, start, -1):
            number = numbers[i][start]
            print(number, end=" ")
1
2
3
numbers = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
c = r = 4
PrintMatrixClockwisely(numbers, c, r)
1
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

NO.30 包含min函数的栈

  • 问题描述：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。
  • 思路：设置辅助栈，和当前栈保持一致的形状，保存栈在某状态下的最小值。
  • 优点：空间换时间。
  • 时间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MinStack:
    def __init__(self):
        self.min_stack = []
        self.data_stack = []
    def push(self, value):
        if len(self.min_stack) == 0 or self.min_stack[-1] > value:
            self.min_stack.append(value)
        else:
            self.min_stack.append(self.min_stack[-1])
        self.data_stack.append(value)
    def pop(self):
        assert len(self.min_stack) > 0 and len(self.data_stack) > 0
        self.min_stack.pop()
        return self.data_stack.pop()
    def min_val(self):
        assert len(self.min_stack) > 0 and len(self.data_stack) > 0
        return self.min_stack[-1]
1
2
3
4
5
6
7
ms = MinStack()
ms.push(3)
ms.push(2)
ms.push(1)
print(ms.min_val())
ms.pop()
print(ms.min_val())
1
2
1
2

NO.31 栈的压入、弹出序列

  • 问题描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
  • 思路：使用一个栈模拟压入和弹出的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def IsPopOrder(pushV, popV):
    stack = []
    i = 0
    for one_pop in popV:
        if len(stack) >0 and stack[-1] == one_pop:
            stack.pop()
        else:
            while i < len(pushV) and one_pop != pushV[i]:
                stack.append(pushV[i])
                i += 1
            if i >= len(pushV):
                return False
            i += 1
    return True
1
2
3
4
5
pushV = [1,2,3,4,5]
# popV = [5,4,3,2,1]
# popV = [2,5,4,3,1]
popV = [4,3,5,1,2]
IsPopOrder(pushV, popV)
1
False

NO.32 从上到下打印二叉树

  • 问题描述：从上倒下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
  • 思路：使用一个队列。
  • 扩展：广度优先遍历一个有向图也是基于队列实现，但广度优先遍历一般必须要查重，树则没有这个问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def printFromTopToBottom(root):
    traverse = []
    if root is None:
        print("This is an empty tree!")
        return 
    queue = [root]
    while len(queue) > 0:
        node = queue.pop()
        traverse.append(node.val)
        if node.left:
            queue.insert(0, node.left)
        if node.right:
            queue.insert(0, node.right)
    print(" ".join([str(one) for one in traverse]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

printFromTopToBottom(n1)
1
8 6 10 5 7 9 11
  • 变体：分行从上到下打印二叉树
  • 问题描述：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

思路：增加一个行结束的标识符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def printFromTopToBottomByLine(root):
    traverse = []
    line_end_token = "<END>"
    if root is None:
        print("This is an empty tree!")
        return 
    queue = [line_end_token, root]
    while len(queue) > 0:
#         print(traverse)
        node = queue.pop()
        if node == line_end_token:
            print(" ".join([str(one) for one in traverse]))
            traverse = []
            continue
        traverse.append(node.val)
        if node.left:
            queue.insert(0, node.left)
        if node.right:
            queue.insert(0, node.right)
        if len(queue) > 0 and queue[-1] == line_end_token:
            queue.insert(0, line_end_token)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

printFromTopToBottomByLine(n1)
1
2
3
8
6 10
5 7 9 11
  • 变体：之字形打印二叉树
  • 问题描述：请实现一个函数按照之字形顺序打印二叉树。即第一行按照从左到右的顺序打印，第二行按照从右到左的顺序打印，第三行按照从左到右的顺序打印，以此类推。
  • 思路：用两个栈实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def printFromTopToBottomByLineWithZHI(root):
    """用两个栈实现之字形层次遍历"""
    traverse = []
    if root is None:
        print("This is an empty tree!")
        return 
    cur_stack, son_stack = [root], []
    is_left_to_right = True
    while len(cur_stack) > 0:
        node = cur_stack.pop()
        traverse.append(node.val)
        if is_left_to_right:
            if node.left:
                son_stack.append(node.left)
            if node.right:
                son_stack.append(node.right) 
        else:
            if node.right:
                son_stack.append(node.right) 
            if node.left:
                son_stack.append(node.left)
        if len(cur_stack) == 0:
            print(" ".join([str(one) for one in traverse]))
            traverse = []
            cur_stack, son_stack = son_stack, []
            is_left_to_right = not is_left_to_right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

printFromTopToBottomByLineWithZHI(n1)
1
2
3
8
10 6
5 7 9 11

NO.33 二叉搜索树的后序遍历序列

  • 问题描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
  • 思路：后序遍历即左右根，搜索树满足：左<根<右。递归地判断是否满足条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def VarifySequenceOfBST(seq):
    return vs_core(seq, 0, len(seq) - 1)
    
def vs_core(seq, s, e):
    if len(seq) == 0:
        return False
    if len(seq) == 1:
        return True
    root = seq[e]
    # 判断左子树是否小于根
    i = s
    while i < e and seq[i] < root:
        i += 1
    if i == e:
        return True
    # 记录左子树的最后一个点的下标
    left_e = i - 1
    # 判断右子树是否大于根
    while i < e:
        if seq[i] < root:
            return False
        i += 1
    # 递归判断
    is_left = True
    is_right = True
    if left_e >= s:
        is_left = vs_core(seq, s, left_e)
    if left_e + 1 < e:
        is_right = vs_core(seq, left_e+1, e-1)
    return is_left and is_right
1
2
3
# seq = [5,7,6,9,11,10,8]
seq = [7,4,6,5]
VarifySequenceOfBST(seq)
1
False

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

  • 问题描述：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
  • 思路：这道题是树状搜索最基础的原型。也可以理解成是回溯法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def FindPath(root, exp_sum):
    if not root:
        return
    path = []
    cur_sum = 0
    FindPathCore(root, exp_sum, path, cur_sum)
    
def FindPathCore(root, exp_sum, path, cur_sum):
    cur_sum += root.val
    path.append(root.val)
    is_leaf = root.left is None and root.right is None
    if cur_sum == exp_sum and is_leaf:
        print(" ".join(map(str, path)))
    if root.left is not None:
        FindPathCore(root.left, exp_sum, path, cur_sum)
    if root.right is not None:
        FindPathCore(root.right, exp_sum, path, cur_sum)
    path.pop()
1
2
3
4
5
6
7
8
9
10
n1 = TreeNode(10)
n2 = TreeNode(5)
n3 = TreeNode(12)
n4 = TreeNode(4)
n5 = TreeNode(7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
FindPath(n1, 22)
1
2
10 5 7
10 12

NO.35 复杂链表的复制

  • 问题描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空。节点使用RandomListNode类）
  • 思路：普通：如果一个一个取复制，那么特殊指针必须遍历到才能复制，因此时间复杂度太高，是$O(n^2)$。优秀：1.将链表复制为AA’BB’这种形式；2.将A’B’之间的链接从AB的链表上复制过来；3.再将两个链表分离。
  • 优点：时间复杂度低。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def cloneCompleteNodes(headNode):
    cloneNodes(headNode)
    connectSiblingNodes(headNode)
    return reconnectNodes(headNode)

def cloneNodes(headNode):
    """将链表复制为AA'BB'这种形式"""
    curNode = headNode
    while curNode is not None:
        copyNode = RandomListNode(curNode.val)
        copyNode.next = curNode.next
        curNode.next = copyNode
        curNode = copyNode.next
    
def connectSiblingNodes(headNode):
    """将A'B'之间的链接从AB的链表上复制过来"""
    curNode = headNode
    while curNode is not None:
        copyNode = curNode.next
        if curNode.random is not None:
            copyNode.random = curNode.random.next
        curNode = copyNode.next
        
def reconnectNodes(headNode):
    """再将两个链表分离"""
    curNode = headNode
    if curNode is not None:
        cloneHead = copyNode = curNode.next
        curNode.next = copyNode.next
        curNode = curNode.next
    while curNode is not None:
        copyNode.next = curNode.next
        copyNode = copyNode.next
        curNode.next = copyNode.next
        curNode = curNode.next
    return cloneHead
1
2
3
4
5
6
7
8
9
10
11
12
n1 = RandomListNode(1)
n2 = RandomListNode(2)
n3 = RandomListNode(3)

n1.next = n2
n2.next = n3
n1.random = n3
n2.random = n1

print_random_list(n1)
n4 = cloneCompleteNodes(n1)
print_random_list(n4)
1
2
3
4
5
6
val: 1, val of next: 2, val of random: 3 
val: 2, val of next: 3, val of random: 1 
val: 3, val of next: None, val of random: None 
val: 1, val of next: 2, val of random: 3 
val: 2, val of next: 3, val of random: 1 
val: 3, val of next: None, val of random: None

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

  • 问题描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
  • 思路：二叉搜索树有一个特性：中序遍历二叉搜索树是排序好的数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def Convert(root):
    # last_node_in_list指向已经转换好的链表的最后一个节点（值最大的节点）
    # 放在list里实现引用传递
    last_node_in_list = [None]
    ConvertNode(root, last_node_in_list)
    # 找到头节点，并返回
    head_node_in_list = last_node_in_list[0]
    while head_node_in_list is not None and head_node_in_list.left is not None:
        head_node_in_list = head_node_in_list.left
    return head_node_in_list

def ConvertNode(root, last_node_in_list):
    if root is None:
        return
    cur = root
    if cur.left is not None:
        ConvertNode(cur.left, last_node_in_list)
    cur.left = last_node_in_list[0]
    if last_node_in_list[0] is not None:
        last_node_in_list[0].right = cur
    last_node_in_list[0] = cur
    if cur.right is not None:
        ConvertNode(cur.right, last_node_in_list)
1
2
3
4
5
6
7
8
9
10
11
12
13
n1 = TreeNode(10)
n2 = TreeNode(5)
n3 = TreeNode(12)
n4 = TreeNode(4)
n5 = TreeNode(7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
head = Convert(n1)
while head:
    print(head.val, end=" ")
    head = head.right
.output n
1
2
3
4
5
6
7
[
 {
  "name": "stdout",
  "output_type": "stream",
  "text": "4 5 7 10 12 "
 }
]

NO.37 序列化二叉树

  • 问题描述：请实现两个函数，分别用来序列化和反序列化二叉树。

思路：序列化：用前序遍历的顺序表示，并用一个特殊的符号如$表示空指针。

1
2
3
4
5
6
7
def serialize(root, s):
    if root is None:
        return s + "$,"
    s = s + str(root.val) + ","
    s = serialize(root.left, s)
    s = serialize(root.right, s)
    return s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)

n1.left = n2
n1.right = n3
n2.left = n4
n3.left = n5
n3.right = n6

print(serialize(n1, ""))
1
1,2,4,$,$,$,3,5,$,$,6,$,$,
1
2
3
4
5
6
7
8
9
10
11
12
def deserialize(s):
    return deserialize_core(s.split(","))
    
def deserialize_core(s):
    if len(s) == 0:
        return None, ""
    if s[0] == "$":
        return None, s[1:]
    node = TreeNode(s[0])
    node.left, s = deserialize_core(s[1:])
    node.right, s = deserialize_core(s)
    return node, s
1
2
3
4
test_str = "1,2,4,$,$,$,3,5,$,$,6,$,$,"
root, s = deserialize(test_str)
print(s)
print_tree(root)
1
2
['']
1 2 3 4 5 6

NO.38 字符串的排列

  • 问题描述：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
  • 思路：固定第一个，递归地求后面所有组合，然后将第一个字符和后面的元素互换，再做递归。
  • 空间复杂度：没有额外的浪费。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def Permutation(ss):
    res = []
    if not ss or len(ss) == 0:
        return res
    set_ = set()
    ss = list(ss)
    fun(set_, ss, 0)
    for one in set_:
        res.append(one)
    res = sorted(res)
    return re

def fun(set_, ss, k):
    if k == len(ss):
        set_.add(''.join(ss))
        return
    for i in range(k, len(ss)):
        swap(ss, i, k)
        fun(set_, ss, k + 1)
        swap(ss, i, k)

def swap(ss, i, j):
    if i != j:
        t = ss[i]
        ss[i] = ss[j]
        ss[j] = t
1
Permutation("abc")
1
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
1
2
3
4
5
6
7
8
9
10
11
12
13
def Permutation2(s):
    """回溯"""
    space = list(s)
    res = []
    PermutationCore("", space, res)
    return res
    
def PermutationCore(cur_str, space, res): 
    for one_char in space:
        next_space = [one for one in space if one != one_char ]
        if len(next_space) == 0:
            res.append(cur_str + one_char)
        PermutationCore(cur_str + one_char, next_space, res)
1
Permutation2("abc")
1
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

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

  • 问题描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
  • 思路：在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。
  • 优点：先排序的时间复杂度是$O(nlogn)$；这种方法的时间复杂度是$O(n)$，不需要改变原数组，额外的空间复杂度也是常数。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 解法1

def MoreThanHalfNum1(numbers, length):
    result = numbers[0]
    times = 1
    for i in range(length):
        if times == 0:
            result = numbers[i]
            times = 1
        elif numbers[i] == result:
            times += 1
        else:
            times -= 1
    return result;
1
2
l = [5,2,1,5,5,3,5,4,5]
MoreThanHalfNum1(l, 9)
1
5
  • 思路：先做一个转化：数组中有一个数字出现的次数超过一半，那么排序之后，位于中间的数字，一定是这个数字，也就是中位数。考虑到快排的partition会返回调整完顺序后pivot的下标，如果返回的下标等于$n/2$，则说明是中位数就是这个数
  • 优点：利用了partition函数的一个特性：返回的piviot的下标和最终排序好的数组中的下标是一样的。所以如果partion返回$n/2$，那么这个数一定是中位数。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def partition(data, s, e):
    if s >= e:
        return 
    small = s - 1
    pivot_index = e
    pivot_value = data[pivot_index]
    for i in range(s, e):
        if data[i] < pivot_value:
            small += 1
            if small != i:
                data[small], data[i] = data[i], data[small]
    small += 1
    if small != e:
        data[small], data[e] = data[e], data[small]
    return small
1
2
3
data = [2, 4, 5, 1, 9, 3]
print(partition(data, 0, 5))
print(data)
1
2
2
[2, 1, 3, 4, 9, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 解法2

def MoreThanHalfNum2(numbers, length):
    mid = length // 2
    s = 0
    e = length - 1
    index = partrition(numbers, s, e)
    while index != mid:
        if index > mid:
            e = index - 1
            index = partition(numbers, s, e)
        else:
            s = index + 1
            index = partition(numbers, s, e)
    res = numbers[mid]
    return res
1
2
l = [5,2,1,5,5,3,5,4,5]
MoreThanHalfNum2(l, 9)
1
5

NO.40 最小的k个数

  • 问题描述：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
  • 思路：类似上一题，使用partition函数，直到返回的下标是k为止。
  • 优点：如果先排序，时间复杂度是$nlog(n)$，这里时间复杂度是$O(n)$。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 解法1

def getLeastNumbers1(data, k):
    if len(data) <= k:
        return data
    s = 0
    e = len(data) - 1
    index = partition(data, s, e)
    while index != k - 1:
        if index > k - 1:
            e = index - 1
            index = partition(data, s, e)
        else:
            s = index + 1
            index = partition(data, s, e)
    return data[:k]
1
2
data = [10, 8, 2, 3, 4, 5, 7, 1, 6]
getLeastNumbers1(data, 4)
1
[1, 2, 3, 4]
  • 思路：使用一个数据结构（这里选择大顶堆），在遍历数据的时候保留最小的k个数。每次要获取k个数中最大的数，所以用大顶堆。大顶堆在插入和删除数据时的时间复杂度都是$O(logk)$。
  • 优点：更能应对海量数据的情况。
  • 时间复杂度：$O(nlogk)$

python自带heapq支持小顶堆。

核心文档，摘自https://docs.python.org/3.6/library/heapq.html 

1
2
3
4
5
6
7
8
9
10
11
12
13
To create a heap,
use a list initialized to [], or you can transform a populated list into a heap
via function heapify().

The following functions are provided:
heapq.heappush(heap, item)
Push the value item onto the heap, maintaining the
heap invariant.

heapq.heappop(heap)
Pop and return the smallest item from the
heap, maintaining the heap invariant. If the heap is empty, IndexError is
raised. To access the smallest item without popping it, use heap[0].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 解法2
import heapq
def getLeastNumbers2(data, k):
    h = []
    for one in data:
        if len(h) < k:
            # heapq默认是小顶堆的操作，将元素加上符号使其变成大顶堆。
            heapq.heappush(h, -one)
        else:
            v = heapq.heappop(h)
            if -one > v:
                heapq.heappush(h, -one)
            else:
                heapq.heappush(h, v)
    return [-one for one in h]
1
2
data = [10, 8, 2, 3, 4, 5, 7, 1, 6]
getLeastNumbers2(data, 4)
1
[4, 3, 2, 1]

NO.41 数据流中的中位数

  • 问题描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
  • 思路：数据流意味着需要考虑新的数据进入时，数据结构的插入的操作。
数据结构 插入的时间复杂度 得到中位数的时间复杂度 得到中位数的思路
没有排序的数组 $O(1)$ $O(n)$ 参考no.39题，使用partition
排序的数组 $O(n)$ $O(1)$ 直接通过下标获取
排序的链表 $O(n)$ $O(1)$ 定义指向中位数的指针
二叉搜索树 平均$O(logn)$，最差$O(n)$ 平均$O(logn)$，最差$O(n)$ 节点中添加一个表示子树节点个数的字段
平衡二叉搜索树AVL 平均$O(logn)$ $O(1)$ 将平衡因子从左右子树的高度差修改成左右子树的节点数目差
最大堆 $O(logn)$ $O(1)$ 用一个最大堆和一个最小堆实现

详细：保证数据平均分配到两个堆中，二者数目差不能超过1。在总数是偶数时，插入最小堆，否则插入最大堆。另外需要保证最大堆中的所有数据都小于最小堆中的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import heapq

class DynamicArray:
    def __init__(self):
        self.max_heap = []
        self.min_heap = []   
        
    def insert(self, val):
        # 总数是偶数时，插入最小堆
        if (len(self.max_heap) + len(self.min_heap)) % 2 == 0:
            heapq.heappush(self.min_heap, val)
            self.check()
        # 否则插入最大堆
        else:
            heapq.heappush(self.max_heap, -val)
            self.check()
            
    def check(self):
        # 如果最小堆的最小值小于最大堆的最大值，则需要交换二者
        if len(self.min_heap) > 0 and len(self.max_heap) > 0 and self.min_heap[0] < -self.max_heap[0]:
            min_one = heapq.heappop(self.min_heap)
            max_one = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, max_one)
            heapq.heappush(self.max_heap, -min_one)
            
    def get_median(self):
        size = len(self.max_heap) + len(self.min_heap)
        if size == 0:
            print("No numbers are available!")
            exit(-1)
        median = 0
        if size % 2 == 1:
            median = self.min_heap[0]
        else:
            median = (self.min_heap[0] + (-self.max_heap[0])) / 2
#         print(self.min_heap, self.max_heap)
        return median
1
2
3
4
5
da = DynamicArray()
data = [3, 2, 1, 5, 7, 8, 9, 10]
for i, one in enumerate(data):
    da.insert(one)
    print(data[:i+1], da.get_median())
1
2
3
4
5
6
7
8
[3] 3
[3, 2] 2.5
[3, 2, 1] 2
[3, 2, 1, 5] 2.5
[3, 2, 1, 5, 7] 3
[3, 2, 1, 5, 7, 8] 4.0
[3, 2, 1, 5, 7, 8, 9] 5
[3, 2, 1, 5, 7, 8, 9, 10] 6.0

NO.42 连续子数组的最大和

  • 问题描述：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。
  • 思路：$$f(i) = \left{\begin{matrix}
    Data[i] \qquad i=0 或者 f(i-1) \leq 0 \
    f(i-1)+Data[i] \qquad i \neq 0 或者 f(i-1) \gt 0
    \end{matrix}\right.$$
    其中$f(i)$代表以第i个数字结尾的子数组的最大和。最终结果即$\underset{i}{max}[f(i)]$。
  • 优点：时间复杂度低。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findGreatestSumOfSubArray(data):
    if len(data) == 0:
        print("Data is empty!!!")
        exit(-1)
    if len(data) == 1:
        return data[0]
    max_sum_end_with_i = [0 for _ in range(len(data))]
    max_sum_end_with_i[0] = data[0] 
    for i in range(1, len(data)):
        if max_sum_end_with_i[i - 1] <= 0:
            max_sum_end_with_i[i] = data[i]
        else:
            max_sum_end_with_i[i] = data[i] + max_sum_end_with_i[i-1]
    print(max_sum_end_with_i)
    return max(max_sum_end_with_i)
1
2
test_data = [1, -2, 3, 10, -4, 7, 2, -5]
print(findGreatestSumOfSubArray(test_data))
1
2
[1, -1, 3, 13, 9, 16, 18, 13]
18

NO.43 从1到n整数中1出现的次数

  • 问题描述：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1
    的数字有1，10，11和12，1一共出现了5次。
  • 思路：简单的可以计算每一个数中1出现的个数，再累加，这种方案的时间复杂度是$nlog(n)$。较优方案：从最高位开始统计1的个数，再递归。具体：将这个问题分解成3部分：1.最高位中1出现的次数；2.除了最高位以后，其他位中1出现的个数。这部分又分成两部分：2.1.最高位是小于当前最高位的时候，其他位数中，1的个数（排列组合）；2.2.最高位是当前最高位时，其他位数中1的个数（递归）。举例：求1到21345中1出现的次数。1.最高位中1出现了10000次；2.最高位是0或者1时，其他位中1出现的次数。选择后四位中其中一位是1，其他三位任意，是$2×(5-1)×10^3=1000$；3.2000021345除第一位之外的数位中1的数目，等同于11345中1的数目，使用递归。
  • 优点：递归的次数和位数相同，时间复杂度是$log(n)$。
  • 时间复杂度：$log(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def numberOf1Between1AndN(n):
    if n <= 0:
        return 0
    return numberOf1(str(n))
    
def numberOf1(str_n):
    if len(str_n) <= 0 or not str_n[0].isdigit():
        return 0
    first = int(str_n[0])
    l = len(str_n)
    if l == 1 and first == 0:
        return 0
    if l == 1 and first > 0:
        return 1
    # 假设str_n是"21345"
    # 1.num_first_digit是数字10000~19999的第一位中的1的数目
    num_first_digit = 0
    if first > 1:
        num_first_digit = powerBase10(l - 1)
    elif first == 1:
        num_first_digit = int(str_n[1:]) + 1
    # 2.num_other_digit是00000~19999除第一位之外的数位中的1的数目，使用排列组合
#     print(first, (l - 1), powerBase10(l - 2))
    num_other_digit = first * (l - 1) * powerBase10(l - 2)
    # 3.num_recursive是20000~21345除第一位之外的数位中1的数目，等同于1~1345中1的数目，使用递归
    numRecursive = numberOf1(str_n[1:])
#     print(num_first_digit, num_other_digit, numRecursive)
    return num_first_digit + num_other_digit + numRecursive

def powerBase10(n):
    res = 1
    for i in range(n):
        res *= 10
    return res
1
numberOf1Between1AndN(12)
1
5

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

  • 问题描述：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。
  • 思路：简单思路：从1开始构建字符串，设置一个简单变量k保存当前的长度，直到k==n，停止遍历。计算m位数最多能到达的边界，确定第n位对应的数字是多少位，再确定n是什么数字。
  • 优点：时间复杂度是$log(n)$。
  • 时间复杂度：$log(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def digitAtIndex(index):
    if index < 0:
        return -1
    digits = 1
    while True:
        numbers = countOfIntegers(digits)
        if index < numbers * digits:
            return digitAtIndexWithMDigits(index, digits)
        index -= numbers * digits
        digits += 1
    
def countOfIntegers(digits):
    """输入1，返回0-9的个数10；输入2，返回10-99的个数90；输入3，返回100-999的个数900"""
    if digits == 1:
        return 10
    count = 9 * pow(10, digits - 1)
    return count
    
def digitAtIndexWithMDigits(index, digits):
    """在直到index指向的数是m位数的前提下，返回index指向的数字"""
    # 找到index指向的这个数是属于哪个整数
    number = beginNumber(digits) + index // digits
    indexFromRight = digits - index % digits
    for i in range(1, indexFromRight):
        number = number // 10
    return number % 10
    
    
def beginNumber(digits):
    """返回m位数的第一个数"""
    if digits == 1:
        return 0
    return pow(10, digits - 1)
1
2
3
print(digitAtIndex(5))
print(digitAtIndex(13))
print(digitAtIndex(19))
1
2
3
5
1
4

NO.45 把数组排成最小的数

  • 问题描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
  • 思路：这道题可以看做是一种特殊的排序，核心在于如何实现比较。给定数字m和n，比较函数需要确定m和n谁排在前面。根据题目要求，如果$mn<nm$，则应该是m排在n前面，也就是说m“小于”n。
  • 优点：时间复杂度跟排序一样。
  • 时间复杂度：采样快排，则为$nlog(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def printMinNumber(numbers):
    l = len(numbers)
    if l == 0:
        return 
    sorted_numbers = sorted(map(my_int, numbers))
    return "".join(map(str, sorted_numbers))
    
class my_int(int):
    """Refer to https://softwareengineering.stackexchange.com/questions/151069/sorting-using-a-custom-definition-of-and-in-python"""
    def __lt__(n, m):
        return str(n) + str(m) < str(m) + str(n)
    
# def compare_ints(n, m):
#     return str(n) + str(m) < str(m) + str(n)
1
printMinNumber([3, 32, 321])
1
'321323'

NO.46 把数字翻译成字符串

  • 问题描述：给定一个数字，按照如下规则翻译成字符串：0翻译成“a”，1翻译成“b”…25翻译成“z”。一个数字有多种翻译可能，例如12258一共有5种，分别是bccfi，bwfi，bczi，mcfi，mzi。实现一个函数，用来计算一个数字有多少种不同的翻译方法。
  • 思路1：使用递归：定义$f(i)$表示从第i位数字开始的不同翻译的数目，$g(i,
    i+1)$代表第i位和第i+1位两位数字拼在一起是否在10~25的范围内，那么$f(i) = f(i+1)+g(i, i+1) × f(i+2)$。
  • 特点：思路清晰，但式子中的$f(i+1)$和$f(i+2)$明显有重复计算的部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getTranslationCount1(num_s):
#     print(num_s)
    count = 0
    if len(num_s) == 0:
        return 0
    if len(num_s) == 1:
        return 1
    if num_s[0] == "1" or (num_s[0] == "2" and int(num_s[1]) < 6):
        if len(num_s) > 2:
            return getTranslationCount1(num_s[1:]) + getTranslationCount1(num_s[2:])
        else:
            return 2
    else:
        return getTranslationCount1(num_s[1:])
  • 第一个测试样例：
    • 2 2 -> cc
    • 22 -> w
  • 第二个测试样例：
    • 1 2 2 5 8 -> bccfi
  • 1 22 5 8 -> bwfi
    • 1 2 25 8 -> bczi
    • 12 2 5 8 -> mcfi
    • 12 25 8 -> mzi
1
2
print(getTranslationCount1("22")) 
print(getTranslationCount1("12258"))
1
5
  • 思路2：考虑从最小的问题自下而上地解决问题，类似动态规划思路。
  • 优点：避免思路1中大量的重复计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def getTranslationCount2(num_s):
    l = len(num_s)
    counts = [0 for _ in range(l)]
    for i in range(l - 1, -1, -1):
        count = 0
        if i < l - 1:
            count = counts[i+1]
        else:
            count = 1
        if i < l - 1:
            digit_1 = int(num_s[i])
            digit_2 = int(num_s[i+1])
            converted = digit_1 * 10 + digit_2
            if converted >= 10 and converted <= 25:
                if i < l - 2:
                    count += counts[i+2]
                else:
                    count += 1
        counts[i] = count
    return counts[0]
1
2
print(getTranslationCount2("22")) 
print(getTranslationCount2("12258"))
1
2
2
5

NO.47 礼物的最大价值

  • 问题描述：在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，知道到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿多少价值的礼物？
  • 思路：这是一个典型的用动态规划解决的问题。定义$f(i,j)$表示到达坐标$(i,j)$的格子能拿到的礼物的最大值。很明显：$f(i,j) = max(f(i,j-1), f(i-1, j)) + gift[i,j]$
  • 优点：思路清晰。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getMaxValue1(values, rows, cols):
    if values is None or rows <= 0 or cols <= 0:
        return 0
    max_values = [[0 for _ in range(cols)] for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            up = 0
            left = 0
            if i > 0:
                up = max_values[i-1][j]
            if j > 0:
                left = max_values[i][j-1]
            max_values[i][j] = values[i][j] + max(up, left)
    return max_values[rows-1][cols-1]
1
2
3
4
5
6
values = [[1, 10, 3, 8], 
          [12, 2, 9, 6],
          [5, 7, 4, 11],
          [3, 7, 16, 5]]

getMaxValue1(values, 4, 4)
1
53
  • 思路：继续优化：每次计算$(i,j)$时只依赖$(i-1,j)$和$(i, j-1)$两个格子，因此第$i-2$行和更上面的所有格子的最优结果无需保存。因此可以用一个一维数组来取代二维数组。在判断位置$(i,j)$时，一维数组前j个数字分别是$f(i,0),f(i,1),…,f(i, j-1)$（当前行已经更新的最佳结果），后面的数字是$f(i-1, j), f(i-1, j+1), …, f(i-1,cols-1)$（上一行的最佳结果）。
  • 优点：空间复杂度相对减少。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getMaxValue2(values, rows, cols):
    if values is None or rows <= 0 or cols <= 0:
        return 0
    max_values = [0 for _ in range(cols)]
    for i in range(rows):
        for j in range(cols):
            up = 0
            left = 0
            if i > 0:
                up = max_values[j]
            if j > 0:
                left = max_values[j-1]
            max_values[j] = values[i][j] + max(up, left)
    return max_values[cols-1]
1
2
3
4
5
6
values = [[1, 10, 3, 8], 
          [12, 2, 9, 6],
          [5, 7, 4, 11],
          [3, 7, 16, 5]]

getMaxValue2(values, 4, 4)
1
53

NO.48 最长不含重复字符的子字符串

  • 问题描述：请从字符串中找出一个最长的不包含重复字符串的子字符串，计算该最长子字符串的长度。假设字符串中只包含‘a’~‘z’的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度是4。
  • 思路：动态规划，定义函数$f(i)$表示第$i$个字符为结尾的不包含重复子字符串的最长长度。如果第$i$个字符之前没有出现过，那么$f(i) = f(i-1) + 1$。如果出现过，则分为两种情况：记录$d$为第$i$个字符和它上次出现的位置之间的距离，如果$d\leq f(i-1)$，则$f(i)=d$；反之，仍有$f(i) = f(i-1) + 1$。
  • 优点：时间复杂度是$O(n)$，暴力法是$O(n^3)$。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def longestSubstringWithoutDuplication(string):
    cur_len = 0
    max_len = 0
    position = [-1 for _ in range(26)]
    
    for i in range(len(string)):
        prev_index = position[ord(string[i]) - ord("a")]
        if prev_index < 0 or i - prev_index > cur_len:
            cur_len += 1
        else:
            if cur_len > max_len:
                max_len = cur_len
            cur_len = i - prev_index
        position[ord(string[i]) - ord("a")] = i
    if cur_len > max_len:
        max_len = cur_len
    return max_len
1
longestSubstringWithoutDuplication("arabcacfr")
1
4

NO.49 丑数

  • 问题描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。
  • 思路1：逐个判断每个整数是不是丑数。
  • 优点：直观但不够高效。需要判断每个不是丑数的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def isUgly(number):
    while number % 2 == 0:
        number /= 2
    while number % 3 == 0:
        number /= 3
    while number % 5 == 0:
        number /= 5
        
    return number == 1

def getUglyNumber1(n):
    if n <= 0:
        return 0
#     ugly_numbers = []  # 调试用
    number = 0
    uglyFound = 0
    while uglyFound < n:
        number += 1
        if isUgly(number):
            uglyFound += 1
#             ugly_numbers.append(number)
#     print(ugly_numbers)
    return number
1
isUgly(40)
1
True
1
2
3
4
import time
s = time.time()
print(getUglyNumber1(500))
print("Time cost: ", time.time() - s)
1
2
937500
Time cost:  0.5277576446533203
  • 思路2：创建数组保存已经找到的丑数，用空间换时间。假设已经有若干个排好序的丑数数组，并且最大的丑数记做$M$，下一个丑数必然是前面其中某一个丑数乘以2、3或者5的结果。第一个乘以2大于$M$的记为$M_2$，第一个乘以3大于$M$的记为$M_3$，第一个乘以5大于$M$的记为$M_5$。
  • 优点：不用计算不是丑数的数，用空间换时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def getUglyNumber2(n):
    if n <= 0:
        return 0
    ugly_numbers = [0 for _ in range(n)]
    ugly_numbers[0] = 1
    next_ugly_index = 1
    mutiply_2_index = 0
    mutiply_3_index = 0
    mutiply_5_index = 0
    
    while next_ugly_index < n:
        min_one = min(ugly_numbers[mutiply_2_index] * 2, ugly_numbers[mutiply_3_index] * 3, ugly_numbers[mutiply_5_index] * 5)
        ugly_numbers[next_ugly_index] = min_one
        
        while ugly_numbers[mutiply_2_index] * 2 <= min_one:
            mutiply_2_index += 1
        while ugly_numbers[mutiply_3_index] * 3 <= min_one:
            mutiply_3_index += 1
        while ugly_numbers[mutiply_5_index] * 5 <= min_one:
            mutiply_5_index += 1
        next_ugly_index += 1
        
#     print(ugly_numbers)
    return ugly_numbers[-1]
1
2
3
4
import time
s = time.time()
print(getUglyNumber2(500))
print("Time cost: ", time.time() - s)
1
2
937500
Time cost:  0.0006611347198486328

可以明显看到思路2的速度快很多，而且n越大，时间差距越明显。

NO.50 第一个只出现一次的字符

  • 问题描述：在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出‘b’。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.51 数组中的逆序对

  • 问题描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.52 两个链表的第一个公共节点

  • 问题描述：输入两个链表，找出它们的第一个公共结点。
  • 思路：遍历两个链表，确定长度m和n，假设m>n，先走m-n步，再一起走，直到碰头。
  • 优点：时间复杂度低。
  • 时间复杂度：$O(m+n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def findFirstCommonNode(head1, head2):
    l1 = getListLength(head1)
    l2 = getListLength(head2)
    head_long = head1 if l1 > l2 else head2
    head_short = head2 if l1 > l2 else head1
    l_diff = l1 - l2 if l1 > l2 else l2 - l1
    
    for i in range(l_diff):
        head_long = head_long.next
        
    while head_long is not None and head_short is not None and head_long != head_short:
        head_long = head_long.next
        head_short = head_short.next
        
    firstCommonNode = head_long
    
    return firstCommonNode

def getListLength(head):
    l = 0
    while head is not None:
        l += 1
        head = head.next
    return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n7 = ListNode(7)

n1.next = n2
n2.next = n3
n4.next = n5
n3.next = n6
n5.next = n6
n6.next = n7

print(findFirstCommonNode(n1, n4).val)
1
6

NO.53 在排序数组中查找数字

  • 问题描述：统计一个数字在排序数组中出现的次数。如，输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。
  • 思路：
  • 优点：
  • 时间复杂度：

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

  • 问题描述：给定一颗二叉搜索树，请找出其中的第k大的结点。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.55 二叉树的深度

  • 问题描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
  • 思路：递归：一棵树的长度 = 1 (根节点) + max(左子树长度, 右子树长度)
  • 优点：简单清晰。
1
2
3
4
5
6
def treeDepth(root):
    if root is None:
        return 0
    n_left = treeDepth(root.left)
    n_right = treeDepth(root.right)
    return n_left + 1 if n_left > n_right else n_right + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)

print(treeDepth(n1))
1
2
8 6 10 5 7 9 11
3

相关：平衡二叉树

  • 问题描述：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中的任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
  • 思路1：递归：使用上面的求深度函数，对每个节点的左右子树检查。
  • 优点：思路简单，但时间复杂度较高。
1
2
3
4
5
6
def isBalanced1(root):
    if root is None:
        return True
    n_left = treeDepth(root.left)
    n_right = treeDepth(root.right)
    return n_left - n_right <= 1 and n_left - n_right >= -1 and isBalanced1(root.left) and isBalanced1(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)

isBalanced1(n1)
1
2
3
8 6 10 5 7 9 11

True
  • 思路2：使用后续遍历，“左右根”的遍历方式可以确保在遍历到一个节点时，其左右子树都是遍历过的。这样只需在遍历的时候记录下当前检查节点的深度并返回即可。
  • 优点：只用遍历一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isBalancedCore2(root, depth_s):
    if root is None:
        depth_s[0] = 0
        return True
    left_ds = [0]
    right_ds = [0]
    if isBalancedCore2(root.left, left_ds) and isBalancedCore2(root.right, right_ds):
        diff = left_ds[0] - right_ds[0]
        if diff <= 1 and diff >= -1:
            depth_s[0] = 1 + left_ds[0] if left_ds[0] > right_ds[0] else 1 + right_ds[0]
            return True
    return False
    
def isBalanced2(root):
    return isBalancedCore2(root, [0])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)

isBalanced2(n1)
1
2
3
8 6 10 5 7 9 11

True

NO.56 数组中数字出现的次数

  • 问题描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度$O(n)$，空间复杂度$O(1)$。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.57 和为s的数字

  • 问题描述：输入一个递增排序的数组和一个数字，在数组中查找两个数，使得他们的和正好是s，如果有多对数字的和等于s，则输出任意一对即可。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.58 翻转字符串

  • 问题描述：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。如，输入字符串“I am a student.”，则输出“student. a am I”。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.59 队列的最大值

  • 问题描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}，{2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}，{2,3,4,2,6,[2,5,1]}。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.60 n个骰子的点数

  • 问题描述：把n个骰子扔在地上，所有骰子朝上的一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.61 扑克牌中的顺子

  • 问题描述：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
  • 思路：
  • 优点：
  • 时间复杂度：

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

  • 问题描述：题目： 0、1…n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。如0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.63 股票的最大利润

  • 问题描述：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.
  • 思路：定义$diff(i)$代表卖出价是数组中第i个数字时，能获得的最大利润，那么最终的结果就是$\underset{i}{max} ;diff(i)$。而由于$diff(i)$可以在遍历时直接计算获得，所以不需要一个长度是n的数组保存所有的$diff(i)$，只需保存之前最大的$diff(i)$即可。
  • 优点：时间复杂度和空间复杂度都低。
  • 时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
def maxDiff(numbers):
    l = len(numbers)
    if l == 0:
        return -1
    max_diff = -99999999
    min_buy = numbers[0]
    for i in range(1, l):
        if numbers[i] - min_buy > max_diff:
            max_diff = numbers[i] - min_buy
        if numbers[i] < min_buy:
            min_buy = numbers[i]
    return max_diff
1
maxDiff([9,11,8,5,7,12,16,14])
1
11

NO.64 求1+2+…+n

  • 问题描述：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.65 不用加减乘除做加法

  • 问题描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.66 构建乘积数组

  • 问题描述：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。
  • 思路：
  • 优点：
  • 时间复杂度：

NO.67 把字符串转换成整数

  • 问题描述：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0
  • 思路：
  • 优点：
  • 时间复杂度：

NO.68 树中两个结点的最低公共祖先

  • 问题描述：输入两个树节点，求他们的最低公共祖先。
    • 二叉树（二叉搜索树）：二叉搜索树是排序的，如果当前节点大于两个节点的值，去左子树中寻找；如果当前节点小于两个节点的值，去右子树中寻找；如果当前节点位于两个节点值之间，则该节点就是要寻找的最低公共祖先。
    • 普通树（存在指向父节点的指针）：从给定节点出发，由父节点指针回到到根结点，形成链表。从而将问题转化为求两个链表的第一个公共节点的问题。
    • 普通树（不存在指向父节点的指针）：利用两个辅助链表通过递归遍历的方法找到两条到达给定节点的路径，寻找两个链表最后一个公共节点，就是最低公共祖先。
  • 思路：
  • 优点：
  • 时间复杂度：