侯瑞哲的博客

Ruizhe's Blog

0%

发表于 Valine：

借助本题深入了解快速排序中的随机选择，和堆的堆化、插入、删除操作

题目

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路

  1. 暴力解法

题目要求我们找到”数组排序后的第k个最大的元素，而不是第k个不同的元素“。

因此，升序排序以后，目标元素的索引是 len - k ，这是最简单的思路。

  • 最简单同时也一定是最容易编码的，编码成功的几率最高，可以用这个简单思路编码的结果和其他思路编码的结果进行比对，验证高级算法的正确性；
  • 在数据规模小、对时间复杂度、空间复杂度要求不高的时候，简单问题简单做；
  • 思路简单的算法考虑清楚了，有些时候能为实现高级算法铺路，这道题也是如此；
  • 低级算法往往容错性最好，即在输入不满足题目条件的时候，往往还能得到正确的答案，而高级算法对输入数据的要求就非常苛刻。

复杂度分析：

  • 时间复杂度：O(nlogn)，这里n是数组的长度，主要是排序，语言内置的排序一般是优化的快排或者归并，O(nlogn)
  • 空间复杂度：O(1)

  1. 借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素（特别注意：随机化切分元素）

以下是注意事项，因为很重要，所以放在前面说：

快速排序虽然快，但是如果实现得不好，在遇到特殊测试用例的时候，时间复杂度会变得很高。

分析：我们在学习"快速排序"的时候，接触的第1个操作就是partition（切分），简单介绍如下：

partition（切分）操作，使得：

  • 对于某个索引j，nums[j]已经排定，即nums[j]经过partition（切分）操作以后会放置在它“最终应该放置的地方”；
  • nums[left]到nums[j - 1]中的所有元素都不大于nums[j]；
  • nums[j + 1]到nums[right]中的所有元素都不小于nums[j]；

partition（切分）操作总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次partition（切分）操作就能缩小搜索的范围，这样的思想叫做“减而治之”（是分而治之的思想的特例）。

切分过程可以不借助额外的数组空间，仅通过交换数组元素来实现。

1
2
3
4
5
6
7
8
9
def partition(nums, l, r):
    pivot = r
    right = l
    for i in range(l, r):
        if nums[i] <= nums[pivot]:
            nums[i], nums[right] = nums[right], nums[i]
            right += 1
    nums[right], nums[pivot] = nums[pivot], nums[right]
    return right

复杂度分析：

  • 时间复杂度：O(N)，这里N是数组的长度，可以通过主定理证明。
  • 空间复杂度：O(1)

注意：本地必须随机初始化pivot元素，否则通过时间会很慢，因为测试中有极端用例。

  1. 为了应对极端测试用例，使得递归树加深，可以在循环一开始的时候，随机交换第1个元素与它后面的任意1个元素的位置；

说明：最极端的是顺序数组与倒序数组，此时递归树画出来是链表，时间复杂度退化为O(N^2)，根本达不到减治的效果。

1
2
3
4
5
6
7
8
9
10
11
def partition(nums, l, r):
    rand = random.randint(l, r)
    nums[r], nums[rand] = nums[rand], nums[r]
    pivot = r
    right = l
    for i in range(l, r):
        if nums[i] <= nums[pivot]:
            nums[i], nums[right] = nums[right], nums[i]
            right += 1
    nums[right], nums[pivot] = nums[pivot], nums[right]
    return right
  1. 使用双指针，将与pivot相等的元素等概率地分到pivot最终排定位置的两边。
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 partition(nums, l, r):
    # randint 是包括左右区间的
    random_index = random.randint(l, r)
    nums[random_index], nums[l] = nums[l], nums[random_index]

    pivot = nums[l]

    lt = l + 1
    rt = r

    while True:
        while lt <= rt and nums[lt] < pivot:
            lt += 1
        while lt <= rt and nums[rt] > pivot:
            rt -= 1

        if lt > rt:
            break
        nums[lt], nums[rt] = nums[rt], nums[lt]
        lt += 1
        rt -= 1

    nums[l], nums[rt] = nums[rt], nums[l]
    return rt

