当前位置：首页 > 编程日记 > 正文

leetcode-300 最长上升子序列

编程日记 2024-04-11 05:00:00

题目描述：
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n^2) 。

方法一（暴力法）：
即针对数组的每一个元素都有两种选择，取或者不取（取的前提是当前元素大于上一个元素，则上升子序列++），最终递归到最后的一个元素，将结果返回。

实现如下：

int lengthOfLIS(vector<int>& nums) {return get_lengthOfLIS(nums, -1, 0);
}
int get_lengthOfLIS(vector<int> &num, int prev, int curr) {if(curr == num.size()) {return 0;}int taken = 0;if(num[curr] > prev) {taken = get_lengthOfLIS(num, num[curr], curr+1);}int notaken = get_lengthOfLIS(num, prev, curr+1);return max(taken, notaken);
}

但是因为暴力解法的时间复杂度较高，针对每个元素都有两种选择，时间复杂度为O(2^n)

方法二（DP动态规划）：

状态的定义
dp[i] 代表以当前元素 nums[i]结尾（最长上升子序列包括nums[i]）的最长上升子序列的大小
状态转移方程
dp[i] = (nums[i] > nums[j]) ? max{dp[0]…dp[j]} + 1 ,1; (j>=0 && j < i)
以上方程的意思是，找到所有nums[i]左侧比nums[i]小的元素的个数，在其基础上+1

实现如下:

