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

算法训练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背包&#xff1a;有n种物品&#xff0c;每种物品只有一个. 完全背包&#xff1a;有n种物品&#xff0c;每种物品有无限个. 多重背包&#xff1a;有n种物品&#xff0c;每种物品个数各不相同. 区别&#xff1a;仅仅体现在物品个数上的不同而已。 确定dp[i][j]数组的…...

HBase-组成

client 读写请求HMaster 管理元数据监控region是否需要进行负载均衡&#xff0c;故障转移和region的拆分RegionServer 负责数据cell的处理&#xff0c;例如写入数据put&#xff0c;查询数据get等 拆分合并Region的实际执行者&#xff0c;由Master监控&#xff0c;由regionServ…...

第一部分:领域中的基本概念

目录 一、什么是模型 二、什么是领域 三、什么是领域模型 四、什么是领域建模 一、什么是模型 模型是一种简化、它是对现实的解释&#xff0c;它与解决问题密切相关的方面抽象出来&#xff0c;而忽略无关细节。 二、什么是领域 领域是指某一专业或事物方面范围的涵盖。比如…...

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 对象被判定为不可达对象之后就“死”了吗 对象的生命周期 创建阶段 &#xff08;1&#xff09;为对象分配存储空间 &#xff08;2&#xff09;开始构造对象 &#xff08;3&#xff09;从超类到子类对static成员进行初始化 &#xff08;4&#xff09;超类成…...

【80天学习完《深入理解计算机系统》】第二天 2.2 整数的表示【有符号数,无符号数,符号数的扩展,有无符号数的转变】

专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客&#xff0c;如有问题交流&#xff0c;欢迎评论区留言&#xff0c;一定尽快回复&#xff01;&#xff08;大家可以去看我的专栏&#xff0c;是所有文章的目录&#xff09;   文章字体风格&#xff1a; 红色文字表示&#…...

基于 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端&#xff08;第三台、第四台&#xff09; 上 3.1、配置W…...

golang trace view 视图详解

大家好&#xff0c;我是蓝胖子&#xff0c;在golang中可以使用go pprof的工具对golang程序进行性能分析&#xff0c;其中通过go trace 命令生成的trace view视图对于我们分析系统延迟十分有帮助&#xff0c;鉴于当前对trace view视图的介绍还是很少&#xff0c;在粗略的看过tra…...

zju代码题:4-6

一 分段函数算水费 #include <stdio.h>int main() {/*** 定义两个* 定义浮点型变量* y:水费* x:用水的吨数* */double x, y;printf("Enter x(x>=0):\n"...

数据链路层概述

数据传输过程如下&#xff1a; 数据包按上述过程传输&#xff0c;详见&#xff08;计算机网络概述三&#xff09;。在分析数据链路层时可以假象成其沿着水平传播。 这三段链路层的传播方式可能会有所不同。 基本概念&#xff1a; 链路&#xff1a;指一个节点到相邻节点的一段物…...

Python代码使用技巧汇总:提升你的编程技能

各位程序员朋友们&#xff0c;今天我要跟大家分享一些关于Python代码的最佳使用技巧&#xff0c;这些技巧可以帮助你们成为更专业且高效的程序员。不管你是刚刚入门还是已经有一些经验&#xff0c;这些技巧都能够为你提供实际操作价值。 一、合理使用Python的数据结构和算法&am…...

Ae 效果:CC Spotlight

透视/CC Spotlight Perspective/CC Spotlight CC Spotlight&#xff08;CC 聚光灯&#xff09; 主要用途是创建和控制逼真的聚光灯效果。通过调整这些属性&#xff0c;可以模拟出各种不同的照明环境和效果&#xff0c;比如舞台照明、日出日落、特定的颜色照明等。 ◆ ◆ ◆ 效…...

如何在页面中嵌入音频和视频?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 嵌入音频⭐ 嵌入视频⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏…...

Unity 中检测射线穿过的所有的物体

在开发中 有个需求&#xff0c;射线要检测所有穿过的物体。 代码如下&#xff1a; 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题:两数相除

题目 给你两个整数&#xff0c;被除数 dividend 和除数 divisor。将两数相除&#xff0c;要求 不使用 乘法、除法和取余运算。 整数除法应该向零截断&#xff0c;也就是截去&#xff08;truncate&#xff09;其小数部分。例如&#xff0c;8.345 将被截断为 8 &#xff0c;-2.…...

Axure RP9中使用Echarts示例

目录 在Axure中拖入一个矩形框&#xff0c;并命名tes 进入Echarts官网示例页面https://echarts.apache.org/examples/zh/index.html 选择自己需要的图表&#xff0c;修改数据&#xff0c;并复制左侧js代码 把上面复制的代码替换下方的option{}; javascript: var script docum…...

利用Jmeter做接口测试全流程分析

利用Jmeter做接口测试怎么做呢&#xff1f;过程真的是超级简单。 明白了原理以后&#xff0c;把零碎的知识点填充进去就可以了。这篇文章就来介绍一下如何利用Jmeter做接口测试的流程&#xff0c;主要针对的是功能测试。暂不涉及到自动化测试和性能测试的内容。 一把来说&…...

超级浏览器与指纹浏览器:功能与特点的比较

导语&#xff1a;随着互联网的快速发展&#xff0c;隐私和安全问题日益受到关注。在这个背景下&#xff0c;超级浏览器和指纹浏览器作为定制化浏览器的两个重要类型&#xff0c;各自具有独特的功能和特点。本文将对超级浏览器和指纹浏览器进行比较&#xff0c;帮助读者更好地理…...

云端同步、高效无界:5款免费的跨平台思维导图软件推荐!

思维导图是一种以图形化方式表示思想、概念或任务的方法&#xff0c;可以帮助用户梳理思维、提高记忆和理解。在工作中&#xff0c;思维导图可以用于会议记录、任务规划、项目管理等&#xff0c;帮助提高工作效率和团队协作能力&#xff1b;在学习中&#xff0c;思维导图可以用…...

OpenAI允许网站阻止其网络爬虫;谷歌推出类似Grammarly的语法检查功能

&#x1f989; AI新闻 &#x1f680; OpenAI推出新功能&#xff0c;允许网站阻止其网络爬虫抓取数据训练GPT模型 摘要&#xff1a;OpenAI最近推出了一个新功能&#xff0c;允许网站阻止其网络爬虫从其网站上抓取数据训练GPT模型。该功能通过在网站的Robots.txt文件中禁止GPTB…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...