Skip to content

Commit 63ac2f5

Browse files
dingjikerbodingjikerbo
committed
fd
1 parent 6ee4452 commit 63ac2f5

3 files changed

Lines changed: 36 additions & 23 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -288,6 +288,7 @@
288288
|317|[Shortest Distance from All Buildings](https://leetcode.com/problems/shortest-distance-from-all-buildings/)| [Java](leetcode/solution/src/ShortestDistanceFromAllBuildings.java)|75|典型的bfs，多做两遍|
289289
|319|[Bulb Switcher](https://leetcode.com/problems/bulb-switcher/)| [Java](leetcode/solution/src/BulbSwitcher.java)|90|
290290
|320|[Generalized Abbreviation](https://leetcode.com/problems/generalized-abbreviation/)| [Java](leetcode/solution/src/GeneralizedAbbreviation.java)|70|这题是典型的back tracking，多做几遍|
291+
|322|[Coin Change](https://leetcode.com/problems/coin-change/)|[Java](leetcode/solution/src/CoinChange.java)|80||
291292
|323|[Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)| [Java](leetcode/solution/src/NumberOfConnectedComponents.java)|90|典型的图，多看两遍|
292293
|324|[Wiggle Sort II](https://leetcode.com/problems/wiggle-sort-ii/)| [Java](leetcode/solution/src/WiggleSortII.java)|60|
293294
|325|[Maximum Size Subarray Sum Equals k](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)| [Java](leetcode/solution/src/MaximumSizeSubarraySumEqualsK.java)|75|这题思路有意思，多做几遍|

‎leetcode/solution/src/CoinChange.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
import java.util.Arrays;
2+
3+
public class CoinChange {
4+
5+
public int coinChange(int[] coins, int amount) {
6+
Arrays.sort(coins);
7+
int[] dp = new int[amount + 1];
8+
Arrays.fill(dp, -1);
9+
dp[0] = 0;
10+
for (int i = 1; i <= amount; i++) {
11+
for (int coin: coins) {
12+
if (i - coin >= 0 && dp[i - coin] >= 0) {
13+
int k = dp[i - coin] + 1;
14+
dp[i] = dp[i] > 0 ? Math.min(dp[i], k) : k;
15+
}
16+
}
17+
}
18+
return dp[amount];
19+
}
20+
}

‎leetcode/src/Main.java‎

Lines changed: 15 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -2,33 +2,25 @@
22

33
public class Main {
44

5-
public int maxAreaOfIsland(int[][] grid) {
6-
int[] area = new int[1];
7-
int max = 0;
8-
9-
for (int i = 0; i < grid.length; i++) {
10-
for (int j = 0; j < grid[0].length; j++) {
11-
area[0] = 0;
12-
dfs(grid, i, j, area);
13-
max = Math.max(max, area[0]);
5+
public static int coinChange(int[] coins, int amount) {
6+
Arrays.sort(coins);
7+
int[] dp = new int[amount + 1];
8+
Arrays.fill(dp, -1);
9+
dp[0] = 0;
10+
for (int i = 1; i <= amount; i++) {
11+
for (int coin: coins) {
12+
if (i - coin >= 0 && dp[i - coin] >= 0) {
13+
int k = dp[i - coin] + 1;
14+
dp[i] = dp[i] > 0 ? Math.min(dp[i], k) : k;
15+
}
1416
}
1517
}
16-
return max;
17-
}
18-
19-
private void dfs(int[][] grid, int i, int j, int[] count) {
20-
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
21-
return;
22-
}
23-
grid[i][j] = 0;
24-
count[0]++;
25-
dfs(grid, i + 1, j, count);
26-
dfs(grid, i - 1, j, count);
27-
dfs(grid, i, j + 1, count);
28-
dfs(grid, i, j - 1, count);
18+
return dp[amount];
2919
}
3020

3121
public static void main(String[] args) {
32-
22+
System.out.println(coinChange(new int[] {
23+
1, 2, 5
24+
}, 11));
3325
}
3426
}

0 commit comments

Comments
 (0)