当前位置: 首页 > news >正文

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. 删除并获得点数

题目 对于该题的题目分析&#xff0c;已经代码分析都一并写入到了代码注释中 代码 class Solution {public int deleteAndEarn(int[] nums) {//核心思路&#xff1a;//由于我们获得 nums[i] 的点数之后&#xff0c;就必须删除所有等于 nums[i] - 1 和 nums[i] 1 的元素//假设…...

算法通关村十三关-青铜:数字与数学基础问题

1.数字统计专题 统计特定场景下的符号或数字个数等 1.1符号统计 LeetCode1822 数组元素积的符号 https://leetcode.cn/problems/sign-of-the-product-of-an-array/description/ 思路分析 如果将所有的数都乘起来&#xff0c;再判断正负&#xff0c;工作量大&#xff0c;还…...

猜拳游戏小程序源码 大转盘积分游戏小程序源码 积分游戏小程序源码

简介&#xff1a; 猜拳游戏大转盘积分游戏小程序前端模板源码&#xff0c;一共五个静态页面&#xff0c;首页、任务列表、大转盘和猜拳等五个页面 图片&#xff1a;...

【Python】爬虫练习-爬取豆瓣网电影评论用户的观影习惯数据

目录 前言 一、配置环境 1.1、 安装Python 1.2、 安装Requests库和BeautifulSoup库 1.3.、安装Matplotlib 二、登录豆瓣网&#xff08;重点&#xff09; 2.1、获取代理 2.2、测试代理ip是否可用 2.3、设置大量请求头随机使用 2.4、登录豆瓣网 三、爬取某一部热门电影…...

webpack基础配置【总结】

webpack打包原理&#xff1a; webpack是一个js应用程序的静态模块打包工具&#xff0c;当webpack处理应用程序时&#xff0c;它的内部构建一个依赖图&#xff0c;此时依赖会映射项目中所需的每个模块&#xff0c;并生成一个或多个bundle包。因此我们会安装配置各种打包规则&…...

typescript 支持与本地调试

typescript 支持与本地调试 typescript 支持与本地调试 前言支持 typescript函数的本地调试 启用 node-terminal 调试invoke localserverless-offline Next Chapter完整示例及文章仓库地址 前言 在上一章节&#xff0c;我们创建了一个 hello world 函数&#xff0c;并把它顺…...

后端面试话术集锦第 十八 篇:JVM面试话术

这是后端面试集锦第十八篇博文——JVM面试话术❗❗❗ 1. 介绍下JVM JVM主要包括:类加载器(class loader)、执行引擎(exection engine)、本地接口(native interface)、运行时数据区(Runtimedata area) 类加载器:加载类文件到内存。Class loader只管加载,只要符合文件…...

“历久弥新 | 用AI修复亚运珍贵史料”活动震撼来袭!

时隔近半个世纪&#xff0c;新中国第一次参与亚运会的影像资料将首次对外披露。只是年代久远&#xff0c;老照片老视频都有了岁月痕迹&#xff0c;画面不再清晰&#xff0c;这些珍贵史料急需你的帮助&#xff01; 一、活动介绍 2023年&#xff0c;正值亚运110周年&#xff0c…...

uni-app 之 scroll-view和swiper

uni-app 之 scroll-view和swiper <!-- vue2的<template>里必须要有一个盒子&#xff0c;不能有两个&#xff0c;这里的盒子就是 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 自动化】自媒体剪辑第一版·思路简述与技术方案

大家都知道我主业是个运维开发&#xff08;或者算法工程师&#xff09;&#xff0c;每天时间不多&#xff0c;但我又想做自媒体。然后呢&#xff0c;我就想了个方案&#xff0c;每天起来之后写个短视频的脚本&#xff0c;包含一系列图片和文字&#xff0c;然后上班的时候给它提…...

【前端】webpack打包去除console.log

0 问题 需要在打包的时候&#xff0c;自动地去除掉所有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使用&#xff08;二&#xff09; dockerhub创建账号创建存储库成功&#xff01;开始推送获取image名 提交成功SpringBoot项目制作Dockerfile镜像部署打jar包 dockerhub创建账号 &#xff08;自认为可以理解为github一类的东西&#xff09; 单击创建存储库按钮。 设定存…...

antd中Popover 气泡卡片样式修改

最近在开发react项目的一个新需求时&#xff0c;遇到气泡卡片Popover组件样式调整的问题&#xff0c;发现不管是在标签中设置className属性&#xff0c;还是在<Popover>标签中直接设置style属性&#xff0c;都不起作用。 最后搜索查阅发现要使用overlayClassName index…...

3月面试华为被刷,准备半年,9月二战华为终于上岸,要个27K不过分吧?

终于二战上岸了&#xff0c;二战华为也并不是说非华为不可&#xff0c;只是觉得心里憋着一口气&#xff0c;这就导致我当时有其他比较好的offer&#xff0c;我也没有去&#xff0c;就是想上岸华为来证明自己,现在也算是如愿了&#xff0c;来跟大伙们分享一下~ 个人情况 我本人…...

Kali之BurpSuite_pro安装配置

文章目录 配置jdk环境安装BurpSuitePro设置快捷方式启动方式 BurpSuite2021专业版本地址&#xff1a; 下载链接&#xff1a;https://pan.baidu.com/s/1PjzcukRDoc_ZFjrNxI8UjA 提取码&#xff1a;nwm7 我的安装工具都在/home/kali/tools/ 解压后我放在burpsuite_pro目录下 把j…...

双指针算法总结

双指针 常见的双指针有两种形式&#xff1a;对撞指针&#xff0c;左右指针。 对撞指针&#xff1a; 对撞指针一般用于顺序结构中&#xff0c;也称左右指针。 • 对撞指针从两端向中间移动。以个指针从最左端开始&#xff0c;另⼀个从最右端开始&#xff0c;然后逐渐往中间逼…...

开源照片管理服务LibrePhotos

本文是为了解决网友 赵云遇到的问题&#xff0c;顺便折腾的。虽然软件跑起来了&#xff0c;但是他遇到的问题&#xff0c;超出了老苏的认知。当然最终问题还是得到了解决&#xff0c;不过与 LibrePhotos 无关&#xff1b; 什么是 LibrePhotos ? LibrePhotos 是一个自托管的开源…...

Linux指令

1 Linux 系统目录结构 /bin 存放系统指令&#xff08;可执行文件&#xff09; /boot 存放linux系统开机引导程序 /dev 存放设备文件的地方 /etc 存放系统配置文件的地方 /home 存放用户家目录的地方。 /lib和/lib64 存放系统动态链接库的地方。 /lostfound linux文件系统下特有…...

如何在Mac电脑上安装WeasyPrint:简单易懂的步骤

1. 安装homebrew 首先需要确保安装了homebrew&#xff0c;通过homebrew安装weasyprint可以将需要的库都安装好&#xff0c;比pip安装更简单快捷。 安装方法如下&#xff1a; /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)&qu…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...