2963. Good Partitions

Count the Number of Good Partitions

直接进入正题 这次的任务是将 输入的数组分割成一个或多个连续子数组

限定任两个子数组不能共享相同的数字 达成此条件才叫好的分割法

要回传的正整数就是代表著究竟有多少种好分割法

不能脚踏两条船？那么......嘿嘿

帮翻译这条限制：同一个数字 把最早和最晚登场的索引$i$和$j$找到手 $i$和$j$这俩索引必须同属一个集团

换言之 我们需要追踪一个数字最晚登场的索引是多少 追踪好后 这样子

方能顺势启动scanIdx和boundaryIdx两个索引

boundaryIdx代表著 当前还没定案的集团$G_i$ 其右端边界 所在的索引位置

scanIdx则是用来 递增扫描 属于$G_i$的索引中 那些还没被检查过的索引

检查什么呢？检查这个索引上对位的数字$x$ 它最晚登场的索引$j$是否大过了boundaryIdx

一旦大过了boundaryIdx 那么必须让boundaryIdx = $j$

才能令$x$展现忠诚 乖乖留守同一个集团 也就是当前还没成形的这个$G_i$ 确保$x$不脚踏两条船😏

反过来说 scanIdx递增扫描的过程 倘若有一刻竟然变成$>$boundaryIdx

自然意味著集团$P_i$彻底结业 能停止成长了 亦能为此更新已成形的总集团数量

已成形的总集团数量又代表什么呢？

假设总集团数量有$k$个 那它们中间有$k - 1$个间隙

每一个间隙都面临两条路：留著分离相邻两个集团；或者消失 好让相邻的集团合而为一

由此答案就出来啦！好分割法总数 = $2^{k - 1}$ ✌️

题外话 咱们三国时期的曹丞相当时听了庞统的连环计 选择了最极端的一种分割法

拿掉全部间隙 把船队全用铁鍊拴在一块 结果就是赤壁之战被一把火烧光......

说回正题 因为分割法总数是 $O(2^k)$ 这种规模的体量 因此需要开一个$10^9 + 7$的模来防止数值爆炸

甚至计算指数$2^{k - 1}$的过程 也要用 模幂运算 来计算比较保险

哈希表存取每个数字最晚登场索引 空间复杂度O(n)

模幂运算采用迭代方式实现 空间复杂度仅O(1)

每个索引都是被scanIdx扫描一次 又建哈希表时也被刚好扫描一次 时间复杂度是O(n)

模幂运算的时间复杂度是$O(\log (k - 1))$ $k$为成形的总集团数量

但是$k$最多就是到$n$ 因此模幂运算时间复杂度其实是$O(\log n)$

最后时空复杂度均为O(n) 轻巧地下庄拿AC👌👌

C++

#include <vector>
#include <unordered_map>
using namespace std;

int countGoodPartitions(vector<int> &nums) // LeetCode Q.2963.
{
    unordered_map<int, int> numsLastIndices; // Each num's last idx.

    for (int idx = 0; idx < nums.size(); idx++)
        numsLastIndices[nums[idx]] = idx;

    int windowsCount = 0; // Sliding window by two pointers.
    int scanIdx = 0, boundaryIdx = 0;

    while (boundaryIdx < nums.size())
    {
        int num = nums[scanIdx];
        scanIdx++; // Already visited.

        if (boundaryIdx < numsLastIndices[num])
        { // Num extends current window.
            boundaryIdx = numsLastIndices[num];
            continue;
        }

        if (scanIdx > boundaryIdx)
        {
            windowsCount++; // Current window is finalized.

            boundaryIdx++; // Search for another window, if possible.
        }
    }

    int goodPartitions = 1;

    int power = windowsCount - 1, modulo = pow(10, 9) + 7;

    while (power > 0)
    {
        goodPartitions *= 2;
        goodPartitions %= modulo; // Must prevent overflow.
        power--;
    }

    return goodPartitions;
}

Python

def count_good_partitions(nums: list[int]) -> int:  # LeetCode Q.2963.
    nums_last_indices: dict[int, int] = dict()  # Each num's last idx.

    for idx, num in enumerate(nums):
        nums_last_indices[num] = idx

    windows_count = 0  # Sliding window by two pointers.
    scan_idx, boundary_idx = 0, 0

    while boundary_idx < len(nums):
        num = nums[scan_idx]
        scan_idx += 1  # Already visited.

        if boundary_idx < nums_last_indices[num]:  # Num extends current window.
            boundary_idx = nums_last_indices[num]
            continue

        if scan_idx > boundary_idx:
            windows_count += 1  # Current window is finalized.

            boundary_idx += 1  # Search for another window, if possible.

    good_partitions = 1
    power = windows_count - 1
    base = 2  # Mod exp method speeds up quite some in Python.
    modulo = 10 ** 9 + 7

    while power > 0:
        if power % 2 == 1:  # Power is odd: product times current base.
            good_partitions *= base
            good_partitions %= modulo

        base = (base * base) % modulo  # Square base and reduce power.
        power //= 2

    return good_partitions