当前位置：首页 > news >正文

力扣每日一题--2025.7.16

news 2025/7/18 18:22:42

📚 力扣每日一题–2025.7.16

📚 3201. 找出有效子序列的最大长度 I（中等）

今天我们要解决的是力扣上的第 3201 题——找出有效子序列的最大长度 I。这道题虽然标记为中等难度，但只要掌握了正确的思路，就能轻松解决！

📝 题目描述

在这里插入图片描述

🤔 思路分析

核心需求推导过程 📝

题目要求子序列中所有相邻元素之和的奇偶性必须相同，即：

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x-2] + sub[x-1]) % 2

这个条件可以从两个角度理解：

数学本质：所有相邻元素对的和具有相同的奇偶性
序列特性：子序列中的元素必须形成一种特定的奇偶性模式

通过进一步推理，我们可以得出两种基本的有效序列模式：

模式一：全同奇偶性序列

当要求相邻元素之和为偶数时，所有元素必须具有相同的奇偶性
证明：若 a+b 为偶数且 b+c 为偶数，则 a 和 b 奇偶性相同，b 和 c 奇偶性相同，因此 a 和 c 奇偶性相同，以此类推

模式二：交替奇偶性序列

当要求相邻元素之和为奇数时，元素必须交替出现奇偶性
证明：若 a+b 为奇数且 b+c 为奇数，则 a 和 b 奇偶性不同，b 和 c 奇偶性不同，因此 a 和 c 奇偶性相同，形成交替模式

让我们通过具体示例验证这些模式：

全奇序列 [1,3,5,7]：所有相邻和都为偶数 (4,8,12)，符合模式一
奇偶交替序列 [1,2,3,4]：所有相邻和都为奇数 (3,5,7)，符合模式二
混合序列 [1,2,2,3]：相邻和为 3(奇)、4(偶)、5(奇)，不符合任何模式

所以，有效子序列有两种基本类型：

所有相邻元素之和都为偶数
所有相邻元素之和都为奇数

我们需要分别找出这两种类型的最长子序列，然后取较大值作为答案。

📑 解法探讨

方法一：暴力枚举（理解问题本质）

最直观的思路是枚举所有可能的子序列，检查它们是否有效，并记录最长有效子序列的长度。

这个官方的测试用例可以通过，但是提交的时候会超时，我这边只是给大家提供一个思路方法。

