LeetCode 1248. 统计「优美子数组」

2020-04-22 00:00:00 数组 统计 优美

我的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个奇数片段当核心左右扩展;

步骤:

  1. 用队列保存奇数下标,当找到第k个奇数时,取队列的头尾下标开始左右扩展统计偶数的数量记为l和r;
  2. 当前k个奇数的优美子数组总数为:l+r+l\(\ast\)r+1,即左右各自和与左右乘积再加左右都不算时的本身;
  3. 统计完当前的,头部的奇数出队,寻找下一个奇数凑够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. 创建长度为源数组长度+1的前缀和数组pre,pre[0]=1(第一个位置是否奇偶都要算为一种情况);
  2. 顺次统计记录第i个奇数左侧的偶数数量+1,及当前奇数数量sum;
  3. 当达到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
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章