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

算法训练营第四十五天 | LeetCode 1049 最后一块石头的重量II、LeetCode 494 目标和、LeetCode 474 一和零

LeetCode 1049 最后一块石头的重量


  1. 继续昨天没有详细说的01背包问题往下继续说。01背包问题是将dp从一维问题升维到二维之后会遇到的一类典型问题。dp数组自然而然地是一个横坐标表示物品序号-1,纵坐标表示背包重量的二维数组
  2. 01背包由一个背包是否放该物品并比照后得到最大值,来表示表示子问题和当前问题之间关系组成递推逻辑。递推过程中由于物品数组逐渐增加,dp[i][j]在每一轮总是由dp[i-1][j]递推而来,因此可以简化为用一维滚动数组来表示。但这样第二重循环中由于从前往后遍历dp[i][0]会被存放多次,因此要从后往前遍历,同时由于我们递推公式是一个将i号物品放入背包,j减去其容量值将dp数组值加上物品value的过程,这个过程逆序时前面的dp值也是正常放入了值不会被覆盖的。也因此,我们可以采用一维数组来节省空间,但要稍微调整内层循环遍历顺序。

初始化都默认为零即可。

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i = 0; i < stones.length; i++) {sum += stones[i];}int weight = sum / 2;int[] dp = new int[weight + 1];for (int i = 0; i < stones.length; i++) {for (int j = weight; j >= stones[i]; j--) {dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return (sum - dp[weight] * 2);}
}

这道题转化为01背包问题的思路可以自行思考或者参照题解。

LeetCode 494 目标和


  • 这一题其实还是可以转化为01背包问题。不过要加上目标数之后除以2,如果加上之后为奇数或者小于0就直接返回0即可。否则我们直接用01背包模式求解即可。但是要注意由于我们求的是方法数,所以要更改下递推公式为加上之前子问题的方法数。

代码如下:

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}sum += target;if (sum < 0) return 0;if (sum % 2 == 1) return 0;sum /= 2;int[] dp = new int[sum + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = sum; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[sum];}
}

LeetCode 474 一和零


这题和上面差不多,还是用的01背包问题,而且要更明显一些。

代码如下:

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[] n0 = new int[strs.length];int[] n1 = new int[strs.length];for (int i = 0; i < strs.length; i++) {for (int j = 0; j < strs[i].length(); j++) {if (strs[i].charAt(j) == '0') n0[i]++;else n1[i]++;}}int[][] dp = new int[m + 1][n + 1];for (int i = 0; i < strs.length; i++) {for (int j = m; j >= n0[i]; j--) {for (int k = n; k >= n1[i]; k--) {dp[j][k] = Math.max(dp[j][k], dp[j - n0[i]][k - n1[i]] + 1);}}}return dp[m][n];}
}

相关文章:

算法训练营第四十五天 | LeetCode 1049 最后一块石头的重量II、LeetCode 494 目标和、LeetCode 474 一和零

LeetCode 1049 最后一块石头的重量 继续昨天没有详细说的01背包问题往下继续说。01背包问题是将dp从一维问题升维到二维之后会遇到的一类典型问题。dp数组自然而然地是一个横坐标表示物品序号-1&#xff0c;纵坐标表示背包重量的二维数组。01背包由一个背包是否放该物品并比照后…...

【数据结构与算法(C 语言)】栈的基本操作函数(动图演示) 及 栈的实际应用之一:进制转换

目录 1. 前言2. 结构及基本操作函数&#xff1a;2.1 栈的结构类型 Stack2.2 初始化栈 InitStack2.3 销毁栈 DestroyStack2.4 清空栈 ClearStack2.5 判断栈是否为空 StackEmpty2.6 获取stack的长度 StackLength2.7 获取栈顶元素 GetTop2.8 入栈 Push2.9 出栈 Pop2.10 访问元素2.…...

[原创]C++ 11的thread_local线程局部变量与Lambda表达式配合使用, 却引发致命的, 难以发现的冲突.

[简介] 常用网名: 猪头三 出生日期: 1981.XX.XX QQ联系: 643439947 个人网站: 80x86汇编小站 https://www.x86asm.org 编程生涯: 2001年~至今[共22年] 职业生涯: 20年 开发语言: C/C、80x86ASM、PHP、Perl、Objective-C、Object Pascal、C#、Python 开发工具: Visual Studio、D…...

C语言-单精度和双精度浮点型

文章目录 一、遇到的问题二、解决方案三、问题根因float和double的区别&#xff1a; 总结-浮点数 一、遇到的问题 将NXP项目的代码移植到RH850F1K的项目上时&#xff0c;程序运行异常&#xff1a; u16Volt (uint16)((double)u16ADVal * (double)6.3) 执行到这一行程序就跑飞了…...

STM32学习问题总结(2)—CubeMX生成项目后串口没效果和Microlib

检查完所有的硬件和软件部分&#xff0c;最后发现&#xff0c;又是Keil的设置问题&#xff0c;啊啊啊啊 打开Keil的魔术棒&#xff0c;勾选Target的Use Microlib选项即可&#xff0c;但这并不是最佳方案 最终解决方案&#xff1a; 参考&#xff1a;http://t.csdnimg.cn/2Tjfc…...

【数据结构与算法 | 二叉树篇】二叉树的前中后序遍历(递归版本)

1. 二叉树的概念 (1). 二叉树的结构 借用了一下力扣的模板 public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.righ…...

Python exp用法:深入探索指数函数的奥秘

Python exp用法&#xff1a;深入探索指数函数的奥秘 在Python中&#xff0c;exp是一个非常重要的数学函数&#xff0c;它属于math模块的一部分&#xff0c;用于计算自然数e的指数。自然数e是一个无理数&#xff0c;约等于2.71828&#xff0c;它在数学、物理和工程等领域有着广…...

