LeetCode 5. Longest Palindromic Substring

用户头像
liu_liu
关注
发布于: 2020 年 08 月 30 日
LeetCode 5. Longest Palindromic Substring

问题描述



给定一个整数数组 nums 和一个整数 k。当子数组中有 k 个奇数时,称之为 nice



要求返回 nice 子数组的个数。



栗 1:



输入: nums = [1,1,2,1,1], k = 3
输出: 2

解释:
包含 3 个奇数的子数组有:[1,1,2,1],[1,2,1,1]



栗 2:

输入:nums = [2,4,6], k = 1
输出:0

解释:
无奇数。



栗 3:

输入: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出: 16



注意:

  • 1 <= nums.length <= 50000

  • 1 <= nums[i] <= 10^5

  • 1 <= k <= nums.length



想看英文原文的戳这里



解题思路



题目要求子数组中只需包含 k 个奇数,因此其可以与任意个数的偶数进行组合。



同时 k 个奇数不一定是连续的,有可能掺杂着偶数。由于子数组的连续性, k 个奇数之间的偶数是必须包含的。当我们找到 k 个奇数时,需要考虑其与前后偶数的组合性。



举个栗子,比如 nums = [2, 2, 1, 2, 3, 4, 6, 8], k = 2



子数组中需包含 2 个奇数,该数组中奇数为 1、3。显然, [1, 2, 3] 是子数组中必须要包含的元素。而左边的偶数 [2, 2] 和右边的偶数 [4, 6, 8] 则是可选的。它们的组合情况如下:



  • 左边有 [], [2], [2, 2] 三种组合。

  • 右边有 [], [4], [6], [4, 6, 8] 四种组合。



因此,左右两两组合总数为 3 * 4 = 12



稍微观察一下,我们可以发现:当有 n 个偶数时,组合数为 n + 1。因此,转换下思路,只需要求出左右两边偶数的个数即可。



而如何求得偶数个数呢?也比较简单,通过记录两个相邻奇数的下标,相减即可。但有种边界情况需要考虑:第一个出现的奇数,它前面没有奇数;最后一个出现的奇数,它后面有没奇数。



还是拿上面的栗子说明。



  • 第一个奇数 1 的下标是 2,可默认前一个奇数下标为 0,那么偶数个数为 2 - 0 = 2

  • 最后一个奇数 3 的下标是 4,可默认最后一个奇数下标为 数组长度 - 1,那么偶数个数为 7 - 4 = 3



当然,k 个奇数的组合方式可能不止一种,那么就需要遍历每 k 个奇数,求出它与偶数的组合数,最终得到总的组合数。



比如 nums = [2, 2, 1, 2, 3, 4, 5, 6], k = 2,奇数为 1、3、5。那么 k 个奇数的可能取值为 1、33、5,这里需要分别计算出它们与偶数的组合数。



注意:当取 1、3 时,由于它后面还有一个奇数 5,因此计算右边偶数个数时,只需计算到 5 的位置。



总体思路如下:



  • 首先取出 k 个奇数,假设其起始下标为 [m, n]

  • 将 m 与左边相邻的奇数下标做计算,求出左边组合数个数 left

  • 将 n 与右边相邻的奇数下标做计算,求出右边组合数个数 right

  • 左右两边组合数相乘,即为这个 k 个奇数的组合数: left * right

  • 向后遍历,继续取出 k 个奇数,重复以上步骤。即始终保持 k 个奇数的窗口,不断向后移动。



解法 1



这种解法比较容易理解,就是上面阐述的思路。



  • 遍历数组,记录所有奇数的下标。

  • 遍历下标列表,分别求出 k 个奇数左右两边的组合数,然后相乘。

  • 注意考虑第一个奇数和最后一个奇数的情况。



代码如下:



var numberOfSubarrays = function (nums, k) {
if (!nums) {
return 0;
}
let sum = 0;
// 奇数的 index 列表
let oddList = [];
nums.forEach((element, index) => {
if (element % 2 === 1) {
oddList.push(index);
}
});
let i = 0;
while (i <= oddList.length - k) {
let left = 0;
let right = 0;
// 计算左边的组合数,从原数组第一个数开始
if (i === 0) {
left = oddList[i] + 1;
} else {
// 计算相邻的个数
left = oddList[i] - oddList[i - 1];
}
// 覆盖 k 个奇数
// 计算右边的组合数
const endIndex = i + k - 1;
// 最后一个,组合个数可一直到原数组末尾
if (endIndex == oddList.length - 1) {
right = nums.length - oddList[endIndex];
} else {
// 计算相邻的个数
right = oddList[endIndex + 1] - oddList[endIndex];
}
sum += left * right;
i += 1;
}
return sum;
};



解法 2



思路上大同小异,只不过不需要事先计算出奇数下标列表,而是在遍历过程中判断是否达到了 k 个奇数的条件。如果满足条件,则计算组合数;如果超过了 k 个奇数,则需更新 k 个奇数列表,再进行计算。



以下代码是采用记录开始窗口的下标,然后不断滑动窗口更新下标的方式。也可以采用操作窗口数组的方式,当元素个数大于 k 时,删除第一个元素,让其始终保持 k 个数。



js 代码如下:



var numberOfSubarrays = function (nums, k) {
if (!nums) {
return 0;
}
let sum = 0;
// 记录上一次 k 个奇数数的第一个数下标
let oddIndex = 0
// 奇数的 index 列表,默认填入 -1
let oddList = [-1];
nums.forEach((element, index) => {
if (element % 2 === 1) {
oddList.push(index)
// 当已经有 k 个奇数,更新记录下标
if (oddList.length - oddIndex - 1 > k) {
oddIndex += 1
}
}
// 满足 k 个奇数
if (oddList.length - oddIndex - 1 === k) {
sum += oddList[oddIndex + 1] - oddList[oddIndex]
}
});
return sum
};



发布于: 2020 年 08 月 30 日 阅读数: 22
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 5. Longest Palindromic Substring