Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit f665919

Browse files
committed
clean code
1 parent 18be595 commit f665919

File tree

11 files changed

+189
-57
lines changed

11 files changed

+189
-57
lines changed

‎leetcode/leetcode-06/src/main/java/Solution581.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,4 +24,6 @@ public int findUnsortedSubarray(int[] nums) {
2424
2525
排序 + 双指针
2626
时间复杂度 O(nlogn)
27+
相似题目: 3555ドル. 排序每个滑动窗口中最小的子数组
28+
https://leetcode.cn/problems/smallest-subarray-to-sort-in-every-sliding-window/description/
2729
*/

‎leetcode/leetcode-16/src/main/java/Solution1561.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,4 +34,6 @@ public int maxCoins(int[] piles) {
3434
时间复杂度 O(nlogn)。
3535
相似题目: 3457. 吃披萨
3636
https://leetcode.cn/problems/eat-pizzas/description/
37+
3627. 中位数之和的最大值
38+
https://leetcode.cn/problems/maximum-median-sum-of-subsequences-of-size-3/description/
3739
*/

‎leetcode/leetcode-33/src/test/java/Solution3213Tests.java

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,17 +2,17 @@
22
import org.junit.jupiter.api.Test;
33

44
public class Solution3213Tests {
5-
private final Solution3213.V1 solution_v1 = new Solution3213.V1();
6-
private final Solution3213.V2 solution_v2 = new Solution3213.V2();
5+
private final Solution3213.V1 solution3213_v1 = new Solution3213.V1();
6+
private final Solution3213.V2 solution3213_v2 = new Solution3213.V2();
77

88
@Test
99
public void example1() {
1010
String target = "abcdef";
1111
String[] words = {"abdef", "abc", "d", "def", "ef"};
1212
int[] costs = {100, 1, 1, 10, 5};
1313
int expected = 7;
14-
Assertions.assertEquals(expected, solution_v1.minimumCost(target, words, costs));
15-
Assertions.assertEquals(expected, solution_v2.minimumCost(target, words, costs));
14+
Assertions.assertEquals(expected, solution3213_v1.minimumCost(target, words, costs));
15+
Assertions.assertEquals(expected, solution3213_v2.minimumCost(target, words, costs));
1616
}
1717

1818
@Test
@@ -21,8 +21,8 @@ public void example2() {
2121
String[] words = {"z", "zz", "zzz"};
2222
int[] costs = {1, 10, 100};
2323
int expected = -1;
24-
Assertions.assertEquals(expected, solution_v1.minimumCost(target, words, costs));
25-
Assertions.assertEquals(expected, solution_v2.minimumCost(target, words, costs));
24+
Assertions.assertEquals(expected, solution3213_v1.minimumCost(target, words, costs));
25+
Assertions.assertEquals(expected, solution3213_v2.minimumCost(target, words, costs));
2626
}
2727

2828
// 补充用例
@@ -35,7 +35,7 @@ public void example3() {
3535
String[] words = UtUtils.loadingStrings(fileName, 1);
3636
int[] costs = UtUtils.loadingInts(fileName, 2);
3737
int expected = 4614;
38-
Assertions.assertEquals(expected, solution_v1.minimumCost(target, words, costs));
38+
Assertions.assertEquals(expected, solution3213_v1.minimumCost(target, words, costs));
3939
}
4040

4141
@Test
@@ -47,6 +47,6 @@ public void example4() {
4747
String[] words = UtUtils.loadingStrings(fileName, 1);
4848
int[] costs = UtUtils.loadingInts(fileName, 2);
4949
int expected = -1;
50-
Assertions.assertEquals(expected, solution_v1.minimumCost(target, words, costs));
50+
Assertions.assertEquals(expected, solution3213_v1.minimumCost(target, words, costs));
5151
}
5252
}
Lines changed: 154 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,55 +1,163 @@
1+
import java.util.ArrayDeque;
2+
import java.util.ArrayList;
3+
import java.util.Arrays;
14
import java.util.List;
5+
import java.util.Queue;
26

37
public class Solution3376 {
4-
public int findMinimumTime(List<Integer> strength, int K) {
5-
int n = strength.size();
6-
int[] strengths = strength.stream().mapToInt(Integer::intValue).toArray();
7-
int[] permute = new int[n];
8-
for (int i = 0; i < n; i++) permute[i] = i;
9-
10-
int ans = Integer.MAX_VALUE;
11-
int maxRound = 1;
12-
for (int i = 2; i <= n; i++) maxRound *= i;
13-
for (int i = 0; i < maxRound; i++) {
14-
ans = Math.min(ans, getAns(strengths, K, permute));
15-
nextPermutation(permute);
8+
// 209ms
9+
static class V1 {
10+
public int findMinimumTime(List<Integer> strength, int K) {
11+
int n = strength.size();
12+
int[] strengths = strength.stream().mapToInt(Integer::intValue).toArray();
13+
int[] permute = new int[n];
14+
for (int i = 0; i < n; i++) permute[i] = i;
15+
16+
int ans = Integer.MAX_VALUE;
17+
int maxRound = 1;
18+
for (int i = 2; i <= n; i++) maxRound *= i;
19+
for (int i = 0; i < maxRound; i++) {
20+
ans = Math.min(ans, getAns(strengths, K, permute));
21+
nextPermutation(permute);
22+
}
23+
return ans;
1624
}
17-
return ans;
18-
}
1925

20-
int getAns(int[] strengths, int k, int[] permute) {
21-
int n = strengths.length;
22-
int res = 0;
23-
int x = 1;
24-
for (int i = 0; i < n; i++) {
25-
int stre = strengths[permute[i]];
26-
// k*b >= stre
27-
res += (stre + x - 1) / x;
28-
x += k;
26+
private int getAns(int[] strengths, int k, int[] permute) {
27+
int n = strengths.length;
28+
int res = 0;
29+
int x = 1;
30+
for (int i = 0; i < n; i++) {
31+
int stre = strengths[permute[i]];
32+
// k*b >= stre
33+
res += (stre + x - 1) / x;
34+
x += k;
35+
}
36+
return res;
2937
}
30-
return res;
31-
}
3238

33-
private void nextPermutation(int[] a) {
34-
int n = a.length;
35-
int i = n - 2;
36-
while (i >= 0 && a[i] >= a[i + 1]) i--;
37-
if (i < 0) return;
38-
int j = n - 1;
39-
while (j >= 0 && a[i] >= a[j]) j--;
40-
swap(a, i, j);
41-
reverse(a, i + 1);
42-
}
39+
private void nextPermutation(int[] a) {
40+
int n = a.length;
41+
int i = n - 2;
42+
while (i >= 0 && a[i] >= a[i + 1]) i--;
43+
if (i < 0) return;
44+
int j = n - 1;
45+
while (j >= 0 && a[i] >= a[j]) j--;
46+
swap(a, i, j);
47+
reverse(a, i + 1);
48+
}
4349

44-
private void swap(int[] a, int l, int r) {
45-
int tmp = a[l];
46-
a[l] = a[r];
47-
a[r] = tmp;
50+
private void swap(int[] a, int l, int r) {
51+
int tmp = a[l];
52+
a[l] = a[r];
53+
a[r] = tmp;
54+
}
55+
56+
private void reverse(int[] a, int st) {
57+
for (int l = st, r = a.length - 1; l < r; l++, r--) {
58+
swap(a, l, r);
59+
}
60+
}
4861
}
4962

50-
private void reverse(int[] a, int st) {
51-
for (int l = st, r = a.length - 1; l < r; l++, r--) {
52-
swap(a, l, r);
63+
// 13ms
64+
static class V2 {
65+
static class neighbor {
66+
int to, rid, cap, cost; // rid 为反向边在邻接表中的下标
67+
68+
public neighbor(int to, int rid, int cap, int cost) {
69+
this.to = to;
70+
this.rid = rid;
71+
this.cap = cap;
72+
this.cost = cost;
73+
}
74+
}
75+
76+
private static final int INF = Integer.MAX_VALUE;
77+
private List<neighbor>[] g;
78+
private int S, T;
79+
private int[] dis, fa_v, fa_i;
80+
private boolean[] inQ;
81+
82+
private void addEdge(int from, int to, int cap, int cost) {
83+
g[from].add(new neighbor(to, g[to].size(), cap, cost));
84+
g[to].add(new neighbor(from, g[from].size() - 1, 0, -cost));
85+
}
86+
87+
public int findMinimumTime(List<Integer> strength, int k) {
88+
int n = strength.size();
89+
S = n * 2;
90+
T = S + 1;
91+
g = new ArrayList[T + 1];
92+
Arrays.setAll(g, e -> new ArrayList<>());
93+
for (int i = 0; i < n; i++) {
94+
int s = strength.get(i);
95+
// 枚举这个锁是第几次开的
96+
for (int j = 0; j < n; j++) {
97+
int x = 1 + k * j;
98+
int cost = (s - 1) / x + 1;
99+
addEdge(i, n + j, 1, cost);
100+
}
101+
addEdge(S, i, 1, 0);
102+
}
103+
for (int i = n; i < n * 2; i++) {
104+
addEdge(i, T, 1, 0);
105+
}
106+
107+
// 下面是最小费用最大流模板
108+
int minCost = 0;
109+
dis = new int[g.length];
110+
fa_v = new int[g.length];
111+
fa_i = new int[g.length];
112+
inQ = new boolean[g.length];
113+
while (spfa()) {
114+
// 沿 st-end 的最短路尽量增广
115+
// 特别地,如果建图时所有边的容量都设为 1,那么 minF 必然为 1,下面第一个 for 循环可以省略
116+
int minF = INF;
117+
for (int v = T; v != S; ) {
118+
int pv = fa_v[v], pi = fa_i[v];
119+
minF = Math.min(minF, g[pv].get(pi).cap);
120+
v = pv;
121+
}
122+
for (int v = T; v != S; ) {
123+
int pv = fa_v[v], pi = fa_i[v];
124+
neighbor e = g[pv].get(pi);
125+
e.cap -= minF;
126+
g[v].get(e.rid).cap += minF;
127+
v = pv;
128+
}
129+
minCost += dis[T] * minF;
130+
}
131+
return minCost;
132+
}
133+
134+
private boolean spfa() {
135+
Arrays.fill(dis, INF);
136+
dis[S] = 0;
137+
inQ[S] = true;
138+
Queue<Integer> q = new ArrayDeque<>();
139+
q.add(S);
140+
while (!q.isEmpty()) {
141+
int v = q.remove();
142+
inQ[v] = false;
143+
for (int i = 0; i < g[v].size(); i++) {
144+
neighbor e = g[v].get(i);
145+
if (e.cap <= 0) continue;
146+
int w = e.to;
147+
int newD = dis[v] + e.cost;
148+
if (newD < dis[w]) {
149+
dis[w] = newD;
150+
fa_v[w] = v;
151+
fa_i[w] = i;
152+
if (!inQ[w]) {
153+
inQ[w] = true;
154+
q.add(w);
155+
}
156+
}
157+
}
158+
}
159+
// 循环结束后所有 inQ[v] 都为 false,无需重置
160+
return dis[T] < INF;
53161
}
54162
}
55163
}
@@ -73,4 +181,8 @@ private void reverse(int[] a, int st) {
73181
1 <= n <= 8
74182
1 <= K <= 10
75183
1 <= strength[i] <= 10^6
184+
185+
nextPermutation / 最小费用流
186+
相似题目: 3385ドル. 破解锁的最少时间 II
187+
https://leetcode.cn/problems/minimum-time-to-break-locks-ii/description/
76188
*/

‎leetcode/leetcode-34/src/test/java/Solution3376Tests.java

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,21 +5,24 @@
55
import java.util.List;
66

77
public class Solution3376Tests {
8-
private final Solution3376 solution3376 = new Solution3376();
8+
private final Solution3376.V1 solution3376_v1 = new Solution3376.V1();
9+
private final Solution3376.V2 solution3376_v2 = new Solution3376.V2();
910

1011
@Test
1112
public void example1() {
1213
List<Integer> strength = Arrays.asList(3, 4, 1);
1314
int k = 1;
1415
int expected = 4;
15-
Assertions.assertEquals(expected, solution3376.findMinimumTime(strength, k));
16+
Assertions.assertEquals(expected, solution3376_v1.findMinimumTime(strength, k));
17+
Assertions.assertEquals(expected, solution3376_v2.findMinimumTime(strength, k));
1618
}
1719

1820
@Test
1921
public void example2() {
2022
List<Integer> strength = Arrays.asList(2, 5, 4);
2123
int k = 2;
2224
int expected = 5;
23-
Assertions.assertEquals(expected, solution3376.findMinimumTime(strength, k));
25+
Assertions.assertEquals(expected, solution3376_v1.findMinimumTime(strength, k));
26+
Assertions.assertEquals(expected, solution3376_v2.findMinimumTime(strength, k));
2427
}
2528
}

‎leetcode/leetcode-36/src/main/java/Solution3528.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,4 +44,6 @@ private void dfs(int x, long mul) {
4444
4545
建图后 DFS。
4646
时间复杂度 O(n)。
47+
相似题目: 3535ドル. 单位转换 II
48+
https://leetcode.cn/problems/unit-conversion-ii/description/
4749
*/

‎leetcode/leetcode-37/src/main/java/Solution3605.java

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -180,7 +180,9 @@ private int getGCD(int num1, int num2) {
180180
0 <= maxC <= n
181181
182182
二分答案 + ST 表。
183-
时间复杂度 O(nlogU)
184-
二分答案 + logTrick。
183+
时间复杂度 O(nlogn)。
184+
https://chat.deepseek.com/a/chat/s/ac7465ca-a7c9-4ecf-b834-6522a4c472f5
185+
二分答案 + LogTrick / 栈 + 滑动窗口 https://leetcode.cn/problems/minimum-stability-factor-of-array/solutions/3716266/er-fen-da-an-logtrickpythonjavacgo-by-en-jqxy/
186+
时间复杂度 O(nlogU + nlogM)。
185187
rating 2434 (clist.by)
186188
*/

‎leetcode/leetcode-37/src/main/java/Solution3666.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,4 +69,5 @@ public int minOperations(String s, int k) {
6969
- 如果 m 是偶数,检查 m * k <= n * m - c。
7070
- 一旦条件满足,返回当前的 m。
7171
时间复杂度 O(n)。
72+
rating 2477 (clist.by)
7273
*/

‎leetcode/leetcode-37/src/main/java/Solution3670.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,4 +51,5 @@ public long maxProduct(int[] nums) {
5151
高维前缀和(Sum Over Subsets DP,SOS DP)
5252
https://chat.deepseek.com/a/chat/s/287693a9-151d-47f1-99c1-b93864dbe0bd
5353
时间复杂度 O(n + UlogU)。
54+
rating 2276 (clist.by)
5455
*/

‎leetcode/leetcode-37/src/main/java/Solution3671.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -125,4 +125,5 @@ long pre(int pos) {
125125
懒初始化树状数组。
126126
https://leetcode.cn/problems/sum-of-beautiful-subsequences/solutions/3768197/bei-shu-rong-chi-zhi-yu-shu-zhuang-shu-z-rs5w/
127127
时间复杂度 O(DnlogU + UlogU),其中 n 是 nums 的长度,U=max(nums)×ばつ10^4,D≤120 为单个数的最大因子个数。
128+
rating 2675 (clist.by)
128129
*/

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /