算法编程知识点总结归纳

算法编程
Word count: 6.6k   |   Reading time≈ 31 min

本文主要对算法编程基础知识进行梳理、回顾，以及一些常见的算法掌握。

算法编程

1. 反转链表(leetcode 206)

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
"""
题目：
反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

# Python packages

# 双指针迭代
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 申请两个指针，pre 和 cur，pre指向None
        pre = None
        cur = head
        # 遍历链表
        while cur:
            # 记录当前节点的下一个节点
            temp = cur.next
            # 然后将当前节点指向pre
            cur.next = pre
            # pre 和 cur 节点都往后移一位
            pre = cur
            cur = temp
        return pre

def createList():
    head = ListNode(1)
    cur = head
    for i in range(1,6):
        cur.next = ListNode(i)
        cur = cur.next
    return head

def printList(head):
    cur = head
    while cur:
        print(cur.val, '-->', end='')
        cur = cur.next

    print('NULL')


if __name__ == '__main__':
    head = createList()
    solution = Solution()
    res = solution.reverseList(head)
    printList(res)


# 递归解法
class Solution(object):
    def reverseList(self, head)：
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 递归终止条件是当前为空，或者下一个节点为空
        if (head == None or head.next == None)：
            return head
        # 这里的cur就是最后一个点
        cur = self.reverseList(head.next)
        # 如果链表是 1->2->3->4->5，那么此时的cur就是5，而head是4，head的下一个是5，下下一个是空，所以head.next.next 就是5 -> 4
        head.next.next = head
        # 防止链表循环，需要将head.next设置为空
        head.next = None
        # 每层递归函数都返回cur，也就是最后一个节点
        return cur

2. DFS

3. BFS

4. 冒泡排序

时间复杂度O(n**n)，空间复杂度O(1)

1
2
3
4
5
6
def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

5. 快排

时间复杂度O(nlogn)，空间复杂度O(logn)

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
def quickSort(arr):
    if len(arr) <= 1:
        return arr
    # 左、右两边数组
    left, right = [], []
    # 基准数
    base = arr.pop()

    # 对需要排序的数组进行划分
    for i in arr:
        if i < base:
            left.append(i)
        else:
            right.append(i)

    # 递归
    return quickSort(left) + [base] + quickSort(right)


if __name__ == "__main__":
    arr = [10, 7, 8, 9, 1, 5]
    print(quickSort(arr))

# 结果
'''
[1, 5, 7, 8, 9, 10]
'''

6. 归并排序

时间复杂度O(nlogn)，空间复杂度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
class Solution(object):
    def mergeSort(self, arr):
        if len(arr) < 2:
            return arr
        mid = len(arr) // 2
        left, right = arr[0: mid], [mid:]
        return self.merge(self.mergeSort(left), self.mergeSort(right))

    def merge(self, left, right):
        res = []
        while left and right:
            if left[0] <= right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
    while left:
        res.append(left.pop(0))
    while right:
        res.append(right.pop(0))
    return res


if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    solution  = Solution()
    res = solution.mergeSort(arr)
    print(res)

7. 二叉树

(1) 二叉树

二叉树是最基本的数据结构之一，二叉树（Binary Tree）是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。二叉树的定义是一种递归的定义。

二叉树的性质：

  • 第 i 层上至多有2^(i-1)个节点，其中i >= 1;
  • 深度为 k 的二叉树至多有2^(k-1)节点，其中k >= 1;
  • 对于一颗二叉树，如果叶子节点的个数为m，度为2的节点个数为n，则m = n + 1;
  • 具有 n 个节点的完全二叉树的深度为log2n + 1

(2) 二叉树的前序遍历(leetcode 144)

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树

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
100
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 递归遍历，根-左-右
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

# 深度优先搜索解法DFS
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []

        def dfs(root):  # 深度优先搜索，从上到下，从左到右
            if not root:
                return
            res.append(root.val)  # 根节点入栈
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res

# 迭代解法(广度优先解法BFS)
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []  # 存放结果
        stack = [root]  # 利用出栈确定根节点
        while stack:
            root = stack.pop()
            if root:
                res.append(root.val)
                if root.right:
                    stack.append(root.right)
                if root.left:
                    stack.append(root.left)
        return res

# 模版解法，内存消耗严重
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        while stack or root:
            while root:
                res.append(root.val)  # 将根节点加入列表
                stack.append(root)
                root = root.left  # 遍历左子树
            root = stack.pop()  # 左子树遍历完毕
            root = root.right  # 遍历右子树
        return res

# 颜色标记法
"""
使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
白色为0，灰色为1
"""
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = [(0, root)]
        while stack:
            flag, node = stack.pop()
            if node is None: continue  # 空节点跳过
            if flag == 0:  # 前序的倒序记录，子节点标记为1，已经标记过 1 的父节点状态设置为0
                stack.append((0, node.right))
                stack.append((0, node.left))
                stack.append((1, node))
            else:  # 标记为1则输出
                res.append(node.val)
        return res

(3) 二叉树的中序遍历(leetcode 94)

中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树

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
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 递归遍历，左-根-右
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

# 深度优先搜索DFS
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []

        def dfs(root):  # 深度优先搜索，从左-根节点-右
            if not root:
                return
            dfs(root.left)
            res.append(root.val)  # 根节点入栈
            dfs(root.right)
        dfs(root)
        return res

# 模版解法
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left  # 遍历左子树
            root = stack.pop()  # 左子树遍历完毕
            res.append(root.val)  # 将节点加入列表
            root = root.right  # 遍历右子树
        return res

# 颜色标记法
class Solution3(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = [(0, root)]
        while stack:  # 前序的中序记录，子节点标记为1，已经标过1的父节点状态置为0
            flag, node = stack.pop()
            if node is None: continue  # 空节点跳过
            if flag == 0:
                stack.append((0, node.right))
                stack.append((1, node))
                stack.append((0, node.left))
            else:  # 标记为1则输出
                res.append(node.val)
        return res

(4) 二叉树的后续遍历(leetcode 145)

后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

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
# 定义一个二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 递归遍历，左-右-根
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]


# 深度优先搜索DFS
class Solution1(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def dfs(root):  # 深度优先搜索，从下到上，从左到右
            if not root:
                return
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)  # 根节点入栈
        dfs(root)
        return res

# 模版解法，将前序遍历结果倒序输出
class Solution2(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        while stack or root:
            while root:
                res.append(root.val)  # 将根节点加入列表
                stack.append(root)
                root = root.right  # 遍历右子树
            root = stack.pop()  # 右子树遍历完毕
            root = root.left  # 遍历左子树
        return res[::-1]


# 颜色标记法(居然超时了)
class Solution3(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = [(0, root)]
        while stack:
            flag, node = stack.pop()
            if node is None: continue  # 空节点继续
            if flag == 0:
                # 后序的中序记录，子节点标记为1，已经标记过1的父节点状态置为0
                stack.append((0, node))
                stack.append((0, node.left))
                stack.append((1, node.right))
            else:  # 标记为1则输出
                res.append(node.val)
        return res

(5) 二叉树的层序遍历(leetcode 102/107)

102.给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

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
# 定义一个二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 广度优先搜索BFS解法（迭代）
"""
广度优先搜索的步骤为：
① 初始化队列q，并将根节点root加入到队列中
② 当队列不为空时，
    队列中弹出节点node，加入到结果中；
    如果左子树非空，左子树加入队列；
    如果右子树非空，右子树加入队列；