完整快速选择实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums, l, r):
            pivot = r
            rand = random.randint(l, r)
            nums[pivot], nums[rand] = nums[rand], nums[pivot]
            right = l
            for i in range(l, r):
                if nums[i] <= nums[pivot]:
                    nums[i], nums[right] = nums[right], nums[i]
                    right += 1
            nums[right], nums[pivot] = nums[pivot], nums[right]
            return right

        l, r = 0, len(nums) - 1
        while True:
            pivot = partition(nums, l, r)
            if pivot == len(nums) - k:
                return nums[pivot]
            if pivot < len(nums) - k:
                l = pivot + 1
            else:
                r = pivot - 1
  1. 优先队列、堆

优先队列的想法是很朴素的。

我们可以维护大小为K的一个小顶堆：

  1. 如果当前堆不满，直接添加；
  2. 堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，大于堆顶，我们pop堆顶元素，插入新到的元素，让堆自己去调整内部结构。

说明：这里最合适的操作其实是replace，即直接把新读进来的数放在堆顶，然后执行下沉操作（siftDown）操作。python中有heapq.heappushpop()操作。Java中的PriorityQueue没有提供这个操作，只好先poll()再offer()。

堆的写法有很多，以下的写法大同小异，没有本质差别。

假设数组有len个元素。

思路1：把len个元素都放入一个小顶堆堆中，然后在pop()出len-k个元素，此时小顶堆只剩下k个元素，堆顶元素就是数组的第k大元素。

思路2：把len个元素都放入一个大顶堆中，然后再pop出k-1个元素，因此前k-1大的元素都被弹出了，此时大顶堆的堆顶元素就是数组中的第k个最大元素。

下面给出第2中思路的实现，这里改变了原数组，如果不能改变原数组，我们要另外使用堆的空间，可以为k规模的大小，也可以为len规模的大小。

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
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def maxheap(a, i, size):
            l = i * 2 + 1
            r = i * 2 + 2
            large = i
            if l < size and a[l] > a[large]:
                large = l
            if r < size and a[r] > a[large]:
                large = r
            if large != i:
                nums[i], nums[large] = nums[large], nums[i]
                maxheap(a, large, size)

        def buildheap(a, size):
            for i in range(size >> 1, -1, -1):
                maxheap(a, i, size)

        heapsize = len(nums)
        buildheap(nums, heapsize)
        for i in range(heapsize - 1, heapsize - k, -1):
            nums[0], nums[i] = nums[i], nums[0]
            heapsize -= 1
            maxheap(nums, 0, heapsize)
        return nums[0]

考察点

这道题目考查了快速选择（快速切分）操作的特性，时间复杂度的了解，和随机化保证时间复杂度不会退化得过于严重。

堆的解法考查了堆化、插入、和删除的代码写法，是非常好的面试题目。

参考

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/

发表于 更新于 Valine：

人最宝贵的是生命，生命每人只有一次。

人的一生应该这样度过：当他回忆往事的时候，他不会因为虚度年华而悔恨；也不会因为碌碌无为而羞愧，当他临死的时候，他能够说：我的整个生命和全部精力，都献给了世界上最壮丽的事业——为人类的解放而斗争。

人应当赶紧的充分的生活，因为意外的疾病和悲惨的事故随时都可能结束他的生命。

发表于 更新于 Valine： 
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
# 堆的实现.py


# 大顶堆
def maxheap(a, i, size):
    l = 2 * i + 1
    r = 2 * i + 2
    large = i
    if l < size and a[l] > a[large]:
        large = l
    if r < size and a[r] > a[large]:
        large = r
    if large != i:
        a[i], a[large] = a[large], a[i]
        maxheap(a, large, size)


def buildheap(a, size):
    for i in range(size >> 1, -1, -1):
        maxheap(a, i, size)


def insert(a, val, size):
    a.append(val)
    assert a[size - 1] == val
    i = size - 1
    p = i >> 1
    while p >= 0 and a[p] < a[i]:
        a[p], a[i] = a[i], a[p]
        i = p
        p = i >> 1


# 小顶堆
# def minheap(a, i, size):
#     l = 2 * i + 1
#     r = 2 * i + 2
#     small = i
#     if l < size and a[l] < a[small]:
#         small = l
#     if r < size and a[r] < a[small]:
#         small = r
#     if small != i:
#         a[i], a[small] = a[small], a[i]
#         minheap(a, small, size)
#
#
# def buildheap(a, size):
#     for i in range(size >> 1, -1, -1):
#         minheap(a, i, size)


