自己开发网站怎么开发,自己开发网站,网站flsh怎么做,有哪些可以做任务的网站题目 2668: 蓝桥杯2022年第十三届省赛真题-最长不下降子序列 原题链接#xff1a;完成情况#xff1a;解题思路#xff1a;代码解释主函数 main辅助函数 computeLNDS 代码说明复杂度分析优化建议 参考代码#xff1a;错误经验吸取 原题链接#xff1a;
题目 2668: 蓝桥杯… 题目 2668: 蓝桥杯2022年第十三届省赛真题-最长不下降子序列 原题链接完成情况解题思路代码解释主函数 main辅助函数 computeLNDS 代码说明复杂度分析优化建议 参考代码错误经验吸取 原题链接
题目 2668: 蓝桥杯2022年第十三届省赛真题-最长不下降子序列
https://www.dotcpp.com/oj/problem2668.html
完成情况
解题思路
代码解释
该代码旨在解决如何通过修改一个整数序列的连续 K 个数使得修改后的序列的最长不下降子序列LNDS的长度最大的问题。以下是代码的详细解释
主函数 main
public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt(); // 序列的长度int K scanner.nextInt(); // 需要修改的连续子序列的长度int arrA[] new int[N]; // 输入的整数序列for (int i 0; i N; i) {arrA[i] scanner.nextInt();}scanner.close();// 计算初始序列的最长不下降子序列长度int initLNDS computeLNDS(arrA);int maxLNDS initLNDS;// 遍历所有可能的连续子序列尝试将其修改为相同值for (int i 0; i N - K; i) {int[] original Arrays.copyOfRange(arrA, i, i K); // 保存原始子序列int uniqueVals[] Arrays.stream(arrA).distinct().toArray(); // 获取序列中所有不同的值for (int value : uniqueVals) {// 将连续的 K 个数修改为当前值for (int j i; j i K; j) {arrA[j] value;}// 计算修改后的序列的LNDS长度int modifiedLNDS computeLNDS(arrA);maxLNDS Math.max(maxLNDS, modifiedLNDS);}// 恢复原始子序列System.arraycopy(original, 0, arrA, i, K);}// 输出最长的LNDS长度System.out.println(maxLNDS);
}辅助函数 computeLNDS
private static int computeLNDS(int[] array) {int[] dp_computeLNDS new int[array.length];int length 0;for (int num : array) {int pos Arrays.binarySearch(dp_computeLNDS, 0, length, num);if (pos 0) {pos -(pos 1);}dp_computeLNDS[pos] num;if (pos length) {length;}}return length;
}代码说明 输入读取 使用 Scanner 读取输入的整数序列的长度 N 和需要修改的连续子序列的长度 K。读取序列 arrA。 初始 LNDS 计算 通过 computeLNDS 函数计算初始序列的最长不下降子序列长度。 遍历所有可能的修改 遍历所有可能的长度为 K 的连续子序列。对于每个子序列尝试将其修改为序列中每一个不同的值。对修改后的序列使用 computeLNDS 重新计算最长不下降子序列的长度。更新最大长度 maxLNDS。 恢复原始子序列 每次修改后使用 System.arraycopy 恢复原始子序列确保每次修改都是独立的。 输出结果 最后输出最大长度 maxLNDS。
复杂度分析
由于需要遍历所有长度为 K 的子序列并对每个子序列尝试所有不同的值算法的时间复杂度较高。计算 LNDS 使用了二分查找因此 computeLNDS 函数的时间复杂度为 O(N log N)。
优化建议
由于可能的输入范围较大N 10^5A[i] 10^6上述算法在最坏情况下的性能可能不足以处理所有测试用例。可以考虑其他优化策略例如利用滑动窗口等方法减少重复计算以提升效率。
参考代码
package leetcode板块;import java.util.Arrays;
import java.util.Scanner;public class _题目2668蓝桥杯2022年第十三届省赛真题_最长不下降子序列 {/**** param args*/public static void main(String[] args) {// 现在你有一次机会将其中【连续的 K 个数】 修改成 【任意一个相同值】。// 请你计算如何修改可以使修改后的数列的最长不下降子序列最长请输出这个最长的长度。// TODO 最长不下降子序列是指序列中的一个子序列子序列中的每个数不小于在它之前的数。/*对于所有评测用例1 ≤ K ≤ N ≤ 10^51 ≤ Ai ≤ 10^6。*/Scanner scanner new Scanner(System.in);// 长度为 N , 将其中连续的 K 个数修改成任意一个相同值int N scanner.nextInt();int K scanner.nextInt();int arrA [] new int[N];for (int i 0; iN;i){arrA[i] scanner.nextInt();}scanner.close();// 重点 LNDS:longest non-decreasing subsequenceint initLNDS computeLNDS(arrA);int maxLNDS initLNDS;// ----------------------------------------------for (int i 0; i N-K;i){int [] original Arrays.copyOfRange(arrA,i,iK);int uniqueVals [] Arrays.stream(arrA).distinct().toArray();for (int value : uniqueVals){for (int j i;jiK;j){arrA[j] value;}int modifiedLNDS computeLNDS(arrA);maxLNDS Math.max(maxLNDS,modifiedLNDS);}System.arraycopy(original,0,arrA,i,K);}System.out.println(maxLNDS);}/**** param array* return*/private static int computeLNDS(int[] array) {int [] dp_computeLNDS new int[array.length];int length 0;for (int num : array){int pos Arrays.binarySearch(dp_computeLNDS,0,length,num);if (pos 0){pos -(pos 1);}dp_computeLNDS[pos] num;if (pos length){length;}}return length;}
}
错误经验吸取
