[toc]
2023-05-23
1090. 受标签影响的最大值 - 力扣（Leetcode）
题意没搞清，白搞半小时
搞清题意后其实很简单，先按values大小排序，再从最大处逐个取，如果对应标签数量已经满足阈值就跳过，其实就是用到了排序和哈希而已。
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 largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
Map<Integer, Integer> lableCountMap = new HashMap<>();
Map<Integer, Integer> indexToLableMap = new HashMap<>();
List<Integer> indexs = new ArrayList<>();
for(int i = 0; i < labels.length;i++) {
indexToLableMap.put(i, labels[i]);
indexs.add(i);
lableCountMap.put(labels[i], 0);
}
Collections.sort(indexs, (a,b)->values[b] - values[a]);
List<Integer> res = new ArrayList<>();
for (int index : indexs) {
if (res.size() >= numWanted) {
break;
}
int label = indexToLableMap.get(index);
if (lableCountMap.get(label) >= useLimit) {
continue;
}
lableCountMap.put(label, lableCountMap.get(label) + 1);
res.add(values[index]);
}
return res.stream().mapToInt(Integer::intValue).sum();
}
}
|
2023-05-22
1080. 根到叶路径上的不足节点 - 力扣（Leetcode）
树的后序遍历应用题目
不管咋做，反正只要知道后序遍历，后面就都好办。
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
| class Solution {
public TreeNode sufficientSubset(TreeNode root, int limit) {
long res = postDfs(root, 0, null, limit);
if (res < limit) {
return null;
} else {
return root;
}
}
long postDfs(TreeNode node, long parentVal, TreeNode parent, int limit) {
if (node == null) {
return Integer.MIN_VALUE;
}
long sonValMax;
if (node.left == null && node.right == null) {
sonValMax = 0;
} else {
long leftMaxVal = postDfs(node.left, parentVal + node.val, node, limit);
long rightMaxVal = postDfs(node.right, parentVal + node.val,node, limit);
sonValMax = Math.max(leftMaxVal, rightMaxVal);
}
if (parent != null && parentVal + sonValMax + node.val < limit) {
if (parent.left == node) {
parent.left = null;
} else {
parent.right = null;
}
}
return sonValMax + node.val;
}
}
|
2023-05-21
LCP 33. 蓄水 - 力扣（Leetcode）
这题说是简单题，但是好难，没仔细看条件数量仅有100个桶，而且是一起倒水，水缸没上限
那么可以做枚举，枚举出倒水次数，然后再倒推出每个桶需要增加多少水，即可得到这一次枚举后的总操作数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int storeWater(int[] bucket, int[] vat) {
int res = Integer.MAX_VALUE;
if (Arrays.stream(vat).allMatch(v->v==0)) {
return 0;
}
for (int pushCount = 1; pushCount <=10000; pushCount++) {
int bChangeCount = 0;
for (int i = 0; i < bucket.length;i++) {
int b = bucket[i];
int v = vat[i];
int newB = v / pushCount + (v%pushCount == 0 ? 0 : 1);
int needB = Math.max(newB - b, 0);
bChangeCount += needB;
}
res = Math.min(bChangeCount + pushCount, res);
}
return res;
}
}
|
改进点：
pushCount的边界条件， 可以是
1
| pushCount <=maxv && pushCount < res
|
核心是<res时， 可以提前退出了