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

【小白友好】LeetCode 删除并获得点数

基础题

打家劫舍https://leetcode.cn/problems/house-robber/

小白解法

  • 删除nums[i]就会使得所有nums[i]-1nums[i]+1的值都消失,手写了几个,发现找来找去不方便,还不如先排个序,然后这样nums[i]-1nums[i]nums[i]+1就能靠在一起了,这样删的时候方便找。
  • 只要获得一次nums[i]的点数那么肯定是要一起把所有的nums[i]都要带上的,也就是获得nums[i]*nums[i]次数个点数

嗯,发现[1,1,1,2,2,3,4,5]的时候怎么这么熟悉,选1就不能选2,选2就不能选3,这不是相邻的2个数不能一起选?这不是打家劫舍吗?

但是也有所区别,当相邻的2个值相差不是1时,可以直接获得,不需要“打家劫舍”。我们此时说的“相邻”是在[1,2,3,4]这个新构造的数组上的相邻,而不是原数组[1,1,1,2,2,3,4,5]未知的相邻。 也就是把每个相同元素的数字看成1个数,其对应的能获得点数是nums[i]*nums[i]次数

那么要怎么新构造的数组?可以使用C++风格的直接[0 for i in range(max(nums))]构造一个可能超长的数组,然后把对应位置的元素填上,解起来就跟打家劫舍的写法一模一样了;也可以使用一个字典num2value,统计key能获得的value,然后在判断的时候加入是否abs(nums[i]-nums[i-1])==1

我个人还是倾向于字典的写法:

class Solution:def deleteAndEarn(self, nums: List[int]) -> int:# 统计每个数字对应能获得的点数from collections import defaultdictnum2value=defaultdict(int)for n in nums:num2value[n]+=n# 构造新数组sorted_nums        sorted_nums=sorted(set(nums))if len(sorted_nums)==1:return num2value[nums[0]]if len(sorted_nums)==2:if abs(sorted_nums[0]-sorted_nums[1])==1:return max(num2value[sorted_nums[0]],num2value[sorted_nums[1]])else:return num2value[sorted_nums[0]]+num2value[sorted_nums[1]]# 上述特殊情况# 下面是初始化+转移方程dp=[0 for _ in range(len(sorted_nums))]dp[0]=num2value[sorted_nums[0]]if abs(sorted_nums[0]-sorted_nums[1])==1:# 如果是相邻元素,那么就是打家劫舍式的更新dpdp[1]= max(num2value[sorted_nums[0]],num2value[sorted_nums[1]])else:# 若不是,可以直接+,不受影响dp[1]= num2value[sorted_nums[0]]+num2value[sorted_nums[1]]for i in range(2,len(sorted_nums)):if abs(sorted_nums[i]-sorted_nums[i-1])!=1:dp[i]=dp[i-1]+num2value[sorted_nums[i]]else:select_now=num2value[sorted_nums[i]]+dp[i-2]unselect_now=dp[i-1]dp[i]=max(select_now,unselect_now)# print(dp)return dp[-1]

在写完下方的一般情况后,仍然不要忘了特殊情况,下方的下标是有i-1和i-2的,这两种需要单独去返回。

不得不说小白写法写的真的很繁琐,不优美,但是便于理解。

相关文章:

【小白友好】LeetCode 删除并获得点数

基础题 打家劫舍https://leetcode.cn/problems/house-robber/ 小白解法 删除nums[i]就会使得所有nums[i]-1和nums[i]1的值都消失,手写了几个,发现找来找去不方便,还不如先排个序,然后这样nums[i]-1和nums[i]和nums[i]1就能靠在…...

c#委托、lambda、事件

Lambda Lambda表达式是一种匿名函数,Lambda表达式通常以箭头“>”分隔左侧的输入和右侧的输出。 (parameter_list) > { statement_block } parameter_list 是由一个或多个参数组成的逗号分隔列表,每个参数都包括类型和名称,可以为空。…...

每日一练——9×9乘法表

#include<stdio.h>int main() {int i 0; //乘数定义for (i 1; i < 9; i) //循环1到9 {int j 0;//被乘数定义for (j 1; j < i; j) //循环被乘数1到9{printf("%d*%d%2d ", i, j, i * j); 乘法}printf("\n"); 换行} return 0; }...

大白话解析LevelDB:ShardedLRUCache

文章目录 Cache 接口定义ShardedLRUCache 的实现ShardedLRUCache 的构造函数ShardedLRUCache::Insert(const Slice& key, void* value, size_t charge, void (\*deleter)(const Slice& key, void* value))ShardedLRUCache::Lookup(const Slice& key)ShardedLRUCach…...

GDOI2024游记

Day0 中午一点钟从学校出发去东莞&#xff0c;大概坐了一个多小时车&#xff0c;两点半多到酒店。住的八方精选酒店&#xff08;ljh说他们住九方精选酒店&#xff0c;乐&#xff09;&#xff0c;说的是景区酒店&#xff0c;但打开外窗&#xff0c;近处是简陋的阳台&#xff0c…...

学编程怎么样才能更快入手,编程怎么简单易学

学编程怎么样才能更快入手&#xff0c;编程怎么简单易学 一、前言 对于初学编程建议先从简单入手&#xff0c;然后再学习其他复杂的编程语言。 今天给大家分享的中文编程开发语言工具 进度条构件的用法。 编程入门视频教程链接 https://edu.csdn.net/course/detail/39036 …...