def main():
    # 示例
    nums = [3, 2, 5, 1, 4]
    heapsize = len(nums)

    # 建堆
    buildheap(nums, heapsize)
    print(nums)
    # output:
    # [5, 4, 3, 1, 2]

    # 插入
    # nums.append(6)
    # heapsize += 1
    # i = heapsize - 1
    # while i >> 1 >= 0 and nums[i] > nums[i >> 1]:
    #     nums[i], nums[i >> 1] = nums[i >> 1], nums[i]
    #     i >>= 1
    # print(nums)
    heapsize += 1
    insert(nums, 6, heapsize)
    print(nums)
    # output:
    # [6, 5, 4, 1, 2, 3]

    # 删除
    heapsize -= 1
    nums[0], nums[heapsize] = nums[heapsize], nums[0]
    maxheap(nums, 0, heapsize)
    print(nums)

    # output:
    # [5, 2, 3, 1, 0, 4]


if __name__ == '__main__':
    main()

发表于 Valine：

leetcode 41 缺失的第一个正数

问题描述

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0] 输出: 3 示例 2:

输入: [3,4,-1,1] 输出: 2 示例 3:

输入: [7,8,9,11,12] 输出: 1

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

思路

这道题目和不使用任何额外空间的计数排序很像，因为都对时空复杂度做了严格的限制，我们都不得不改变原数组，设法将其改为我们能够利用的数据结构。否则这两道题目都无法有「真正」的解。不使用额外空间计数排序的那道题目规定数组的元素有一定的范围，我们可以利用32位整数的前16位计数，最终输出计数排序的结果。

