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. 副作用分为需要清除的和不需要清除 假如设置…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
