LeetCode刷题实战300:最长递增子序列
程序IT圈
共 8529字,需浏览 18分钟
· 2021-06-23
示例
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
解题
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define NAMESPACE_LENGTHOFLIS namespace NAME_LENGTHOFLIS {
#define NAMESPACE_LENGTHOFLISEND }
NAMESPACE_LENGTHOFLIS
// 动态规划
// 递推公式:dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
// 时间复杂度:O(n^2), 空间复杂度:O(n)
class Solution1
{
public:
int lengthOfLIS(vector<int>& nums)
{
int n=(int)nums.size();
if (n == 0) return 0;
vector<int> dp(n, 0);
int maxLen = 1;
for (int i = 0; i < n; ++i)
{
dp[i] = 1;
for (int j = 0; j < i; ++j)
{
if (nums[j] < nums[i])
{
dp[i] = max(dp[i], dp[j] + 1);
maxLen = max(maxLen, dp[i]);
}
}
}
//return *max_element(dp.begin(), dp.end());
return maxLen;
}
};
// 动态规划
// dp[i] = max(dp[j]) + 1, 其中 0 ≤ j < i 且 num[j] < num[i]
class Solution
{
public:
// 返回不小于目标值的位置
int search(vector<int> & nums, int target)
{
int l = 0;
int r = nums.size() - 1;
while(l < r)
{
int mid = (r + l) / 2;
if(target == nums[mid])
return mid;
else if(target > nums[mid])
l = mid + 1;
else if(target < nums[mid])
r = mid;
}
return l;
}
int lengthOfLIS(vector<int>& nums)
{
int len = nums.size();
vector<int> dp;
if(len <= 0) return 0;
dp.push_back(nums[0]);
for(int i = 1;i < len;i++)
{
if(nums[i] > dp[dp.size() - 1])
dp.push_back(nums[i]);
else
{
//auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
//*it = nums[i];
int p = search(dp,nums[i]);
dp[p] = nums[i];
}
}
return dp.size();
}
};
以下为测试代码//
// 测试 用例 START
void test(const char* testName, vector<int>& nums, int expect)
{
Solution_1 s1;
int result1 = s1.lengthOfLIS(nums);
Solution_2 s2;
int result2 = s2.lengthOfLIS(nums);
if (expect == result1 && expect == result2)
cout << testName << ", solution passed." << endl;
else
cout << testName << ", solution failed. expect:" << expect << ", result1:" <<result1 << ", result2:" << result2 << endl;
}
// 测试用例
void Test1()
{
vector<int> nums = { 10,9,2,5,3,7,101,18 };
int expect = 4;
test("Test1()", nums, expect);
}
void Test2()
{
vector<int> nums = { 10,11,1,2,3,12,13,4 };
int expect = 5;
test("Test2()", nums, expect);
}
NAMESPACE_LENGTHOFLISEND
// 测试 用例 END
//
void LengthOfLIS_Test()
{
NAME_LENGTHOFLIS::Test1();
NAME_LENGTHOFLIS::Test2();
}
评论
5000w+ 的大表如何拆?亿级别大表拆分实战复盘
前言笔者是在两年前接手公司的财务系统的开发和维护工作。在系统移交的初期,笔者和团队就发现,系统内有一张5000W+的大表。跟踪代码发现,该表是用于存储资金流水的表格,关联着众多功能点,同时也有众多的下游系统在使用这张表的数据。进一步的观察发现,这张表还在以每月600W+的数据持续增长,也就是说,不超
码农编程进阶笔记
0
15种时间序列预测方法总结(包含多种方法代码实现)
向AI转型的程序员都关注了这个号👇👇👇在这篇文章中,我们将深入探讨时间序列预测的基本概念和方法。我们将首先介绍单元预测和多元预测的概念,然后详细介绍各种深度学习和传统机器学习方法如何应用于时间序列预测,包括循环神经网络(RNN)、一维卷积神经网络(1D-CNN)、Transformer、自回归模型(
机器学习AI算法工程
0
好未来测开一面,挺简单!(0428面试原题解析)
大家好,我是二哥呀。今天继续给大家分享春招面试题《好未来测开一面原题》,附详细答案,我会用通俗易懂+手绘图的方式,让天下所有的面渣都能逆袭 😁二哥的 Java 面试指南内容较长,建议正在冲刺 24 届春招和 25 届暑期实习、秋招的同学先收藏起来,面试的时候大概率会碰到,1、二哥的 Linux 速查
沉默王二
0
GPT的风也吹到了CV,详解自回归视觉模型的先驱! ImageGPT:使用图像序列训练图像 GPT模型
作者丨科技猛兽编辑丨极市平台导读 在 CIFAR-10 上,iGPT 使用 linear probing 实现了 96.3% 的精度,优于有监督的 Wide ResNet,并通过完全微调实现了 99.0% 的精度,匹配顶级监督预训练模型。本文目录1 自回归视觉模型的先驱 ImageGPT:
机器学习初学者
0
【每周一课#06】MidJourney应用实战
#AI绘画# #MJ# #文生图#时间:4月24日周三 21:00课程大纲:1、关于AIGC:概念、发展历程、就业前景2、MJ基础认识:如何使用、底层逻辑、MJ与SD优缺点比较3、MJ基础功能介绍:任务指令、后缀参数、图生图、图生文、垫图、局部修改等4、MJ应用场景与变现方向
Python涨薪研究所
0
【每周一课#06】MidJourney 应用实战
#AI绘画# #MJ# #文生图#时间:4月24日周三 21:00课程大纲:1、关于AIGC:概念、发展历程、就业前景2、MJ基础认识:如何使用、底层逻辑、MJ与SD优缺点比较3、MJ基础功能介绍:任务指令、后缀参数、图生图、图生文、垫图、局部修改等4、MJ应用场景与变现方向
Python涨薪研究所
0
Java项目实战——打造一款股票区间交易盯盘系统
点击上方“Java进阶学习交流”,进行关注后台回复“Java”即可获赠Java学习资料今日鸡汤身无彩凤双飞翼,心有灵犀一点通。一、简介大家好,我是Snowball。今天给大家分享的内容是基于Java编程,实现股票交易相关功能开发,如果读者对股票或金融衍生物交易不太了解,又比较感兴趣的话可自行查询相关
Java进阶学习交流
0
【PythonCode】力扣Leetcode16~20题Python版
作者通常周更,为了不错过更新,请点击上方“Python碎片”,“星标”公众号前言力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台,很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。在Leetcode上刷题,可以选择各种主流的编程语言,如C++、JAVA、Pyth
Python 碎片
0