当前位置: 首页 > 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…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...