算法训练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…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
