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

2023-3-10 刷题情况

打家劫舍 IV

题目描述

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上,从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ,表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

样例

样例输入

nums = [2,3,5,9], k = 2
nums = [2,7,9,3,1], k = 2

样例输出

5
2

提示

  • 1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
  • 1<=nums[i]<=1091 <= nums[i] <= 10^91<=nums[i]<=109
  • 1<=k<=(nums.length+1)/21 <= k <= (nums.length + 1)/21<=k<=(nums.length+1)/2

思路

这题目刚开始根本想不到使用二分+动态规划。
看的题解

代码实现

class Solution {int[] nums;int k;public int minCapability(int[] nums, int k) {this.nums = nums;this.k = k;int r = 0;for(var n : nums)if(r < n)r = n;int l = 1; while(l <= r){int mid = (l + r) >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}return l;}private boolean check(int num){int dp0 = 0, dp1 = 0;for(var n : nums){if(n > num) dp0 = dp1;else{int tmp = dp1;dp1 = Math.max(dp1, dp0 + 1);dp0 = tmp;}}return dp1 >= k;}
}

获得分数的方法数

题目描述

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ,其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道,每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大,结果需要对 109 +7 取余。

注意,同类型题目无法区分。

比如说,如果有 3 道同类型题目,那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

样例

样例输入

target = 6, types = [[6,1],[3,2],[2,3]]
target = 5, types = [[50,1],[50,2],[50,5]]
target = 18, types = [[6,1],[3,2],[2,3]]

样例输出

7
4
1

提示

  • 1 <= target <= 1000
  • n == types.length
  • 1 <= n <= 50
  • types[i].length == 2
  • 1 <= counti, marksi <= 50

思路

分组背包模版题,但还是初次接触,借鉴了一下

代码实现

class Solution {public int waysToReachTarget(int target, int[][] types) {int MOD = (int)1e9 + 7;long[] dp = new long[target + 1];dp[0] = 1;for(int[] type : types){for(int i = target; i > 0; i--){for(int j = 1; j <= Math.min(type[0], i / type[1]); j++){dp[i] += dp[i - type[1] * j];}dp[i] %= MOD;}}return (int)dp[target];}
}

相关文章:

2023-3-10 刷题情况

打家劫舍 IV 题目描述 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统&#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大…...

如何建立一个成功的MES?

制造执行系统&#xff08;MES&#xff09;是一种为制造业企业提供实时生产过程控制、管理和监视的信息系统。一个成功的MES系统可以帮助企业提高生产效率&#xff0c;降低成本&#xff0c;提高产品质量&#xff0c;提高客户满意度等。下面是一些关键步骤来建立一个成功的MES系统…...

Kafka生产者幂等性/事务

Kafka生产者幂等性/事务幂等性事务Kafka 消息交付可靠性保障&#xff1a; Kafka 默认是&#xff1a;至少一次最多一次 (at most once) : 消息可能会丢失&#xff0c;但绝不会被重复发送至少一次 (at least once) : 消息不会丢失&#xff0c;但有可能被重复发送精确一次 (exact…...

JavaWeb--案例(Axios+JSON)

JavaWeb--案例&#xff08;AxiosJSON&#xff09;1 需求2 查询所有功能2.1 环境准备2.2 后端实现2.3 前端实现2.4 测试3 添加品牌功能3.1 后端实现3.2 前端实现3.3 测试1 需求 使用Axios JSON 完成品牌列表数据查询和添加。页面效果还是下图所示&#xff1a; 2 查询所有功能 …...

css制作动画(动效的序列帧图)

相信 animation 大家都用过很多&#xff0c;知道是 CSS3做动画用的。而我自己就只会在 X/Y轴 上做位移旋转&#xff0c;使用 animation-timing-function 规定动画的速度曲线&#xff0c;常用到的 贝塞尔曲线。但是这些动画效果都是连续性的。 今天发现个新功能 animation-timi…...

【设计模式】装饰器模式

装饰器模式 以生活中的场景来举例&#xff0c;一个蛋糕胚&#xff0c;给它涂上奶油就变成了奶油蛋糕&#xff0c;再加上巧克力和草莓&#xff0c;它就变成了巧克力草莓蛋糕。 像这样在不改变原有对象的基础之上&#xff0c;将功能附加到原始对象上的设计模式就称为装饰模式(D…...

Nginx配置实例-反向代理案例一

实现效果&#xff1a;使用nginx反向代理&#xff0c;访问 www.suke.com 直接跳转到本机地址127.0.0.1:8080 一、准备工作 Centos7 安装 Nginxhttps://liush.blog.csdn.net/article/details/125027693 1. 启动一个 tomcat Centos7安装JDK1.8https://liush.blog.csdn.net/arti…...

Java中IO流中字节流(FileInputStream(read、close)、FileOutputStream(write、close、换行写、续写))

IO流&#xff1a;存储和读取数据的解决方案 纯文本文件&#xff1a;Windows自带的记事本打开能读懂 IO流体系&#xff1a; FileInputStream&#xff1a;操作本地文件的字节输入流&#xff0c;可以把本地文件中的数据读取到程序中来 书写步骤&#xff1a;①创建字节输入流对象 …...

C#完全掌握控件之-combbox

