个人网站建设模板/引流app推广软件
目录
Leecode 1049.最后一块石头的重量II
Leecode 494.目标和
Leecode 474.一和零
Leecode 1049.最后一块石头的重量II
题目地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目类型:01背包
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 背包的最大容量应当是 sum / 2 ,因为当两堆石头的重量最接近的时候mint sum = accumulate(stones.begin(), stones.end(), 0);int target = sum / 2;vector<int> dp(target + 1);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] * 2;}
};
Leecode 494.目标和
题目地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目类型:01背包
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// sum = right + left// target = right - left// sum - target = 2left int sum = accumulate(nums.begin(), nums.end(), 0);if ((sum - target) % 2 == 1 || abs(target) > sum) return 0; // left代表较少那一部分组合的和int left = (sum - target) / 2;// dp数组的含义是,当求和为i时,组合的数目vector<int> dp(left + 1);dp[0] = 1;for (int i = 0; i < nums.size(); ++i) {for (int j = left; j >= nums[i]; --j) {dp[j] += dp[j - nums[i]];}}return dp[left];}
};
Leecode 474.一和零
题目地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目类型:01背包
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 存储个数vector<pair<int, int>> nums;for (auto &it : strs) {int zero = 0, one = 0;for (auto &c : it) {if (c == '0') zero++;else one++;}nums.push_back({zero, one});}// dp[i][j]代表当有i个0,j个1时,最大的子集长度vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 先物品,后背包for (int k = 0; k < nums.size(); ++k) {// 二维for (int i = m; i >= nums[k].first; --i) {for (int j = n; j >= nums[k].second; --j) {// 注意,这里如果将第k个子集放进来,则代表增加一个子集,value是1,所以直接加1就行了dp[i][j] = max(dp[i][j], dp[i - nums[k].first][j - nums[k].second] + 1);}}}return dp[m][n];}
};
可以少一个循环,时间复杂度再降一下:
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// dp[i][j]含义:当0的容量为i,1的容量为j时,子集的最大数目// 可知此时最大值问题,故考虑状态转移方程1vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int k = 0; k < strs.size(); ++k) { // 遍历所有物品,即遍历所有子集int num0 = 0, num1 = 0;for (char c : strs[k]) {if (c == '0') num0++;else num1++;}for (int i = m; i >= num0; --i) {for (int j = n; j >= num1; --j) {dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1);}}}return dp[m][n];}
};
相关文章:

