C语言 Logstash JAVA学习 dynamic types terminal ssis arduino Modernizr jquery绑定click事件 linux超级用户 arduino程序 oracle取第一条数据 matlab自然对数 数据库教程 mysql临时表 郑州普通话 python新手教程 python开发工具 如何配置python环境 python怎么入门 python设置环境变量 java连数据库 java中class java输出当前时间 java泛型方法 java数组排序 自制题库答题考试软件 整站系统 网络工程师教程 kontakt 图片轮播代码 苹果双微信 js正则匹配字符串 一键换肤大师 只狼台词 airdrop是什么 appdata是什么文件夹 ps索引怎么解锁 日文游戏乱码转换工具
当前位置: 首页 > 学习教程  > python

力扣 leetcode 1423. 可获得的最大点数 (python)滑窗

2021/2/7 10:24:33 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Topic 几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 给你一个整数数组 card…

Topic

几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k,请你返回可以获得的最大点数。

Example_1

输入:cardPoints = [1,2,3,4,5,6,1], k = 3
输出:12
解释:第一次行动,不管拿哪张牌,你的点数总是 1 。但是,先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌,最终点数为 1 + 6 + 5 = 12 。

Example_2

输入:cardPoints = [2,2,2], k = 2
输出:4
解释:无论你拿起哪两张卡牌,可获得的点数总是 4 。

Example_3

输入:cardPoints = [9,7,7,9,7,7,9], k = 7
输出:55
解释:你必须拿起所有卡牌,可以获得的点数为所有卡牌的点数之和。

Example_4

输入:cardPoints = [1,1000,1], k = 1
输出:1
解释:你无法拿到中间那张卡牌,所以可以获得的最大点数为 1 。

Example_5

输入:cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出:202

Tips

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Solution

本题运用滑窗同样是一个比较简单的方法

这里需要一个思路转换
最大删除数为k个数
那么剩下的数字我们放到滑窗当中
并使其长度为原序列长减k

计算滑窗中的值为total
同时令最小值暂为total

若删去的数字值最大,则滑窗中的总值total要最小

不断右移滑窗直至结束
若滑窗的总值total比最小值min_sum要小
则将total赋值给min_sum

完成遍历后
返回原序列中的总值减min_sum即为结果

Code

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        window = n - k
        total = sum(cardPoints[:window])

        min_sum = total 
        for i in range(window, n):
            total += cardPoints[i] 
            total -= cardPoints[i - window]
            if total < min_sum:
                min_sum = total

        return sum(cardPoints) - min_sum

Result

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000223.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?