这道题目我们要利用，关心的只有[1, 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
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
# 如果本题没有额外的时空复杂度要求，那么就很容易实现：
# 1. 我们可以将数组所有的数放入哈希表，随后从1开始依次枚举正整数，并判断其是否在哈希表中；
# 2. 我们可以从1开始依次枚举正整数，并遍历数组，判断其是否在数组中
# 如果数组的长度为N，那么第一种做法的时间复杂度为O(N)，空间复杂度为O(N)；
# 第二种做法的时间复杂度为O(N^2)，空间复杂度为O(1)。
# 「真正」满足此要求的算法是不存在的。但是我们可以退而求其次：利用给定数组中的空间来存储一些状态。
# 也就是说，如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法；
# 但如果我们可以修改给定的数组，那么是存在满足要求的算法的。

# 方法一.哈希表
# 对于「前言」中提到的第一种做法
# 我们可以将数组所有的数放入哈希表，随后从1开始依次枚举正整数，并判断其是否在哈希表中；
# 仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一个可以支持快速查找的数据结构：
# 给定一个元素，我们可以在O(1)的时间查找给元素是否在哈希表中。
# 因此，我们可以考虑将给定的数组设计成哈希表的「替代产品」。
# 实际上，对于一个长度为N的数组，其中更没有出现的最小正整数只能在[1, N+1]中。
# 这是因为如果[1,N]都出现了，那么答案是N+1，否则答案是[1, N]中没有出现的最小正整数。
# 这样一来，我们将所有在[1,N]范围内的数放入哈希表，也可以得到最终的答案。
# 而给定的数组恰好长度为N，这让我们有了一种将数组设计成哈希表的思路。
# 我们对数组进行遍历，对于遍历到的数x，如果它在[1,N]的范围内，那么就将数组的中的
# 第x-1个位置（注意：数组下标从0开始）打上『标记』。
# 在遍历结束后，如果所有的位置都打上了标记，那么答案是N+1，
# 否则答案是最小的没有打上标记的位置加1.
# 那么如何设计这个『标记』呢？由于数组中的数没有任何限制，因此这并不是一件很容易的事情。
# 但我们可以继续利用上面提到的性质：由于我们只在意[1,N]中的数
# 因此我们可以先对数组进行遍历，把不在[1,N]范围内的数修改成任意一个大于N的数（例如N+1）
# 这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下
# 我们将数组中所有小于等于0的数修改成N+1
# 我们遍历数组中的每一个数x，它可能已经被打了标记，因此原本对应的数|x|，其中||为绝对值符号。
# 如果|x|∈[1,N]，那么我们给数组中的第|x|-1个位置添加一个负号。
# 注意如果它已经有负号，不需要重复添加；
# 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是N+1，否则答案是第一个正数的位置加1.
# 时间复杂度：O(n)，遍历3次数组
# 空间复杂度：O(1)
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1
        for i in range(n):
            x = abs(nums[i])
            if 0 < x <= n:
                nums[x - 1] = nums[x - 1] if nums[x - 1] < 0 else -nums[x - 1]
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1


# 除了打标记之外，我们哈可以使用置换的方法，将给定的数组「恢复」成下面的形式：
# 如果数组中包含x∈[1,N]，那么恢复后，数组的第x-1和元素为x。
# 在恢复后，数组应当有[1,2,...,N]的形式，但其中有若干个位置上的数是错误的
# 每一个错误的位置就代表一个缺失的正数。以题目中的示例2[3,4,-1,1]为例，
# 恢复后的数组应当为[1,-1,3,4]，我们就可以知道缺失的数为2.
# 那么我们如何将数组进行恢复呢？我们可以对数组进行一次遍历吗，对于遍历到的数x=nums[i]，
# 如果x∈[1, N]，我们就知道x应当出现在数组中的x-1的位置，因此交换nums[i]和nums[x-1]，
# 这样x就出现在了正确的位置。在完成交换之后，新的nums[i]可能还在[1,N]的范围内，
# 我们需要继续进行交换操作，直到x∉[1,N].
# 注意到上面的方法可能会陷入死循环，如果nums[i]恰好与nums[x-1]相等，那么就会无限交换下去。
# 此时我们有nums[i] = x = nums[x-1]，说明x已经出现在了正确的位置。
# 因此我们可以跳出循环，开始遍历下一个数。
# 由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为N，
# 整个方法的时间复杂度为O(N)

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 0 < nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

发表于 Valine：

布隆过滤器

布隆过滤器vshash table

布隆过滤器本质上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点：空间效率和查询时间都远远超过一般的算法

缺点：有一定的误识别率和删除困难

对于测试元素，当它验证这个元素所对应的⼆进制位是1的时候，那么它可能存在在布隆过滤器⾥⾯， 当它验证这个元素所对应的⼆进制位只要有⼀个不为1的话，那么我们可以百分之百肯定它不在。

那么接下来要怎么判断它到底是否存在？布隆过滤器只是放在最外⾯当⼀个缓存使的，当⼀个很快速的判断使的。当B查到了之后，布隆过滤器⾥⾯是存在的，那么B会继续到这台机器的DB⾥⾯去查。C不在布隆过滤器中，就不⽤查了。

案例

  1. 比特币网络
  2. 分布式系统（Map-Reduce) - Hadoop、search engine
    1. 搜索引擎，经常需要把大量的网页信息，图片信息存到整个服务器里面，一般来说，不同的网页是存在不同的集群里面的。那么就先去这个集群的布隆过滤器里面查一下。
  3. Redis缓存
  4. 垃圾邮件、评论等的过滤

简单实现示例

布隆过滤器主要有构造函数，和add一个元素，search一个元素，三个API需要实现。

构造函数，我们可以假定传入二进制数组的长度（工业实现中可能会传如元素的数量，然后推断出人禁止数组的长度），需要的哈希函数数量。

add的函数签名是 add(s:str) -> None，我们假定查询的是字符串

search是search(s:str) ->bool

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size: int, hash_num: int):
        self.size = size
        self.hash_num = hash_num
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, s: str) -> None:
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            self.bit_array[result] = 1

    def search(self, s: str) -> bool:
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            if not self.bit_array[result]:
                return False
                # Nope
        return True
        # Probably

发表于 Valine： 
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
# 本题可约化为： 课程安排图是否是 有向无环图(DAG)。
# 即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
# 思路是通过 拓扑排序 判断此课程安排图是否是 有向无环图(DAG) 。
# 拓扑排序原理： 对 DAG 的顶点进行排序，使得对每一条有向边 (u,v)，
# 均有 u（在排序记录中）比 v 先出现。
# 亦可理解为对某点 v 而言，只有当 v 的所有源点均出现了，v 才能出现。
# 通过课程前置条件列表 prerequisites 可以得到课程安排图的 邻接表 adjacency，
# 以降低算法时间复杂度，以下两种方法都会用到邻接表。