无论是QT还是VC&#xff0c;这些可视化编程的工具&#xff0c;掌握好控件的用法是第一步&#xff0c;C#的控件也不例外&#xff0c;尤其这些常用的控件。常见控件中较难的往往是这些与数据源打交道的&#xff0c;比如CombBox、ListBox、ListView、TreeView、DataGridView. 文章…...

STL的空间配置器(allocator)

简答&#xff1a; 在CSTL中&#xff0c;空间配置器便是用来实现内存空间(一般是内存&#xff0c;也可以是硬盘等空间)分配的工具&#xff0c;他与容器联系紧密&#xff0c;每一种容器的空间分配都是通过空间分配器alloctor实现的。 解析: 1.两种C类对象实例化方式的异同在c中&a…...

linux系统莫名其妙的环境变量问题

今天使用Ubuntu20.04系统&#xff0c;使用less命令查看日志&#xff0c;发现日志中的“中文”显示为乱码&#xff1b; 使用vim命令查看该日志文件也显示为乱码&#xff1b; 使用more命令查看该日志文件则显示正常。 首先查询系统的字符集编码&#xff0c;发现编码正常支持中…...

使用 Microsoft Dataverse 简化的连接快速入门

重复昨天本地部署dynamics实例将其所有的包删除之后&#xff0c;再次重新下载回来。运行填写跟之前登陆插件一样的信息点击login 然后查看控制台&#xff0c;出现这样就说明第一个小示例就完成了。查看你的dy365平台下的 “我的活动”就可以看到刚刚通过后台代码创建的东西了。…...

PLSQL Developer 安装指南

PLSQL Developer 是 Oracle 的客户端。 下面以64位破解版的PLSQL Developer为例&#xff0c;进行PLSQL Developer 安装讲解。 0. 下载 PLSQL Developer https://download.csdn.net/download/Shipley_Leo/87557938 1. 根据操作系统选择对应“plsqldev.exe”可执行文件&#xff…...

腾讯云企业网盘2.5版本全新发布啦!!!

腾讯云企业网盘又又又更新啦&#xff01;本期重点打磨管理协同、企业安全守护能力&#xff0c;同时也不断强化自身产品体验&#xff0c;助力企业高效办公~那么&#xff0c;此次更新具体有什么安全可靠的新功能呢&#xff1f;今天就带大家一起解锁~01协同管理&#xff0c;提升工…...

Excel职业版本(4)

图表 图表基本结构 组成元素 图表的分类 柱状图 介绍&#xff1a;在竖直方向比较不同类型的数据 适用场景&#xff1a;用于二维数据集&#xff0c;对于不同类型的数据进行对比&#xff0c;也可用于同一类型的数据在不同的时间维度的数据对比&#xff0c;通过柱子的高度来反…...

3-2 SpringCloud快速开发入门:Ribbon 实现客户端负载均衡

接上一章节Ribbon 是什么&#xff0c;这里讲讲Ribbon 实现客户端负载均衡 Ribbon 实现客户端负载均衡 由于 Spring Cloud Ribbon 的封装&#xff0c; 我们在微服务架构中使用客户端负载均衡调用非常简单&#xff0c; 只需要如下两步&#xff1a; 1、启动多个服务提供者实例并…...

ChatGPT,乌合之众的疯狂

最近ChatGPT有多火爆就不用我说了。公司里&#xff0c;从CEO到技术人员&#xff0c;乃至于门口的保安、食堂的大婶&#xff0c;没有一个不会聊两句ChatGPT的。连我20年未见的小学同学、三线城市警官&#xff0c;都问我这东西能不能给领导写汇报材料。 用不了多久&#xff0c;家…...

代码随想录刷题-数组-长度最小的子数组

文章目录长度最小的子数组习题暴力解法滑动窗口长度最小的子数组 本节对应代码随想录中&#xff1a;代码随想录&#xff0c;讲解视频&#xff1a;拿下滑动窗口&#xff01; | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili 习题 题目链接&#xff1a;209. 长度最小的子数…...

成功解决安装MySQL5.7提示公钥GPG密钥配置为file:///etc/pki/rpm-gpg/RPM-GPG-KEY-mysql

前言 大家好,我是沐风晓月,今天做MySQL5.7安装的时候遇到问题了,我们一起来复盘下这个问题,如果你使用我的方法没有解决,一定要留言给我,我们一起来排查和学习和完善。 本文收录于csdn 我是沐风晓月的专栏 【日常遇到的疑难问题和bug解决】 ,若点击无法跳转,请在csdn …...

vue配置环境变量

目录 创建配置文件 .env.development 文件 .env.production 文件 .env.dev 文件 使用变量 配置 package.json 文件 例子&#xff1a;在 api.js 使用 可以继续添加 创建配置文件 在根目录与 package.json 同级创建文件 .env.development、 .env.production、.env.dev 文件…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 public class VariableDemo {publi…...

C++11 constexpr和字面类型:从入门到精通

文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...

多模态大语言模型arxiv论文略读(110)

CoVLA: Comprehensive Vision-Language-Action Dataset for Autonomous Driving ➡️ 论文标题&#xff1a;CoVLA: Comprehensive Vision-Language-Action Dataset for Autonomous Driving ➡️ 论文作者&#xff1a;Hidehisa Arai, Keita Miwa, Kento Sasaki, Yu Yamaguchi, …...