【蓝桥Java每日一题】——12.可获得的最大点数

2022-05-22 101

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 今天给大家带来一道前缀和的练手题目。前缀和虽然不是动规那么复杂的知识点，但是还是有很多坑的，掌握好对我们还是有很大的帮助的，是一种非常基础的算法，大家一定要掌握。

👻LeetCode——可获得的最大点数

几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

题目链接：可获得的最大点数https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/

题目分析：当我们拿到一道题目时，一定要去分析题目给的数据范围。这道题每张卡牌对于的点数都是正数，且k最大值为和卡牌数量一样多。所以这里我们可以马上意识到这种情况可以特判，直接返回整个数组之和。下面进行仔细分析

每次我们抽卡只能从首或尾抽，说明被我们丢弃的卡一定是连续的靠在一起的。因为我们每次都要么从最左边或者从最右边抽，直到抽够k张，那些我们不要的卡片说明就是原数组的一个子数组。

如果数组的长度为n，我们需要从n长抽够k张卡，则说明剩下的卡数量为n-k

所有卡片之和是固定的。我们想让抽的卡尽可能点数之和大，理所当然想到让剩下的卡点数小。所以这道题目转换为从数组长度为n中找到一个长度为n-k且和最小的子数组

通过上述分析，我们可以很容易判断出使用前缀和的标志，因为前缀和数组可以在O(1)的时间内得到任意一个子数组之和，我们只需要去枚举起始坐标获得所有所有长度为n-k的子数组之和，并获得最小值，用所有卡牌之和减去这个最小值即可得到答案。

方法1：前缀和

时间复杂度O(n)

class Solution {
    public int maxScore(int[] nums, int k) {
        int n=nums.length;
        int[] arr=new int[n+1];
        //获得前缀和数组
        for(int i=0;i<n;i++) arr[i+1]=arr[i]+nums[i];
        //特判：k==n时直接返回所有卡牌之和即可
        if(k==n) return arr[n];
        //剩余卡牌也就是子数组的长度
        int len=n-k;
         //记录最小值
        int value=Integer.MAX_VALUE;
        //i是子数组的起始坐标，i+len-1则是子数组的结尾坐标
        for(int i=0;i+len-1<n;i++){
            //去更新最小值
            value=Math.min(value,arr[i+len]-arr[i]);
        }
        return arr[n]-value;
    }
}

方法2：滑动窗口

这道题的标志不仅仅是前缀和，滑动窗口也很明显。只要大家不要把注意力全放在选择的卡牌上，去思考一下未选择的卡牌。我们同样维护一个n-k大小的窗口，每次移动去更新最小值，其思路和前缀和大同小异。

class Solution {
    public int maxScore(int[] nums, int k) {
        int n=nums.length;
        int len=n-k;
        int count=0;
        for(int i=0;i<n-k;i++){
            count+=nums[i];
        }
        int min=count;
        int r=n-k;
        while(r<n){
            count+=nums[r];
            count-=nums[r-len];
            r++;
            min=Math.min(min,count);
        }
        return Arrays.stream(nums).sum()-min;
    }
}