LeetCode Ts-2871. Split Array Into Maximum Number of Subarrays

    AllenLi
    CodingLeetCode Js-DP

    You are given an array nums consisting of non-negative integers.
    We define the score of subarray nums[l..r] such that l <= r as nums[l] AND nums[l + 1] AND ... AND nums[r] where AND is the bitwise AND operation. Consider splitting the array into one or more subarrays such that the following conditions are satisfied: Each element of the array belongs to exactly one subarray. The sum of scores of the subarrays is the minimum possible. Return the maximum number of subarrays in a split that satisfies the conditions above. A subarray is a contiguous part of an array. 

    你給予一個非負整數組成的陣列 nums。
我們定義子陣列 nums[l..r] 的分數，其中 l <= r 定義為 nums[l] AND nums[l + 1] AND ... AND nums[r]，
其中 AND 表示按位元運算。
考慮將陣列分割成一個或多個子陣列，並滿足以下條件：
陣列中的每個元素都恰好屬於一個子陣列。
子陣列的分數總和為最小值。
回傳滿足上述條件分割子陣列的最大數量。
子陣列是陣列中連續的部分。

    Example 1:

    Input: nums = [1,0,2,0,1,2]
Output: 3
Explanation: We can split the array into the following subarrays:
- [1,0]. The score of this subarray is 1 AND 0 = 0.
- [2,0]. The score of this subarray is 2 AND 0 = 0.
- [1,2]. The score of this subarray is 1 AND 2 = 0.
The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain.
It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3.

    Example 2:

    Input: nums = [5,7,1,3]
Output: 1
Explanation: We can split the array into one subarray: [5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain.
It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1.

    Solution:
    題目要求要將陣列切成最多的連續子陣列，
    而每段 AND 值的加總最小(理想狀況為 0)。
    如果整段陣列的 AND !== 0，無法切更小只能切一段，
    如果 AND = 0，我們使用動態規劃 + 位元記錄的方式找到每個元素可以切的位置。
    last[j] 記錄第 j 位（bit）最近出現 0 的位置。
    對每個元素 nums[i]：
    – 更新每個 bit 的 last[j]。
    – 找出最早可以切段的起點 minIndex = min(last[0..19])。
    – 更新 dp[i]：
    如果 minIndex == -1 → 無法切 → dp[i] = -1
    如果 minIndex == 0 或前面無法切 → dp[i] = 1
    否則 → dp[i] = dp[minIndex – 1] + 1
    最後回傳：dp[n-1] → 表示最多可以切成的子陣列數。

    Code 1: BigO(n)

    function maxSubarrays(nums: number[]): number {
    const n = nums.length;
    let [totalAnd] = nums;
    for (const num of nums) {
        totalAnd &= num;
    }

    if (totalAnd !== 0) return 1;

    const dp: number[] = new Array(n).fill(-1);
    const last: number[] = new Array(20).fill(-1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < 20; j++) {
            if ((nums[i] & (1 << j)) === 0) {
                last[j] = i;
            }
        }

        let minIndex: number = i;
        for (let j = 0; j < 20; j++) {
            minIndex = Math.min(minIndex, last[j]);
        }

        if (minIndex === -1) {
            dp[i] = -1;
        } else if (minIndex === 0 || dp[minIndex - 1] === -1) {
            dp[i] = 1;
        } else {
            dp[i] = dp[minIndex - 1] + 1;
        }
    }    
    return dp[n - 1];
};

    FlowChart:
    Example 1

    Input: nums = [1,0,2,0,1,2]

i=0, dp=-1, minIndex=-1, last=-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
i=1, dp=1, minIndex=1, last=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
i=2, dp=1, minIndex=1, last=2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2
i=3, dp=2, minIndex=3, last=3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3
i=4, dp=2, minIndex=3, last=3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4
i=5, dp=3, minIndex=4, last=5,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5

    Example 2

    Input: nums = [5,7,1,3]

5 & 7 & 1 & 3
= 5 & 7 → 5
= 5 & 1 → 1
= 1 & 3 → 1

totalAnd !== 0, return -1;

    Related Posts