class072 最长递增子序列问题与扩展【算法】

class072 最长递增子序列问题与扩展【算法】

在这里插入图片描述
在这里插入图片描述

code1 300. 最长递增子序列

// 最长递增子序列和最长不下降子序列
// 给定一个整数数组nums
// 找到其中最长严格递增子序列长度、最长不下降子序列长度
// 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/

dp[i]：以i位置作结尾的最长递增子序列长度
返回Max(dp[…])

优化
ends[i]：目前所有长度为i+1的递增子序列的最小结尾
返回len

code1 动态规划
code2 优化

package class072;

// 最长递增子序列和最长不下降子序列
// 给定一个整数数组nums
// 找到其中最长严格递增子序列长度、最长不下降子序列长度
// 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/
public class Code01_LongestIncreasingSubsequence {

	// 普通解法的动态规划
	// 时间复杂度O(n^2)，数组稍大就会超时
	public static int lengthOfLIS1(int[] nums) {
		int n = nums.length;
		int[] dp = new int[n];
		int ans = 0;
		for (int i = 0; i < n; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[j] < nums[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}

	// 最优解
	// 时间复杂度O(n * logn)
	public static int lengthOfLIS2(int[] nums) {
		int n = nums.length;
		int[] ends = new int[n];
		// len表示ends数组目前的有效区长度
		// ends[0...len-1]是有效区，有效区内的数字一定严格升序
		int len = 0;
		for (int i = 0, find; i < n; i++) {
			find = bs1(ends, len, nums[i]);
			if (find == -1) {
				ends[len++] = nums[i];
			} else {
				ends[find] = nums[i];
			}
		}
		return len;
	}

	// "最长递增子序列"使用如下二分搜索 :
	// ends[0...len-1]是严格升序的，找到>=num的最左位置
	// 如果不存在返回-1
	public static int bs1(int[] ends, int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] >= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	// 如果求最长不下降子序列，那么使用如下的二分搜索 :
	// ends[0...len-1]是不降序的
	// 在其中找到>num的最左位置，如果不存在返回-1
	// 如果求最长不下降子序列，就在lengthOfLIS中把bs1方法换成bs2方法
	// 已经用对数器验证了，是正确的
	public static int bs2(int[] ends, int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] > num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}

code2 354. 俄罗斯套娃信封问题

// 俄罗斯套娃信封问题
// 给你一个二维整数数组envelopes ，其中envelopes[i]=[wi, hi]
// 表示第 i 个信封的宽度和高度
// 当另一个信封的宽度和高度都比这个信封大的时候
// 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
// 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封
// 即可以把一个信封放到另一个信封里面，注意不允许旋转信封
// 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/

排序策略:宽度从小到大；宽度一样，高度从大到小
构成高度数组，求最长递增子序列的长度

package class072;

import java.util.Arrays;

// 俄罗斯套娃信封问题
// 给你一个二维整数数组envelopes ，其中envelopes[i]=[wi, hi]
// 表示第 i 个信封的宽度和高度
// 当另一个信封的宽度和高度都比这个信封大的时候
// 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
// 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封
// 即可以把一个信封放到另一个信封里面，注意不允许旋转信封
// 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/
public class Code02_RussianDollEnvelopes {

	public static int maxEnvelopes(int[][] envelopes) {
		int n = envelopes.length;
		// 排序策略:
		// 宽度从小到大
		// 宽度一样，高度从大到小
		Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (b[1] - a[1]));
		int[] ends = new int[n];
		int len = 0;
		for (int i = 0, find, num; i < n; i++) {
			num = envelopes[i][1];
			find = bs(ends, len, num);
			if (find == -1) {
				ends[len++] = num;
			} else {
				ends[find] = num;
			}
		}
		return len;
	}

	public static int bs(int[] ends, int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] >= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}

code3 2111. 使数组 K 递增的最少操作次数

// 使数组K递增的最少操作次数
// 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k
// 如果对于每个满足 k <= i <= n-1 的下标 i
// 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的
// 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数
// 请你返回对于给定的 k ，使数组变成K递增的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

把每一组分出来
求出每一组的最长不下降子序列的长度，
修改长度就是总长度减去最长不下降子序列的长度
每一组的修改长度求和即为答案

package class072;

// 使数组K递增的最少操作次数
// 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k
// 如果对于每个满足 k <= i <= n-1 的下标 i
// 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的
// 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数
// 请你返回对于给定的 k ，使数组变成K递增的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/
public class Code03_MinimumOperationsToMakeArraykIncreasing {

	public static int MAXN = 100001;

	public static int[] nums = new int[MAXN];

	public static int[] ends = new int[MAXN];

