归并排序

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
def mergesort(nums, left, right):
    if left >= right:
        return 0
    mid = left + (right - left) // 2

    cnt_l = mergesort(nums, left, mid)
    cnt_r = mergesort(nums, mid + 1, right)
    cnt_c = merge(nums, left, mid, right)

    return cnt_l + cnt_r + cnt_c

def merge(nums, left, mid, right):
    tmp, cnt = [], 0
    l1, l2 = left, mid + 1

    while l1 <= mid and l2 <= right:
        if nums[l1] <= nums[l2]:
            tmp.append(nums[l1])
            l1 += 1
        else:
            tmp.append(nums[l2])
            l2 += 1
            cnt += (mid - l1 + 1)

    if l1 <= mid:
        tmp.extend(nums[l1 : mid + 1])
    else:
        tmp.extend(nums[l2 : right + 1])

    nums[left : right + 1] = tmp[:]
    return cnt

nums = [7, 3, 2, 6, 0, 1, 5, 4]
mergesort(nums, 0, len(nums) - 1)
print(nums)

例题：剑指 Offer 51. 数组中的逆序对

DFS

图方式的遍历 例题https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minimumFuelCost(self, nodes: List[List[int]]) -> int:
        g = [[] for _ in range(len(nodes)+1)]
        for x,y in nodes:
            g[x].append(y)
            g[y].append(x)
        def dfs(x: int, fa: int) -> None:
            for y in g[x]:
                if y != fa:
                    # -----
                    dfs(y, x)
        dfs(0, -1)

树方式的遍历 例题https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/

1
2
3
4
5
6
7
8
9
10
class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        a = []
        def dfs(o: Optional[TreeNode]) -> None:
            if o is None: return
            dfs(o.left)
            a.append(o.val)
            dfs(o.right)
        dfs(root)
		# 中序遍历二叉搜索树的代码实现