[有监督学习] 8.详细图解神经网络

神经网络 一直以来&#xff0c;人们都认为神经网络&#xff08;Neural Network&#xff0c;NN&#xff09;是模仿生物体的神经网络设计而成的。神经网络既可以用于回归&#xff0c;也可以用于分类&#xff0c;但在实际应用中常用于分类。基于神经网络的深 度学习因在图像识别和…...

我给线程池管理框架hippo4j找bug

1 虚拟机参数不生效 hippo4j的docker启动脚本位于 docker/docker-startup.sh 。从下图可以看到 JAVA_OPT放在了jar包名 hippo4j-server.jar之后&#xff0c;而只有项目参数才放在jar包名之后。 实际上这里JAVA_OPT中包含虚拟机参数&#xff0c;而虚拟机参数要放在jar包名之前…...

win10键盘按乱了,如何恢复?

今天键盘被宝宝给按乱了&#xff0c;好不容易给重新调整回来&#xff0c;记录备忘&#xff1a; 1、win10的asdw和方向键互换了&#xff1a; 使用Fnw键来回切换&#xff0c;OK&#xff01; 2、键盘的win键失效&#xff0c;例如&#xff1a;按winD无法显示桌面。此时&#xf…...

5.29工效学-人因工程人机交互

对于工效学这门课&#xff0c;一直都感觉很有意思&#xff0c;是一个值得再认真一点的课。可惜上课的时候效率不高&#xff0c;有感兴趣的东西课后也没有自行去拓展开来&#xff0c;前面的课我感觉还讲了比较重要的东西&#xff0c;但是&#xff0c;全忘了呢&#xff08;真的对…...

头歌数据结构与算法课程设计中-硬币找零

给定n种不同面值的硬币k_i和每种硬币的数量x_i以及一个总金额k,请编写一个程序计算最少需要几枚硬币凑出这个金额k,凑出的方案是什么? 如果凑不出则输出“凑不出” 输入描述: 第一行两个正整数,n和k 然后n行每行两个数k_i和x_i 表示k_i面值的硬币有x_i个,中间以空格分隔 输…...

Golang的内存关系

1.Page Golang的Page,在操作系统对虚拟内存管理的MMU定义的物理页有相似的定义,默认的Page为8KB 2.mSpan 多个连续的Page称之为是一个Span&#xff0c;其定义含义有操作系统的管理的页表相似 3.Size Class Size Class: 相当于 一个等级和刻度, 比如 第二等级 就代表 一个Pag…...

VRTK4.0学习——(二)

手柄绑定以及显示 1.导入CameraRigs.UnityXRPluginFramework 和 CameraRigs.TrackedAlias 预设&#xff0c;将CameraRigs.UnityXRPluginFramework拖入CameraRigs.TrackedAlias的Elements中即可&#xff0c;运行软件后即可看到手柄了 注&#xff1a;如果无法看到手柄&#xff…...

体验Photoshop:无需下载,直接在浏览器编辑图片

搜索Photoshop时&#xff0c;映入眼帘的是PS软件下载&#xff0c;自学PS软件需要多长时间&#xff0c;学PS软件有必要报班吗...PS软件的设计功能很多&#xff0c;除了常见的图像处理功能外&#xff0c;还涉及图形、文本、视频、出版等。不管你是平面设计师&#xff0c;UI/UX设计…...

Codeforces Round 895 (Div. 3)(A,B,C)题解(自己VP的,没有参加这场比赛)

A. Two Vessels 题解&#xff1a; 这题直接计算两个杯子之间的差值&#xff0c;然后直接除以2倍杯子的容量直接过&#xff0c;没有任何难度 #include<bits/stdc.h> using namespace std;int t; int a,b,c;int main() {cin>>t;while(t--){cin>>a>>b>…...

9秒爬取庆余年2分集剧情

版本一: 要创建一个Python爬虫程序来爬取指定网站的分集剧情,我们需要使用requests库来发送HTTP请求,以及BeautifulSoup库来解析HTML内容。以下是一个简单的示例,展示了如何爬取你提供的网站的分集剧情,并将每集剧情保存到本地的.txt文件中。 首先,确保你已经安装了req…...

阿里云布置net core 项目

一、 创建镜像 给镜像添加触发器&#xff0c;编译的时候会触发k8s集群里的taget链接&#xff0c;从而更新项目 二&#xff0c;创建k8s集群 使用镜像创建 添加基本信息 镜像名称&#xff1a;镜像仓库》基本信息公网地址镜像Tag:创建镜像时的镜像版本镜像配置为&#xff1a;总…...

两整数之和 ---- 位运算

题目链接 题目: 分析: 题目中要求不能使用-, 考虑到我们的位运算异或^, 是无进位加法, 可以使用如果是无进位加法, 那么我们就要找到进位, 并进行计算, 进位只有1和1相加时才会产生进位1, 而0和1相加无进位, 进位为0, 那么我们就想到了&运算, 1&1 1, 0&1 0, 所…...

长城电脑压缩文件丢失了怎么办?怎么解决

在数字化时代&#xff0c;电脑已成为我们日常生活和工作中不可或缺的设备。长城电脑作为国内知名品牌&#xff0c;以其稳定可靠的性能赢得了广大用户的信赖。然而&#xff0c;即便是可靠的电脑&#xff0c;也难免会遇到一些问题。其中&#xff0c;压缩文件丢失无疑是一个令人头…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...

python可视化:俄乌战争时间线关键节点与深层原因

俄乌战争时间线可视化分析&#xff1a;关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一&#xff0c;自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具&#xff0c;系统分析这场战争的时间线、关键节点及其背后的深层原因&#xff0c;全面…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战

🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...