11 周赛最后一题，真的不难

2963. 统计好分割方案的数目

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 11 篇题解，更多题解关注 Somnia1337@力扣。

本篇介绍 @2023.12.10 第 375 场周赛的最后一题，有人说难度只能算中等，不过赛场上还是憋了挺久才拿下 AK🤣

题目描述

难度：🔴困难

标签：#数学哈希表

给你一个下标从 0 开始、由正整数组成的数组 nums。

将数组分割成一个或多个连续子数组，如果不存在包含了相同数字的两个子数组，则认为是一种好分割方案。

返回 nums 的好分割方案的数目。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

输入: nums = [1,2,1,3]
输出: 2
解释: 有 2 种好分割方案: ([1,2,1], [3]),([1,2,1,3])

输入: nums = [1,1,1,1]
输出: 1
解释: 只有 1 种好分割方案: ([1,1,1,1])

解题思路

先考虑没有限制条件时的方案数：相邻元素之间的空位上可以放隔板，加 / 不加是 $2$ 种选择，则 $n$ 个元素有 $2^{n - 1}$ 种方案。

加限制条件相当于禁用其中一些位置（不能放隔板）。

假设某元素重复出现的位置列表为 [p0,...,pk]，由于它必须全部出现在一个子数组，则 p0 到 pk 间的所有位置都不能放隔板。

boolean[n - 1] 标记每个位置是否被禁用，哈希表记录 <元素, 下标[最左, 最右]>，对于重复出现的元素，禁用其出现的两端之间的所有位置。最后，计数没有被禁用的位置，用带模快速幂计算 $2^{c n t}$ 。

复杂度

时间复杂度： $O (N)$
空间复杂度： $O (N)$

代码

Java

class Solution {
    public int numberOfGoodPartitions(int[] nums) {
        boolean[] ban = new boolean[nums.length - 1]; // 禁用的位置
        Map<Integer, int[]> pos = new HashMap<>(); // <元素, 下标[最左, 最右]>
        for (int i = 0; i < nums.length; i++) {
            if (pos.containsKey(nums[i])) pos.get(nums[i])[1] = i; // 重复出现, 最右位置 i
            else pos.put(nums[i], new int[]{i, -1}); // 首次出现, 最左位置 i
        }
        
        for (int[] p : pos.values()) {
            if (p[1] > 0) { // 重复出现
                Arrays.fill(ban, p[0], p[1], true); // 禁用两端之间的位置
            }
        }
        
        int cnt = 0; // 未禁用的位置计数
        for (boolean b : ban) if (!b) cnt++;
        return pow(2, cnt, 1000000007); // 带模快速幂
    }
	
    private int pow(long x, int p, int MOD) {
        long ret = 1;
        while (p > 0) {
            if (p % 2 == 1) ret = ((ret % MOD) * (x % MOD)) % MOD;
            x = ((x % MOD) * (x % MOD)) % MOD;
            p >>= 1;
        }
        return (int) ret;
    }
}

Python

Python 内置带模快速幂。

class Solution:
    def numberOfGoodPartitions(self, nums):
        ban = [False] * (len(nums) - 1)  # 禁用的位置
        pos = {}  # <元素, 下标[最左, 最右]>
        for i in range(len(nums)):
            if nums[i] in pos:
                pos[nums[i]][1] = i  # 重复出现, 最右位置 i
            else:
                pos[nums[i]] = [i, -1]  # 首次出现, 最左位置 i
		
        for p in pos.values():
            if p[1] > 0:  # 重复出现
                ban[p[0] : p[1]] = [True] * (p[1] - p[0])  # 禁用两端之间的位置
		
        return pow(2, sum(1 for b in ban if not b), 1000000007)  # 带模快速幂

最后

更多系列「外源推文」&「生活分享」关注公众号：

🥑 EmberNecro

Explorer