	public static int kIncreasing(int[] arr, int k) {
		int n = arr.length;
		int ans = 0;
		for (int i = 0, size; i < k; i++) {
			size = 0;
			// 把每一组的数字放入容器
			for (int j = i; j < n; j += k) {
				nums[size++] = arr[j];
			}
			// 当前组长度 - 当前组最长不下降子序列长度 = 当前组至少需要修改的数字个数
			ans += size - lengthOfNoDecreasing(size);
		}
		return ans;
	}

	// nums[0...size-1]中的最长不下降子序列长度
	public static int lengthOfNoDecreasing(int size) {
		int len = 0;
		for (int i = 0, find; i < size; i++) {
			find = bs(len, nums[i]);
			if (find == -1) {
				ends[len++] = nums[i];
			} else {
				ends[find] = nums[i];
			}
		}
		return len;
	}

	public static int bs(int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (num < ends[m]) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}

code4 646. 最长数对链

// 最长数对链
// 给你一个由n个数对组成的数对数组pairs
// 其中 pairs[i] = [lefti, righti] 且 lefti < righti
// 现在，我们定义一种 跟随 关系，当且仅当 b < c 时
// 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
// 我们用这种形式来构造 数对链
// 找出并返回能够形成的最长数对链的长度
// 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/

按开头有序
ends数组，放数对的最小结尾，查要查数对的开头，第一个比它大的，再更新最小结尾。

package class072;

import java.util.Arrays;

// 最长数对链
// 给你一个由n个数对组成的数对数组pairs
// 其中 pairs[i] = [lefti, righti] 且 lefti < righti
// 现在，我们定义一种 跟随 关系，当且仅当 b < c 时
// 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
// 我们用这种形式来构造 数对链
// 找出并返回能够形成的最长数对链的长度
// 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/
public class Code04_MaximumLengthOfPairChain {

	public static int findLongestChain(int[][] pairs) {
		int n = pairs.length;
		// 数对根据开始位置排序，从小到大
		// 结束位置无所谓！
		Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
		// 结尾的数值
		int[] ends = new int[n];
		int len = 0;
		for (int[] pair : pairs) {
			int find = bs(ends, len, pair[0]);
			if (find == -1) {
				ends[len++] = pair[1];
			} else {
				ends[find] = Math.min(ends[find], pair[1]);
			}
		}
		return len;
	}

	// >= num最左位置
	public static int bs(int[] ends, int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] >= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}

code5 P8776 [蓝桥杯 2022 省 A] 最长不下降子序列

// 有一次修改机会的最长不下降子序列
// 给定一个长度为n的数组arr，和一个整数k
// 只有一次机会可以将其中连续的k个数全修改成任意一个值
// 这次机会你可以用也可以不用，请返回最长不下降子序列长度
// 1 <= k, n <= 10^5
// 1 <= arr[i] <= 10^6
// 测试链接 : https://www.luogu.com.cn/problem/P8776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

    		   [k个z]  	z
0   		i       	j
最后小于z的 	+k 		+包含j位置的
不下降子序列的长度     不下降子序列的长度

包含j位置的不下降子序列的长度等同于求出n-1…j的最长不上升子序列
ends存放最大结尾

673. 最长递增子序列的个数
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
测试链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

重剑无锋，大巧不工

package class072;

// 有一次修改机会的最长不下降子序列
// 给定一个长度为n的数组arr，和一个整数k
// 只有一次机会可以将其中连续的k个数全修改成任意一个值
// 这次机会你可以用也可以不用，请返回最长不下降子序列长度
// 1 <= k, n <= 10^5
// 1 <= arr[i] <= 10^6
// 测试链接 : https://www.luogu.com.cn/problem/P8776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code05_LongestNoDecreaseModifyKSubarray {

	public static int MAXN = 100001;

	public static int[] arr = new int[MAXN];

	public static int[] right = new int[MAXN];

	public static int[] ends = new int[MAXN];

