跳转至

Algorithm

约 1 个字 预计阅读时间不到 1 分钟

  • 分类于 Algorithm
  • 需要 2 分钟阅读时间

Dijkstra算法

约 94 个字 64 行代码 1 张图片 预计阅读时间 1 分钟

Pasted image 20240717033502

技巧： 如果图为无向图（有向图反转）且不存在负边，要求求各个点 i 到同一终点 n 的最短路径，可以设置Dijkstra的起点和终点 均为 n，求解得到的 distance 数组即 各个点 i 到终点 n 的最短距离。

以743. 网络延迟时间为例

Dijkstra算法模版

Java 题解：

Java
 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 Solution {
    public int networkDelayTime(int[][] times, int n, int s) {
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        // 节点下标为 1 - n
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : times) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[s] = 0;
        boolean[] visted = new boolean[n + 1];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        heap.add(new int[]{s, 0});
        while (!heap.isEmpty()) {
            int u = heap.poll()[0];
            if (visted[u]) {
                continue;
            }
            visted[u] = true;
            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                int w = edge[1];
                if (!visted[v] && distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                    heap.add(new int[] {v, distance[u] + w});
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, distance[i]);
        }
        return ans;
    }
}

Python 题解：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, s: int) -> int:
        graph = [[] for _ in range(n + 1)]
        for u, v, w in times:
            graph[u].append((v, w))

        distance = [inf for _ in range(n + 1)]
        distance[s] = 0
        visited = [False for _ in range(n + 1)]

        heap = [(0, s)]
        while heap:
            _, u = heappop(heap)
            if visited[u]:
                continue
            visited[u] = True
            for v, w in graph[u]:
                if not visited[v] and distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w
                    heappush(heap, (distance[v], v))
        ans = max(distance[1:])
        return ans if ans < inf else -1
  • 分类于 Algorithm
  • 需要 1 分钟阅读时间

滑动窗口模版

约 21 个字 36 行代码 预计阅读时间 1 分钟

统一模版

Java
1
2
3
4
5
6
7
8
//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
        //当前考虑的元素
        while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}



模版题：3. 无重复字符的子串

Java题解

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int res = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            char ch = ss[right];
            while (set.contains(ch)) {
                set.remove(ss[left]);
                left++;
            }
            set.add(ss[right]);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

python题解

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        x = set()
        res, left = 0, 0
        for right in range(len(s)):
            while s[right] in x:
                x.remove(s[left])
                left += 1
            x.add(s[right])
            res = max(res, right - left + 1)
        return res