算法练习——可获得的最大点数

2021年2月6日LeetCode每日一题为1423. 可获得的最大点数,首先如果k与数组长度相等,那么最大点数就是所有牌的值的和,否则进行递归求解。每一步取牌之后都需要进行大小总和的比较,当k为1的时候将两边的最大值返回。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int maxScore(int[] cardPoints, int k) {
int ans = 0;
if (k == cardPoints.length) {
for (int cardPoint : cardPoints) {
ans += cardPoint;
}
} else {
ans = maxScore(cardPoints, k, 0, cardPoints.length - 1);
}
return ans;
}

public int maxScore(int[] cardPoints, int k, int left, int right) {
if (k == 1) return Math.max(cardPoints[left], cardPoints[right]);
int leftAns = cardPoints[left] + maxScore(cardPoints, k - 1, left + 1, right);
int rightAns = cardPoints[right] + maxScore(cardPoints, k - 1, left, right - 1);
return Math.max(leftAns, rightAns);
}
}

超时后通过题解得到新的思路,既然对两边的选择比较麻烦,那么通过滑动窗口来计算中间的最小值得到两边最大值的组合结果即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxScore(int[] cardPoints, int k) {
int sum = 0;
int size = cardPoints.length - k;
for (int i = 0; i < size; i++) {
sum += cardPoints[i];
}
int minSum = sum;
for (int i = 0; i < k; i++) {
sum = sum - cardPoints[i] + cardPoints[i + size];
minSum = Math.min(minSum, sum);
}
return Arrays.stream(cardPoints).sum() - minSum;
}
}