	public static int n, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			k = (int) (in.nval);
			for (int i = 0; i < n; i++) {
				in.nextToken();
				arr[i] = (int) in.nval;
			}
			if (k >= n) {
				out.println(n);
			} else {
				out.println(compute());
			}
		}
		out.flush();
		out.close();
		br.close();
	}

	public static int compute() {
		right();
		int len = 0;
		int ans = 0;
		for (int i = 0, j = k, find, left; j < n; i++, j++) {
			find = bs2(len, arr[j]);
			left = find == -1 ? len : find;
			ans = Math.max(ans, left + k + right[j]);
			find = bs2(len, arr[i]);
			if (find == -1) {
				ends[len++] = arr[i];
			} else {
				ends[find] = arr[i];
			}
		}
		ans = Math.max(ans, len + k);
		return ans;
	}

	// 生成辅助数组right
	// right[j] :
	// 一定以arr[j]做开头的情况下，arr[j...]上最长不下降子序列长度是多少
	// 关键逻辑 :
	// 一定以arr[i]做开头的情况下，arr[i...]上最长不下降子序列
	// 就是！从n-1出发来看(从右往左遍历)，以arr[i]做结尾的情况下的最长不上升子序列
	public static void right() {
		int len = 0;
		for (int i = n - 1, find; i >= 0; i--) {
			find = bs1(len, arr[i]);
			if (find == -1) {
				ends[len++] = arr[i];
				right[i] = len;
			} else {
				ends[find] = arr[i];
				right[i] = find + 1;
			}
		}
	}

	// 求最长不上升子序列长度的二分
	// ends[0...len-1]是降序的，找到<num的最左位置
	// 不存在返回-1
	public static int bs1(int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] < num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	// 求最长不下降子序列长度的二分
	// ends[0...len-1]是升序的，找到>num的最左位置
	// 不存在返回-1
	public static int bs2(int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] > num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}

2023-11-09 20:58:41

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/233495.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Java 基础】29 序列化

【Java 基础】29 序列化

文章目录 1.定义2.目的3.使用1&#xff09;序列化2&#xff09;反序列化 3.应用场景4.注意事项总结 1.定义 序列化&#xff08;Serialization&#xff09;是将对象的状态转换为字节流的过程&#xff0c;以便将其存储到文件、数据库或通过网络传输 说简单点&#xff0c;序列化就…
阅读更多...
关于DNS服务器地址总是127.0.0.1且无法解析域名地址

关于DNS服务器地址总是127.0.0.1且无法解析域名地址

问题 笔者尝试nslookup解释域名时&#xff0c;出现服务器变成本地环回口地址&#xff0c;导致无法解析域名 C:\Users\Zsy>nslookup www.baidu.com 服务器: UnKnown Address: 127.0.0.1*** UnKnown 找不到 www.baidu.com: Server failed排查思路 尝试关闭虚拟网卡&#…
阅读更多...
SQL语句的执行顺序怎么理解？

SQL语句的执行顺序怎么理解？

SQL语句的执行顺序怎么理解&#xff1f; 我们常常会被SQL其书写顺序和执行顺序之间的差异所迷惑。理解这两者的区别&#xff0c;对于编写高效、可靠的SQL代码至关重要。今天&#xff0c;让我们用一些生动的例子和场景来深入探讨SQL的执行顺序。 一、书写顺序 VS 执行顺序 SQ…
阅读更多...
JS生成用户登录图形验证码

JS生成用户登录图形验证码

生成用户登录图形验证码的过程可以通过几个步骤来实现&#xff0c;包括创建画布&#xff0c;生成随机验证码文本&#xff0c;将验证码文本绘制到画布上&#xff0c;以及添加一些噪点和线条来增加复杂性。 HTML 首先&#xff0c;在HTML文件中创建一个<canvas>元素和一个…
阅读更多...
c#生成二维码二维码中间添加定制LoGo

c#生成二维码二维码中间添加定制LoGo

