算法训练Day42|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零
背包类别
01背包:有n种物品,每种物品只有一个.
完全背包:有n种物品,每种物品有无限个.
多重背包:有n种物品,每种物品个数各不相同.
区别:仅仅体现在物品个数上的不同而已。
确定dp[i][j]数组的含义:[0,i]的物品任取放容量为j的背包里.
LeetCode:1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II - 力扣(LeetCode)
1.思路
01背包问题,dp[n + 1]初始化大小之所以是 n + 1 ,在于 n 是一个最大容量,且数组下标从 0 开始。
遍历顺序:先遍历物品再遍历背包,后者背包倒序是为了将物品大值先放入背包,保证每个物品只能遍历一次。
递推公式:取决于物品大小和背包容量,如果背包容量 > 物品大小,则允许放入(此时背包状态:dp[j - stones[i]] + stones[i]),否则不允许放入(此时背包状态:dp[j]),选择两者之中的较大值即可。
2.代码实现
1// 一维似乎更好理解2class Solution {3 public int lastStoneWeightII(int[] stones) {4 int sum = 0;5 for (int num : stones) {6 sum += num;7 }8 int target = sum / 2;9 int[] dp = new int[target + 1];
10 for (int i = 0; i < stones.length; i++) {
11 for (int j = target; j >= stones[i]; j--) {
12 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
13 }
14 }
15 return sum - 2 * dp[target];
16 }
17}
3.复杂度分析
时间复杂度:O(n^2).
空间复杂度:O(n).
LeetCode: 494. 目标和
494. 目标和 - 力扣(LeetCode)
1.思路
本题可以抽象成01背包问题,中间需要计算一下…
遍历顺序依旧是:先物品再背包,保证物品先放入最大值及元素的唯一性.
分两种情况:sum<0时,取绝对值之后进入遍历.
2.代码实现
1class Solution {2 public int findTargetSumWays(int[] nums, int target) {3 int sum = 0;4 for (int num : nums) {5 sum += num;6 }7 if (target < 0 && sum < -target) return 0;8 if ((target + sum) % 2 != 0) return 0;9 int size = (target + sum) / 2;
10 if (size < 0) size = -size;
11
12 int[] dp = new int[size + 1];
13 dp[0] = 1;
14 for (int i = 0; i < nums.length; i++) {
15 for (int j = size; j >= nums[i]; j--) {
16 dp[j] += dp[j - nums[i]];
17 }
18 }
19 return dp[size];
20 }
21}
3.复杂度分析
时间复杂度:O(n^2).
空间复杂度:O(n).
LeetCode: 474.一和零
474. 一和零 - 力扣(LeetCode)
1.思路
拆解将m和n共同看作背包的整体,字符串中每个元素看成物品。沿用上述遍历顺序和dp[][]数组定义,输出即可.
2.代码实现
1class Solution {2 public int findMaxForm(String[] strs, int m, int n) {3 // dp[i][j] 表示i个0 和 j个1时的最大子集数4 int[][] dp = new int[m + 1][n + 1];5 int one;6 int zero;7 // 先遍历物品8 for (String str : strs) {9 one = 0;
10 zero = 0;
11 // 得出每个字符串元素中包含的0和1的个数
12 for (char ch : str.toCharArray()) {
13 if (ch == '0') {
14 zero++;
15 } else {
16 one++;
17 }
18 }
19 // 倒序遍历背包,保证每个字符串元素只会被用一次
20 for (int i = m; i >= zero; i--) {
21 for (int j = n; j >= one; j--) {
22 dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
23 }
24 }
25 }
26 return dp[m][n];
27 }
28}
3.复杂度分析
时间复杂度:O(kmn). 空间复杂度:O(mn).
相关文章:
算法训练Day42|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零
背包类别 01背包:有n种物品,每种物品只有一个. 完全背包:有n种物品,每种物品有无限个. 多重背包:有n种物品,每种物品个数各不相同. 区别:仅仅体现在物品个数上的不同而已。 确定dp[i][j]数组的…...
HBase-组成
client 读写请求HMaster 管理元数据监控region是否需要进行负载均衡,故障转移和region的拆分RegionServer 负责数据cell的处理,例如写入数据put,查询数据get等 拆分合并Region的实际执行者,由Master监控,由regionServ…...
第一部分:领域中的基本概念
目录 一、什么是模型 二、什么是领域 三、什么是领域模型 四、什么是领域建模 一、什么是模型 模型是一种简化、它是对现实的解释,它与解决问题密切相关的方面抽象出来,而忽略无关细节。 二、什么是领域 领域是指某一专业或事物方面范围的涵盖。比如…...
react使用ref调用子组件的方法
Class类组件 import React, { useRef } from react;const MyComponent () > {const myComponentRef useRef(null);const handleClick () > {// 调用MyComponent组件的方法myComponentRef.current.myMethod();};return (<div><MyComponent ref{myComponentRe…...
JVM面试突击班2
JVM面试突击班2 对象被判定为不可达对象之后就“死”了吗 对象的生命周期 创建阶段 (1)为对象分配存储空间 (2)开始构造对象 (3)从超类到子类对static成员进行初始化 (4)超类成…...
【80天学习完《深入理解计算机系统》】第二天 2.2 整数的表示【有符号数,无符号数,符号数的扩展,有无符号数的转变】
专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录) 文章字体风格: 红色文字表示&#…...
基于 CentOS 7 构建 LVS-DR 群集以及配置nginx负载均衡
目录 一、基于 CentOS 7 构建 LVS-DR 群集 1、前期准备 1、关闭防火墙 2、安装ifconfig 3、准备四台虚拟机 2、在DS上 2.1、配置LVS虚拟IP 2.2、手工执行配置添加LVS服务并增加两台RS 2.3、查看配置 3、在RS端(第三台、第四台) 上 3.1、配置W…...
golang trace view 视图详解
大家好,我是蓝胖子,在golang中可以使用go pprof的工具对golang程序进行性能分析,其中通过go trace 命令生成的trace view视图对于我们分析系统延迟十分有帮助,鉴于当前对trace view视图的介绍还是很少,在粗略的看过tra…...
zju代码题:4-6
一 分段函数算水费 #include <stdio.h>int main() {/*** 定义两个* 定义浮点型变量* y:水费* x:用水的吨数* */double x, y;printf("Enter x(x>=0):\n"...
数据链路层概述
数据传输过程如下: 数据包按上述过程传输,详见(计算机网络概述三)。在分析数据链路层时可以假象成其沿着水平传播。 这三段链路层的传播方式可能会有所不同。 基本概念: 链路:指一个节点到相邻节点的一段物…...
Python代码使用技巧汇总:提升你的编程技能
各位程序员朋友们,今天我要跟大家分享一些关于Python代码的最佳使用技巧,这些技巧可以帮助你们成为更专业且高效的程序员。不管你是刚刚入门还是已经有一些经验,这些技巧都能够为你提供实际操作价值。 一、合理使用Python的数据结构和算法&am…...
Ae 效果:CC Spotlight
透视/CC Spotlight Perspective/CC Spotlight CC Spotlight(CC 聚光灯) 主要用途是创建和控制逼真的聚光灯效果。通过调整这些属性,可以模拟出各种不同的照明环境和效果,比如舞台照明、日出日落、特定的颜色照明等。 ◆ ◆ ◆ 效…...
如何在页面中嵌入音频和视频?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 嵌入音频⭐ 嵌入视频⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏…...
Unity 中检测射线穿过的所有的物体
在开发中 有个需求,射线要检测所有穿过的物体。 代码如下: using UnityEngine;public class HitCollider : MonoBehaviour {public float raycastDistance Mathf.Infinity;// Update is called once per framevoid Update(){Ray ray Camera.main.Scre…...
LeetCode 29题:两数相除
题目 给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。 整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.…...
Axure RP9中使用Echarts示例
目录 在Axure中拖入一个矩形框,并命名tes 进入Echarts官网示例页面https://echarts.apache.org/examples/zh/index.html 选择自己需要的图表,修改数据,并复制左侧js代码 把上面复制的代码替换下方的option{}; javascript: var script docum…...
利用Jmeter做接口测试全流程分析
利用Jmeter做接口测试怎么做呢?过程真的是超级简单。 明白了原理以后,把零碎的知识点填充进去就可以了。这篇文章就来介绍一下如何利用Jmeter做接口测试的流程,主要针对的是功能测试。暂不涉及到自动化测试和性能测试的内容。 一把来说&…...
超级浏览器与指纹浏览器:功能与特点的比较
导语:随着互联网的快速发展,隐私和安全问题日益受到关注。在这个背景下,超级浏览器和指纹浏览器作为定制化浏览器的两个重要类型,各自具有独特的功能和特点。本文将对超级浏览器和指纹浏览器进行比较,帮助读者更好地理…...
云端同步、高效无界:5款免费的跨平台思维导图软件推荐!
思维导图是一种以图形化方式表示思想、概念或任务的方法,可以帮助用户梳理思维、提高记忆和理解。在工作中,思维导图可以用于会议记录、任务规划、项目管理等,帮助提高工作效率和团队协作能力;在学习中,思维导图可以用…...
OpenAI允许网站阻止其网络爬虫;谷歌推出类似Grammarly的语法检查功能
🦉 AI新闻 🚀 OpenAI推出新功能,允许网站阻止其网络爬虫抓取数据训练GPT模型 摘要:OpenAI最近推出了一个新功能,允许网站阻止其网络爬虫从其网站上抓取数据训练GPT模型。该功能通过在网站的Robots.txt文件中禁止GPTB…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