int lengthOfLIS(vector<int>& nums) {if(nums.size() <= 1) return nums.size();vector<int> dp(nums.size(),0);int res = 1,i = 1, j = 0;dp[0] = 1;for(i = 1;i < nums.size(); ++i) {dp[i] = 1;for (j = 0;j < i; ++j) {if(nums[i] > nums[j] && dp[i] < dp[j] + 1) { //找到nums[i]左边比nums[i]小的元素，取它的dp[j] + 1给到dp[i]dp[i] = dp[j]+1;}}if(res < dp[i]) { //res取最大即可res = dp[i];}}return res;
}

以上方法的时间复杂度为O(n^2)，j的遍历的层数和i的个数基本一致

方法三（递增栈 + 二分）：
维护一个持续递增的栈，元素添加进来有两种规则：

当要添加的元素大于栈顶元素，则压栈
当要添加的元素小于栈顶元素，那么在栈中找到该元素的插入位置，将其替换该位置的元素

只有当满足第一中情况的时候栈的大小才会增加，否则栈的大小是固定的，优化的办法是使用二分法查找待插入的位置

实现如下：

int lengthOfLIS(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> stack;//使用vector代替栈stack.push_back(nums[0]);for (int i = 1;i < nums.size(); ++i) {if (nums[i] > stack.back()) {stack.push_back(nums[i]);} else {int pos = binary_search(stack,nums[i]);stack[pos] = nums[i];}}return stack.size();
}//二分查找，返回待插入元素的下标
int binary_search(vector<int> &stack,int target) {int index = -1;int begin = 0;int end = stack.size() - 1;while (index == -1) {int mid = (begin + end) / 2;if (target == stack[mid]) {index = mid;} else if (target < stack[mid]) {if (mid == 0 || target > stack[mid - 1]) {index = mid;}end = mid - 1;} else {if (mid == stack.size() - 1 || target < stack[mid + 1] ) {index = mid + 1;}begin = mid + 1;}}return index;
}

时间复杂度为O(N*logn)，遍历n次，每次二分查找的时间复杂度是logn

https://www.dkcj.cn/info/4503.html

转载自——Json.net动态序列化以及对时间格式的处理

关于我工作中对Json处理的东西第一:动态序列化类第二:时间格式处理通常我们一个类里可能有十到更多的属性,但是我们序列化通常只需要序列化其中的三到五个这样的话就会有多余的数据如果我只想序列化 id 跟name如何处理这是我找的网上的方法: using Newtonsoft.Json…

编程日记2024/04/11 04:30:00

congratulation的用法_congratulation的用法

congratulation用作名词，表示祝贺，恭喜；congratulation表示抽象意义的“祝贺”时，为不可数名词。表示祝贺词时，用作可数名词。1.表示抽象意义的“祝贺”时，为不可数名词。I sent her a gift as a token of …

编程日记2024/04/11 04:00:00

腾讯微博API时间线相关接口返回的微博信息中head值使用问题

腾讯微博API时间线相关接口返回的微博信息中head值表示作者头像url，这个链接直接访问并不能使用，需要再附加一个参数指定图片的大小（100、50），比如：[head]/100。

编程日记2024/04/11 03:30:00

java实现https请求

参考： https://www.cnblogs.com/chinway/p/5802541.html java 实现https请求 JSSE是一个SSL和TLS的纯Java实现，通过JSSE可以很容易地编程实现对HTTPS站点的访问。但是，如果该站点的证书未经权威机构的验证，JSSE将拒绝信任该证书从…

编程日记2024/04/11 03:00:00

设计模式之美 --- 初篇

接下来的一段时间将按照如下体系导图，对23种设计模式按照自己的理解一一总结，为后续工作中持续灵活使用做好积累。学习应用设计模式的过程有如下好处提高复杂代码的设计开发能力让阅读源码和学习框架事半功倍告别被别人吐槽的烂代码为职场发展做…

编程日记2024/04/11 02:30:00

C语言中将0到1000的浮点数用强制指针类型转换的方式生成一幅图像

搞过计算机图像的人都知道，图像中的每一个像素通常为一个整型数，它可以分成4个无符号的char类型，以表示其RGBA四个分量。一幅图像可以看做是一个二维整型数组。这里我会生成一个float数组，其数组大小为1000000，刚好100…

编程日记2024/04/11 02:00:00

mysql用户控制登录_MySql用户权限控制_MySQL

bitsCN.comMySql用户权限控制本文将介绍ＭySql创建帐号，删除帐号，设置和介绍各种帐号的权限创建用户帐号： www.bitsCN.com[sql]CREATE USER user_name IDENTIFIED BY your_password;改名[sql]RENAME USER old_name TO new_name;删除…

编程日记2024/04/11 01:30:00

[python] 从GPS坐标获取国家名

目标比较明确，就是从GPS坐标得到它所在的国家。网上可以找的比较典型的解决方案是利用一些网站（例如Google）的webservice来完成这个任务，但是这些解决方案有一个比较大的弱点，就是这些webservice会限制请求的次数&…

编程日记2024/04/11 01:00:00

一、变量 def dtl(request):num 3.14ss abc123嘿嘿# return render(request, django_dtl.html, {number: num, ss: ss})result Truelist [1, 2, 3, 4, 5]dic {name: owen, age: 28}# 函数不能带有参数，模板中{{ fn }} 本质就是调用函数拿到函数值（函…

编程日记2024/04/11 00:30:00

设计模式之美 -- 面向对象（C/C++分别实现）

文章目录前言封装C实现C 实现继承C 实现C实现前言为了保证代码的可复用性、可扩展性、可维护性，我们提出了面向对象的思想。面向对象的核心特性有以下几个封装特性信息隐藏或者数据访问保护。类通过暴露有限的访问接口，授权外部仅能通过类提供的方…

编程日记2024/04/11 00:00:01

数据结构编程实战汇总

出自数据结构与算法分析第二版（C） 一引论二算法分析三表栈队列四树五散列六优先队列七排序优先队列实现事件模拟 ：http://maozj.iteye.com/blog/676567d堆左式堆斜堆： http://blog.csdn.net/yangtrees/article/detai…

编程日记2024/04/10 23:30:00

同时支持三个mysql+sqlite+pdo的php数据库类_同时支持三个MySQL+SQLite+PDO的PHP数据库类...

PHP学习教程文章简介： 同时支持三个MySQLSQLitePDO的PHP数据库类使用方法: // mysql connect $db new SQL(mysql:hostlocalhost;database21andy_blog;, 21andy.com_user, 21andy.com_password); // PDO SQLite3 connect $db new SQL(pdo:database/21andy.com/21an…

编程日记2024/04/10 23:00:01

VB6基本数据库应用（五）：数据的查找与筛选

同系列的第五篇，上一篇在：http://blog.csdn.net/jiluoxingren/article/details/9633139 数据的查找与筛选第4篇发布到现在已经过了4天，很抱歉，学生党，还是悲催的高三，没办法，8月1就开学了。以后…

编程日记2024/04/10 22:30:00

学习进度条（第一周）

学习进度条： 第一周所花时间（包括上课） 5h 代码量（行） 150 博客量（篇） 2 了解到的知识点这种主要是对上学期web知识的一个回顾，进行了第一次开学测验，了解了实…

编程日记2024/04/10 22:00:01

设计模式之美 -- 单例模式

为什么要使用单例？ 一个类只允许创建一个对象或者实例。背景简介：使用多线程并发访问同一个类，为了保证类的线程安全，可以有两种方法： 将该类定义为单例模式，即该类仅允许创建一个实例为该类的成员函数添…

编程日记2024/04/10 21:30:00

(int)，Int32.Parse() 和 Convert.toInt32() 的区别

在 C# 中，(int)，Int32.Parse() 和 Convert.toInt32() 三种方法有何区别? int 关键字表示一种整型，是32位的，它的 .NET Framework 类型为 System.Int32。 (int)表示使用显式强制转换，是一种类型转换。当我们从 int 类型…

编程日记2024/04/10 21:00:01

MySQL留言板怎么创建_如何使用JSP+MySQL创建留言本(三)

如何使用JSPMySQL创建留言本(三)推荐查看本文HTML版本下面我们开始建立留言的页面！import "java.util.*"import "java.text.*"import"java.sql.*"import "java.io.*"import "java.lang.*"contentType"t…

编程日记2024/04/10 20:30:00

刚子扯谈:微信今天你打飞机了嘛吗？

文/刚子 2013年8月5日开片语:昨日爆爬二坨山后，精神豁然靓丽。虽然晒伤的不算厉害，但是还是有同事关切。说刚子你真黑了。好吧！当然今天咱不扯爬山涉水，也不扯刚子咋就黑了，咱扯今天那个“热”。也许有部分朋友已经猜…

编程日记2024/04/10 20:00:00

OMS API

plot cd("C:/……/") 转载于:https://www.cnblogs.com/Pusteblume/p/10467200.html

编程日记2024/04/10 19:30:00

设计模式之美 -- 简单工厂模式

文章目录1. 解决问题2. 应用场景3. 实现C实现：C语言实现4. 缺点1. 解决问题举例如下： 我们实现一个卖衣服的功能，衣服的种类有很多：帽子，裤子，T恤。。。每卖一种衣服，我们都要进行一次实例化…

编程日记2024/04/10 19:00:01

mysql 分表原理_MYSQL 分表原理（转）

简介:引用MySQL官方文档中的一段话:MERGE存储引擎,也被认识为MRG_MyISAM引擎,是一个相同的可以被当作一个来用的MyISAM表的集合."相同"意味着所有表同样的列和索引信息.你不能合并列被以不同顺序列于其中的表,没有恰好同样列的表,或有不同顺序索引的表.而且,任何或者…

编程日记2024/04/10 18:30:00

popStar手机游戏机机对战程序

DFS算，五分钟如果答案没有更新，那个解一般来说就很优了。 #include <cstdio> #include <iostream> #include <string.h> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #incl…

编程日记2024/04/10 18:00:00

ps aux参数说明

运行 ps aux 的到如下信息： ps auxUSER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMANDsmmsp 3521 0.0 0.7 6556 1616 ? Ss 20:40 0:00 sendmail: Queue runner01:00:00 froot 3532 0.0 0.2 2428 …

编程日记2024/04/10 17:30:00

myeclipse使用maven整合ssh配置

最近写项目，由于公司需求，使用myeclispe来开发maven项目，关于maven就不再介绍,无论是jar包管理功能，还是作为版本构建工具，优点自然是很多，下面先贴出所需要的配置文件。 maven所需要的 pom.xml 1 <proj…

编程日记2024/04/10 17:00:00

C语言 #ifndef 引起的redefinition of xxx 问题解决

问题如下多个.c和.h文件其中cloth.h分布被hat.h和paths.h包含，编译时出现如下问题： error: redefinition of struct _Cloth 我的cloth.h定义如下： #include <stdio.h> #include <stdlib.h> #include "retval.h"…

编程日记2024/04/10 16:30:00

mysql如何下载连接到visual_Visual Studio 2015 Community连接到Mysql

Visual Studio 2015 Community连接到MySQL，步骤很简单，但刚弄的时候一脸懵，现在记录如下以作备忘：安装好VS2015和Mysql后，只需要再安装两个东西即可。一个是SDK：MySQL for Visual Studio另一个是驱动&#…

编程日记2024/04/10 16:00:00

web.py下获取get参数

比较简单，就直接上代码了： import web urls (/, hello ) app web.application(urls, globals()) class hello: def GET(self):print web.input()return "GET hello world"def POST(self):print web.input()return "POST hello w…

编程日记2024/04/10 15:30:00

ORACLE 体系结构知识总结

ORACLE 体系结构.Oracle 体系结构图：.1.ORACLE 实例.1.1. Oracle 实例Oracle实例包括内存结构和后台进程System Global Area(SGA) 和Background Process 称为数据库实例文件。.2. Oracle 数据库一系列物理文件的集合（数据文件，控制文件&#…

编程日记2024/04/10 15:00:00

余额宝技术架构读后感

本次阅读文章为：余额宝技术架构及演讲文章地址：https://mp.weixin.qq.com/s?__bizMzAwMDU1MTE1OQ&mid2653547540&idx1&snb3f568ba4bd1c4a0a2d35c0e5ef033cc&scene21#wechat_redirect 通过阅读“余额宝技术架构及演讲”，了解…

编程日记2024/04/10 14:30:00

网络故障排查命令

ping #检测目标主机是否畅通traceroute #追踪路由mtr #检查到目标主机之间是否有数据包丢失nslookup #查看域名并解析，获取IP地址telnet #检查端口链接状态tcpdump #细致分析数据包发送接收的详细内容netstat #查看网络端口连接状态ss #另外一种各式的查看网络端口…

编程日记2024/04/10 14:00:00