代码随想录算法训练营第52天|300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组

news/2024/12/22 16:40:34/

代码随想录算法训练营第52天|300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组

  • 300.最长递增子序列
  • 674. 最长连续递增序列
  • 718. 最长重复子数组

300.最长递增子序列

题目链接:300.最长递增子序列,难度:中等
【实现代码】

//动态规划
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int result = 1;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1);}}if (dp[i] > result) {result = dp[i];}}return result;}
};//动态规划+二分查找
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> tail;tail.push_back(nums[0]);for (int i = 1; i < nums.size(); i++) {if (nums[i] > tail.back()) {tail.push_back(nums[i]);} else {int left = 0;int right = tail.size() - 1;while (left <= right) {int mid = (left + right) >> 1;if (tail[mid] >= nums[i]) {right = mid - 1;} else {left = mid + 1;}}if (left < tail.size()) {tail[left] = nums[i];} }}return tail.size();}
};

【解题思路】

动规五部曲:

  1. dp[i]的定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
  2. 状态转移方程:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
  3. dp[i]的初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.
  4. 确定遍历顺序:dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。
  5. 举例推导dp数组
    动态规划+二分查找题解

674. 最长连续递增序列

题目链接:674. 最长连续递增序列,难度:简单
【实现代码】

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int result = 1;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;result = result > dp[i] ? result : dp[i];}}return result;}
};

【解题思路】

动规五部曲:

  1. dp[i]的定义:dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。
  2. 状态转移方程:if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
  3. dp[i]的初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.
  4. 确定遍历顺序:dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。
  5. 举例推导dp数组

718. 最长重复子数组

题目链接:718. 最长重复子数组,难度:中等
【实现代码】

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] +1;}if (result < dp[i][j]) {result = dp[i][j];}}}return result;}
};

【解题思路】

动规五部曲:

  1. dp[i]的定义:dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 )
  2. 状态转移方程:当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
  3. dp[i]的初始化:dp[0][0]初始为0
  4. 确定遍历顺序:外层for循环遍历A,内层for循环遍历B。在遍历的时候顺便把dp[i][j]的最大值记录下来。
  5. 举例推导dp数组

http://www.ppmy.cn/news/47047.html

相关文章

C/C++外观模式解析:简化复杂子系统的高效方法

C外观模式揭秘&#xff1a;简化复杂子系统的高效方法 引言设计模式的重要性外观模式简介与应用场景外观模式在现代软件设计中的地位与价值 外观模式基本概念外观模式的定义与核心思想提供简单接口隐藏复杂子系统设计原则与外观模式的关系外观模式实现外观模式的UML图 外观模式的…

【通过Cpython3.9源码看看python的内存回收机制】

一&#xff1a;建立对象引用计数 1. 相关代码 void _Py_NewReference(PyObject *op) {if (_Py_tracemalloc_config.tracing) {_PyTraceMalloc_NewReference(op);} #ifdef Py_REF_DEBUG_Py_RefTotal; #endifPy_SET_REFCNT(op, 1); #ifdef Py_TRACE_REFS_Py_AddToAllObjects(op…

webRtc播放rtsp视频流(vue2、vue3+vite+ts)

一、下载webRtc 开发环境用的win10版本的。 github上直接下载&#xff0c;速度感人。 Releases mpromonet/webrtc-streamer GitHub 提供资源下载&#xff0c;0积分 https://download.csdn.net/download/weiqiang915/87700892 二、启动&#xff0c;测试 webrtc-streame…

辉煌优配|刚刚!“中字头”再度爆发

今天早盘&#xff0c;A股全体持续震动收拾&#xff0c;上证50指数跌破2700点整数关口&#xff0c;沪深300亦失守4100点。 盘面上&#xff0c;国防军工、种业、中字头、电气设备等板块涨幅居前&#xff0c;前期抢手的人工智能、半导体、信创、软件服务等板块全线回调。北上资金净…

高效又稳定的ChatGPT大模型训练技巧总结,让训练事半功倍!

文&#xff5c;python 前言 近期&#xff0c;ChatGPT成为了全网热议的话题。ChatGPT是一种基于大规模语言模型技术&#xff08;LLM&#xff0c; large language model&#xff09;实现的人机对话工具。现在主流的大规模语言模型都采用Transformer网络&#xff0c;通过极大规模的…

腾讯新增长,AI扛大旗?

经历了疫情期间的低谷与波折&#xff0c;腾讯正在恢复它的活力。 3月22日&#xff0c;腾讯发布了2022年第四季度及全年财报。财报显示&#xff0c;2022全年营收为5546亿元人民币&#xff0c;归母净利润(Non-IFRS)为1156亿元人民币&#xff1b;2022年腾讯第四季度的营收为1450亿…

Python爬虫实战——获取电影影评

Python爬虫实战——获取电影影评 前言第三方库的安装示例代码效果演示结尾 前言 使用Python爬取指定电影的影评&#xff0c; 注意&#xff1a;本文仅用于学习交流&#xff0c;禁止用于盈利或侵权行为。 操作系统&#xff1a;windows10 家庭版 开发环境&#xff1a;Pycharm Co…

nginx 简介 第四章

一、Nginx简介 1、Nginx简介 Nginx&#xff08;特点&#xff1a;占用内存少&#xff0c;并发能力强&#xff09; Nginx是一个高性能的 HTTP 和反向代理服务器。 Nginx是一款轻量级的 Web 服务器/反向代理服务器及电子邮件 单台物理服务器可支持30 000&#xff5e;50 000个并发…