3.31 代码随想录第三十一天打卡
1049.最后一块石头的重量II
(1)题目描述:
(2)解题思路:
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};
(3)总结:
1.石头相撞,把石头分为重量总和基本相等的两堆(比如看示例石头总和为23,那如果分为11和12的两队相撞后重量最小为1)
2.物品的数值即是重量又是价值
3.23/2==11向下取整,sum-z*11==1
4.dp[j]的定义是石头重量总和
494.目标和
(1)题目描述:
(2)解题思路:
1.一维数组方法
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};
2.二维数组方法:
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));// 初始化最上行if (nums[0] <= bagSize) dp[0][nums[0]] = 1; // 初始化最左列,最左列其他数值在递推公式中就完成了赋值dp[0][0] = 1; int numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);}// 以下遍历顺序行列可以颠倒for (int i = 1; i < nums.size(); i++) { // 行,遍历物品for (int j = 0; j <= bagSize; j++) { // 列,遍历背包if (nums[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};
(3)总结:
1.dp[j] 容量为j 有dp[j]种方法
题可以转化成我们常见的「背包模型」的问题。设我们最终选取的结果中,前面加 + 号的数字之和为 a ,前面加 - 号的数字之和为 b ,整个数组的总和为 sum ,于是我们有:
a + b = sum
a - b = target
上面两个式子消去 b 之后,可以得到 a = (sum + target) / 2
也就是说,我们仅需在 nums 数组中选择一些数,将它们凑成和为 (sum + target) / 2 即
可。问题就变成了 416. 分割等和子集 这道题。我们可以用相同的分析模式,来处理这道题。
1. 状态表示:
dp[i][j] 表示:在前 i 个数中选,总和正好等于 j ,一共有多少种选法。
2. 状态转移方程:
老规矩,根据「最后一个位置」的元素,结合题目的要求,我们有「选择」最后一个元素或者「不选择」最后一个元素两种策略:
不选 nums[i] :那么我们凑成总和 j 的总方案,就要看在前 i - 1 个元素中选,凑成总和为 j 的方案数。根据状态表示,此时 dp[i][j] = dp[i - 1][j] ;
选择 nums[i] :这种情况下是有前提条件的,此时的 nums[i] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和大,选择它就没有意义呀。那么我们能够凑成总和为j 的方案数,就要看在前 i - 1 个元素中选,能否凑成总和为 j - nums[i] 。根据状态表示,此时 dp[i][j] = dp[i - 1][j - nums[i]]
综上所述,两种情况如果存在的话,应该要累加在一起。因此,状态转移方程为:
dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] += dp[i - 1][j - nums[i- 1]]
3. 初始化:
由于需要用到「上一行」的数据,因此我们可以先把第一行初始化。第一行表示不选择任何元素,要凑成目标和 j 。只有当目标和为 0 的时候才能做到,因此第一行仅需初始化第一个元素 dp[0][0] = 1
4. 填表顺序:
根据「状态转移方程」,我们需要「从上往下」填写每一行,每一行的顺序是「无所谓的」。
5. 返回值:
根据「状态表示」,返回 dp[n][aim] 的值。其中 n 表示数组的大小, aim 表示要凑的目标和。
474.一和零
(1)题目描述:
(2)解题思路:
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};
(3)总结:
1.dp[i][j] i个0 j个1 最多能装dp[i][j]个物品
相关文章:
3.31 代码随想录第三十一天打卡
1049.最后一块石头的重量II (1)题目描述: (2)解题思路: class Solution { public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum 0;for (int i 0; i < stones.size(); i) sum stones[i];int target sum / 2;for (in…...
基于网启PXE服务器的批量定制系统平台
一.项目背景 公司新购了一批服务器和台式机,需要为台式机和服务器安装系统,一部分需要安装国产OpenEuler,一部分要求安装CentOS 7.9,同时也要满足定制化需求,即按要求分区安装相应软件。 二.项目环境 安装win10/11 …...
Unity光线传播体积(LPV)技术实现详解
一、LPV技术概述 光线传播体积(Light Propagation Volumes)是一种实时全局光照技术,通过将场景中的间接光信息存储在3D网格中,实现动态物体的间接光照效果。 核心优势: 实时性能:相比传统光照贴图,支持动态场景 硬件…...
蓝桥杯备考---》贪心算法之矩阵消除游戏
我们第一次想到的贪心策略一定是找出和最大的行或者列来删除,每次都更新行和列 比如如图这种情况,这种情况就不如直接删除两行的多,所以本贪心策略有误 so我们可以枚举选的行的情况,然后再贪心的选择列和最大的列来做 #include …...
python+playwright 学习-93 结合pands 抓取网页表格数据
playwright 结合 pands 抓取网页表格数据 pandas 直接抓取网页表格数据 web 网页表格数据 """ 上海 202501 天气抓取 """ import pandas as pddf = pd.read_html(fhttp://www.tianqihoubao.com/lishi/shanghai/month/202501.html,encoding...
MVC编程
MVC基本概述 例子——显示本地文件系统结构 先分别拖入ListView,TableView,TreeView 然后在进行布局 在widget.cpp 结果 mock测试 1,先加入json测试对象 2.创建后端目录 3,在src添加新文件 在models文件夹里 在mybucket.h,添加测试用例的三个字段 4.在…...
51单片机总结
写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难,但我还是想去做! 本文写于:2025.03.31 51单片机学习总结(有感而发) 一、总结结语 一、总结 一路…...
端到端语音识别案例
《DeepSeek大模型高性能核心技术与多模态融合开发(人工智能技术丛书)》(王晓华)【摘要 书评 试读】- 京东图书 语音识别这一技术正如其名,是通过精密地解析说话人的语音来识别并准确转写出其所说的内容。它不仅仅是一个简单的转录过程&#…...
iOS自定义collection view的page size(width/height)分页效果
前言 想必大家工作中或多或少会遇到下图样式的UI需求吧 像这种cell长度不固定,并且还能实现的分页效果UI还是很常见的 实现 我们这里实现主要采用collection view,实现的方式是自定义一个UICollectionViewFlowLayout的子类,在这个类里对…...
CI/CD基础知识
什么是CI/CD CI:持续集成,开发人员频繁地将代码集成到主干(主分支)中每次集成都通过自动化构建和测试来验证,从而尽早发现集成错误,常用的CI工具包括Jenkins、Travis CI、CircleCI、GitLab CI等 CD&#…...
MySQL 的 SQL 语句执行顺序
MySQL 的 SQL 语句执行顺序并不完全按照代码的书写顺序执行,而是遵循一套固定的逻辑流程 1. FROM 和 JOIN 作用:确定查询的数据来源,包括表和它们的连接方式(如 INNER JOIN, LEFT JOIN 等)。 细节: 先执行…...
Dubbo(21)如何配置Dubbo的注册中心?
在分布式系统中,注册中心是一个关键组件,用于服务的注册和发现。Dubbo 支持多种注册中心,包括 ZooKeeper、Nacos、Consul、Etcd 等。下面详细介绍如何配置 Dubbo 的注册中心,以 ZooKeeper 为例。 配置步骤 引入依赖:…...
AISEO中的JSON 如何部署?
一、JSON 是什么? JSON(JavaScript Object Notation) 是一种轻量级的数据格式,用于在不同系统之间传递结构化信息。它的核心特点是: 易读:用简单的 {键: 值} 对表示数据,例如: json…...
力扣hot100——最长连续序列(哈希unordered_set)
题目链接:最长连续序列 1、错解:数组做哈希表(内存超出限制) int longestConsecutive(vector<int>& nums) {vector<bool> hash(20000000010, false);for(int i0; i<nums.size();i){hash[1000000000nums[i]]t…...
几种常见的.NET单元测试模拟框架介绍
目录 1. Moq 2. NSubstitute 3. AutoFixture 4. FakeItEasy 总结对比 单元测试模拟框架是一种在软件开发中用于辅助单元测试的工具。 它的主要作用是创建模拟对象来替代真实对象进行测试。在单元测试中,被测试的代码可能依赖于其他组件或服务,如数…...
装饰器模式与模板方法模式实现MyBatis-Plus QueryWrapper 扩展
pom <dependency><groupId>com.github.yulichang</groupId><artifactId>mybatis-plus-join-boot-starter</artifactId> <!-- MyBatis 联表查询 --> </dependency>MPJLambdaWrapperX /*** 拓展 MyBatis Plus Join QueryWrapper 类&…...
11-SpringBoot3入门-整合aop
1、概念(个人理解) AOP(Aspect Oriented Programming),面向切面编程。 1)切面(Aspect):提供切入连接点的方法 2)连接点(Joinpoint)…...
naive_admin项目实战03 基于Go语言的后端
01.使用Goland打开项目 02.使用Goland连接MySQL 03.执行SQL脚本 set names utf8mb4; set foreign_key_checks 0;-- ---------------------------- -- table structure for permission -- ---------------------------- drop table if exists permission; create table permiss…...
基于卷积神经网络的眼疾识别系统,resnet50,efficentnet(pytorch框架,python代码)
更多图像分类、图像识别、目标检测、图像分割等项目可从主页查看 功能演示: 眼疾识别系统resnet50,efficentnet,卷积神经网络(pytorch框架,python代码)_哔哩哔哩_bilibili (一)简介…...
Python数据可视化-第1章-数据可视化与matplotlib
环境 开发工具 VSCode库的版本 numpy1.26.4 matplotlib3.10.1 ipympl0.9.7教材 本书为《Python数据可视化》一书的配套内容,本章为第1章 数据可视化与matplotlib 本文主要介绍了什么是数据集可视化,数据可视化的目的,常见的数据可视化方式…...
Ansible playbook-ansible剧本
一.playbook介绍 便于功能的重复使用 本质上就是文本文件,一般都是以.yml结尾的文本文件。 1.遵循YAML语法 1.要求同级别代码要有相同缩进,建议4个空格。【同级别代码是同一逻辑的代码】 在计算机看来空格和Tob键是两个不同的字符。 2.一个键对应一…...
UDP网络通信
UDP网络通信: 步骤1 创建套接字: #include <sys/types.h> #include <sys/socket.h>int socket(int domain, int type, int protocol);参数一 domain: AF_UNIX Local communication unix(7) 本地通信 AF_INET IPv4 Inte…...
【学习笔记】计算机网络(六)
第6章应用层 文章目录 第6章应用层6.1 域名系统DNS6.1.1 域名系统概述6.1.2 互联网的域名结构6.1.3 域名服务器域名服务器的分区管理DNS 域名服务器的层次结构域名服务器的可靠性域名解析过程-两种查询方式DNS 高速缓存机制 6.2 文件传送协议6.2.1 FTP 概述6.2.2 FTP 的基本工作…...
RK3588使用笔记:系统算法依赖库安装
一、前言 嵌入式设备随着需求的提升,不再仅仅只只运行个单机程序那么简单了,社会发展设备升级,都会逐步引用人工智能,涉及到算法模型,这里基础的部分就是算法环境的安装,有的算法是C,大部分算法…...
数据结构C语言练习(单双链表)
本篇练习题(单链表): 1.力扣 203. 移除链表元素 2.力扣 206. 反转链表 3.力扣 876. 链表的中间结点 4.力扣 21. 合并两个有序链表 5. 牛客 链表分割算法详解 6.牛客 链表回文结构判断 7. 力扣 160. 相交链表 8. 力扣 141 环形链表 9. 力扣 142 环形链表 II…...
Linux驱动开发 中断处理
目录 序言 1.中断的概念 2.如何使用中断 中断处理流程 中断上下文限制 屏蔽中断/使能 关键区别与选择 上半部中断 下半部中断 软中断(SoftIRQ) 小任务(Tasklet) 工作队列(Workqueue) 线程 IRQ(Threaded IRQ…...
C++ set map
1.set和map是什么 set和map是 C STL 提供的容器,用于高效的查找数据,底层采用红黑树实现,其中set是Key模型,map是Key-Value模型 set和map的基本使用较为简单,这里不再叙述,直接进入实现环节 2.set和map的…...
Vue2和Vue3响应式的基本实现
目录 简介Vue2 响应式Vue2 响应式的局限性 Vue3 响应式Vue3 响应式的优点 Vue2 和 Vue3 响应式对比 简介 在 Vue 框架中,数据的响应式是其核心特性之一。当页面数据发生变化时,我们希望界面能自动更新,而不是手动操作 DOM。这就需要对数据进…...
PyQt6实例_批量下载pdf工具_界面开发
目录 前置: 代码: 视频: 前置: 1 本系列将以 “PyQt6实例_批量下载pdf工具”开头,放在 【PyQt6实例】 专栏 2 本系列涉及到的PyQt6知识点: 线程池:QThreadPool,QRunnable; 信号…...
FOC 控制笔记【三】磁链观测器
一、磁链观测器基础 1.1 什么是磁链 磁链(magnetic linkage)是电磁学中的一个重要概念,指导电线圈或电流回路所链环的磁通量。单位为韦伯(Wb),又称磁通匝。 公式为: 线圈匝数 穿过单匝数的…...
前端Material-UI面试题及参考答案
目录 Material-UI 的设计理念与 Material Design 规范的关系是什么? 如何通过 npm/yarn/pnpm 安装 Material-UI 的核心依赖? Material-UI 的默认主题系统如何实现全局样式管理? 如何在项目中配置自定义字体和颜色方案? 什么是 emotion 和 styled-components,它们在 Ma…...
【LeetCode基础算法】链表所有类型
1. 遍历链表 二进制链表转整数找出临界点之间的最小和最大距离 2. 删除节点 移除链表元素从链表中移除在数组中存在的节点删除排序链表中的重复元素删除排序链表中的重复元素 II 3. 插入节点 在链表中插入最大公约数 计算最大公约数的内置函数gcd(a,b),也可以m…...
备赛蓝桥杯之第十六届模拟赛第1期职业院校组第五题:回忆画廊
提示:本篇文章仅仅是作者自己目前在备赛蓝桥杯中,自己学习与刷题的学习笔记,写的不好,欢迎大家批评与建议 由于个别题目代码量与题目量偏大,请大家自己去蓝桥杯官网【连接高校和企业 - 蓝桥云课】去寻找原题࿰…...
51 驱动 INA219 电流电压功率测量
文章目录 一、INA219简介二、引脚功能三、寄存器介绍1.配置寄存器 0x002.分流电压寄存器 0x013.总线电压寄存器 0x024.功率寄存器 0x035.电流寄存器 0x046.基准寄存器 0x05 四、IIC 时序说明1.写时序2.读时序 五、程序六、实验现象1.线路图2.输出数据 一、INA219简介 INA219是…...
JavaScript弹出框的使用:对话框、确认框、提示框、弹窗操作
关于 Window对象和 Document 对象的详细使用,系列文章: 《Window对象的常用属性和方法》 《Document对象的常用属性和方法:getElementById()、getElementsByName()、createElement()方法》 《Document获取元素并修改内容:getElementById()方法、value属性、innerHTML属性、…...
【设计模式】深入解析设计模式:门面模式(外观模式)的定义、优点和代码实现
门面模式(外观模式) SLF4J是门面模式的典型应用(但不仅仅使用了门面模式)。 门面模式定义 门面模式(Facade Pattern)又称为外观模式,提供了一个统一的接口,用来访问子系统中的一群…...
UE5学习笔记 FPS游戏制作34 触发器切换关卡
文章目录 搭建关卡制作触发器传送门显示加载界面 搭建关卡 首先搭建两个关卡,每个关卡里至少要有一个角色 制作触发器传送门 1 新建一个蓝图,父类为actor,命名为portal(传送门) 2 为portal添加一个staticMesh&#…...
UE5学习笔记 FPS游戏制作26 UE中的UI
文章目录 几个概念创建一个UI蓝图添加UI获取UI的引用 切换设计器和UI蓝图将UI添加到游戏场景锚点轴点slotSizeToContent三种UI数据更新方式(Text、Image)函数绑定属性绑定事件绑定 九宫格分割图片按钮设置图片绑定按下事件 下拉框创建添加数据修改样式常用函数 滚动框创建添加数…...
Spring Boot分布式项目重试实战:九种失效场景与正确打开方式
在分布式系统架构中,网络抖动、服务瞬时过载、数据库死锁等临时性故障时有发生。本文将通过真实项目案例,深入讲解Spring Boot项目中如何正确实施重试机制,避免因简单粗暴的重试引发雪崩效应。 以下是使用Mermaid语法绘制的重试架构图和决策…...
首个物业plus系列展 2025上海国际智慧物业博览会开幕
AI赋能服务升级!首个“物业plus”系列展 2025上海国际智慧物业博览会盛大开幕 3月31日,2025上海国际智慧物业博览会(简称“上海物博会”)在上海新国际博览中心N4馆隆重开幕。本届展会由广州旭杨国际展览有限公司主办,…...
《C++多线程下单例 “锁钥” 法则》
一、概述 本文章介绍了一段 C 代码,该代码实现了在多线程环境下的单例模式。单例模式确保一个类只有一个实例,并提供全局访问点。在多线程场景中,需要额外的同步机制来保证单例对象创建的线程安全性。单例模式在许多场景中都有重要应用&#…...
WEB或移动端常用交互元素及组件 | Axure / 元件类型介绍(表单元件、菜单和表格 、流程元件、标记元件)
文章目录 引言I Axure / 元件类型介绍基本元件表单元件菜单和表格流程元件标记元件II Axure 基础Axure / 常用功能介绍Axure / 常用元素实例Axure / 动态交互实例Axure / 常用设计分辨率推荐III Axure / 创建自己的元件库元件库作用元件库的创建及使用引言 I Axure / 元件类型介…...
开发环境解决Secure Cookie导致302重定向
问题现象与根源分析 故障现象 前端本地开发时(HTTP协议),调用接口返回302 Found状态码浏览器控制台警告:“Cookie被阻止,因为设置了Secure属性但未通过HTTPS传输”登录态无法保持,页面陷入重定向循环 技…...
华为三进制逻辑与高维量子计算的对比分析
此博客深入探讨华为三进制逻辑状态的技术意义,并与高维量子计算系统进行对比。文章将全面展开技术原理、实现机制、计算能力对比、未来应用前景等方面的内容。 目录 引言 华为三进制逻辑的创新意义 2.1 二进制逻辑的局限与历史探索 2.2 三进制逻辑的优势ÿ…...
网红指路机器人是否支持环境监测功能?
嘿呀,你可知道?如今的叁仟网红指路机器人那可太牛啦!它们可不单单局限于为行人指明方向,还纷纷兼职当起了 “环境小卫士”,为咱们的城市生活注入了前所未有的超智能便利。就拿那个依托叁仟智慧杆打造的数智指路机器人来…...
【进阶】vscode 中使用 cmake 编译调试 C++ 工程
基于 MSYS2 的 MinGW-w64 GCC 工具链与 CMake 构建系统,结合VSCode及其扩展插件( ms-vscode.cmake-tools),可实现高效的全流程C开发调试。既可通过 VSCode 可视化界面(命令面板、状态栏按钮)便捷完成配置、…...
突发,国行 iPhone 17,支持 eSIM
古人云“无心生大用”,往往你感到绝望的时候,转机就莫名其妙的来了。 根据供应链的最新消息,国行 iPhone 17 Air,有望用上 eSIM。 不仅如此,国产手机厂商,也计划推出类似iPhone 17 Air的超薄机型…...
红宝书第二十二讲:详解JavaScript类型化数组与二进制数据处理
红宝书第二十二讲:详解JavaScript类型化数组与二进制数据处理 资料取自《JavaScript高级程序设计(第5版)》。 查看总目录:红宝书学习大纲 一、为什么需要类型化数组? 普通JavaScript数组(Array࿰…...
Elasticsearch安全与权限控制指南
在Elasticsearch维护中,安全管理是保障数据合规性和集群稳定性的关键。本文将详细介绍用户与角色管理、索引/字段级权限控制、HTTPS加密通信、审计日志与合规性检查等核心安全实践,希望可以帮助你构建更安全的Elasticsearch环境。 1 用户与角色管理 1.1…...
SAP 学习笔记 - 系统移行业务 - MALSY(由Excel 移行到SAP 的收费工具)
以前有关移行,也写过一些文章,比如 SAP 学习笔记 - 系统移行业务 - Migration cockpit工具 - 移行Material(品目)-CSDN博客 SAP 学习笔记 - 系统移行业务 - Migration cockpit工具2 - Lot导入_sap cockpit-CSDN博客 SAP学习笔记…...