/*** 方法一：暴力枚举法* 思路：枚举所有可能的子序列起点和两种类型的有效子序列，*       构建并检查每个子序列的有效性，记录最长有效子序列长度* 注意：此方法仅用于理解问题本质，实际提交可能会超时*/
public class Solution {/*** 找出最长有效子序列的长度* @param nums 输入的整数数组* @return 最长有效子序列的长度*/public int maximumLength(int[] nums) {int n = nums.length;// 边界情况处理：空数组或单元素数组，直接返回数组长度if (n <= 1) return n;// 最小有效子序列长度为1（单个元素本身就是有效子序列）int maxLen = 1;// 枚举所有可能的子序列起点for (int i = 0; i < n; i++) {// 尝试两种类型的有效子序列// type=0: 相邻元素之和为偶数// type=1: 相邻元素之和为奇数for (int type = 0; type <= 1; type++) {int len = 1;          // 当前子序列长度，至少包含起点元素int last = nums[i];   // 记录子序列最后一个元素// 从起点后一个元素开始构建子序列for (int j = i + 1; j < n; j++) {// 计算当前元素与子序列最后一个元素之和的奇偶性int sumMod = (last + nums[j]) % 2;// 如果符合当前类型要求，则加入子序列if (sumMod == type) {len++;last = nums[j]; // 更新子序列最后一个元素}}// 更新最长有效子序列长度maxLen = Math.max(maxLen, len);}}return maxLen;}
}

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组长度
空间复杂度：O(1)，只使用了常数额外空间

方法二：贪心算法（最优解法）

通过观察，我们可以发现两种类型的有效子序列具有明显的模式：

类型 0（相邻元素之和为偶数）：所有元素必须具有相同的奇偶性
- 全是偶数，或全是奇数
- 最长长度 = max(偶数元素个数, 奇数元素个数)
类型 1（相邻元素之和为奇数）：元素必须交替出现奇偶性
- 奇偶奇偶…或偶奇偶奇…
- 最长长度取决于两种模式中较长的一个

基于这些观察，我们可以设计出 O(n)时间复杂度的贪心算法：

/*** 方法二：贪心算法（最优解法）* 思路：通过分析有效子序列的两种模式，分别计算其最大长度*       类型0（相邻和为偶数）：所有元素奇偶性相同，取较多的那种奇偶性元素个数*       类型1（相邻和为奇数）：元素奇偶性交替出现，计算两种起始模式的最大长度* 时间复杂度：O(n)，空间复杂度：O(1)*/
public class Solution {/*** 找出最长有效子序列的长度* @param nums 输入的整数数组* @return 最长有效子序列的长度*/public int maximumLength(int[] nums) {int n = nums.length;// 边界情况处理：空数组或单元素数组，直接返回数组长度if (n <= 1) return n;// 统计数组中奇数和偶数的个数int oddCount = 0, evenCount = 0;for (int num : nums) {if (num % 2 == 0) evenCount++;else oddCount++;}// 类型0的最大长度：所有元素奇偶性相同，取较多的那种int type0Max = Math.max(oddCount, evenCount);// 如果只有一种奇偶性，无法形成类型1的子序列（需要交替出现）if (oddCount == 0 || evenCount == 0) {return type0Max;}// 计算类型1的两种模式的最大长度// 模式1：以奇数开始的交替序列（奇-偶-奇-偶...）int type1Max1 = calculateAlternatingLength(nums, true);// 模式2：以偶数开始的交替序列（偶-奇-偶-奇...）int type1Max2 = calculateAlternatingLength(nums, false);// 取两种模式中的较大值int type1Max = Math.max(type1Max1, type1Max2);// 返回两种类型中的最大值return Math.max(type0Max, type1Max);}/*** 计算交替奇偶性序列的长度* @param nums 输入的整数数组* @param startWithOdd 是否以奇数开始* @return 交替序列的长度*/private int calculateAlternatingLength(int[] nums, boolean startWithOdd) {int length = 0;               // 序列长度boolean expectedOdd = startWithOdd; // 期望的下一个元素的奇偶性// 遍历数组，构建交替序列for (int num : nums) {boolean isOdd = num % 2 == 1; // 当前元素是否为奇数// 如果当前元素符合期望的奇偶性，则加入序列if (isOdd == expectedOdd) {length++;expectedOdd = !expectedOdd; // 切换期望的奇偶性}}return length;}
}

复杂度分析：

时间复杂度：O(n)，只需遍历数组几次
空间复杂度：O(1)，只使用了常数额外空间

方法三：动态规划（更通用的解决方案）

这个也超时了，但是方法思路应该是这样的，之后我再想办法去优化一下。

我们也可以使用动态规划来解决这个问题，定义两个状态：

dp0[i]：以第 i 个元素结尾，且相邻元素之和为偶数的最长有效子序列长度
dp1[i]：以第 i 个元素结尾，且相邻元素之和为奇数的最长有效子序列长度

/*** 方法三：动态规划（更通用的解决方案）* 思路：定义两个状态数组，分别记录以每个位置结尾的两种类型子序列的最大长度*       dp[i][0]：以第i个元素结尾，相邻和为偶数的最长子序列长度*       dp[i][1]：以第i个元素结尾，相邻和为奇数的最长子序列长度* 时间复杂度：O(n²)，空间复杂度：O(n)*/
public class Solution {/*** 找出最长有效子序列的长度* @param nums 输入的整数数组* @return 最长有效子序列的长度*/public int maximumLength(int[] nums) {int n = nums.length;// 边界情况处理：空数组或单元素数组，直接返回数组长度if (n <= 1) return n;// 动态规划数组定义：// dp[i][0]：以第i个元素结尾，且相邻元素之和为偶数的最长有效子序列长度// dp[i][1]：以第i个元素结尾，且相邻元素之和为奇数的最长有效子序列长度int[][] dp = new int[n][2];// 初始化：第一个元素本身就是长度为1的有效子序列dp[0][0] = 1; // 以第一个元素结尾的类型0子序列dp[0][1] = 1; // 以第一个元素结尾的类型1子序列int maxLen = 1; // 记录最长有效子序列长度// 从第二个元素开始计算for (int i = 1; i < n; i++) {// 默认情况下，子序列只包含当前元素，长度为1dp[i][0] = 1;dp[i][1] = 1;// 检查前面所有元素，看是否可以形成更长的有效子序列for (int j = 0; j < i; j++) {// 计算nums[j]和nums[i]之和的奇偶性int sumMod = (nums[j] + nums[i]) % 2;// 如果前面元素j和当前元素i的和的奇偶性为sumMod// 则可以将i添加到以j结尾的sumMod类型子序列后面if (dp[j][sumMod] + 1 > dp[i][sumMod]) {dp[i][sumMod] = dp[j][sumMod] + 1;}}// 更新最长有效子序列长度maxLen = Math.max(maxLen, Math.max(dp[i][0], dp[i][1]));}return maxLen;}
}

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组长度
空间复杂度：O(n)，需要存储 dp 数组

🚀 优化后的贪心算法

我们可以进一步优化贪心算法，只需要一次遍历就能计算出两种类型 1 子序列的最大长度：

/*** 方法四：优化后的贪心算法* 思路：在基础贪心算法的基础上，通过一次遍历同时计算两种类型1子序列的长度*       减少了遍历次数，进一步优化了性能* 时间复杂度：O(n)，空间复杂度：O(1)*/
public class Solution {/*** 找出最长有效子序列的长度* @param nums 输入的整数数组* @return 最长有效子序列的长度*/public int maximumLength(int[] nums) {int n = nums.length;// 边界情况处理：空数组或单元素数组，直接返回数组长度if (n <= 1) return n;// 统计数组中奇数和偶数的个数int oddCount = 0, evenCount = 0;for (int num : nums) {if (num % 2 == 0) evenCount++;else oddCount++;}// 类型0的最大长度：所有元素奇偶性相同，取较多的那种int type0Max = Math.max(oddCount, evenCount);// 如果只有一种奇偶性，无法形成类型1的子序列（需要交替出现）if (oddCount == 0 || evenCount == 0) {return type0Max;}// 一次遍历同时计算两种类型1子序列的最大长度int type1OddStart = 0;  // 以奇数开始的交替序列长度（奇-偶-奇-偶...）int type1EvenStart = 0; // 以偶数开始的交替序列长度（偶-奇-偶-奇...）boolean expectOddForOddStart = true;  // 奇开始模式下期望的下一个奇偶性boolean expectOddForEvenStart = false; // 偶开始模式下期望的下一个奇偶性// 遍历数组，同时构建两种交替模式的子序列for (int num : nums) {boolean isOdd = num % 2 == 1; // 当前元素是否为奇数// 处理奇-偶-奇-偶...模式if (isOdd == expectOddForOddStart) {type1OddStart++;expectOddForOddStart = !expectOddForOddStart; // 切换期望的奇偶性}// 处理偶-奇-偶-奇...模式if (isOdd == expectOddForEvenStart) {type1EvenStart++;expectOddForEvenStart = !expectOddForEvenStart; // 切换期望的奇偶性}}// 类型1的最大长度为两种模式中的较大值int type1Max = Math.max(type1OddStart, type1EvenStart);// 返回两种类型中的最大值return Math.max(type0Max, type1Max);}
}