# 1.统计课程安排图中弄每个节点的入度，生成入度表indegrees
# 2.借助一个队列queue，将所有入度为0的节点入队。
# 3.当queue非空时，依次将队首节点出队，在课程安排图中删除此节点pre：
#    并不是真正从邻接表中删除此节点pre，而是将此节点对应所有邻接节点cur的入度-1
#    即indegrees[cur] -= 1.
#    当入度-1后邻接节点cur的入度为0，说明cur所有的前驱节点已经被"删除"，此时将cur入队。
# 4.在每次pre出队时，执行numCourses--;
#    若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。
#    换个角度说，若课程安排图中存在环，一定有节点的入度始终不为0。
#    因此，拓扑排序出队次数等于课程个数，返回numCourses==0判断课程是否可以成功安排
# 时间复杂度 O(N+M)： 遍历一个图需要访问所有节点和所有临边，N 和 M 分别为节点数量和临边数量；
# 空间复杂度 O(N+M)： 为建立邻接表所需额外空间，adjacency 长度为 N ，并存储 M 条临边的数据。
class Solution:
    def canFinish(self, numCourses: int,
                  prerequisites: List[List[int]]) -> bool:
        indegrees = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        queue = deque()
        # Get the indegree and adjacency of every course.
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        # Get all the courses with the indegree of 0.
        for i in range(len(indegrees)):
            if not indegrees[i]:
                queue.append(i)
        # BFS TopSort.
        while queue:
            pre = queue.popleft()
            numCourses -= 1
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                if not indegrees[cur]:
                    queue.append(cur)
        return not numCourses


# 原理是通过DFS判断图中是否有环
# 算法流程
# 1.借助一个标志列表flags，用于判断每个节点i（课程）的状态：
#    1.未被DFS访问：i==0
#    2.已被其他节点启动的DFS访问：i==-1
#    3.已被当前节点启动的DFS访问：i==1。
# 2.对numCourses个节点一次执行DFS，判断每个节点起步DFS是否存在换，若存在直接放回False
#    DFS流程
#    1.终止条件：
#      当flag[i] == -1，说明当前访问节点已被其他节点启动的DFS访问，
#      无需再重复搜索，直接返回True
#      当flag[i] == 1，说明在本轮DFS搜索中节点i被第2次访问，即课程安排图有环，直接返回False
#    2.将当前访问节点i对应flag[i]置1，即标记其本轮被DFS访问过；
#    3.递归访问当前节点i的所有邻接节点j，当发现环直接返回False；
#    4.当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点flag置为-1并返回True
# 3.若整个图DFS结束并未发现环，返回True
class Solution:
    def canFinish(self, numCourses: int,
                  prerequisites: List[List[int]]) -> bool:
        def dfs(i, adjacency, flags):
            if flags[i] == -1:
                return True
            if flags[i] == 1:
                return False
            flags[i] = 1
            for j in adjacency[i]:
                if not dfs(j, adjacency, flags):
                    return False
            flags[i] = -1
            return True

        adjacency = [[] for _ in range(numCourses)]
        flags = [0 for _ in range(numCourses)]
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not dfs(i, adjacency, flags):
                return False
        return True

发表于 Valine：

问题描述

给定一个图和图中的源顶点，找到从源到给定图中所有顶点的最短路径。

Dijkstra的算法与Prim的最小生成树算法非常相似。和Prim的MST一样，我们以给定的源为根，生成一个SPT（shortest path tree 最短路径树）。我们维护两个集合，一个集合包含最短路径树中包含的顶点，另一个集合包含尚未包含在最短路径树中的顶点。在算法的每一步，我们都会找到一个在另一个集合（尚未包含的集合）中的顶点，并且与源的距离最小。

下面是Dijkstra算法的详细步骤，用于寻找从单个源顶点到给定图中所有其他顶点的最短路径。

