Leetcode.2140 解决智力问题
题目链接
Leetcode.2140 解决智力问题 Rating : 1709
题目描述
给你一个下标从 0开始的二维整数数组 questions,其中 questions[i] = [pointsi, brainpoweri]。
这个数组表示一场考试里的一系列题目,你需要 按顺序 (也就是从问题 0开始依次解决),针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi的分数,但是你将 无法 解决接下来的 brainpoweri个问题(即只能跳过接下来的 brainpoweri个问题)。如果你跳过问题 i,你可以对下一个问题决定使用哪种操作。
- 比方说,给你
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]: -
- 如果问题
0被解决了, 那么你可以获得3分,但你不能解决问题1和2。
- 如果问题
-
- 如果你跳过问题
0,且解决问题1,你将获得4分但是不能解决问题2和3。
- 如果你跳过问题
请你返回这场考试里你能获得的 最高 分数。
示例 1:
输入:questions = [[3,2],[4,3],[4,4],[2,5]]
输出:5
解释:解决问题 0 和 3 得到最高分。
解决问题 0 :获得 3 分,但接下来 2 个问题都不能解决。
不能解决问题 1 和 2
解决问题 3 :获得 2 分 总得分为:3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
示例 2:
输入:questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出:7
解释:解决问题 1 和 4 得到最高分。
跳过问题 0
解决问题 1 :获得 2 分,但接下来 2 个问题都不能解决。
不能解决问题 2 和 3
解决问题 4 :获得 5 分 总得分为:2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。
提示:
- 1<=questions.length<=1051 <= questions.length <= 10^51<=questions.length<=105
- questions[i].length==2questions[i].length == 2questions[i].length==2
- 1<=pointsi,brainpoweri<=1051 <= pointsi, brainpoweri <= 10^51<=pointsi,brainpoweri<=105
分析:
我们使用 动态规划 求解本题。
我们定义 f(i)f(i)f(i) 为解决区间 [i,n]的问题能获得的最高分数。
按照定义,最后返回的答案就是 f(1)f(1)f(1) ,即 解决区间[1,n]所能获得的最高分数。
当前问题 i的分数是 point,需要跳过的问题数是 t。
f[i] = point- 如果
i + t + 1 <= n(跳过了t问题还没越界的话),f[i] = f[i] + f[i+t+1] - 最后
f[i] = max(f[i] , f[i+1])
时间复杂度:O(n)O(n)O(n)
C++代码:
using LL = long long;
class Solution {
public:long long mostPoints(vector<vector<int>>& questions) {int n = questions.size();LL f[n+1];memset(f,0,sizeof f);f[n] = questions[n-1][0];for(int i = n-1;i >= 1;i--){int point = questions[i-1][0] , t = questions[i-1][1];f[i] = point;if(i + t + 1 <= n) f[i] += f[i + t + 1];f[i] = max(f[i],f[i+1]);}return f[1];}
};
Java代码:
class Solution {public long mostPoints(int[][] questions) {int n = questions.length;long[] f = new long[n+1];f[n] = questions[n-1][0];for(int i = n-1;i >= 1;i--){int point = questions[i-1][0] , t = questions[i-1][1];f[i] = point;if(i + t + 1 <= n) f[i] += f[i + t + 1];f[i] = Math.max(f[i],f[i+1]);}return f[1];}
}
相关文章:
Leetcode.2140 解决智力问题
题目链接 Leetcode.2140 解决智力问题 Rating : 1709 题目描述 给你一个下标从 0开始的二维整数数组 questions,其中 questions[i] [pointsi, brainpoweri]。 这个数组表示一场考试里的一系列题目,你需要 按顺序 (也就是从问题…...
新时代下的医疗行业新基建研讨会
1、会议纪要 2023年2月17日,HIT专家网进行了《新时代下的医疗行业新基建研讨会》的会议。 对会议内容进行了记录。 会议中有友谊医院、301、北肿主任进行了分享。大纲如下所示 2、本人所想 本人的所想所感: 1、301在多院区的医疗信息建设,…...
BEV感知:DETR3D
3D检测:DETR3D前言MethodImage Feature Extracting2D-to-3D Feature TransformationLoss实验结果前言 在这篇paper,作者提出了一个更优雅的2D与3D之间转换的算法在自动驾驶领域,它不依赖于深度信息的预测,这个框架被称之为DETR3D…...
亿级高并发电商项目-- 实战篇 --万达商城项目 十二(编写用户服务、发送短信功能、发送注册验证码功能、手机号验证码登录功能、单点登录等模块)
👏作者简介:大家好,我是小童,Java开发工程师,CSDN博客博主,Java领域新星创作者 📕系列专栏:前端、Java、Java中间件大全、微信小程序、微信支付、若依框架、Spring全家桶 Ǵ…...
整合spring cloud云服务架构 - 企业分布式微服务云架构构建
1. 介绍 Commonservice-system是一个大型分布式、微服务、面向企业的JavaEE体系快速研发平台,基于模块化、服务化、原子化、热插拔的设计思想,使用成熟领先的无商业限制的主流开源技术构建。采用服务化的组件开发模式,可实现复杂的业务功能。…...
leetcode 540. Single Element in a Sorted Array(排序数组中的单个元素)
给一个已经排好序的升序数组,其中每个元素都会重复2次,只有一个元素只有一个, 找出这个只有一个的元素。 要求时间复杂度在O(logn), 空间复杂度在O(1). 思路: 时间复杂度为O(logn), 让人想到了binary search. 因为时间复杂度为…...
Color correction for tone mapping
Abstract色调映射算法提供了复杂的方法,将真实世界的亮度范围映射到输出介质的亮度范围,但它们经常导致颜色外观的变化。在本研究中,我们进行了一系列的主观外观匹配实验,以测量对比度压缩和增强后图像色彩的变化。结果表明&#…...
JavaScript-XHR-深入理解
JavaScript-XHR-深入理解1. XHR(Asynchronous JavaScript And XML)初始1.1. xhr request demo1.2. status of XHRHttpRequest1.3. send synchronous request by xhr1.4. onload监听数据加载完成1.5. http status code1.6. get/post request with josn/form/urlcoded1.7. encaps…...
mathtype7.0最新版安装下载及使用教程
MathType是一款专业的数学公式编辑器,理科生专用的必备工具,可应用于教育教学、科研机构、工程学、论文写作、期刊排版、编辑理科试卷等领域。2014年11月,Design Science将MathType升级到MathType 6.9版本。在苏州苏杰思网络有限公司与Design…...
响应状态码
✨作者:猫十二懿 ❤️🔥账号:CSDN 、掘金 、个人博客 、Github 🎉公众号:猫十二懿 一、状态码大类 状态码分类说明1xx响应中——临时状态码,表示请求已经接受,告诉客户端应该继续请求或者如果…...
第六章.卷积神经网络(CNN)—CNN的实现(搭建手写数字识别的CNN)
第六章.卷积神经网络(CNN) 6.2 CNN的实现(搭建手写数字识别的CNN) 1.网络构成 2.代码实现 import pickle import matplotlib.pyplot as plt import numpy as np import sys, ossys.path.append(os.pardir)from dataset.mnist import load_mnist from collections import Order…...
【go】defer底层原理
defer的作用 defer声明的函数在当前函数return之后执行,通常用来做资源、连接的关闭和缓存的清除等。 A defer statement pushes a function call onto a list. The list of saved calls is executed after the surrounding function returns. Defer is commonly u…...
TypeScript 学习笔记
最近在学 ts 顺便记录一下自己的学习进度,以及一些知识点的记录,可能不会太详细,主要是用来巩固和复习的,会持续更新 前言 想法 首先我自己想说一下自己在学ts之前,对ts的一个想法和印象,在我学习之前&a…...
【C++】map和set的使用
map和set一、set1.1 set的介绍1.2 set的使用1.2.1 set的构造1.2.2 set的迭代器1.2.3 set的修改1.2.3.1 insert && find && erase1.2.3.2 count1.3 multiset二、map2.1 map的介绍2.2 map的使用2.2.1 map的修改2.2.1.1 insert2.2.1.2 统计次数2.3 multimap一、se…...
微电影广告具有哪些特点?
微电影广告是广告主投资的,以微电影为形式载体,以新媒体为主要传播载体,综合运用影视创作手法拍摄的集故事性、艺术性和商业性于一体的广告。它凭借精彩的电影语言和强大的明星效应多渠道联动传播,润物细无声地渗透和传递着商品信…...
Android RxJava框架源码解析(四)
目录一、观察者Observer创建过程二、被观察者Observable创建过程三、subscribe订阅过程四、map操作符五、线程切换原理简单示例1: private Disposable mDisposable; Observable.create(new ObservableOnSubscribe<String>() {Overridepublic void subscribe(…...
Linux信号-进程退出状态码
当进程因收到信号被终止执行退出后,父进程可以通过wait或waitpid得到它的exit code。进程被各信号终止的退出状态码总结如下:信号编号信号名称信号描述默认处理方式Exit code1SIGHUP挂起终止12SIGINT终端中断终止23SIGQUIT终端退出终止、coredump1314SIG…...
springcloud+vue实现图书管理系统
一、前言: 今天我们来分享一下一个简单的图书管理系统 我们知道图书馆系统可以有两个系统,一个是管理员管理图书的系统,管理员可以(1)查找某一本图书情况、(2)增加新的图书、(3&…...
GEE学习笔记 六十:GEE中生成GIF动画
生成GIF动画这个是GEE新增加的功能之一,这一篇文章我会简单介绍一下如何使用GEE来制作GIF动画。 相关API如下: 参数含义: params:设置GIF动画显示参数,详细的参数可以参考ee.data.getMapId() callback:回调…...
react中的useEffect
是函数组件中执行的副作用,副作用就是指每次组件更新都会执行的函数,可以用来取代生命周期。 1. 基本用法 import { useEffect } from "react"; useEffect(()>{console.log(副作用); });2. 副作用分为需要清除的和不需要清除 假如设置…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
