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

代码随想录算法训练营第五十六天|1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划

1143. 最长公共子序列

int longestCommonSubsequence(char * text1, char * text2){int len1 = strlen(text1);int len2 = strlen(text2);int dp[len1+1][len2+1];for (int i = 0; i <= len1; i++){for (int j = 0; j <= len2; j++){dp[i][j] = 0;}}for (int i = 1; i <= len1; i++){for (int j = 1; j <= len2; j++){if (text1[i-1] == text2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else {dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);}}}   return dp[len1][len2];
}

1035. 不相交的线

与1143.最长公共子序列一样

int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size){int len1 = nums1Size;int len2 = nums2Size;int dp[len1+1][len2+1];for (int i = 0; i <= len1; i++){for (int j = 0; j <= len2; j++){dp[i][j] = 0;}}for (int i = 1; i <= len1; i++){for (int j = 1; j <= len2; j++){if (nums1[i-1] == nums2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else {dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);}}}   return dp[len1][len2];
}

53. 最大子数组和

贪心算法:

int maxSubArray(int* nums, int numsSize){int result = INT_MIN;int count = 0;for (int i=0; i<numsSize; i++){count += nums[i];if (count > result) result = count;if (count < 0) count = 0;}return result;
}

动态规划:

int maxSubArray(int* nums, int numsSize){int dp[numsSize];for (int i = 0; i < numsSize; i++){dp[i] = 0;}dp[0] = nums[0];int ans = nums[0];for (int j = 1; j < numsSize; j++){// 比较的是当前数字大小和上次累加本次的大小dp[j] = fmax(nums[j], dp[j-1] + nums[j]);ans = fmax(dp[j], ans);}return ans;
}

整理一下

int maxSubArray(int* nums, int numsSize){int dp[numsSize];int ans = dp[0] = nums[0];for (int j = 1; j < numsSize; j++){// 比较的是当前数字大小和上次累加本次的大小dp[j] = fmax(nums[j], dp[j-1] + nums[j]);if (dp[j] > ans) ans = dp[j];}return ans;
}

相关文章:

代码随想录算法训练营第五十六天|1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划

1143. 最长公共子序列 int longestCommonSubsequence(char * text1, char * text2){int len1 strlen(text1);int len2 strlen(text2);int dp[len11][len21];for (int i 0; i < len1; i){for (int j 0; j < len2; j){dp[i][j] 0;}}for (int i 1; i < len1; i){f…...

虚拟机和Windows的文件传输

拖拽/复制粘贴 直接将虚拟机linux系统的文件拖曳到windows桌面&#xff0c;或者直接将windows的文件拖曳到虚拟机linux系统当中&#xff0c;可以实现文件传输。当然复制粘贴方式也可以&#xff0c;但是前提是需要下载安装好VMware tools。 共享文件夹 概念&#xff1a;在Win…...

leetcode分类刷题:二叉树(八、二叉搜索树特有的自顶向下遍历)

二叉搜索树是一个有序树&#xff1a;每个二叉树都满足左子树上所有节点的值均小于它的根节点的值&#xff0c;右子树上所有节点的值均大于它的根节点的值&#xff1b;利用该性质&#xff0c;可以实现二叉搜索树特有的自顶向下遍历 700. 二叉搜索树中的搜索 思路1、自顶向下的遍…...

Vue 插槽 组件插入不固定内容

定义好一个组件&#xff0c;如果想插入图片或视频这非常不好的控制应该显示什么&#xff0c;这个时候可以使用插槽插入自定义内容 默认插槽 <Login><template><h1>我是插入的内容</h1></template></Login >组件 <slot></slot>…...

webpack打包时配置环境变量

webpack打包时配置环境变量 一、常规环境变量配置1. 使用webpack.DefinePlugin定义全局常量2. 在Vue静态页面中使用该环境变量 二、纯静态文件配置环境变量1. 使用npm或yarn安装html-webpack-plugin2. 在Webpack配置中引入并使用插件3. 使用htmlwebpackplugin.options方式配置环…...

【c++|opencv】一、基础操作---3.访问图像元素

every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 访问图像元素 1. 访问图像像素 1.1 访问某像素 //灰度图像&#xff1a; image.at<uchar>(j, i) //j为行数&#xff0c;i为列数 //BGR彩色图像 i…...

机器视觉3D项目评估的基本要素及测量案例分析

目录 一. 检测需求确认 1、产品名称&#xff1a;【了解是什么产品上的零件&#xff0c;功能是什么】 2、*产品尺寸&#xff1a;【最大兼容尺寸】 3、*测量项目&#xff1a;【确认清楚测量点位】 4、*精度要求&#xff1a;【若客户提出的精度值过大或者过小&#xff0c;可以和客…...

力扣日记10.31-【栈与队列篇】前 K 个高频元素

力扣日记&#xff1a;【栈与队列篇】前 K 个高频元素 日期&#xff1a;2023.10.31 参考&#xff1a;代码随想录、力扣 347. 前 K 个高频元素 题目描述 难度&#xff1a;中等 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意…...

TensorFlow案例学习:简单的音频识别

前言 以下内容均来源于官方教程&#xff1a;简单的音频识别&#xff1a;识别关键字 音频识别 下载数据集 下载地址&#xff1a;http://storage.googleapis.com/download.tensorflow.org/data/mini_speech_commands.zip 可以直接浏览器访问下载。 下载完成后将其解压到项目…...

css小程序踩坑记录

写标签设置距离 一直设置不动 写个双层 设置动了 神奇 好玩...

Android sqlite分页上传离线订单后删除

1、判断订单表的的总数是否大于0&#xff0c;如果大于0开始上传订单 public int getOrderCount() {String query "SELECT COUNT(*) FROM " TABLE_NAME;Cursor cursor db.rawQuery(query, null);int count 0;if (cursor.moveToFirst()) {count cursor.getInt(0);…...

Flask基本教程以及Jinjia2模板引擎简介

flask基本使用 直接看代码吧&#xff0c;非常容易上手&#xff1a; # 创建flask应用 app Flask(__name__)# 路由 app.route("/index", methods[GET]) def index():return "FLASK&#xff1a;欢迎访问主页&#xff01;"if __name__ "__main__"…...

Django实战项目-学习任务系统-兑换物品管理

接着上期代码框架&#xff0c;开发第5个功能&#xff0c;兑换物品管理&#xff0c;再增加一个学习兑换物品表&#xff0c;主要用来维护兑换物品&#xff0c;所需积分&#xff0c;物品状态等信息&#xff0c;还有一个积分流水表&#xff0c;完成任务奖励积分&#xff0c;兑换物品…...

jmeter和postman你选哪个做接口测试?

软件测试行业做功能测试和接口测试的人相对比较多。在测试工作中&#xff0c;有高手&#xff0c;自然也会有小白&#xff0c;但有一点我们无法否认&#xff0c;就是每一个高手都是从小白开始的&#xff0c;所以今天我们就来谈谈一大部分人在做的接口测试&#xff0c;小白变高手…...

mac版本 Adobe总是弹窗提示验证问题如何解决

来自&#xff1a; mac软件下载macsc站 mac电脑使用过程中总是弹出Adobe 的弹窗提示&#xff0c;尤其是打开Adobe的软件&#xff0c;更是频繁的弹出提示&#xff1a; Your Adobe app is not genuine. Adobe reserves the right to disable this software after a 0 grace period…...

钡铼技术ARM工控机在机器人控制领域的应用

ARM工控机是一种基于ARM架构的工业控制计算机&#xff0c;用于在工业自动化领域中进行数据采集、监控、控制和通信等应用。ARM&#xff08;Advanced RISC Machine&#xff09;架构是一种低功耗、高性能的处理器架构&#xff0c;广泛应用于移动设备、嵌入式系统和物联网等领域。…...

HTML+CSS+JS实现计算器

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

Git工作原理和常见问题处理方案

博客定位Git工作区域工作区域划分暂存区设计目的 Git基本操作核心操作初始化和配置指令 HEAD指针Git版本回滚指令介绍reset模式reset hard使用场景reset soft使用场景reset mixed使用场景reset使用注意事项checkout使用场景 Git分支管理什么是分支分支应用场景分支相关指令被合…...

C++-实现一个简单的菜单程序

C-实现一个简单的菜单程序 1&#xff0c;if-else语句实现1.1&#xff0c;代码实现1.2&#xff0c;功能检测 2&#xff0c;switch语句实现2.1&#xff0c;代码实现2.2&#xff0c;功能检测 1&#xff0c;if-else语句实现 实现一个简单的菜单程序&#xff0c;运行时显示"Men…...

Git更新 fork 的仓库

文章目录 确保本地仓库是最新的配置上游存储库(remote upstream)获取上游存储库的更改合并上游存储库的更改推送更改到你 fork 的仓库 确保本地仓库是最新的 在命令行中&#xff0c;导航到存储库的本地副本所在的目录&#xff0c;并执行以下命令&#xff1a; # 切换到主分支 …...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

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

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

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...