"""
class Solution1(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        queue = [root]

        while queue:
            level = []  # 保存每一层的节点
            for i in range(len(queue)):
                node = queue.pop(0)  # 取队列头节点
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)
        return res

# 深度优先搜索DFS解法（递归）
# 记录每个节点的深度depth，递归到新节点要把该节点放入depth对应列表的末尾
class Solution2(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:
            return []

        def dfs(node, depth):
            if len(res) == depth:
                res.append([])  # 当一层遍历完，增加[]
            res[depth].append(node.val)  # 将节点添加进[]末尾
            if node.left:
                dfs(node.left, depth + 1)
            if node.right:
                dfs(node.right, depth + 1)
        dfs(root, 0)
        return res

107.给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

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
# 定义一个二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 广度搜索优先BFS
class Solution1(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        queue = [root]

        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.pop(0)  # 取队列头结点
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.insert(0, level)  # 插入到列表开头

        return res


# 深度搜索优先DFS，改用 inserrt 插入到列表开头
class Solution2(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:
            return []

        def dfs(node, depth):
            if len(res) == depth:
                res.insert(0, [])  # 当一层遍历完，插入[]到开头
            res[-(depth + 1)].append(node.val)  # 将节点添加进[]
            if node.left:
                dfs(node.left, depth + 1)
            if node.right:
                dfs(node.right, depth + 1)

        dfs(root, 0)
        return res

8. 二叉树打的最大深度(leetcode 104)

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
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 递归（深度优先搜索DFS）
# 时间复杂度为 O(N)，空间复杂度 O(log(N))
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return 0 if not root else max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1


# 迭代（深度优先搜索DFS），利用栈
class Solution1(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        stack = [(1, root)]
        depth = 0
        while stack:
            h, node = stack.pop()
            depth = max(depth, h)
            if node.left:
                stack.append((h + 1, node.left))
            if node.right:
                stack.append((h + 1, node.right))
        return depth


# 迭代（广度优先搜索BFS），队列
class Solution2(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        queue = [(1, root)]  # 添加一个层数depth参数
        while queue:
            depth, root = queue.pop(0)
            if root.left:
                queue.append((depth + 1, root.left))
            if root.right:
                queue.append((depth + 1, root.right))
        return depth


# 分治法
class Solution3(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        if left > right:
            return left + 1
        else:
            return right + 1

9. 平衡二叉树（leetcode 110）

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 递归（深度优先搜索DFS）自底向上
class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def dfs(root):
            if not root:
                return 0
            left = dfs(root.right) + 1
            right = dfs(root.left) + 1

            if left == 0 or right == 0 or abs(left - right) > 1:
                return -1
            return max(left, right)

        return dfs(root) != -1


# 自顶而下
class Solution1(object):
    def depth(self, root):
        if not root:
            return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1

    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(
            root.left) and self.isBalanced(root.right)


class Solution2(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def maxDepth(root):
            if not root:
                return True, 0
            lf, lh = maxDepth(root.left)
            rf, rh = maxDepth(root.right)
            if lf and rf and abs(lh - rh) < 2:
                return True, max(lh, rh) + 1
            return False, max(lh, rh) + 1
        return maxDepth(root)[0]


def createTree(data):
    """
    创建二叉树
    :param data: List
    :return:
    """
    if len(data) == 0:
        return TreeNode(0)
    nodeQueue = []
    # 创建一个根节点，并将根节点进栈
    root = TreeNode(data[0])
    nodeQueue.append(root)
    # 记录当前节点的数量
    lineNum = 2
    # 记录当前行中数字在数组中的位置
    startIndex = 1
    # 记录数组中剩余元素的数量
    restLength = len(data) - 1
    while restLength > 0:
        for index in range(startIndex, startIndex + lineNum, 2):
            if index == len(data):
                return root
            cur_node = nodeQueue.pop()
            if data[index] is not None:
                cur_node.left = TreeNode(data[index])
                nodeQueue.append(cur_node.left)
            if index + 1 == len(data):
                return root
            if data[index + 1] is not None:
                cur_node.right = TreeNode(data[index + 1])
                nodeQueue.append(cur_node.right)
        startIndex += lineNum
        restLength -= lineNum
        # 更新下一层树对应节点的最大值
        lineNum = len(nodeQueue) * 2
    return root


if __name__ == '__main__':
    nums = [3, 9, 20, None, None, 15, 7]
    root = createTree(nums)
    solution = Solution()
    res = solution.isBalanced(root)
    print(res)

    solution1 = Solution1()
    res1 = solution1.isBalanced(root)
    print(res1)

    solution2 = Solution2()
    res2 = solution2.isBalanced(root)
    print(res2)

10. 二叉树的最近公共祖先（leetcode 236）

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
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left and not right:  # 当left和right同时为空，这root的左右指数都不包含p、q，返回null
            return
        if not left:  # 当left为空，right不为空，p、q都不在root的左子树中，直接返回right
            return right
        if not right:  # 当right为空，left不为空，p、q都不在root的右子树中，直接返回left
            return left

        return root  # 当left和right都不为空，p、q在root的不同侧，返回root

11. 二叉树的锯齿形层次遍历（leetcode 103）

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

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
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 深度优先遍历（DFS）
class Solution1(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        def dfs(root, depth):
            if not root:
                return []
            if len(res) == depth:
                res.append([])
            if depth % 2 == 0:  # 偶数行正常排序
                res[depth].append(root.val)
            else:  # 奇数行倒序插入
                res[depth].insert(0,root.val)

            dfs(root.left, depth + 1)
            dfs(root.right, depth + 1)

        dfs(root, 0)
        return res

12. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数；
  • 节点的右子树只包含大于当前节点的数；
  • 所有的左子树和右子树自身必须也是二叉搜索树。
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
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 递归解法
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(node, lower=float('-inf'), upper=float('inf')):
            if not node:
                return True
            if node.val <= lower or node.val >= upper:
                return False
            if not helper(node.right, node.val, upper):
                return False
            if not helper(node.left, lower, node.val):
                return False
            return True

        return helper(root)

# 中序遍历（左-根-右），得到的序列是是升序结果即可
class Solution1(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack = []
        inorder = float('-inf')
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()  # 左子树遍历完毕
            if root.val <= inorder:  # 中序遍历得到的节点值小于等于前一个inorder，则非二叉搜索树
                return False
            inorder = root.val
            root = root.right

        return True

# 递归解法，pythonic代码
class Solution2(object):
    def isValidBST(self, root):
        """
        :param root: TreeNode
        :return: bool
        """
        def BFS(node, left, right):
            """
            :param root: 节点
            :param left: 下界
            :param right: 上界
            :return: bool
            """
            if not node:
                return True
            if left < node.val < right:
                return BFS(node.left, left, node.val) and BFS(node.right, node.val, right)
            else:
                return False

        return BFS(root, -float('inf'), float('inf'))

13. 二叉搜索树中的插入操作（leetcode 701）

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意: 可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

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
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, val = 0, left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

# 递归
class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val:  int
        :rtype: TreeNode
        """
        if not root:
            return TreeNode(val)

        if val > root.val:  # 插入的值大于根节点，则插入到右子树中
            root.right = self.insertIntoBST(root.right, val)
        else:  # 插入的值小于根节点，则插入到左子树中
            root.left = self.insertIntoBST(root.left, val)
        return root

