【算法】算法模板

作者：笔触狂放9 | 2024-07-20 11:02:06

踩

【算法】算法模板

算法模板

文章目录

算法模板

简介

博主在LeetCode网站中学习算法的过程中使用到并总结的算法模板，在算法方面算是刚过初学者阶段，竞赛分数仅2000。

为了节省读者的宝贵时间，部分基础的算法与模板未列出。当然也并非全面。

文章及代码存在不正不明之处还望指正。

数组

生成数组测试数据
区间合并
前缀和二维前缀和差分数组
二分查找(各种开闭区间组合)
回溯子集型(选或不选/选哪个) 组合型排列

    class ArrTemplates {


        class Generator {
            public void generateArr(int n, int max) {
                Random r = new Random();
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = r.nextInt(max);
                }
                System.out.println(Arrays.toString(arr));
            }

            public void generateArr(int m, int n, int max) {
                Random r = new Random();
                int[][] arr = new int[m][n];
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        arr[i][j] = r.nextInt(max);
                    }
                }
                for (int[] ints : arr) {
                    System.out.println(Arrays.toString(ints));
                }
            }
        }

        /**
         * 区间
         */
        class Interval {
            /**
             * 区间合并
             */
            List<int[]> intervalMerge(int[][] ranges) {
                int n = ranges.length;
                Arrays.sort(ranges, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
                List<int[]> rList = new ArrayList<>(n);
                int[] r1 = ranges[0];
                for (int i = 1; i < n; i++) {
                    int[] r2 = ranges[i];
                    if (r2[0] <= r1[1]) {
                        r1[1] = Math.max(r1[1], r2[1]);
                    } else {
                        rList.add(r1);
                        r1 = r2;
                    }
                }
                rList.add(r1);
                return rList;
            }

        }


        class PrefixSum {
            /**
             * 前缀和
             */
            public int[] getPreFix(int[] arr) {
                int n = arr.length;
                int[] pre = new int[n + 1];
                for (int i = 0; i < n; i++) {
                    pre[i + 1] = pre[i] + arr[i];
                }
                return pre;
            }

            /**
             * 二维前缀和
             */
            public int[][] getPrefix(int[][] matrix) {
                int m = matrix.length, n = matrix[0].length;
                int[][] pre = new int[m + 1][n + 1];
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + matrix[i][j];
                    }
                }
                return pre;
            }

            /**
             * 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和
             */
            public int query(int[][] pre, int r1, int c1, int r2, int c2) {
                return pre[r2 + 1][c2 + 1] - pre[r2 + 1][c1] - pre[r1][c2 + 1] + pre[r1][c1];
            }

            //差分数组
            public int[] getDiff(int n, int[] arr) {
                int[] diff = new int[n];
                diff[0] = arr[0];
                for (int i = 1; i < n; i++) {
                    diff[i] = arr[i] - arr[i - 1];
                }
//            for (int i = 1; i < n; i++) {
//                diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
//            }
                return diff;
            }

            int[] getDiff(int n, int[][] arr) {
                int[] diff = new int[n]; // 差分数组
                for (int[] q : arr) {
                    int l = q[0], r = q[1], x = q[2];
                    diff[l] += x;
                    if (r + 1 < n) {
                        diff[r + 1] -= x;
                    }
                }
                for (int i = 1; i < n; i++) {
                    diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
                }
                return diff;
            }


        }

        class BinarySearch {
            /**
             * 二分查找
             * 闭区间
             * 循环不变量:左侧小于等于目标值,右侧大于目标值
             * r-1<=target,l+1>target
             */
            int binarySearch(int[] nums, int target) {
                int l = 0, r = nums.length - 1;
                while (l <= r) {
                    int m = l + (r - l) / 2;
                    if (nums[m] < target) {
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                }
                return l;
            }

            /**
             * 左闭右开区间[l,r)
             * [l,mid) [mid+1,r)
             */
            int binarySearch2(int[] nums, int target) {
                int l = 0, r = nums.length;
                while (l < r) {
                    int m = l + (r - l) / 2;
                    if (nums[m] < target) {
                        l = m + 1;
                    } else {
                        r = m;
                    }
                }
                return l;
            }

            /**
             * 左开右闭区间(l,r]
             * (l,mid-1] (mid,r]
             */
            int binarySearch3(int[] nums, int target) {
                int l = -1, r = nums.length - 1;
                while (l < r) {
                    int m = l + (r - l) / 2;
                    if (nums[m] < target) {
                        l = m;
                    } else {
                        r = m - 1;
                    }
                }
                return l;
            }

            /**
             * 开区间(l,r)
             * (l,mid)(mid,r)
             */
            int binarySearch4(int[] nums, int target) {
                int l = -1, r = nums.length;
                while (l + 1 < r) {
                    int m = l + (r - l) / 2;
                    if (nums[m] < target) {
                        l = m;
                    } else {
                        r = m;
                    }
                }
                return r;
            }

        }

        class Backtrack {

            List<List<Integer>> res = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            int n;
            boolean[] visited = new boolean[n];

            /**
             * 子集型
             * 选或不选 n*2^n
             */
            void backtrack(int[] nums, int idx) {
                //解
                if (idx == n) {
                    res.add(new ArrayList<>(path));
                }
                //尝试 选或不选
                //不选
                backtrack(nums, idx + 1);
                //选
                path.add(nums[idx]);
                backtrack(nums, idx + 1);
                //回溯
                path.remove(path.size() - 1);
            }

            /**
             * 子集型
             * 每次选一个
             */
            void backtrack2(int[] nums, int idx) {
                //解
                res.add(new ArrayList<>(path));
                if (idx == n) {
                    return;
                }
                for (int i = idx; i < n; i++) {
                    path.add(nums[i]);
                    backtrack2(nums, i + 1);
                    //回溯
                    path.remove(path.size() - 1);
                }
            }

            /**
             * 组合型
             * 逆序排列
             */
            void backtrack(int[] nums, int idx, int k) {
                //剩余不足达到k个
                if (idx < k - path.size()) {
                    return;
                }
                if (path.size() == k) {
                    res.add(new ArrayList<>(path));
                    return;
                }
                for (int i = idx; i >= 0; i--) {
                    path.add(nums[i]);
                    backtrack(nums, i - 1, k);
                    //回溯
                    path.remove(path.size() - 1);
                }
            }

            /**
             * 组合型
             * 正序排列
             */
            void backtrack2(int[] nums, int idx, int k) {
                if (n - idx < k - path.size()) {
                    return;
                }
                if (path.size() == k) {
                    res.add(new ArrayList<>(path));
                    return;
                }
                for (int i = idx; i < n; i++) {
                    path.add(nums[i]);
                    backtrack2(nums, i + 1, k);
                    //回溯
                    path.remove(path.size() - 1);
                }
            }

            /**
             * 排列
             * Tn*n!
             */
            void backtrack3(int[] nums, int idx) {
                if (idx == n) {
                    res.add(new ArrayList<>(path));
                    return;
                }
                for (int i = 0; i < n; i++) {
                    if (!visited[i]) {
                        visited[i] = true;
                        path.add(nums[i]);
                        backtrack3(nums, idx + 1);
                        visited[i] = false;
                        path.remove(path.size() - 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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301

字符串

kmp字符串匹配
子串
回文串

class StringTemplates {
        /**
         * kmp
         */
        public int kmpSearchIndex(String source, String target) {
            int n = source.length(), m = target.length();
            if (m == 0) {
                return 0;
            }
            // 创建部分匹配表
            int[] kmp = new int[m];
            for (int i = 1, j = 0; i < m; i++) {
                // 字符不匹配时，j回溯到上一个匹配的字符，继续匹配
                while (j > 0 && target.charAt(i) != target.charAt(j)) {
                    j = kmp[j - 1];
                }
                // 当haystack和needle的字符匹配时，将j的值加一
                if (target.charAt(i) == target.charAt(j)) {
                    j++;
                }
                // 更新部分匹配表
                kmp[i] = j;
            }

            // 在haystack中查找needle
            for (int i = 0, j = 0; i < n; i++) {
                // 字符不匹 j回溯到上一个匹配的字符
                while (j > 0 && source.charAt(i) != target.charAt(j)) {
                    j = kmp[j - 1];
                }
                // 字符匹配时，已匹配字符数+1
                if (source.charAt(i) == target.charAt(j)) {
                    j++;
                }
                //找到needle
                if (j == m) {
                    return i - m + 1;
                }
            }

            // 没有找到needle，则返回-1
            return -1;
        }

        /**
         * 获取长度为len的所有子串
         */
        private String[] getSubstrings(String s, int len) {
            int n = s.length();
            String[] substrings = new String[n - len + 1];
            for (int j = 0; j <= n - len; j++) {
                substrings[j] = s.substring(j, j + len);
            }
            return substrings;
        }

        /**
         * 是否回文串
         */
        boolean isPalindrome(String str) {
            int left = 0, right = str.length() - 1;
            while (left < right) {
                if (str.charAt(left) != str.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

        /**
         * 是否回文串
         */
        private boolean isPalindrome(char[] ss, int l, int r) {
            if (l == r) {
                return true;
            }
            while (l < r) {
                if (ss[l++] != ss[r--]) {
                    return false;
                }
            }
            return true;
        }


        /**
         * 字符串任意子串是否回文串
         */
        boolean[][] palindrome(char[] cs) {
            int n = cs.length;

            boolean[][] p = new boolean[n][n];
            //1
//            for (int i = 0; i < n; i++) {
//                Arrays.fill(p[i], true);
//            }
//            for (int i = n - 1; i >= 0; i--) {
//                for (int j = i + 1; j < n; ++j) {
//                    p[i][j] = cs[i] == cs[j] && p[i + 1][j - 1];
//                }
//            }
            //2
            for (int len = 1; len <= n; len++) {
                //从i开始,统计长度为len的子串是否为回文串
                for (int i = 0; i <= n - len; i++) {
                    int j = i + len - 1;
                    if (len == 1) {
                        p[i][j] = true;
                    } else if (len == 2) {
                        p[i][j] = cs[i] == cs[j];
                    } else {
                        // 大于两个字符时，判断首尾字符是否相等，并且去除首尾字符后的子串是否是回文串
                        p[i][j] = cs[i] == cs[j] && p[i + 1][j - 1];
                    }
                }
            }
            return p;
        }

    }
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
118
119
120
121
122

列表

翻转
快慢指针

    class ListTemplates {

        /**
         * 翻转链表
         */
        public void reverse(ListNode head, ListNode tail) {
            ListNode last = null;
            ListNode curr = head;
            ListNode end = tail.next;
            while (curr != end) {
                //下一个节点
                ListNode next = curr.next;
                //将当前节点的指针指向前一个节点
                curr.next = last;
                //将当前节点置位下一个节点的前置
                last = curr;
                //循环控制
                curr = next;
            }
        }

        /**
         * 快慢指针
         */
        boolean fast_slowPoints(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (slow != null && fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    return true;
                }
            }
            return false;
        }
    }
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

数学

最大/小值
lcm
gcd
快速幂
lowbit
质数/素数(埃氏筛)
回文数
组合数

    class MathTemplates {

        /**
         * min
         */
        public int min(int a, int... b) {
            for (int i : b) {
                a = Math.min(a, i);
            }
            return a;
        }

        /**
         * max
         */
        public int max(int a, int... b) {
            for (int i : b) {
                a = Math.max(a, i);
            }
            return a;
        }

        /**
         * 最小公倍数 Lowest Common Multiple
         */
        private long lcm(long a, long b) {
            return a * b / gcd(a, b);
        }

        /**
         * 最大公约数 Greatest common divisor
         */
        public long gcd(long x, long y) {
            return y == 0 ? x : gcd(y, x % y);
        }

        /**
         * 快速幂
         */
        public double fastPow(double x, long n) {
            double res = 1.0;
            while (n > 0) {
                if (n % 2 == 1) {
                    res *= x;
                }
                x *= x;
                n /= 2;
            }
            return res;
        }

        /**
         * 快速幂
         */
        public long fastPow(long x, long n) {
            long res = 1;
            while (n > 0) {
                if (n % 2 == 1) {
                    res *= x;
                }
                x *= x;
                n /= 2;
            }
            return res;
        }

        public int lowbit(int i) {
            //x & (~x + 1);
            return i & -i;
        }

        /**
         * 二进制1个数
         * Integer.bitCount(i)
         */
        public int bitCount(int i) {
            i = i - ((i >>> 1) & 0x55555555);
            i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
            i = (i + (i >>> 4)) & 0x0f0f0f0f;
            i = i + (i >>> 8);
            i = i + (i >>> 16);
            return i & 0x3f;
        }

        /**
         * 是否质数
         */
        private boolean isPrime(int n) {
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }

        private boolean isPrime2(int n) {
            // 小于等于1的整数不是素数
            if (n <= 1) {
                return false;
            }
            // 2和3是素数
            if (n <= 3) {
                return true;
            }
            // 如果整数能被2或3整除，不是素数
            if (n % 2 == 0 || n % 3 == 0) {
                return false;
            }
            // 除了2和3，素数都可以表示成6的倍数加1或减1的形式(在6的倍数两侧的数不是素数)
            for (int i = 5; i * i <= n; i += 6) {
                if (n % i == 0 || n % (i + 2) == 0) {
                    return false;
                }
            }

            return true;
        }

        boolean[] isPrime;

        /**
         * 质数表-埃氏筛
         * Tnlog(logn) Sn
         */
        private void getPrimes(int n) {
            isPrime = new boolean[n];
            Arrays.fill(isPrime, true);
            isPrime[1] = false;
            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (isPrime[i]) {
                    // 将 i 的所有倍数标记为非质数(合数)
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }

        /**
         * 回文数
         */
        public boolean isPalindrome(int x) {
            if (x < 0 || x % 10 == 0 && x != 0) {
                return false;
            }
            int reverse = 0;
            while (x > reverse) {
                reverse = reverse * 10 + x % 10;
                x /= 10;
            }
            return x == reverse || x == reverse / 10;
        }


        private final int N = 31;
        private final int[][] c = new int[N][N];

        {
            for (int i = 0; i < N; i++) {
                c[i][0] = c[i][i] = 1;
                for (int j = 1; j < i; j++) {
                    //Cn,k = Cn-1,k-1 + Cn-1,k
                    c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                }
            }
        }


        /**
         * 计算n个数里拿k个数的组合数
         */
        public long comb(int n, int k) {
            long ans = 1;
            for (int i = 1; i <= k; i++) {
                ans *= (n - k + i);
                ans /= i;
            }
            return ans;
        }


    }
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

树

树状数组

    class TreeTemplates {


        /**
         * 树状数组
         */
        class BinaryIndexedTrees {
            private int[] tree;
            private int[] nums;

            /**
             * TOnlogn
             */
            public BinaryIndexedTrees(int[] nums) {
                //lowbit(0)计算为0;舍弃0下标;
                this.tree = new int[nums.length + 1];
                this.nums = nums;
                for (int i = 0; i < nums.length; i++) {
                    add(i + 1, nums[i]);
                }
            }

            /**
             * TOlogn
             */
            public void update(int index, int val) {
                add(index + 1, val - nums[index]);
                nums[index] = val;
            }

            /**
             * TOlogn
             */
            public int sumRange(int left, int right) {
                return prefixSum(right + 1) - prefixSum(left);
            }

            /**
             * 用于计算树状数组的 x节点的父节点
             * x的父节点索引= x+=lowbit(x)
             * lowbit(x) 未 非负整数x在二进制下的最低为1及其后面的0构成的数(x的除最后一位1外,其他位置0)
             */
            private int lowBit(int x) {
                //return x & (~x + 1);
                return x & -x;
            }

            private void add(int index, int val) {
                while (index < tree.length) {
                    tree[index] += val;
                    index += lowBit(index);
                }
            }

            private int prefixSum(int index) {
                int sum = 0;
                while (index > 0) {
                    sum += tree[index];
                    index -= lowBit(index);
                }
                return sum;
            }
        }
    }
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

图

无向图/带权图领接矩阵/表
并查集
Dijkstra
Floyd

    class GraphTemplates {


        /**
         * 无向图
         */
        public List<Integer>[] edgesToGraph(int n, int[][] edges) {
            List<Integer>[] graph = new List[n];
            Arrays.setAll(graph, i -> new ArrayList<>());
            for (int[] edge : edges) {
                int x = edge[0];
                int y = edge[1];
                graph[x].add(y);
                graph[y].add(x);
            }
            return graph;
        }

        /**
         * 带权图
         */
        public List<int[]>[] edgesToWGraph(int n, int[][] edges) {
            List<int[]>[] wgraph = new List[n];
            Arrays.setAll(wgraph, i -> new ArrayList<>());
            for (int[] edge : edges) {
                int x = edge[0];
                int y = edge[1];
                int w = edge[2];
                wgraph[x].add(new int[]{y, w});
                wgraph[y].add(new int[]{x, w});
            }
            return wgraph;
        }

        /**
         * 带权领接矩阵
         */
        public int[][] edgesToWGraph2(int n, int[][] edges) {
            int INF = Integer.MAX_VALUE / 2;
            int[][] graph = new int[n][n];
            for (int i = 0; i < n; i++) {
                Arrays.fill(graph[i], INF);
            }
            for (int[] edge : edges) {
                graph[edge[0]][edge[1]] = edge[2];
            }
            return graph;
        }


        /**
         * 并查集
         */
        class UnionFind {
            int[] fa;

            public UnionFind(int n) {
                fa = new int[n];
                for (int i = 0; i < n; i++) {
                    fa[i] = i;
                }
            }

            public int find(int x) {
                if (fa[x] == x) {
                    return x;
                }
                return fa[x] = find(fa[x]);
            }


            boolean union(int x, int y) {
                int fx = find(x), fy = find(y);
                if (fx == fy) {
                    return false;
                }
                if (fx > fy) {
                    fa[fy] = fx;
                } else {
                    fa[fx] = fy;
                }
                return true;
            }

        }

        /**
         * 长度统计 联通分量统计 高度压缩 并查集
         */
        class UnionFind2 {
            //父节点
            int[] fa;
            //高度
            int[] rk;
            //子集长度
            int[] sz;
            //连通分量数
            int count;

            public UnionFind2(int n) {
                fa = new int[n];
                rk = new int[n];
                sz = new int[n];
                for (int i = 0; i < n; i++) {
                    fa[i] = i;
                    sz[i] = 1;
                }
                count = n;
            }

            public int find(int x) {
                if (fa[x] == x) {
                    return x;
                }
                return fa[x] = find(fa[x]);
            }


            boolean union(int x, int y) {
                int fx = find(x), fy = find(y);
                if (fx == fy) {
                    return false;
                }
                //如果 x的高度大于 y，则令 y的上级为 x
                if (rk[fx] > rk[fy]) {
                    fa[fy] = fx;
                    sz[fx] += sz[fy];
                } else {
                    //如果 x的高度和 y的高度相同，则令 y的高度加1
                    if (rk[fx] == rk[fy]) {
                        rk[fy]++;
                    }
                    fa[fx] = fy;
                    sz[fy] += sz[fx];
                }
                count--;
                return true;
            }

            public boolean isSame(int x, int y) {
                return find(x) == find(y);
            }

            public int size(int x) {
                return sz[find(x)];
            }

            public int count() {
                return count;
            }
        }

        class Dijkstra {
            /**
             * dijkstra 统计单源最短路径长度
             */
            public long dijkstraCalculateLenOfShortestPaths(int n, int[][] edges, int start, int end) {
                List<int[]>[] wgraph = edgesToWGraph(n, edges);
                //最短路径长度,最短路径次数
                long[] dist = new long[n];
                Arrays.fill(dist, Long.MAX_VALUE);
                dist[start] = 0;

                PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
                //节点,权重
                pq.offer(new long[]{start, 0});

                while (!pq.isEmpty()) {
                    long[] node = pq.poll();
                    int u = (int) node[0];
                    //s到达u的最短路径权重
                    long suw = node[1];
                    //此路径不是到达u的最短路径
                    if (suw > dist[u]) {
                        continue;
                    }
                    for (int[] edge : wgraph[u]) {
                        int v = edge[0], uvw = edge[1];
                        //s到达v的最短路径权重
                        long svw = dist[v];
                        if (suw + uvw < svw) {
                            dist[v] = suw + uvw;
                            pq.offer(new long[]{v, dist[v]});
                        }
                    }
                }
                return dist[end];
            }


            /**
             * dijkstra 统计单源最短路径数量
             */
            public int dijkstraCalculateCount0fShortestPaths(int n, int[][] edges, int start, int end) {
                List<int[]>[] wgraph = edgesToWGraph(n, edges);
                //最短路径长度,最短路径次数
                long[] dist = new long[n];
                Arrays.fill(dist, Long.MAX_VALUE);
                dist[start] = 0;

                int[] counts = new int[n];
                counts[start] = 1;

                PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
                //节点,权重
                pq.offer(new long[]{start, 0});

                while (!pq.isEmpty()) {
                    long[] node = pq.poll();
                    int u = (int) node[0];
                    //s到达u的最短路径权重
                    long suw = node[1];
                    //此路径不是到达u的最短路径
                    if (suw > dist[u]) {
                        continue;
                    }
                    for (int[] edge : wgraph[u]) {
                        int v = edge[0], uvw = edge[1];
                        //s到达v的最短路径权重
                        long svw = dist[v];
                        //s到达u的最短路径数量
                        int suc = counts[u];
                        if (suw + uvw < svw) {
                            dist[v] = suw + uvw;
                            counts[v] = suc;
                            pq.offer(new long[]{v, dist[v]});
                        } else if (suw + uvw == svw) {
                            counts[v] = (counts[v] + suc) % 1000000007;
                        }
                    }
                }

                return counts[end];
            }

            /**
             * dijkstra 单元 统计最短路径长度与数量
             */
            public long[][] dijkstraCalculateLenAndCount0fShortestPaths(int n, int[][] edges) {
                List<int[]>[] wgraph = edgesToWGraph(n, edges);
                //最短路径长度,最短路径次数
                long[][] dist = new long[n][2];
                Arrays.setAll(dist, i -> new long[]{Long.MAX_VALUE, 0});
                dist[0] = new long[]{0, 1};

                PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
                //节点,权重
                pq.offer(new long[]{0, 0});

                while (!pq.isEmpty()) {
                    long[] node = pq.poll();
                    int u = (int) node[0];
                    //s到达u的最短路径权重
                    long suw = node[1];
                    //此路径不是到达u的最短路径
                    if (suw > dist[u][0]) {
                        continue;
                    }
                    for (int[] edge : wgraph[u]) {
                        int v = edge[0], uvw = edge[1];
                        //s到达v的最短路径权重
                        long svw = dist[v][0];
                        //s到达u的最短路径数量
                        long suc = dist[u][1];
                        if (suw + uvw < svw) {
                            dist[v][0] = suw + uvw;
                            dist[v][1] = suc;
                            pq.offer(new long[]{v, dist[v][0]});
                        } else if (suw + uvw == svw) {
                            dist[v][1] = (dist[v][1] + suc) % 1000000007;
                        }
                    }
                }

                return dist;
            }

            /**
             * 稠密图 邻接矩阵
             */
            public int[] dijkstra(int n, int[][] edges, int start) {
                int INF = Integer.MAX_VALUE / 2;
                int[][] graph = new int[n][n];
                int[] dist = new int[n];
                for (int i = 0; i < n; i++) {
                    Arrays.fill(graph[i], INF);
                    dist[i] = INF;
                }
                for (int[] edge : edges) {
                    graph[edge[0]][edge[1]] = edge[2];
                }

                boolean[] vis = new boolean[n];
                dist[start] = 0;

                for (int i = 0; i < n; i++) {
                    // 找到当前距离最小的未访问节点
                    int x = -1;
                    for (int y = 0; y < n; ++y) {
                        if (!vis[y] && (x == -1 || dist[y] < dist[x])) {
                            x = y;
                        }
                    }
                    // 访问标记
                    vis[x] = true;
                    for (int y = 0; y < n; ++y) {
                        // 更新最短路长度
                        dist[y] = Math.min(dist[y], dist[x] + graph[x][y]);
                    }
                }

                return dist;
            }

        }

        //多源最短路径
        class Floyd {
            public int[][] floyd(int n, int[][] edges) {
                int INF = Integer.MAX_VALUE;
                int[][] dist = new int[n][n];
                for (int i = 0; i < n; ++i) {
                    Arrays.fill(dist[i], INF);
                    dist[i][i] = 0;
                }
                for (int[] e : edges) {
                    dist[e[0]][e[1]] = e[2];
                }
                for (int k = 0; k < n; k++) {
                    for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                            if (dist[i][k] == INF || dist[k][j] == INF) {
                                continue;
                            }
                            dist[i][j] = Math.max(dist[i][j], dist[i][k] + dist[k][j]);
                        }
                    }
                }
                return dist;
            }

        }


        class Prim {
            public void primMST(int n, int[][] edges) {

            }
        }
    }
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350

动态规划

爬楼梯
打家劫舍
子数组
子序列
背白 01背包完全背包
划分
区间

    class DpTemplates {

        /**
         * 入门
         * 爬楼梯 打家劫舍
         */
        class Base {

            /**
             * 爬楼梯-每次相同方式二选一
             */
            public int climbingStairs(int n) {
                int[] dp = new int[n + 1];
                dp[0] = 1;
                dp[1] = 1;
                for (int i = 2; i <= n; i++) {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                return dp[n];

            /*int p1 = 0, p2 = 1;
            for (int i = 1; i <= n; i++) {
                p2 += p1;
                p1 = p2 - p1;
            }
            return p2;*/
            }

            /**
             * 花费代价爬楼梯 每次相同方式二选一,并选择较少消费
             */
            public int climbingStairsByMinCost(int[] cost) {
                int len = cost.length;
                for (int i = 2; i < len; i++) {
                    cost[i] = Math.min(cost[i - 1], cost[i - 2]) + cost[i];
                }
                return Math.min(cost[len - 1], cost[len - 2]);
            }


            /**
             * 打家劫舍 根据要求选或不选
             */
            public int rob(int[] nums) {
                int[] dp = new int[2];
                for (int num : nums) {
                    //选 上一个只能是不选
                    int doit = dp[1] + num;
                    //不选 上一个选或不选
                    int not = Math.max(dp[0], dp[1]);
                    dp[0] = doit;
                    dp[1] = not;
                }
                return Math.max(dp[0], dp[1]);
            }

        }

        /**
         * 子数组dp
         */
        class Subarray {

            /**
             * 子数组最大值
             */
            public int maxSubArrayDp(int[] nums) {
                int[] dp = new int[nums.length];
                dp[0] = nums[0];
                int res = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                    res = Math.max(res, dp[i]);
                }
                return res;
            }

            /**
             * 子数组最大值
             */
            public int maxSubArray(int[] nums) {
                int max = nums[0];
                int pre = max;
                for (int i = 1; i < nums.length; i++) {
                    pre = Math.max(pre + nums[i], nums[i]);
                    max = Math.max(max, pre);
                }
                return max;
            }


            /**
             * 单调递增/减 最长子数组
             */
            public int longestMonotonicSubarray(int[] nums) {
                int res = 1;
                int i = 0, n = nums.length;
                while (i < n - 1) {
                    //相等直接跳过
                    if (nums[i + 1] == nums[i]) {
                        i++;
                        continue;
                    }
                    // 记录开始位置
                    int start = i;
                    //定下基调：递增/递减
                    boolean inc = nums[i + 1] > nums[i];
                    // i 和 i+1 已经满足要求，从 i+2 开始判断
                    i += 2;
                    while (i < n && nums[i] != nums[i - 1] && (nums[i] > nums[i - 1]) == inc) {
                        i++;
                    }
                    // 从 start 到 i-1 是满足题目要求的（并且无法再延长的）子数组
                    res = Math.max(res, i - start);
                    i--;
                }
                return res;
            }
        }

        /**
         * 子序列dp
         */
        class Subsequence {

            /**
             * 最长公共子序列LCS
             */
            public int longestCommonSubsequence(int[] arr1, int[] arr2) {
                int m = arr1.length, n = arr2.length;
                int[][] dp = new int[m + 1][n + 1];

                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        dp[i + 1][j + 1] = arr1[i] == arr2[j] ? dp[i][j] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);
                    }
                }

                return dp[m][n];
            }

            /**
             * 子序列数量
             */
            public int diffSubsequenceCount(int[] arr1, int[] arr2) {
                int MOD = 1_000_000_007;
                int m = arr1.length;
                int n = arr2.length;
                int[][] dp = new int[m + 1][n + 1];
                //init
                for (int i = 0; i <= m; i++) {
                    dp[i][0] = 1;
                }
                for (int i = 1; i <= m; i++) {
                    for (int j = 1; j <= i && j <= n; j++) {
                        dp[i][j] = dp[i - 1][j];
                        if (arr1[i - 1] == arr2[j - 1]) {
                            dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
                        }
                    }
                }
                return dp[m][n];
            }

            /**
             * 最长递增子序列 LIS
             */
            public int longestIncreasingSubsequence(int[] nums) {
                int n = nums.length;
                int[] dp = new int[n];
                int res = 0;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < i; j++) {
                        if (nums[j] < nums[i]) {
                            dp[i] = Math.max(dp[i], dp[j] + 1);
                        }
                    }
                    res = Math.max(res, dp[i]);
                }
                return res + 1;
            }


        }


        /**
         * 背包dp
         */
        class Knapsack {

            /**
             * 01背包
             */
            public int zeroOneKnapsack(int[] ws, int[] vs, int c) {
                int n = ws.length;
                int[][] dp = new int[n + 1][c + 1];
                dp[0][0] = 1;
                // 动态规划求解
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= c; j++) {
                        if (ws[i - 1] > j) {
                            dp[i][j] = dp[i - 1][j];
                        } else {
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - ws[i - 1]] + vs[i - 1]);
                        }
                    }
                }

                return dp[n][c];
            }

            /**
             * 完全背包
             */
            public int completeKnapsack(int[] ws, int[] vs, int c) {
                int n = ws.length;
                int[][] dp = new int[n + 1][c + 1];
                dp[0][0] = 1;
                // 动态规划求解
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= c; j++) {
                        if (ws[i - 1] > j) {
                            // 物品 i 不被选入背包
                            dp[i][j] = dp[i - 1][j];
                        } else {
                            // 物品 i 被选入背包
                            // 可以重复选取，所以是 dp[i][j - weights[i - 1]] + values[i - 1]
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - ws[i - 1]] + vs[i - 1]);
                        }
                    }
                }
                return dp[n][c];
            }
        }


        /**
         * 划分dp
         */
        class Partition {

            /**
             * 能否划分
             * f[i] 表示 a[:i]能否划分;
             * 枚举最右侧划分左端l,判断a[l,i]是否符合条件
             * f[i] = min/max(f[i],f[l-1]+1)
             */
            boolean canPartition(int[] nums) {
                int n = nums.length;
                boolean[] dp = new boolean[n + 1];
                dp[0] = true;
                for (int i = 1; i <= n; i++) {
                    for (int l = 0; l <= i; l++) {
                        if (dp[l] && check(nums, l, i)) {//num[l:i] 是否符合条件
                            dp[i] = true;
                            break;
                        }
                    }
                }
                return dp[n];
            }


            /**
             * 划分个数  f[i] 表示a[:i]在约束下 能划分的最大/小个数
             * 枚举右侧划分左端l,判断a[l,i]是否符合条件
             * f[i] = min/max(f[i],f[l-1]+1)
             */
            int partitionNum(int[] nums) {
                int n = nums.length;
                int[] dp = new int[n + 1];
                for (int i = 0; i < n; i++) {
                    dp[i + 1] = dp[i] + 1;
                    for (int l = 0; l <= i; l++) {
                        //符合划分条件
                        if (check(nums, l, i)) {
                            //min / max
                            dp[i + 1] = Math.min(dp[i + 1], dp[l] + 1);
                        }
                    }
                }
                return dp[n];
            }

            /**
             * 约束划分数量  划分为k个,计算最优解;
             * f[i][j]: 将a[:i]划分为j个部分的最优解;
             * 枚举右侧左端l,从f[l][j-1]转移到f[i][j],考虑最最优解的影响
             */
            public int partitionCnt(int[] nums, int k) {
                int n = nums.length;
                int[] pre = new int[n + 1];
                for (int i = 0; i < n; i++) {
                    pre[i + 1] = pre[i] + nums[i];
                }

                int[][] dp = new int[n + 1][k + 1];
                for (int i = 0; i <= n; i++) {
                    Arrays.fill(dp[i], Integer.MAX_VALUE);
                }

                dp[0][0] = 0;
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= Math.min(i, k); j++) {
                        for (int l = j - 1; l < i; l++) {
                            //最小化 划分子数组的和
                            dp[i][j] = Math.min(dp[i][j], Math.max(dp[l][j - 1], pre[i] - pre[l]));
                        }
                    }
                }
                return dp[n][k];
            }

            /**
             * 约束划分长度 子数组长度<=k时,最大和
             * f[i] 表示nums[:i] 划分后,子数组最大值
             * 枚举最后子数组左端点l
             * f[i] = f[r]+val
             */
            public int partitionLen(int[] nums, int k) {
                int n = nums.length;
                int[] dp = new int[n + 1];
                for (int i = 1; i <= n; i++) {
                    //逆序维护区间最大值
                    int max = 0;
                    for (int l = i - 1; l >= i - k && l >= 0; l--) {
                        max = Math.max(max, nums[l]);
                        dp[i] = Math.max(dp[i], dp[l] + max * (i - l));
                    }
                }
                return dp[n];
            }


            private boolean check(int[] nums, int l, int r) {
                return true;
            }

            /**
             * 区间不相交划分 限定区间范围(1~n)或 [is[0],is[1]]区间范围较小
             */
            public long intervalPartition(int n, int[][] is) {
                //按区间结束排序
                List<int[]>[] list = new List[n + 1];
                for (int[] interval : is) {
                    if (list[interval[1]] == null) {
                        list[interval[1]] = new ArrayList<>();
                    }
                    list[interval[1]].add(new int[]{interval[0], interval[1] - interval[0] + interval[2]});
                }

                //dpi 表示 到达第i个点时,能获得的最大价值
                long[] dp = new long[n + 1];
                for (int i = 1; i <= n; i++) {
                    dp[i] = dp[i - 1];
                    if (list[i] == null) {
                        continue;
                    }
                    for (int[] r : list[i]) {
                        dp[i] = Math.max(dp[i], dp[r[0]] + r[1]);
                    }
                }
                return dp[n];
            }

            /**
             * 区间不相交划分  [is[0],is[1]]区间范围较大时
             */
            public int intervalPartition(int[][] is) {
                int n = is.length;
                //按区间排序
                Arrays.sort(is, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);

                //dpi: 在i项中 能获得的最大价值
                int[] dp = new int[n + 1];
                for (int i = 0; i < n; i++) {
                    int s = is[i][0], p = is[i][2];
                    //二分找到上一个区间
                    int l = 0, r = i - 1;
                    while (l <= r) {
                        int m = l + (r - l) / 2;
                        //可无缝衔接<=,否则<
                        if (is[m][1] <= s) {
                            l = m + 1;
                        } else {
                            r = m - 1;
                        }
                    }

                    dp[i + 1] = Math.max(dp[i], dp[r + 1] + p);
                }

                return dp[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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401

在这里插入图片描述

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/856548