Android 通知--判断通知是否有跳转

一. 从应用层来分析 在 Android 中&#xff0c;可以通过 PendingIntent 来实现有跳转的通知和没有跳转的通知的区别。具体来说&#xff0c;有跳转的通知会设置一个 PendingIntent&#xff0c;当用户点击通知时会触发该 PendingIntent&#xff0c;打开指定的界面或执行特…...

【计算机网络】IO多路转接之poll

文章目录 一、poll函数接口二、socket就绪条件三、poll的优点四、poll的缺点五、poll使用案例--只读取数据的server服务器1.err.hpp2.log.hpp3.sock.hpp4.pollServer.hpp5.main.cc 一、poll函数接口 #include <poll.h> int poll(struct pollfd *fds, nfds_t nfds, int t…...

性能比较:in和exists

当在Hive SQL中使用NOT IN和NOT EXISTS时&#xff0c;性能差异主要取决于底层数据的组织方式、数据量大小、索引的使用情况以及具体查询的复杂程度。下面是对这两种方法的性能分析&#xff1a; 1. NOT IN&#xff1a;- 工作原理&#xff1a;NOT IN子查询会逐个比较主查询中的值…...

【Java设计模式】五、建造者模式

文章目录 1、建造者模式2、案例&#xff1a;共享单车的创建3、其他用途 1、建造者模式 某个对象的构建复杂将复杂的对象的创建 和 属性赋值所分离&#xff0c;使得同样的构建过程可以创建不同的表示建造的过程和细节调用者不需要知道&#xff0c;只需要通过构建者去进行操作 …...

nginx代理minio教程 避坑过的教程 避开SignatureDoesNotMatch

本次教程使用的是单机minio进行演示&#xff0c;集群minio也和这个差不多。 按照这个教程&#xff0c;可以避开nginx代理minio之后&#xff0c;只能访问文件&#xff0c;但是通过预签名url上传文件就会报SignatureDoesNotMatch的坑 暂定如下&#xff1a; 你已经下载好miniom…...

Linux进程详细介绍

文章目录 Linux进程1、计算机体系结构和操作系统管理1.1、计算机体系结构 -- 硬件1.2、操作系统&#xff08;Operator System&#xff09; -- 软件 2、进程2.1、进程基本概念2.2、进程标识符2.2.1、获取当前进程标识符和当前进程的父进程标识符2.2.2、通过系统调用创建进程 -- …...

2024年3月产品认证基础考试简答题及答案

产品认证基础 46.产品认证的工厂检查有哪几种路线&#xff1f;各有什么优缺点&#xff1f; 答案&#xff1a;两种常用的检查路线&#xff1a; 1.按照要素或过程检查 按照认证规则规定的工厂应满足的要素要求&#xff08;包括质量保证能力要求&#xff09;&#xff0c;结合部…...

嵌入式蓝桥杯做题总结

第十二届省赛 按键代码 ——自认为比较巧妙&#xff0c;定时器3被设置为10ms进入一次中断&#xff0c;代替了HAL_Delay(10)的方法消抖&#xff1b; 运用状态机机思想实现检测多个按键检测——且分为两个状态&#xff0c;其中一个状态PB&#xff11;和PB&#xff12;的按键不…...

Spring Boot 常用注解大全

以下是Spring Boot中常用的注解及其详细解释以及相应的代码示例&#xff1a; SpringBootApplication: 这个注解用于标识一个Spring Boot应用的主类。它整合了 Configuration&#xff0c;EnableAutoConfiguration 和 ComponentScan。 SpringBootApplication public class Demo…...

(MATLAB)第十二章-数列与极限

目录 12.1 数列 12.1.1 数列求和 1. 累计求和函数sum() 2. 忽略NaN累计求和函数 nansum() 3. 求此元素位置之前的元素和函数cumsum() 4. 求梯形累计和函数cumtrapz() 12.1.2 数列求积 1. 元素连续相乘函数 prod() 2. 求累计积函数 cumprod() 3. 阶乘函数 ffactorial(n…...

OJ输入问题+准备

写在之前&#xff1a; 发现题目输入是这样的&#xff1a; 我的问题&#xff1a;如何通过空格分割这些输入的字符串并分别保存&#xff01;&#xff01;&#xff08;C语言scanf好解决一点但我选择C....&#xff09; C引入了ostringstream、istringstream、stringstream这三个类…...

软考高级:主动攻击和被动攻击概念和例题

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;大厂高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《Effective Java》独家解析》专栏作者。 热门文章推荐&am…...

cuda python torch 虚拟环境配置

以下是Pytorch和CUDA对应的版本 以下是Pytorch和Python对应的版本 检查cuda与Python版本是否匹配 import torch print(torch.__version__) print(torch.cuda.is_available()) print(torch.empty(3,4,devicecuda))cuda 删除cuda conda uninstall cudatoolkit --forceconda u…...

激光炸弹 刷题笔记

前置知识 二维前缀和 子矩阵的和 刷题笔记 {二维前缀和}-CSDN博客 思路 参考二维前缀和 将子矩阵的和 做成动态矩阵 一个个矩阵搜索 符合要求边长 矩阵中的元素和最大值 将x1,y1用i-k,j-k表示即可 x2,y2用i&#xff0c;j表示 代码 #include<iostream> #include<…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...