# 迭代
class Solution1(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val:  int
        :rtype: TreeNode
        """
        node = root
        while node:
            if val > node.val:  # 插入到右子树
                if not node.right:  # 当右子树没有右子节点，则插入到右子树右节点
                    node.right = TreeNode(val)
                    return root
                else:  # 当右子树右节点存在，则指针指向该右子节点
                    node = node.right
            else:  # 插入左子树
                if not node.left:  # 当左子树没有左子节点，则插入到左子树右节点
                    node.left = TreeNode(val)
                    return root
                else:  # 当左子树左节点存在，则指针指向该左子节点
                    node = node.left
        return TreeNode(val)

14. 二叉树中的最大路径和（leetcode 124）

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# 定义二叉树节点
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 官方递归解法
class Solution(object):
    def __init__(self):
        self.maxSum = float("-inf")

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def get_max(node):
            if not node:
                return 0

            # 递归计算左右节点的最大贡献值，并且要大于0
            left = max(get_max(node.left), 0)
            right = max(get_max(node.right), 0)

            # 节点的最大路径和取决于该节点的值与该节点的左右节点的最大贡献值
            max_path = node.val + left + right

            # 更新最大路径值
            self.maxSum = max(self.maxSum, max_path)

            # 返回节点的最大贡献值
            return node.val + max(left, right)

        get_max(root)
        return self.maxSum


# 大佬逻辑清晰解答
"""
思路：
最大路径和：根据当前节点的角色，路径和可分为两种情况：
    一：以当前节点为根节点
    1.只有当前节点
    2.当前节点+左子树
    3.当前节点+右子书
    4.当前节点+左右子树    
    这四种情况的最大值即为以当前节点为根的最大路径和
    此最大值要和已经保存的最大值比较，得到整个树的最大路径值
    
    二：当前节点作为父节点的一个子节点
    和父节点连接的话则需取【单端的最大值】
    1.只有当前节点
    2.当前节点+左子树
    3.当前节点+右子书
    这三种情况的最大值   
"""
import sys


class Solution1(object):
    res = -sys.maxsize - 1

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxValue(root)
        return self.res

    def maxValue(self, node):
        if not node:
            return 0
        left_value = self.maxValue(node.left)
        right_value = self.maxValue(node.right)

        value1 = node.val
        value2 = node.val + left_value
        value3 = node.val + right_value
        value4 = node.val + left_value + right_value

        # 以此节点为根节点的最大值
        maxValue = max([value1, value2, value3, value4])

        # 当前遍历树的最大值
        self.res = max(maxValue, self.res)

        # 和父节点关联，去除情况4的最大值
        return max([value1, value2, value3])


# 递归，后续遍历
class Solution2(object):
    res = float('-inf')

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def helper(node):
            if not node:
                return 0
            l = helper(node.left)
            r = helper(node.right)
            self.res = max(self.res, max(l, 0) + max(r, 0) + node.val)
            return max(l, r, 0) + node.val

        helper(root)
        return self.res

15. 动态规划问题

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
100
101
# 青蛙跳台阶问题
import functools  # 调试时估计不让导入模块，而且常规递归容易超时


# 直接递归法，容易超时，加入缓存装饰器，递归转换成迭代
class Solution1(object):
    @functools.lru_cache(100)  # 缓存装饰器
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0: return 1
        if n == 1: return 1
        if n == 2: return 2
        return self.numWays(n - 1) + self.numWays(n - 2)


# 数组记忆递归法，减少重复计算
class Solution2(object):
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = [-1 for i in range(n + 1)]
        if n == 0: return 1
        if n == 1: return 1
        if n == 2: return 2
        if nums[n] == -1:
            nums[n] = self.numWays(n - 1) + self.numWays(n - 2)
        return nums[n] % 1000000007


# 直接DP，利用字典存储变量
class Solution3(object):
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = {}
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n] % 1000000007


# DP，存储元素交换，建议用一个临时变量temp，使得a,b a+b进行交换，这样更节省时间
class Solution4(object):
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0 or n == 1: return 1
        if n == 2: return 2
        a, b = 1, 2
        for i in range(3, n + 1):
            b, a = a + b, b
        return b % 1000000007


# 动态规划
class Solution5(object):
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2: return 1
        dp = [1 for i in range(n + 1)]
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1] % 1000000007


if __name__ == '__main__':
    n = 7
    solution1 = Solution1()
    res1 = solution1.numWays(n)
    print(res1)

    solution2 = Solution2()
    res2 = solution2.numWays(n)
    print(res2)

    solution3 = Solution3()
    res3 = solution3.numWays(n)
    print(res3)

    solution4 = Solution4()
    res4 = solution4.numWays(n)
    print(res4)

    solution5 = Solution5()
    res5 = solution5.numWays(n)
    print(res5)

16. 01背包问题

17. 两个栈实现一个队列

18. 二叉树的直径

19. 全排列

  • itertools内置permutations方法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from itertools import permutations

def func():
    while True:
        try:
            n = int(input().strip())
            s = [str(i + 1) for i in range(n)]
            res = list(permutations(s))
            for i in res:
                print(" ".join(i))
            print(len(res))
        except:
            break

if __name__ == "__main__":
    func()
  • 递归实现

具体详细的思路参考：

递归实现全排列（回溯思想）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def permutations(s, begin, end):
    global count
    if begin == end:
        print(" ".join(s))
        count += 1
    else:
        for i in range(begin, end):
            s[i], s[begin] = s[begin], s[i]
            permutations(s, begin + 1, end)
            s[i], s[begin] = s[begin], s[i]


if __name__ == "__main__":
    s = [str(i + 1) for i in range(int(input().strip()))]
    count = 0
    permutations(s, 0, len(s))
    print(count)
  • DFS实现

深度优先搜索（DFS）实现全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def permutations(s, position, visit, num):
    if position == len(s):
        print(" ".join(num))
        return

    else:
        for index in range(len(s)):
            if visit[index] == True:
                num[position] = s[index]
                visit[index] = False
                permutations(s, position + 1, visit, num)
                visit[index] = True


if __name__ == "__main__":
    n = int(input().strip())
    s = [str(i + 1) for i in range(n)]
    visit = [True] * n
    num = ["" for i in range(n)]
    permutations(s, 0, visit, num)

20. 重建二叉树

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
# 递归求解

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

class Solution(object):
    def rebuildTree(self, preorder, inorder):
        """
        :type preorder: List[int]  # 前序遍历
        :type inorder: List[int]  # 中序遍历
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None

        # 前序遍历的特征：根-左-右，因此此前序列表的第一个元素必是根节点
        root_value = preorder[0]
        root = TreeNode(root_value)

        # 中序遍历的特征：左-根-右，结合前序遍历的特征，中序列表和前序列表的最后一部分一定是右子树，分割点就是中序遍历的根节点
        # 根节点值在中序列表中的索引
        root_in_index = inorder.index(root_value)

        # 左子树在前序列表中的子列表
        left_pre = preorder[1:root_in_index+1]
        # 左子树在中序列表中的子列表
        left_in = inorder[:root_in_index]

        # 右子树在前序列表中的子列表
        right_pre = preorder[root_in_index+1:]
        # 右子树在中序列表中的子列表
        right_in = inorder[root_in_index+1:]

        # 遍历创建子树
        root.left = self.rebuildTree(left_pre, left_in)
        root.right = self.rebuildTree(right_pre, right_in)

        return root
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
# 利用栈
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]  # 前序遍历
        :type inorder: List[int]  # 中序遍历
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return

        root = TreeNode(preorder)
        stack = [root]

        for node in preorder[1:]:
            parent = stack[-1]

            if parent.val != inorder[i]:
                parent.left = TreeNode(node)
                stack.append(parent.left)
            else:
                while stack and stack[-1].val == inorder[i]:
                    parent = stack.pop()
                    i += 1
                parent.right = TreeNode(node)
                stack.append(parent.right)
        return root

21. 最大公约数

22. 最小公倍数

最小公倍数

23. 求素数

24. 求质数

25. 查并集

并查集(Union-Find)算法详解
并查集详解
并查集(Union-Find)算法介绍

26. 排序算法复杂度中nlgn中的lgn是怎么来的

27. 字符串中最长不重复子串

28. 两个字符串，求其最长子串

29. 按序打印(多线程)

（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
from multiprocessing import Queue
class Foo(object):
    def __init__(self):
        self.q2 = Queue()
        self.q3 = Queue()


    def first(self, printFirst):
        """
        :type printFirst: method
        :rtype: void
        """

        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.q2.put("")


    def second(self, printSecond):
        """
        :type printSecond: method
        :rtype: void
        """
        self.q2.get()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.q3.put("")


    def third(self, printThird):
        """
        :type printThird: method
        :rtype: void
        """
        self.q3.get()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2019-2020 holysll
  • Visitors: | Views: