LeetCode 1248. 统计「优美子数组」
2020-04-21 16:08:29来源:博客园 阅读 ()
LeetCode 1248. 统计「优美子数组」
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 1248. 统计「优美子数组」
题目
给你一个整数数组?nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
- 比较简单的想法是,顺次找到每k个奇数的子数组,然后左右各自扩展直至遇到奇数,左右和+左右乘积+1就是该k个奇数的总优美子数组情况;
- 对上述的优化点是,每次左右扩展实际是在找相邻两个奇数间的偶数数量,所以可以把这部分数据用map保存下来复用,避免每次都扫描;
- 前缀和进一步优化,因为奇偶数对应的就是10,所以可以把map进一步压缩为一维数组,统计第i个奇数其左侧的偶数数量+1(奇数本身也算一个优美子数组);
思路1-寻找k个奇数片段当核心左右扩展;
步骤:
- 用队列保存奇数下标,当找到第k个奇数时,取队列的头尾下标开始左右扩展统计偶数的数量记为l和r;
- 当前k个奇数的优美子数组总数为:l+r+l\(\ast\)r+1,即左右各自和与左右乘积再加左右都不算时的本身;
- 统计完当前的,头部的奇数出队,寻找下一个奇数凑够k个奇数重复2的逻辑;
算法复杂度: n为数组长度
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $ 因为最差时可能每次都要扫描整个数组
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路2-对1优化,使用map保存相邻奇数间的偶数数量
步骤思路同1
算法复杂度: n为数组长度
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路3-对1优化,使用前缀和,或者说是二进制01压缩思想;
步骤: 这里配合代码看比较容易懂
- 创建长度为源数组长度+1的前缀和数组pre,pre[0]=1(第一个位置是否奇偶都要算为一种情况);
- 顺次统计记录第i个奇数左侧的偶数数量+1,及当前奇数数量sum;
- 当达到k个奇数事,累加第sum-k个奇数的的值;
算法复杂度: n为数组长度
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
算法源码示例
package leetcode;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
/**
* @author ZhouJie
* @date 2020年4月21日 下午3:54:13
* @Description: 1248. 统计「优美子数组」
*
*/
public class LeetCode_1248 {
}
class Solution_1248 {
/**
* @author: ZhouJie
* @date: 2020年4月21日 下午4:47:43
* @param: @param nums
* @param: @param k
* @param: @return
* @return: int
* @Description: 1-每找到一个连续k,再左右贪心;
*
*/
public int numberOfSubarrays_1(int[] nums, int k) {
int all = 0;
if (k > nums.length) {
return all;
}
Deque<Integer> deque = new ArrayDeque<Integer>();
int len = nums.length;
int count = 0;
for (int i = 0; i < len; i++) {
if ((nums[i] & 1) == 1) {
deque.offer(i);
count++;
if (count == k) {
int left = deque.peekFirst();
int right = deque.peekLast();
int l = 0, r = 0;
while (--left > -1 && (nums[left] & 1) == 0) {
l++;
}
while (++right < len && (nums[right] & 1) == 0) {
r++;
}
all += l + r + l * r + 1;
deque.pollFirst();
count--;
}
}
}
return all;
}
/**
* @author: ZhouJie
* @date: 2020年4月21日 下午4:48:28
* @param: @param nums
* @param: @param k
* @param: @return
* @return: int
* @Description: 2-对1的优化,可以保留贪心时的扩展供下次使用;
*
*/
public int numberOfSubarrays_2(int[] nums, int k) {
int all = 0;
if (k > nums.length) {
return all;
}
// 记录奇数的索引位置
Deque<Integer> deque = new ArrayDeque<Integer>();
// 记录奇数对应索引左侧连续偶数数量
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int len = nums.length;
// index从-1开始,因为要记录奇数之间的偶数,所以从-1开始,可认为-1位置是一个奇数
int count = 0, index = -1;
for (int i = 0; i < len; i++) {
if ((nums[i] & 1) == 1) {
// 奇数入队
deque.offer(i);
// 记录当前奇数索引左侧偶数数量
map.put(i, i - index - 1);
// 更新奇数标记
index = i;
count++;
// 因为要记录奇数间隔,所以需要多找第k+1个奇数位置并记录其左侧连续偶数数量,然后再计算
if (count == k + 1) {
// queue头部奇数所在索引左侧连续偶数数量
int l = map.get(deque.poll());
// 当前第count+1个奇数左侧的连续偶数数量
int r = map.get(i);
// 连续字数组计算:左侧连续偶数数量+右侧连续偶数数量+左右成乘积+不添加左右连续-本体
all += l + r + l * r + 1;
count--;
}
}
}
// 右边界判断,若有k个奇数但末尾有若干连续偶数时或者最后一个数恰是奇数时
if (count == k) {
// 此时队列有k个奇数,只需要获得头部奇数所在位置左侧偶数数量
int l = map.get(deque.poll());
// 最后一个数是奇数
if (index == len - 1) {
int r = 0;
all += l + r + l * r + 1;
// 最后一个非奇数
} else {
int r = len - index - 1;
all += l + r + l * r + 1;
}
}
return all;
}
/**
* @author: ZhouJie
* @date: 2020年4月21日 下午6:48:44
* @param: @param nums
* @param: @param k
* @param: @return
* @return: int
* @Description: 3-前缀和/0压缩
*
*/
public int numberOfSubarrays_3(int[] nums, int k) {
int all = 0;
if (k > nums.length) {
return all;
}
// nums奇数的数量,k个奇数本身算一个子数组,共需要存nums.length + 1种情况
int[] preArr = new int[nums.length + 1];
// 0位置是否奇数都要算一个子数组
preArr[0] = 1;
int sum = 0;
for (int i : nums) {
// 统计奇数数量,二进制末尾位置1为奇数,0为偶数
sum += (i & 1);
// 第sum个奇数左侧的非奇数数量+1,奇数本身也算作一个子数组
preArr[sum]++;
if (sum >= k) {
// 遇到k个之后的奇数,k个奇数左侧的子数组数为preArr[sum - k],k个奇数右侧每匹配到一个非奇数就多了preArr[sum - k]种子数组
all += preArr[sum - k];
}
}
return all;
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12747471.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LeetCode 287. 寻找重复数 2020-05-31
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash