微官网和微网站,网站开发需要多钱,新的网站建设技术,百度官方app免费下载题目描述 这是 LeetCode 上的 「2698. 求一个整数的惩罚数」 #xff0c;难度为 「简单」。 Tag : 「双指针」、「滑动窗口」 给你一个下标从 开始的整数数组 nums 和一个整数 threshold。 请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 ( ) 且满足以下条件的 最长子… 题目描述 这是 LeetCode 上的 「2698. 求一个整数的惩罚数」 难度为 「简单」。 Tag : 「双指针」、「滑动窗口」 给你一个下标从 开始的整数数组 nums 和一个整数 threshold。 请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 ( ) 且满足以下条件的 最长子数组 nums[l] % 2 0 对于范围 内的所有下标 i nums[i] % 2 ! nums[i 1] % 2 对于范围 内的所有下标 i nums[i] threshold 以整数形式返回满足题目要求的最长子数组的长度。 注意子数组 是数组中的一个连续非空元素序列。 示例 1 输入nums [3,2,5,4], threshold 5输出3解释在这个示例中我们选择从 l 1 开始、到 r 3 结束的子数组 [2,5,4] 满足上述条件。因此答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。 示例 2 输入nums [1,2], threshold 2输出1解释在这个示例中我们选择从 l 1 开始、到 r 1 结束的子数组 [2] 。该子数组满足上述全部条件。可以证明 1 是满足题目要求的最大长度。 示例 3 输入nums [2,3,4,5], threshold 4输出3解释在这个示例中我们选择从 l 0 开始、到 r 2 结束的子数组 [2,3,4] 。 该子数组满足上述全部条件。因此答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。 提示 双指针 整体题意找 nums 中的最长的子数组 对于任意 不超过 threshold且从 开始按照「先偶后奇」顺序交替。 假设子数组的左端点为 i且“最远的”合法右端点为 j那么在 之间的任意右端点 k即使能够使得 合法对统计答案而言也是没有意义的因为我们求的是最长。 基于此我们容易想到「找到所有的合法左端点 i并统计该合法左端点的最远右端点 j。跳过 之间的点作为左端点的情况直接从结束位置 j 开始找下一个合法左端点。」 该做法可将朴素的 做法优化至 。 但这做法为什么是正确的 我们只考虑了 中间点作为右端点的情况那作为左端点呢为什么跳过 之间的 作为左端点正确性也不受影响我们不是漏到了某些方案吗 答案「是漏掉了但也只是漏掉了那些必不可能是最长子数组的方案」。 具体的我们重新整理上述的「双指针」做法 从前往后扫描 nums变量 i 作为当前子数组左端点首先确保 i 的合法性跳过不满足 nums[i] % 2 0 和 nums[i] threshold 的位置 随后在固定左端点 i 前提下找最远的第一个不满足要求的右端点 j值不超过 threshold且奇偶性与前值交替 得到当前连续段长度 更新 ans从当前结束位置 j 开始重复上述过程直到处理完 nums Java 代码 class Solution { public int longestAlternatingSubarray(int[] nums, int threshold) { int n nums.length, ans 0, i 0; while (i n) { if ((nums[i] % 2 ! 0 || nums[i] threshold) i 0) continue; int j i 1, cur nums[i] % 2; while (j n) { if (nums[j] threshold || nums[j] % 2 cur) break; cur nums[j] % 2; } ans Math.max(ans, j - i); i j; } return ans; }} C 代码 class Solution {public: int longestAlternatingSubarray(vectorint nums, int threshold) { int n nums.size(), ans 0, i 0; while (i n) { if ((nums[i] % 2 ! 0 || nums[i] threshold) i 0) continue; int j i 1, cur nums[i] % 2; while (j n) { if (nums[j] threshold || nums[j] % 2 cur) break; cur nums[j] % 2; } ans max(ans, j - i); i j; } return ans; }}; Python 代码 class Solution: def longestAlternatingSubarray(self, nums: List[int], threshold: int) - int: n, ans, i len(nums), 0, 0 while i n: if nums[i] % 2 ! 0 or nums[i] threshold: i 1 continue j, cur i 1, nums[i] % 2 while j n: if nums[j] threshold or nums[j] % 2 cur: break cur, j nums[j] % 2, j 1 ans max(ans, j - i) i j return ans TypeScript 代码 function longestAlternatingSubarray(nums: number[], threshold: number): number { let n nums.length, ans 0, i 0 while (i n) { if ((nums[i] % 2 ! 0 || nums[i] threshold) i 0) continue; let j i 1, cur nums[i] % 2; while (j n) { if (nums[j] threshold || nums[j] % 2 cur) break; cur nums[j] % 2; } ans Math.max(ans, j - i); i j; } return ans;}; 时间复杂度 空间复杂度 最后 这是我们「刷穿 LeetCode」系列文章的第 No.2760 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
