leetcode-1423

发表于 更新于 分类于 Waline：

这个周的每日一题，做算法，要有想象力，要足够充分发掘已知条件。

题目

https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/

解法

回溯 + 双指针

这道题目每次都只能从开头或者末尾拿一个，那么做决策的过程可以是为一个二叉树。

我们分别用两个指针指向还未遍历的队头结尾，用作指向左子树和右子树的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
const trackback = (cardPoints, k, count, left, right, result) => {
    if (count === k) {
        return result;
    } else {
        const leftresult = trackback(cardPoints, k, count + 1, left + 1, right, result + cardPoints[left]);
        const rightresult = trackback(cardPoints, k, count + 1, left, right - 1, result + cardPoints[right]);
        return Math.max(leftresult, rightresult);
    }
}

var maxScore = function(cardPoints, k) {
    return trackback(cardPoints, k, 0, 0, cardPoints.length - 1, 0);
};

反向思考+滑动窗口

上面这种解法是常规解法，但是其实这个题目还有个已知条件我们没有好好利用。

就是每次只能从头或者尾取值，那也就是说完成k个的取值后，剩下的是连续的。

那么假设数组长度为n，则取完k个值后剩n-k个连续数组。

我们只需要求出n-k的连续数组的最小值，就可以推出取值的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var maxScore = function(cardPoints, k) {
    const n = cardPoints.length;
    // 滑动窗口大小为 n-k
    const windowSize = n - k;
    // 选前 n-k 个作为初始值
    let sum = 0;
    for (let i = 0; i < windowSize; ++i) {
        sum += cardPoints[i];
    }
    let minSum = sum;
    for (let i = windowSize; i < n; ++i) {
        // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
        sum += cardPoints[i] - cardPoints[i - windowSize];
        minSum = Math.min(minSum, sum);
    }
    let totalSum = 0;
    for (let i = 0; i < n; i++) {
        totalSum += cardPoints[i];
    }
    return totalSum - minSum;
};