&#x1f680;介绍 &#x1f340;QRCoder是一个开源的.NET库&#xff0c;用于生成QR码&#xff08;Quick Response Code&#xff09;。这个库是用C#编写的&#xff0c;并且可以在.NET框架的各种版本上使用&#xff0c;包括.NET Framework, .NET Core, Mono, Xamarin等。QRCode…
阅读更多...
深入解析Linux内核网络-拥塞控制系列(二）

深入解析Linux内核网络-拥塞控制系列(二）

上篇文章&#xff1a;深入解析Linux内核网络-拥塞控制系列(一&#xff09;对Linux内核网络中网络拥塞框架的框架进行了分析。本次针对具体的Cubic拥塞控制算法进行简单分析。在进行代码的梳理前&#xff0c;同样还是先来看一下相关概念、原理&#xff1a; 在上一篇文章中也提到…
阅读更多...
电脑出现这些现象，说明你的固态硬盘要坏了

电脑出现这些现象，说明你的固态硬盘要坏了

与传统机械硬盘&#xff08;HDD&#xff09;相比&#xff0c;固态硬盘&#xff08;SSD&#xff09;速度更快、更稳定、功耗更低。但固态硬盘并不是完美无瑕的&#xff0c;由于颗粒写入机制&#xff0c;可能会在七到十年的预期寿命之前出现故障。所以用户最好为最终故障做好准备…
阅读更多...
vue3 自己写一个月的日历

vue3 自己写一个月的日历

效果图 代码 <template><div class"monthPage"><div class"calendar" v-loading"loading"><!-- 星期 --><div class"weekBox"><div v-for"(item, index) in dayArr" :key"index&q…
阅读更多...
认识计算机的设备管理

认识计算机的设备管理

在计算机系统中&#xff0c;除了处理器和内存之外&#xff0c;其他的大部分硬设备称为外部设备。它包括输入/输出设备&#xff0c;辅存设备及终端设备等。这些设备种类繁多&#xff0c;特性各异&#xff0c;操作方式的差异很大&#xff0c;从而使操作系统的设备管理变得十分繁杂…
阅读更多...
数据仓库工具Hive

数据仓库工具Hive

1. 请解释Hive是什么&#xff0c;它的主要用途是什么&#xff1f; Hive是一个基于Hadoop的数据仓库工具&#xff0c;主要用于处理和分析大规模结构化数据。它可以将结构化的数据文件映射为一张数据库表&#xff0c;并提供类似SQL的查询功能&#xff0c;将SQL语句转换为MapRedu…
阅读更多...
使用 iperf 和 iftop 测试网络带宽

使用 iperf 和 iftop 测试网络带宽

博主历时三年精心创作的《大数据平台架构与原型实现&#xff1a;数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行&#xff0c;点击《重磅推荐&#xff1a;建大数据平台太难了&#xff01;给我发个工程原型吧&#xff01;》了解图书详情&#xff0c;…
阅读更多...
京东商品详情数据在数据分析行业中的重要性

京东商品详情数据在数据分析行业中的重要性

京东商品详情数据在数据分析行业中具有重要作用。这些数据提供了丰富的信息&#xff0c;可以帮助企业了解市场趋势、消费者需求、产品表现以及运营策略等多个方面。 首先&#xff0c;京东商品详情数据可以为企业提供市场趋势分析的依据。通过观察商品的销售量、销售额、价格等…
阅读更多...
Qt 6.5 类库实例大全：QObject

Qt 6.5 类库实例大全：QObject

大家好&#xff0c;我是20YC小二&#xff01;福利时间&#xff1a;欢迎(wx)扫码关注&#xff0c;免费领取《C程序员入门必修第一课&#xff1a;C基础课程》在线视频教程&#xff0c;还有更多技术分享&#xff01;#下面进入今天内容# 1. QObject 介绍 QObject 是 Qt 库中最重要…
阅读更多...
RocketMq集成SpringBoot(待完善)

RocketMq集成SpringBoot(待完善)

环境 jdk1.8, springboot2.7.3 Maven依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.3</version><relativePath/> <!-- lookup parent from…
阅读更多...
C++学习笔记:继承

C++学习笔记:继承

继承 什么是继承?继承的写法基类和派生类的赋值转换继承中的作用域派生类的默认成员函数单继承,多继承,虚拟继承is-a 和 has-a 什么是继承? 继承是C语言面向对象的三大特性之一&#xff0c;是面向对象程序设计使代码可以复用的最重要的手段,基本都是在一个类的基础上为了增加…
阅读更多...
一个简单的可视化的A星自动寻路

一个简单的可视化的A星自动寻路

一个简单的应用场景&#xff0c;流程图连线 源码&#xff1a; addExample("A星路径查找", function () {return {template: <div><div ref"main"></div></div>,data() { return {}; },computed: {},methods: {},mounted() {var c…
阅读更多...
2-3、运算符

2-3、运算符

语雀原文链接 文章目录 1、算术运算符2、关系运算符3、逻辑运算符4、赋值运算符5、移位运算符6、位运算符(二进制位进行运算)7、条件运算符:三目运算符8、运算符的优先级 1、算术运算符 &#xff1a;加法-&#xff1a;减法*&#xff1a;乘法/&#xff1a;除法取商%&#xff1…
阅读更多...
logback日志框架使用

logback日志框架使用

依赖引入 <dependency><groupId>ch.qos.logback</groupId><artifactId>logback-classic</artifactId><version>1.1.7</version> </dependency> 使用logback日志框架只需要引入以上即可&#xff0c;(我们平时使用较多的Slf4j…
阅读更多...
Fall in love with English

Fall in love with English

Fall in love with English 爱上英语 Hiding behind the loose dusty curtain, a teenager packed up his overcoat into the suitcase. 躲藏在布满尘土的松软的窗帘后边&#xff0c;一个年轻人打包他的外套到行李箱中。 He planned to leave home at dusk though there was th…
阅读更多...
ssh免密登录及scp/rsync免密传输文件的方式

ssh免密登录及scp/rsync免密传输文件的方式

在通过ssh登录其它电脑或通过scp/rsync同其它电脑之间传输文件时&#xff0c;每次都需要输入密码&#xff0c;如下图所示&#xff1a;在windows10上通过ssh登录虚拟机&#xff0c;每次登录都需要输入密码&#xff1b;若端口默认为22,可省略通过-p指定 可通过将本机上的公钥key存…
阅读更多...
最新文章

Copyright @ 2022~2023