Java 动态规划 Leetcode 740. 删除并获得点数
题目
对于该题的题目分析,已经代码分析都一并写入到了代码注释中
代码
class Solution {public int deleteAndEarn(int[] nums) {//核心思路://由于我们获得 nums[i] 的点数之后,就必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素//假设我们现在要解决的数组为 1,2,3,4,5 当我们获得2的点数就不能获得 1,3 的点数,我们的选择就是 2,4 或者 1,3,5(即相邻的点数不能获取)//这样明显问题就简单了许多,所以我们要进行处理,将源数组转换为0,1,2,3...顺序排序的形式//我们可以创建一个辅助数组 arr ,让 arr 的下标表示源数组 nums[i] 的值, arr 的值表示源数组 nums[i] 值的总和//例如:对于nums=[2,2,3,3,3,4]// arr=[0,0,4,9,4]// 下标:0,1,2,3,4//对于arr数组,我们就可以转换问题为相邻的点数不能获取求最大点数//由于 arr 数组的下标表示 nums 数组的值,而 nums 数组的值的最大值为10000(由题可知),所以 arr 数组的下标也要有10000int n=10001;int[] arr=new int[n];//初始化arr数组for(int x:nums){arr[x]+=x;}//创建dp表//对于arr数组中的点数我们可以选择要也可以选择不要//假设 f[i] 表示下标为i的点数我们必定要时所得的点数最大值, g[i] 表示下标为i的点数我们必定不要时所得的点数最大值// f[i] 由于下标为i的点数我们必定要,所以下标i-1的点数我们必定不要,那么到下标 i 我们能够获得的最大点数为f[i]=g[i-1]+arr[i]// g[i] 由于下标为i的点数我们必定不要,所以下标为 i-1 的点数我们可以选择要也可以选择不要,由于我们要求最大点数,所以我们应该选择点数较大的情况//g[i]=Math.max(f[i-1],g[i-1])//由于点数最大能达到10000,所以我们最大要判断10000这个点数是要还是不要,所以f数组和g数组都要开辟10001的大小int[]f=new int[n];int[]g=new int[n];//初始化//根据上面对f数组和g数组的分析,我们知道 i 的取值应该从1开始,所以我们需要知道f[0]和g[0]的值f[0]=arr[0];//g[0]=0;//填充dp数组for(int i=1;i<n;i++){f[i]=g[i-1]+arr[i];g[i]=Math.max(f[i-1],g[i-1]);}//返回值//当我们填充完f和g数组后,我们就知道了最后一个数选和不选的最大值,由于我们要的是最大点数,所以返回的应该是两个最大值中较大的一个return Math.max(f[n-1],g[n-1]);}
}
相关文章:
Java 动态规划 Leetcode 740. 删除并获得点数
题目 对于该题的题目分析,已经代码分析都一并写入到了代码注释中 代码 class Solution {public int deleteAndEarn(int[] nums) {//核心思路://由于我们获得 nums[i] 的点数之后,就必须删除所有等于 nums[i] - 1 和 nums[i] 1 的元素//假设…...
算法通关村十三关-青铜:数字与数学基础问题
1.数字统计专题 统计特定场景下的符号或数字个数等 1.1符号统计 LeetCode1822 数组元素积的符号 https://leetcode.cn/problems/sign-of-the-product-of-an-array/description/ 思路分析 如果将所有的数都乘起来,再判断正负,工作量大,还…...
猜拳游戏小程序源码 大转盘积分游戏小程序源码 积分游戏小程序源码
简介: 猜拳游戏大转盘积分游戏小程序前端模板源码,一共五个静态页面,首页、任务列表、大转盘和猜拳等五个页面 图片:...
【Python】爬虫练习-爬取豆瓣网电影评论用户的观影习惯数据
目录 前言 一、配置环境 1.1、 安装Python 1.2、 安装Requests库和BeautifulSoup库 1.3.、安装Matplotlib 二、登录豆瓣网(重点) 2.1、获取代理 2.2、测试代理ip是否可用 2.3、设置大量请求头随机使用 2.4、登录豆瓣网 三、爬取某一部热门电影…...
webpack基础配置【总结】
webpack打包原理: webpack是一个js应用程序的静态模块打包工具,当webpack处理应用程序时,它的内部构建一个依赖图,此时依赖会映射项目中所需的每个模块,并生成一个或多个bundle包。因此我们会安装配置各种打包规则&…...
typescript 支持与本地调试
typescript 支持与本地调试 typescript 支持与本地调试 前言支持 typescript函数的本地调试 启用 node-terminal 调试invoke localserverless-offline Next Chapter完整示例及文章仓库地址 前言 在上一章节,我们创建了一个 hello world 函数,并把它顺…...
后端面试话术集锦第 十八 篇:JVM面试话术
这是后端面试集锦第十八篇博文——JVM面试话术❗❗❗ 1. 介绍下JVM JVM主要包括:类加载器(class loader)、执行引擎(exection engine)、本地接口(native interface)、运行时数据区(Runtimedata area) 类加载器:加载类文件到内存。Class loader只管加载,只要符合文件…...
“历久弥新 | 用AI修复亚运珍贵史料”活动震撼来袭!
时隔近半个世纪,新中国第一次参与亚运会的影像资料将首次对外披露。只是年代久远,老照片老视频都有了岁月痕迹,画面不再清晰,这些珍贵史料急需你的帮助! 一、活动介绍 2023年,正值亚运110周年,…...
uni-app 之 scroll-view和swiper
uni-app 之 scroll-view和swiper <!-- vue2的<template>里必须要有一个盒子,不能有两个,这里的盒子就是 view--> <template><view><navigator url"/pages/home/home"><button style"background: #ff00f…...
Harmony网络请求工具类
使用的网络请求框架是axios 1、安装axios ohpm install @ohos/axios2、封装 import axios, { FormData } from "@ohos/axios" import fs from @ohos.file.fs import ArrayList from @ohos.util.ArrayList/*** 网络请求工具类*/ class HttpManager {baseUrl:string…...
【Python 自动化】自媒体剪辑第一版·思路简述与技术方案
大家都知道我主业是个运维开发(或者算法工程师),每天时间不多,但我又想做自媒体。然后呢,我就想了个方案,每天起来之后写个短视频的脚本,包含一系列图片和文字,然后上班的时候给它提…...
【前端】webpack打包去除console.log
0 问题 需要在打包的时候,自动地去除掉所有console.log 1 方法 // vue.config.js //... module.exports {//...config.optimization.minimizer[0].iptions.terserOptions.compress.drop_console true//... } //...也可以用if(process.env.NODE_ENV production…...
docker使用(二)提交到dockerhub springboot制作镜像
docker使用(二) dockerhub创建账号创建存储库成功!开始推送获取image名 提交成功SpringBoot项目制作Dockerfile镜像部署打jar包 dockerhub创建账号 (自认为可以理解为github一类的东西) 单击创建存储库按钮。 设定存…...
antd中Popover 气泡卡片样式修改
最近在开发react项目的一个新需求时,遇到气泡卡片Popover组件样式调整的问题,发现不管是在标签中设置className属性,还是在<Popover>标签中直接设置style属性,都不起作用。 最后搜索查阅发现要使用overlayClassName index…...
3月面试华为被刷,准备半年,9月二战华为终于上岸,要个27K不过分吧?
终于二战上岸了,二战华为也并不是说非华为不可,只是觉得心里憋着一口气,这就导致我当时有其他比较好的offer,我也没有去,就是想上岸华为来证明自己,现在也算是如愿了,来跟大伙们分享一下~ 个人情况 我本人…...
Kali之BurpSuite_pro安装配置
文章目录 配置jdk环境安装BurpSuitePro设置快捷方式启动方式 BurpSuite2021专业版本地址: 下载链接:https://pan.baidu.com/s/1PjzcukRDoc_ZFjrNxI8UjA 提取码:nwm7 我的安装工具都在/home/kali/tools/ 解压后我放在burpsuite_pro目录下 把j…...
双指针算法总结
双指针 常见的双指针有两种形式:对撞指针,左右指针。 对撞指针: 对撞指针一般用于顺序结构中,也称左右指针。 • 对撞指针从两端向中间移动。以个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼…...
开源照片管理服务LibrePhotos
本文是为了解决网友 赵云遇到的问题,顺便折腾的。虽然软件跑起来了,但是他遇到的问题,超出了老苏的认知。当然最终问题还是得到了解决,不过与 LibrePhotos 无关; 什么是 LibrePhotos ? LibrePhotos 是一个自托管的开源…...
Linux指令
1 Linux 系统目录结构 /bin 存放系统指令(可执行文件) /boot 存放linux系统开机引导程序 /dev 存放设备文件的地方 /etc 存放系统配置文件的地方 /home 存放用户家目录的地方。 /lib和/lib64 存放系统动态链接库的地方。 /lostfound linux文件系统下特有…...
如何在Mac电脑上安装WeasyPrint:简单易懂的步骤
1. 安装homebrew 首先需要确保安装了homebrew,通过homebrew安装weasyprint可以将需要的库都安装好,比pip安装更简单快捷。 安装方法如下: /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)&qu…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
