代码随想录算法训练营第五十六天|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桌面,或者直接将windows的文件拖曳到虚拟机linux系统当中,可以实现文件传输。当然复制粘贴方式也可以,但是前提是需要下载安装好VMware tools。 共享文件夹 概念:在Win…...
leetcode分类刷题:二叉树(八、二叉搜索树特有的自顶向下遍历)
二叉搜索树是一个有序树:每个二叉树都满足左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值;利用该性质,可以实现二叉搜索树特有的自顶向下遍历 700. 二叉搜索树中的搜索 思路1、自顶向下的遍…...
Vue 插槽 组件插入不固定内容
定义好一个组件,如果想插入图片或视频这非常不好的控制应该显示什么,这个时候可以使用插槽插入自定义内容 默认插槽 <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 访问某像素 //灰度图像: image.at<uchar>(j, i) //j为行数,i为列数 //BGR彩色图像 i…...
机器视觉3D项目评估的基本要素及测量案例分析
目录 一. 检测需求确认 1、产品名称:【了解是什么产品上的零件,功能是什么】 2、*产品尺寸:【最大兼容尺寸】 3、*测量项目:【确认清楚测量点位】 4、*精度要求:【若客户提出的精度值过大或者过小,可以和客…...
力扣日记10.31-【栈与队列篇】前 K 个高频元素
力扣日记:【栈与队列篇】前 K 个高频元素 日期:2023.10.31 参考:代码随想录、力扣 347. 前 K 个高频元素 题目描述 难度:中等 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意…...
TensorFlow案例学习:简单的音频识别
前言 以下内容均来源于官方教程:简单的音频识别:识别关键字 音频识别 下载数据集 下载地址:http://storage.googleapis.com/download.tensorflow.org/data/mini_speech_commands.zip 可以直接浏览器访问下载。 下载完成后将其解压到项目…...
css小程序踩坑记录
写标签设置距离 一直设置不动 写个双层 设置动了 神奇 好玩...
Android sqlite分页上传离线订单后删除
1、判断订单表的的总数是否大于0,如果大于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基本使用 直接看代码吧,非常容易上手: # 创建flask应用 app Flask(__name__)# 路由 app.route("/index", methods[GET]) def index():return "FLASK:欢迎访问主页!"if __name__ "__main__"…...
Django实战项目-学习任务系统-兑换物品管理
接着上期代码框架,开发第5个功能,兑换物品管理,再增加一个学习兑换物品表,主要用来维护兑换物品,所需积分,物品状态等信息,还有一个积分流水表,完成任务奖励积分,兑换物品…...
jmeter和postman你选哪个做接口测试?
软件测试行业做功能测试和接口测试的人相对比较多。在测试工作中,有高手,自然也会有小白,但有一点我们无法否认,就是每一个高手都是从小白开始的,所以今天我们就来谈谈一大部分人在做的接口测试,小白变高手…...
mac版本 Adobe总是弹窗提示验证问题如何解决
来自: mac软件下载macsc站 mac电脑使用过程中总是弹出Adobe 的弹窗提示,尤其是打开Adobe的软件,更是频繁的弹出提示: Your Adobe app is not genuine. Adobe reserves the right to disable this software after a 0 grace period…...
钡铼技术ARM工控机在机器人控制领域的应用
ARM工控机是一种基于ARM架构的工业控制计算机,用于在工业自动化领域中进行数据采集、监控、控制和通信等应用。ARM(Advanced RISC Machine)架构是一种低功耗、高性能的处理器架构,广泛应用于移动设备、嵌入式系统和物联网等领域。…...
HTML+CSS+JS实现计算器
🙈作者简介:练习时长两年半的Java up主 🙉个人主页:程序员老茶 🙊 ps:点赞👍是免费的,却可以让写博客的作者开心好久好久😎 📚系列专栏:Java全栈,…...
Git工作原理和常见问题处理方案
博客定位Git工作区域工作区域划分暂存区设计目的 Git基本操作核心操作初始化和配置指令 HEAD指针Git版本回滚指令介绍reset模式reset hard使用场景reset soft使用场景reset mixed使用场景reset使用注意事项checkout使用场景 Git分支管理什么是分支分支应用场景分支相关指令被合…...
C++-实现一个简单的菜单程序
C-实现一个简单的菜单程序 1,if-else语句实现1.1,代码实现1.2,功能检测 2,switch语句实现2.1,代码实现2.2,功能检测 1,if-else语句实现 实现一个简单的菜单程序,运行时显示"Men…...
Git更新 fork 的仓库
文章目录 确保本地仓库是最新的配置上游存储库(remote upstream)获取上游存储库的更改合并上游存储库的更改推送更改到你 fork 的仓库 确保本地仓库是最新的 在命令行中,导航到存储库的本地副本所在的目录,并执行以下命令: # 切换到主分支 …...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...
第22节 Node.js JXcore 打包
Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本,基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...
