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

@ 代码随想录算法训练营第7周(C语言)|Day43(动态规划)

@ 代码随想录算法训练营第7周(C语言)|Day43(动态规划)

Day41、动态规划(包含题目 ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零 )

1049. 最后一块石头的重量 II

题目描述

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;

如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。

最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

题目解答

int lastStoneWeightII(int* stones, int stonesSize) {int target;int sum;sum=0;for(int i=0;i<stonesSize;i++){sum+=stones[i];}target=sum/2;int dp[target+1];for(int i=0;i<target+1;i++){dp[i]=0;}for(int i=0;i<stonesSize;i++){for(int j=target;j>=stones[i];j--){dp[j]=dp[j]>(dp[j-stones[i]]+stones[i])?dp[j]:(dp[j-stones[i]]+stones[i]);}}return sum-dp[target]*2;
}

题目总结

01背包。

494. 目标和

题目描述

给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数

题目解答

int findTargetSumWays(int* nums, int numsSize, int target) {int sum=0;for(int i=0;i<numsSize;i++){sum+=nums[i];}if((sum+target)%2==1){return 0;}if(target<0&&(-target)>sum){return 0;}int k=(sum+target)/2;int dp[k+1];for(int i=0;i<=k;i++){dp[i]=0;}dp[0]=1;for(int i=0;i<numsSize;i++){for(int j=k;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[k];
}

题目总结

背包问题。

474.一和零

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。### 题目解答

#define MAX(a,b) (a>=b?a:b);
int findMaxForm(char** strs, int strsSize, int m, int n) {int **dp=(int**)malloc(sizeof(int*)*(m+1));for(int i=0;i<m+1;i++){dp[i]=(int*)malloc(sizeof(int)*(n+1));for(int j=0;j<=n;j++){dp[i][j]=0;}}for(int z=0;z<strsSize;z++){int zeronum=0,onenum=0;for(int h=0;h<strlen(strs[z]);h++){if(strs[z][h]=='0'){zeronum++;}else{onenum++;}}for(int i=m;i>=zeronum;i--){for(int j=n;j>=onenum;j--){dp[i][j]=MAX(dp[i][j],dp[i-zeronum][j-onenum]+1);}}}return dp[m][n];
}

题目总结

三维01背包。

相关文章:

@ 代码随想录算法训练营第7周(C语言)|Day43(动态规划)

代码随想录算法训练营第7周&#xff08;C语言&#xff09;|Day43&#xff08;动态规划&#xff09; Day41、动态规划&#xff08;包含题目 ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零 &#xff09; 1049. 最后一块石头的重量 II 题目描述 有一堆石头&am…...

深度学习的新进展:探索人工智能的未来

文章目录 &#x1f4d1;引言深度学习技术概述计算机视觉领域的深度应用自然语言处理的深度革命跨领域应用的深度拓展深度学习的挑战与未来展望结语 &#x1f4d1;引言 在科技日新月异的今天&#xff0c;深度学习作为人工智能领域的一颗璀璨明珠&#xff0c;正在引领着技术创新…...

Vue中@change、@input和@blur、@focus的区别及@keyup介绍

Vue中change、input和blur、focus的区别及keyup介绍 1. change、input、blur、focus事件2. keyup事件3. 补充&#xff1a;el-input的change事件自定义传参 1. change、input、blur、focus事件 change在输入框发生变化且失去焦点后触发&#xff1b; input在输入框内容发生变化后…...

Raspbian简易RTSP服务

Raspbian简易RTSP服务 1. 源由2. 搭建简易RTSP服务器2.1 系统安装2.2 软件安装2.3 命令介绍2.3.1 libcamera-hello2.3.2 libcamera-vid2.3.3 cvlc 3. 实测4. 参考资料 1. 源由 鉴于前期的一些准备工作&#xff1a; 《ArduPilot开源飞控之Companion Computers简单分析》《Ardu…...

【ASP.NET 6 Web Api 全栈开发实战】--前言

《ASP.NET 6 Web Api 实战》专栏通过一步一步的开发并完善一个记账软件项目&#xff0c;来引导大家学习相关的知识&#xff0c;其中的知识包括但不限于如下内容&#xff1a; Web Api 开发.NET 6 项目微服务架构的搭建身份认证移动端应用开发more。。。 专栏结构 专栏分为单体…...

跳过mysql8.0密码重置密码 Shell脚本

要在 MySQL 8.0 中通过 Shell 脚本跳过密码验证以重置密码&#xff0c;你可以遵循以下步骤&#xff1a;首先&#xff0c;确保你有足够的权限来编辑配置文件和重启 MySQL 服务。下面是一个简单的 Shell 脚本示例&#xff0c;该脚本展示了如何跳过密码验证以重置 MySQL 8.0 的 ro…...

Maven之安装自定义jar到本地Maven仓库中

Maven之安装自定义jar到本地Maven仓库中 文章目录 Maven之安装自定义jar到本地Maven仓库中1. 命令行窗口安装方式1. 常用参数说明2. 安装实例 2. IDEA中安装方式3. 使用 1. 命令行窗口安装方式 安装指定文件到本地仓库命令&#xff1a;mvn install:install-file; 在windows的cm…...

SPI控制8_8点阵屏

协议与硬件概述 SPI SPI是串行外设接口&#xff08;Serial Peripheral Interface&#xff09;的缩写。是一种高速的&#xff08;10Mbps&#xff09;的&#xff0c;全双工&#xff0c;同步的通信总线&#xff0c;并且在芯片的管脚上只占用四根线。 引脚介绍 SCLK&#xff1a;…...

2.10

头文件&#xff1a; #include <sqlite3.h> 编译时候要加上-lsqlite3 gcc a.c -lsqlite3 1&#xff09;sqlite3_open 打开一个数据库&#xff0c;如果数据库不存在&#xff0c;则创建一个数据库 2&#xff09;sqlite3_close 关闭数据库&#xff0c;断开句柄所拥有的资…...

计算机服务器中了360后缀勒索病毒怎么办?360后缀勒索病毒处理流程

网络技术的不断应用与发展&#xff0c;为企业的生产运营提供了有利保障&#xff0c;越来越多的企业走向数字化办公模式&#xff0c;并且企业的发展离不开数据支撑&#xff0c;重视数据安全成为了众多企业关心的主要话题。春节前后&#xff0c;云天数据恢复中心接到很多企业的求…...

BigDecimal的常用API

BigDecimal用于解决浮点型运算时结果出现失真的问题。 这里0.20.1等于0.3就出现了失真 import java.math.BigDecimal; import java.math.RoundingMode;public class Test {public static void main(String[] args) {//BigDeciaml的使用&#xff1a;解决小数运算失真的问题doub…...

Android---Jetpack Compose学习005

动画 1. 简单值动画 示例&#xff1a;背景颜色在紫色和绿色之间&#xff0c;以动画形式切换。使用 animateColorAsState() val backgroundColor by animateColorAsState(if (tabPage TabPage.Home) Purple100 else Green300) 该句代码中&#xff0c;有一个 backgroundColo…...

安卓价值1-如何在电脑上运行ADB

ADB&#xff08;Android Debug Bridge&#xff09;是Android平台的调试工具&#xff0c;它是一个命令行工具&#xff0c;用于与连接到计算机的Android设备进行通信和控制。ADB提供了一系列命令&#xff0c;允许开发人员执行各种操作&#xff0c;包括但不限于&#xff1a; 1. 安…...

第三百四十七回

文章目录 1. 概念介绍2. 原理与方法2.1 知识对比2.2 使用方法 3. 示例代码4. 内容总结 我们在上一章回中介绍了"加密包crypto"相关的内容&#xff0c;本章回中将介绍characters包.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 在项目中会遇到获取字…...

23种设计模式之原型模式

目录 什么是原型模式 为什么使用原型模式 原型模式的基本结构 原型模式的实现步骤 实现代码&#xff08;含注释&#xff09; 使用场景 什么是原型模式 原型模式是一种创建型设计模式&#xff0c;该模式的核心思想是基于现有的对象创建新的对象&#xff0c;而不是从头开…...

揭秘Angular世界的奥秘:全面提升你的前端开发技能!

介绍&#xff1a;Angular是一个由Google维护的开源JavaScript框架&#xff0c;专为构建Web应用程序而设计&#xff0c;特别适合开发大型单页应用&#xff08;SPA&#xff09;。以下是对Angular的详细介绍&#xff1a; 技术栈&#xff1a;Angular使用HTML作为模板语言&#xff0…...

【开源】SpringBoot框架开发企业项目合同信息系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 合同审批模块2.3 合同签订模块2.4 合同预警模块2.5 数据可视化模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 合同审批表3.2.2 合同签订表3.2.3 合同预警表 四、系统展示五、核心代码5.1 查询合同…...

高斯伪谱C++封装库开源!

Windows x64/86 C无依赖运行高斯伪谱法求解最优控制问题&#xff0c;你只需要ElegantGP! Author: Y. F. Zhang His Github: https://github.com/ZYunfeii 写在前面 这个库在你下载它的那一时刻起不再依赖任何其他代码&#xff0c;直接可用来构建C的最优控制问题并进行求解。…...

Spring + Tomcat项目中nacos配置中文乱码问题解决

实际工作的时候碰到了nacos中文乱码的问题&#xff0c;一顿排查最终还是调源码解决了。下面为具体的源码流程&#xff0c;有碰到的可以参考下。 对于nacos配置来说&#xff0c;初始主要源码就在NacosConfigService类中。里面有初始化获取配置content以及设置对应监听器的操作。…...

Unity SRP 管线【第十讲:SRP/URP 图形API】

Unity 封装的图形API 文章目录 Unity 封装的图形API一、 CommandBuffer 要执行的图形命令列表1. CommandBuffer 属性2. CommandBuffer 常用图形API&#xff08;方法&#xff09;(1)设置(2)获取临时纹理 GetTemporaryRT以及释放(3)设置纹理为渲染目标 SetRenderTarget(4)Command…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

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

目录 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…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...