算法

  1. 创建一个集合sptSet（最短路径树集合），用来跟踪最短路径树中包含的顶点，即这个集合中的点到源的最小距离已经被计算和确定下来。开始的时候，这个集合是空的。
  2. 给输出图中的所有顶点分配一个距离值。初始化所有距离值为INFINITE。为源顶点分配距离值为0，这样它就会被首先选中。
  3. while sptSet不包含所有的顶点：
    • 选取一个在sptSet中不存在的顶点u，并且它的距离值最小。
    • 将u加入到sptSet中。
    • 更新u的所有相邻顶点的距离值。要更新距离值，需要遍历所有相邻顶点。对于每一个相邻的顶点v，如果u的距离值（从源点）和边的权重之和小于v的距离值，那么更新v的距离值。

代码示例

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
# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph


class Graph:

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printSolution(self, dist):
        print("Vertex tDistance from Source")
        for node in range(self.V):
            print(node, "t", dist[node])

        # A utility function to find the vertex with

    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = float('inf')

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [float('inf')] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        self.printSolution(dist)

    # Driver program


# This code is contributed by Divyanshu Mehta

def main():
    g = Graph(9)
    g.graph = [
        [0, 4, 0, 0, 0, 0, 0, 8, 0],
        [4, 0, 8, 0, 0, 0, 0, 11, 0],
        [0, 8, 0, 7, 0, 4, 0, 0, 2],
        [0, 0, 7, 0, 9, 14, 0, 0, 0],
        [0, 0, 0, 9, 0, 10, 0, 0, 0],
        [0, 0, 4, 14, 10, 0, 2, 0, 0],
        [0, 0, 0, 0, 0, 2, 0, 1, 6],
        [8, 11, 0, 0, 0, 0, 1, 0, 7],
        [0, 0, 2, 0, 0, 0, 6, 7, 0]
    ]

    g.dijkstra(0)


if __name__ == '__main__':
    main()

# Output:
# Vertex tDistance from Source
# 0 t 0
# 1 t 4
# 2 t 12
# 3 t 19
# 4 t 21
# 5 t 11
# 6 t 9
# 7 t 8
# 8 t 14

参考

geeksForGeeks: https://www.geeksforgeeks.org/python-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/

发表于 Valine：

原题链接

https://leetcode-cn.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/

原题简要描述

给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，且恰好有 n - 1 条 edges 。树的根节点为节点 0 ，树上的每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ）

边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。

返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。

树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。

这道题目问题的描述有点绕，我第一遍没有读明白，后来才明白。

其实就是将树变成无环无向图，有一个顶点。所有的边都给你了，顶点用数字表示，数字对应一个字符串的索引，让你写出每个数字的子树上（包括这个数字的顶点本身），有多少个和这个数字对应索引的字符相同的。

代码

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
# 定义一个子函数
# 这个函数计算每一个节点为根的子树，所有标记的计数
# 因为用邻接表表示的边，我们为了防止边的重复访问，需要记录访问节点
# 因为没有环，所以我们只要记住前一个节点，在访问下一个节点的相邻节点的时候
# 不访问这个节点就可以了
# 参数为dfs(i, pre)， i就是这个节点的编号，pre就是前一个节点的编号
# 终止条件就是这个点的相邻节点都访问过了
# 这样我们在全局的一个数组变量中，更新相应的i的值即可
# 最后我们返回这个数组变量就是所求
# 利用了python中Counter有加法的api
# 我们可以简化代码
# 否则我们如果用字典，我们要遍历字典，把存在于本层的加上，不存在于本层的添加进来即可
# 稍微麻烦点
class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> \
            List[int]:
        edge_map = defaultdict(list)
        for e in edges:
            edge_map[e[0]].append(e[1])
            edge_map[e[1]].append(e[0])
        ans = [1] * n

        def dfs(i, pre):
            data = {labels[i]: 1}
            for nxt in edge_map[i]:
                if nxt != pre:
                    for k, v in dfs(nxt, i).items():
                        if k in data:
                            data[k] += v
                        else:
                            data[k] = v
            ans[i] = data[labels[i]]
            return data

        dfs(0, None)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> \
            List[int]:
        edge_map = defaultdict(list)
        for e in edges:
            edge_map[e[0]].append(e[1])
            edge_map[e[1]].append(e[0])
        ans = [1] * n

        def dfs(i, pre):
            data = Counter({labels[i]: 1})
            for nxt in edge_map[i]:
                if nxt != pre:
                    data += dfs(nxt, i)
            ans[i] = data[labels[i]]
            return data

        dfs(0, None)
        return ans