本期总结：
- N种东西组成最大字典序回文时，先把成双的都处理掉，每组留下1个或者0个， 最后再考虑怎么拼接这些
- 子序列和第K个，可以考虑从最小数字开始， 每次保留当前数字，选下一个数字， 或者废弃当前数字，选下一个数字， 并都放入堆中， 这样每次可更新得到最小的子序列。
6152. 赢得比赛需要的最少训练时长 - 力扣（LeetCode）
最开始有点事情，解决完之后发现脑子很乱，这题目其实很简答
对于精力，可以提前算出需要的精力， 而经验可以在每次对战时判断是否要再增加。
但这题就是条件容易看漏，导致错了2次：
需要在经验和精力上都 严格超过对手才能击败他们
严格超过意味着不能等于，导致很多地方得+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
int exp = initialExperience;
int sum = Arrays.stream(energy).sum();
int res = Math.max(0, sum + 1 - initialEnergy);
for (int i = 0; i < experience.length;i++) {
if (exp < experience[i] + 1) {
res += experience[i] - exp + 1;
exp = experience[i]+1;
}
exp += experience[i];
}
return res;
}
}
|
6166. 最大回文数字 - 力扣（LeetCode）
这题也搞晕了，实际上很简单。
一堆已知数量的字母要组成回文数， 记住你先把所有成双成对的单独都按拿出来， 剩下的都是1个或者0个字母
然后成双的按大小顺序从外向内组成回文 ， 最后最里面那个单字母的用最大的。
我最开始直接把奇数个数的字母当整体去思考了，其实应该先剔除奇数个数字母中成双的部分，只留下单个的， 最后再去考虑他
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
| class Solution {
public String largestPalindromic(String num) {
int[] charCounts = new int[10];
for (char c : num.toCharArray()) {
charCounts[c-'0']++;
}
int numCount = 0;
int endUseChar = -1;
boolean[] oneChar = new boolean[10];
for (int i = 9; i >=0;i--) {
oneChar[i] = (charCounts[i] %2 == 1);
charCounts[i] /= 2;
}
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
for (int i = 9;i>=0;i--) {
if (i == endUseChar) {
continue;
}
char c = (char)('0' + i);
int count = charCounts[i];
if (i == 0 && sb1.length() == 0) {
continue;
}
while (count-->0) {
sb1.append(c);
sb2.append(c);
}
}
for (int i = 9;i>=0;i--) {
if (oneChar[i]) {
sb1.append((char) ('0' + i));
break;
}
}
if (sb1.length() == 0) {
return "0";
}
return sb1.append(sb2.reverse()).toString();
}
}
|
6154. 感染二叉树需要的总时间 - 力扣（LeetCode）
很容易想到bfs， 先dfs一遍，把每个点的父节点也得到。
然后做bfs即可
另外二叉树的题目中如果涉及map或者set，最好还是直接用引用做key，不容易写错
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
|
class Solution {
Map<TreeNode,TreeNode> parents = new HashMap<>();
TreeNode startNode;
public int amountOfTime(TreeNode root, int start) {
Queue<TreeNode> queue = new LinkedList<>();
find(root, null, start);
queue.offer(startNode);
Set<TreeNode> vis = new HashSet<>();
vis.add(startNode);
int res = 0;
while (!queue.isEmpty()) {
res++;
List<TreeNode> nowNodes = new ArrayList<>(queue);
queue.clear();
for (TreeNode node : nowNodes) {
if (node.left != null && !vis.contains(node.left)) {
queue.offer(node.left);
vis.add(node.left);
}
if (node.right != null && !vis.contains(node.right)) {
queue.offer(node.right);
vis.add(node.right);
}
if (parents.get(node) != null && !vis.contains(parents.get(node))) {
queue.offer(parents.get(node));
vis.add(parents.get(node));
}
}
}
return res-1;
}
void find(TreeNode node, TreeNode parent, int start) {
if (node == null) {
return;
}
parents.put(node, parent);
if (node.val == start) {
startNode = node;
}
find(node.left, node, start);
find(node.right, node, start);
}
}
|
6155. 找出数组的第 K 大和 - 力扣（LeetCode）
这题好难，其实知道套路就可以了
我是已经想到先得到 正数的和sum， 然后以这个sum不断减去其他的值，这个减去的就是子序列而且要尽可能小， 同时负数要转整数， 到底是加还是减不需要我们关心。
但是怎么得到第K小的子序列和呢？
答案是用最小堆
先按从小到大排序
然后第0个数字肯定是最小的子序列
接着有2个选择：
① 保留第0个数字， 并继续选取第1个数字
② 废弃第0个数字， 并继续选取第1个数字
这样又得到2个子序列， 最小序列肯定在者2个里面
你会奇怪，者肯定是第②个最小啊？
但是继续走下去
当对于“废弃第0个数字， 并继续选取第1个数字”这个位置，你想废弃第1个数字，选第2个数字时，前面的“保留第0个数字， 并继续选取第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
| class Solution {
public long kSum(int[] nums, int k) {
long sum = Arrays.stream(nums).filter(num -> num > 0).mapToLong(num -> Long.valueOf(num)).sum();
for (int i = 0 ; i < nums.length;i++) {
nums[i] = Math.abs(nums[i]);
}
Arrays.sort(nums);
Queue<long[]> queue = new PriorityQueue<>((a,b) -> (a[0] > b[0] ? 1 : -1));
queue.offer(new long[]{0, 0L});
while (!queue.isEmpty()) {
long subSum = queue.peek()[0];
int index = (int)queue.poll()[1];
if (k == 1) {
return (sum - subSum);
}
k--;
if (index >= nums.length) {
continue;
}
queue.offer(new long[]{subSum + nums[index], index+1});
if (index -1 >= 0) {
queue.offer(new long[]{subSum - nums[index - 1] + nums[index], index + 1});
}
}
return -1;
}
}
|