力扣1423. 可获得的最大点数-C语言
题目
几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k,请你返回可以获得的最大点数。
示例 1:
输入:cardPoints = [1,2,3,4,5,6,1], k = 3
输出:12
解释:第一次行动,不管拿哪张牌,你的点数总是 1 。但是,先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌,最终点数为 1 + 6 + 5 = 12 。
示例 2:
输入:cardPoints = [2,2,2], k = 2
输出:4
解释:无论你拿起哪两张卡牌,可获得的点数总是 4 。
示例 3:
输入:cardPoints = [9,7,7,9,7,7,9], k = 7
输出:55
解释:你必须拿起所有卡牌,可以获得的点数为所有卡牌的点数之和。
示例 4:
输入:cardPoints = [1,1000,1], k = 1
输出:1
解释:你无法拿到中间那张卡牌,所以可以获得的最大点数为 1 。
示例 5:
输入:cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出:202
提示:
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
题解模板(C)
int maxScore(int* cardPoints, int cardPointsSize, int k){
}
解题
对于题设我们可以很明显知道题目的目的是从一个固有的整型数组里面从两端取出卡牌,数量有限,同时,返回最大取出的值,可以反过来思考题目的意思就是:
你要使得取出来的和是最大的就要使得留下来的和是最小的,大小长度是固定的,所以对于剩下的长度推演就是对于原有的最大长度减去你所要取出的部分的长度,就是剩下的长度,同时,又知道他是两边开始取出的,所以最后余下的是一个连续的子数组
题设长度为cardPointSize,取出k个卡牌
就可以转化为对这个长度为cardPointSize的数组取出其内部长度为(carrPointSize-k)的最小子数组,这就转化成了简单的滑动窗口了。
参考两天前的题目,这个就很简单了
int maxScore(int* cardPoints, int cardPointsSize, int k){
int sum = 0;
int all=0;
for( int i = 0; i < cardPointsSize ; i++)
all += cardPoints[i];//计算所有总和
for( int i = 0; i < cardPointsSize - k; i++)
{
sum += cardPoints[i];//计算第一窗口和
printf("sum=%d ,",sum);
}
int minsum= sum;//暂得最小值
for(int i = cardPointsSize - k; i < cardPointsSize; i++)
{
sum = sum - cardPoints[i - cardPointsSize+k]+cardPoints[i];//以固定长度滑动窗口
printf("sum=%d ,",sum);
minsum = fmin(sum ,minsum);//窗口最小值更新
printf("minsum=%d ;",minsum);
}
return (all-minsum);
}
想要自己测试的小伙伴可以拷贝下面的代码在自己的编译器上测试
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int maxScore(int* cardPoints, int cardPointsSize, int k);
int main()
{
int cardPoints[]={1,79,80,1,1,1,200,1};
int max=maxScore(cardPoints,8,3);
printf("%d",max);
}
int maxScore(int* cardPoints, int cardPointsSize, int k){
int sum = 0;
int all=0;
for( int i = 0; i < cardPointsSize ; i++)
all += cardPoints[i];//计算所有总和
for( int i = 0; i < cardPointsSize - k; i++)
{
sum += cardPoints[i];//计算第一窗口和
printf("sum=%d ,",sum);
}
int minsum= sum;//暂得最小值
for(int i = cardPointsSize - k; i < cardPointsSize; i++)
{
sum = sum - cardPoints[i - cardPointsSize+k]+cardPoints[i];//以固定长度滑动窗口
printf("sum=%d ,",sum);
minsum = fmin(sum ,minsum);//窗口最小值更新
printf("minsum=%d ;",minsum);
}
return (all-minsum);
}
再贴上一张运行图,截取了最好看的数据
最新文章
- Spring+Quartz实现定时任务
- JUnit3的作用
- 开启梦幻般的webrtc之旅
- Number()数据类型转换
- C语言中怎么将文件里的数据创建到(读到)链表中?
- C++ 中的形参与返回值
- 20160501--struts2入门2
- Oracle自治事务
- 导出Excel数据
- 修改/home内子目录的名字
- Sqlserver事务备份和还原实例
- Linux上程序调试的基石(2)--GDB
- 【java】[文件上传jar包]commons-fileUpload组件解决文件上传(文件名)乱码问题
- xampp+YII搭建网站
- (转载)Spring定时任务的几种实现
- poj 1159 Palindrome - 动态规划
- java 字符串截取的几种方式(转)
- php数组添加元素的方法
- HTML开发之(块级标签,行内标签,行内块标签)
- 002_IO磁盘深入理解
热门文章
- 风炫安全WEB安全学习第二十四节课 利用XSS钓鱼攻击
- 【递推】P1028数的计算
- 基于腾讯云存储COS的ClickHouse数据冷热分层方案
- 剑指offer 面试题5:替换空格
- Docker安装MySQL,Redis,阿里云镜像加速
- Mac配置jmeter环境变量
- 【Spring】Spring的数据库开发 - 1、Spring JDBC的配置和Spring JdbcTemplate的解析
- innobackupex: Connecting to MySQL server with DSN &#39;dbi:mysql
- HTML DOM 定义了访问和操作 HTML 文档标准
- 攻防世界 - Web(三)