1636. 按照频率将数组升序排序 - 力扣（LeetCode）
先统计个数，然后按照个数进行排序
注意：
对于int[]，不可以直接进行Arrays.sort(nums, (a,b)->a-b);
要么先转成Integer[]
要么用
1
2
| Arrays.stream(nums).boxed().sorted((a,b)->
(counts[a] - counts[b) ).mapToInt(Integer::intValue).toArray()
|
来实现，先stream然后boxed最后还要mapToInt才能toArray
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int[] frequencySort(int[] nums) {
int[] counts = new int[201];
for (int num : nums) {
counts[num + 100]++;
}
return Arrays.stream(nums).boxed().sorted((a,b)->
counts[a+100] != counts[b+100] ? (counts[a+100] - counts[b+100]) : (b-a)).mapToInt(Integer::intValue).toArray();
}
}
|
剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）
维护2个数组即可，stack数组和min数组（毕竟往栈底看过去的最小值一定是确定的）
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
| class MinStack {
int[] min = new int[20001];
int[] stack = new int[20001];
int index = 0;
public MinStack() {
}
public void push(int x) {
min[index] = Math.min(x, index-1>=0 ? min[index-1] : Integer.MAX_VALUE);
stack[index++] = x;
}
public void pop() {
min[index-1] = Integer.MAX_VALUE;
index--;
}
public int top() {
return stack[index-1];
}
public int min() {
return min[index-1];
}
}
|
322. 零钱兑换 - 力扣（LeetCode）
时间很紧，先是相当了bfs并用记忆化处理，每次出队硬币个数最少的，类似于走迷宫了。
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
| class Solution {
public int coinChange(int[] coins, int amount) {
Queue<int[]> queue = new PriorityQueue<>((a,b)->(a[0]-b[0]));
queue.offer(new int[]{0,0});
Set<Integer> vis = new HashSet<>();
vis.add(0);
while(!queue.isEmpty()) {
int count = queue.peek()[0];
int am = queue.poll()[1];
if (am == amount) {
return count;
}
for (int coin : coins) {
int newAmount = am + coin;
if (newAmount > amount) {
continue;
}
if (vis.contains(newAmount)) {
continue;
}
vis.add(newAmount);
queue.offer(new int[]{count+1, newAmount});
}
}
return -1;
}
}
|
性能太差了
看了答案想起来这个完全可以动态规划
因为amount的范围是0~104而非109，完全可以把amount作为一个dp状态处理， 且coin的数量也只有12个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int coinChange(int[] coins, int amount) {
long[] dp = new long[amount+1];
for (long a = 1; a <= amount;a++) {
dp[(int)a] = Integer.MAX_VALUE;
for (int coin : coins) {
if (a - coin < 0) {
continue;
}
dp[(int)a] = Math.min(dp[(int)a], dp[(int)a-coin] + 1);
}
}
return (int)dp[amount] == Integer.MAX_VALUE ? -1 : (int)dp[amount];
}
}
|
性能一下子就上去了
再做一下优化，根据数据范围，去除long和int的强转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
for (int a = 1; a <= amount;a++) {
dp[a] = 10001;
for (int coin : coins) {
if (a < coin) {
continue;
}
dp[a] = Math.min(dp[a], dp[a-coin] + 1);
}
}
return dp[amount] == 10001 ? -1 : dp[amount];
}
}
|
提升到11ms了
另外有个很奇怪的，下面这个的性能始终慢2ms，我感觉明明过滤了很多不必要的coins循环才对
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
| class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
int minCoin = coins[0];
for (int i = 1; i < coins.length;i++) {
minCoin= Math.min(minCoin, coins[i]);
}
Arrays.sort(coins);
for (int a = 1; a <= amount;a++) {
dp[a] = 10001;
if (a < minCoin) {
continue;
}
for (int coin : coins) {
int lastCoinSum = a-coin;
if (lastCoinSum < 0) {
break;
}
dp[a] = Math.min(dp[a], dp[lastCoinSum] + 1);
}
}
return dp[amount] == 10001 ? -1 : dp[amount];
}
}
|