算法训练营第三十四天(8.23)| 动态规划Part04:01背包
目录 Leecode 1049.最后一块石头的重量II Leecode 494.目标和 Leecode 474.一和零 Leecode 1049.最后一块石头的重量II 题目地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目类型:01背包 class Solution { public:int…...

【python】tkinter使用多进程打包成exe后multiprocessing无法关闭对应进程
这是由于multiprocessing模块在Windows操作系统下使用fork方法创建子进程时会导致打包成exe后无法正常运行的问题。 可以尝试使用freeze_support函数来解决这个问题。freeze_support函数是在Windows操作系统下用于支持multiprocessing模块的函数。 下面是一个示例代码&#x…...

Redis工具类(缓存操作,Object转换成JSON数据)
依赖spring-data-redis-2.4.1.jar Component Data public class RedisUtils {Autowiredprivate RedisTemplate<String, Object> redisTemplate;Resource(name "stringRedisTemplate")private ValueOperations<String, String> valueOperations;/*** 默…...

Linux 下 Java Socket 编程报 java.net.Exception:Permission denied (权限不足)
本人用Linux部署springboot项目时遇见这个错误,原因很简单,就是端口号没有选对。 在linux系统中,端口号再1024以下的需要root权限,只要把端口改成大于1024的就可以了,但避开一些软件的默认端口,如Tomcat的8…...

IDEA项目实践——VUE介绍与案例分析
系列文章目录 IDEA项目实践——JavaWeb简介以及Servlet编程实战 IDEA项目实践——Spring集成mybatis、spring当中的事务 IDEA项目实践——Spring当中的切面AOP IDEWA项目实践——mybatis的一些基本原理以及案例 IDEA项目实践——Spring框架简介,以及IOC注解 I…...

vue-canvas基本使用和注意事项-动画闪烁效果-自适应适配不同分辨率问题
前言 canvas画布是html的新特性,熟悉画布我们可以完成很多拖拽,标注,动画的功能 使用canvas实现一个小例子很容易,但是真正在项目中使用时,我们需要注意的地方有很多 canvas基本原理就是它基于渲染方法,根…...

Jmeter 如何才能做好接口测试?
现在对测试人员的要求越来越高,不仅仅要做好功能测试,对接口测试的需求也越来越多! 所以也越来越多的同学问,怎样才能做好接口测试? 要真正的做好接口测试,并且弄懂如何测试接口,需要从如下几…...

电商平台京东平台获得京东商品描述API接口演示案例
京东商品描述API接口可以获取京东商品描述: 详细介绍商品的特点和功能,让消费者能够了解商品的具体用途和效果。 使用简洁明了的语言,避免使用过于专业的术语和长句子,让消费者能够轻松理解。 重点突出商品的卖点和优势,让消费者能够更加清晰地了解商品的价值 …...

《算法竞赛·快冲300题》每日一题:“单位转换”
《算法竞赛快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 单…...

R语言13-R语言中的数据导入导出和批量导入
数据导入 CSV 文件: 使用 read.csv() 函数导入逗号分隔的文本文件。 data <- read.csv("data.csv")Excel 文件: 使用 readxl 包中的函数 read_excel() 导入 Excel 文件。 install.packages("readxl") # 安装 readxl 包&#…...

【Java】对象与类
【Java】对象与类 文章目录 【Java】对象与类1、学习背景2、定义&使用2.1 创建类2.2 创建对象 3、static关键字3.1 修饰变量3.2 修饰方法3.3 修饰代码块3.4 修饰内部类 4、this关键字5、封装特性5.1 访问修饰符5.2 包的概念 6、构造方法7、代码块7.1 普通代码块7.2 成员代码…...

视频尺寸缩小,一键批量剪辑,轻松制作精简版
大家好!在视频剪辑中,有时我们需要将大尺寸的视频缩小,以适应特定的需求和平台要求。为了帮助您轻松制作精简版视频,我们推出了一款全新的工具——视频尺寸缩小批量剪辑软件!让您一键批量将视频尺寸缩小,轻…...

leetcode做题笔记94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 思路一:模拟题意 void inorder(struct TreeNode*root,int* ans,int *resSize) {if(!root){return ;}inorder(root->left,ans,resSize);ans[(*resSize)] root->val;inorder(root->right…...
UWB高精度人员定位系统源码,微服务+java+ spring boot+ vue+ mysql技术开发
工业物联网感知预警体系,大中小企业工业数字化转型需求的工业互联网平台 工厂人员定位系统是指能够对工厂中的人员、车辆、设备等进行定位,实现对人员和车辆的实时监控与调度的系统,是智慧工厂建设中必不可少的一环。由于工厂的工作环境比较…...

企业党建杂志企业党建杂志社企业党建编辑部2023年第4期目录
卷首语 坚持学思用贯通 知信行统一 (0001) 赵荣地 国企与国资《企业党建》投稿:cn7kantougao163.com 深入推进新时代党的建设的重大部署 (0004) 陈锋 国有企业推进中国式现代化建设的使命任务和实践路径 (0006) 蒋雪群 创新与实践 浅析国企党建与生产经营工作…...

ChatGPT + Flutter快速开发多端聊天机器人App
下载地址:ChatGPT Flutter快速开发多端聊天机器人App 下载地址:ChatGPT Flutter快速开发多端聊天机器人App...

ubuntu18.04复现yolo v8之最终章,realsenseD435i+yolo v8完美运行
背景:上一篇博客我们已经为复现yolov8配置好了环境,如果前面的工作顺利进行,我们已经完成了90%(学习类程序最难的是环境配置)。 接下来将正式下载yolov8的相关代码,以及进行realsenseD435i相机yolo v8的de…...

Python统计中文词频的四种方法
统计中文词频是Python考试中常见的操作,由于考察内容较多,因此比较麻烦,那么有没有好的方法来实现呢?今天,我们总结了四种常见的中文词频统计方法,并列出代码,供大家学习参考。 中文词频统计主…...

sql server 快速安装
目录标题 一、下载二、直接选择基本安装二、下载ssms(数据库图形化操作页面)三、开启sa账号认证(一)第一步:更改身份验证模式(二)第二步:启用 sa 登录四、开启tcp/ip 一、下载 下载…...

机器学习之损失函数
深度学习中常用的损失函数多种多样,具体选择取决于任务类型和问题的性质。以下是一些常见的深度学习任务和相应的常用损失函数: 分类任务: 交叉熵损失函数(Cross-Entropy Loss):用于二分类和多类别分类任务…...

nacos适配SqlServer、Oracle
继上文《nacos适配达梦、瀚高、人大金仓数据库及部分源码探究 》后补充nacos适配SqlServer、Oracle的贴码,主要区别是SqlServer、Oracle的分页SQL有点不一样,做个记录; SqlServer的分页有三种实现方式:offset /fetch next、利用ma…...

力扣:74. 搜索二维矩阵(Python3)
题目: 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返…...

CPU、MCU、MPU、SOC、SOCPC、概念解释之在嵌入式领域常听到的名词含义
CPU、MCU、MPU、SOC等几个在嵌入式领域学习过程中会涉及到的几个名词。我们来学习一下,资料从网上搜集的,有错的地方可以指出。。。 CPU、MCU、MPU、SOC、SOCPC、 1. CPU2. MPU3.MCUMPU和MCU的区别:4.SOC5. SoPC 1. CPU CPU,即中…...

每日两题 111二叉树的最小深度 112路径总和(递归)
111 题目 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:2示例 2&#x…...

实训笔记8.24
实训笔记8.24 8.24笔记一、Sqoop数据迁移工具1.1 Sqoop的基本概念1.2 Sqoop的基本操作1.2.1 命令语法1.2.2 list-databases1.2.3 list-tables1.2.3 eval1.2.4 import1.2.5 export1.2.6 导入 二、Flume日志采集工具2.1 数据采集的问题2.2 数据采集一般使用的技术2.3 扩展&#x…...

Linux下的系统编程——系统调用(五)
前言: 由操作系统实现并提供给外部应用程序的编程接口。(Application Programming Interface,API)。系统调用就是应用程序同系统之间数据交互的桥梁。 open/close函数 1.open函数: (1)int open(char *pathname, int flags) …...

动物体外受精手术VR模拟仿真培训系统保证学生及标本的安全
奶牛是养殖业主要的资源,因此保证奶牛的健康对养殖业的成功和可持续发展具有重要已用,奶牛有一些常见易发病,一旦处理不当,对奶牛业都会造成较大的经济损失,传统的奶牛手术培训实操难度大、风险高且花费大,…...

微信小程序|步骤条
步骤条是现代用户界面设计中常见的元素之一,它能够引导用户按照预定顺序完成一系列任务或步骤。在小程序中,实现步骤条可以为用户提供更好的导航和引导,使用户体验更加流畅和直观。本文将介绍如何在小程序中实现步骤条,并逐步展示实现的过程和关键技巧 目录 步骤条的作用及…...

如何才能设计出“好的”测试用例?
软件测试用例的设计质量直接影响到测试的完整性、有效性以及自动化测试的实施效果,是软件测试成功的重要保证,良好的软件测试用例对于提高测试的有效性和效率至关重要。那大家知道好的测试用例该怎么写吗?应该从哪几个方面来撰写呢࿱…...

DirectExchange直连交换机
目录 一、简介 二、使用步骤 三、demo 父pom文件 pom文件 配置文件 config 消费者 生产者 测试 一、简介 直连型交换机,根据消息携带的路由键将消息投递给对应队列。 大致流程,有一个队列绑定到一个直连交换机上,同时赋予一个路由…...