近期算法刷题总结

Dijkstra 算法，温故而知新

1.一道例题

先看题目：LeetCode 3342. 到达最后一个房间的最少时间 II

本质上都是求一个最短的路径，不过这里不是最短距离，而是最短时间。

个人写的算法如下，想说的都在注释里了：就是用一个堆加一个数组维护状态会更快。

python复制
from heapq import heappush, heappop
from math import inf
from line_profiler import profile

python复制
class Point:
    def __init__(self, time, x, y):
        self.time = time
        self.x = x
        self.y = y

    def __lt__(self, other):
        return self.time < other.time

    def get_adjacent(self, n, m):
        adjs = []
        for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_x = self.x + direction[0]
            new_y = self.y + direction[1]
            if new_x < 0 or new_x >= n:
                continue
            if new_y < 0 or new_y >= m:
                continue
            adjs.append((new_x, new_y))
        return adjs

    # 获取到达这个点的时间移动需要的时间（前提是相邻）
    def get_move_time(self):
        return 1

python复制
class Solution:
    @profile
    def minTimeToReach(self, moveTime) -> int:
        n = len(moveTime)
        m = len(moveTime[0])
      
        heap = [Point(0, 0, 0)] # 用一个小顶堆维护已经已知最短路径的点的集合
        # 由于用堆不好知道快速知道某个点的最短路径是多少，再用一个数组维护已知最短路径点的最小时间
        min_time = [[inf] * m for _ in range(n)]

        while True:
            # 先拿还没有遍历过的点中最短时间的点
            curr = heappop(heap)
            # 如果这个就是目标，说明到目标的最短时间已经找到
            if (curr.x, curr.y) == (n-1, m-1):
                return curr.time

            # 由于我们不好去更新堆的最小时间，所以有可能取出来没有更新过的时间，遇到这种情况直接跳过
            if curr.time > min_time[curr.x][curr.y]:
                continue

            # 遍历这个点的邻居
            for adj_x, adj_y in curr.get_adjacent(n, m):
                p_adj = Point(inf, adj_x, adj_y)
                time_to_adj = curr.time + p_adj.get_move_time() + max(moveTime[adj_x][adj_y] - curr.time, 0)
                if time_to_adj < min_time[adj_x][adj_y]:
                    # 更新最小时间数组
                    min_time[adj_x][adj_y] = time_to_adj
                    # 更新最小时间堆
                    p_adj.time = time_to_adj
                    heappush(heap, p_adj)

python复制
def test(l = 10):
    solver = Solution()
    moveTime = [[i + j for j in range(l)] for i in range(l)]
    # print(moveTime)
    print(solver.minTimeToReach(moveTime))

python复制
%reload_ext line_profiler
%lprun -f test test(100)

plaintext复制
    199  
    Timer unit: 1e-07 s    Total time: 0.199525 s
    File: C:\Users\18499\AppData\Local\Temp\ipykernel_14112\1144503081.py
    Function: test at line 1    Line #      Hits         Time  Per Hit   % Time  Line Contents
    ==============================================================
         1                                           def test(l = 10):
         2         1         11.0     11.0      0.0      solver = Solution()
         3         1      17694.0  17694.0      0.9      moveTime = [[i + j for j in range(l)] for i in range(l)]
         4                                               # print(moveTime)
         5         1    1977548.0    2e+06     99.1      print(solver.minTimeToReach(moveTime))

2.Dijkstra 算法正确性证明

之前上《算法设计与分析》课程的贪心算法章节的时候看过证明，当时没太懂，现在回顾了下证明，感觉还是挺好懂的。

课上讲的是 贪心选择性质 和 最优子结构性质 的证法。这里不再这么证了，现在我觉得这两个性质本质上就是在使用归纳法证明策略是最优的。

算法策略表示

$v_0,\ldots v_n$ ,要找到$v_0$ 到 $v_m$ 的最短路径。复习下最短路径算法的过程，设已找到的最短
路径的结点集合为$S$ ,未找到最短路径的结点集合为$T$ ,$V_0$到所有结点的最短路径数组为
dist ,初始状态$dist[0]=0,dist[1..n]=\infty$

重复以下步骤:

1.从集合$T$中基于dist中找到当前已知的最短路径结点$v_x$加入集合$S$中
2.基于$v_x$所相连的结点 更新dist数组，即

$$dist\left[v_y\right]=min(dist\left[v_y\right],dist\left[v_x\right]+W(v_x,v_y))$$

3.重复1、2步骤直到所有结点都加入集合$S$

证明

设算法迭代每一次加入集合$S$的结点依次为$v_{x_1},v_{x_2}\ldots v_{x_k}$证明每一次加入$S$中的结点都是最短路径

1.第一次加入的结点$v_{x_1}$显然是最短路径。

2.假设第K次加入的结点$v_{x_k}$为最短路径，此时集合S为$\{v_{x_1},v_{x_2},\ldots v_{x_k}\}$ ,现证明根据算法运行第k+ 1次加入的结点 $v_{x_{k+1}}$ 仍为最短路径。

3.反证，假设加入的点 $v_{x_{k+1}}$ 所对应的路径 $S$ -> $v_{x_{k+1}}$ 不是最短路径，即存在另外一条路径 $S$ -> $v_u$ -> $v_{x_{k+1}}$ 为最短路径，其中 $v_u$ 为该路径中不在集合 $S$ 中的结点，则 $dist\left[v_u\right]$ + $v_u$到$v_{x_{k+1}}$的路径长度 < $dist\left[v_{x_{k+1}}\right]$

然而，dijkstra的算法的第一个步骤是每次从集合T中基于dist选取距离最小的结点加入集合 $S$ ,因此 $dist\left[v_{x_{k+1}}\right]<=dist\left[v_{u}\right]$ ,因此产生矛盾。得证。

快速幂

因为觉得自己讲得肯定没有这个清楚，所以借用一下灵神的题解中的讲解：

O(logn)的算法。非常快。

代码实现

python复制
from line_profiler import profile

python复制
@profile
def quick_pow(x: float, n: int) -> float:
    ans = 1
    if n < 0:  # x^-n = (1/x)^n
        n = -n
        x = 1 / x
    while n:  # 从低到高枚举 n 的每个比特位
        if n & 1:  # 这个比特位是 1
            ans *= x  # 把 x 乘到 ans 中
        x *= x  # x 自身平方
        n >>= 1  # 继续枚举下一个比特位
    return ans

@profile
def simple_pow(x: float, n: int) -> float:
    ans = 1
    for i in range(n):
        ans *= x
    return ans

# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/powx-n/solutions/2858114/tu-jie-yi-zhang-tu-miao-dong-kuai-su-mi-ykp3i/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python复制
def test(x, n):
    result_quick = quick_pow(x, n)
    result_simple = simple_pow(x, n)
    print(result_quick == result_simple)

python复制
%reload_ext line_profiler
%lprun -f test test(1145, 1919)

plaintext复制
    True  
    Timer unit: 1e-07 s    Total time: 0.001734 s
    File: C:\Users\18499\AppData\Local\Temp\ipykernel_14112\631474956.py
    Function: test at line 1    Line #      Hits         Time  Per Hit   % Time  Line Contents
    ==============================================================
         1                                           def test(x, n):
         2         1       1312.0   1312.0      7.6      result_quick = quick_pow(x, n)
         3         1      14627.0  14627.0     84.4      result_simple = simple_pow(x, n)
         4         1       1401.0   1401.0      8.1      print(result_quick == result_simple)