• Leetcode 2871. Split Array Into Maximum Number of Subarrays
  • 1. 解題思路
  • 2. 代碼實(shí)現(xiàn)

• 題目鏈接：2871. Split Array Into Maximum Number of Subarrays

1. 解題思路

這一題實(shí)現(xiàn)上其實(shí)還是比較簡(jiǎn)單的，就是一個(gè)貪婪算法，主要就是思路上需要想想清楚。

顯然，如果所有數(shù)的與操作結(jié)果不為0，那么要使得結(jié)果最小，那么有且只有一種分法，那就是完全不進(jìn)行切割，否則切割之后的兩個(gè)子序列一定均不為0，其和必然大于不切分的結(jié)果。

因此，要考慮的就是所有數(shù)的與操作結(jié)果為0的情況，此時(shí)必然有所有分割之后的子串的與操作結(jié)果均為0，此時(shí)，我們用一個(gè)貪婪算法找到所有切割之后與操作結(jié)果為0的子串即可。

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(xiàn)如下：

class Solution:def maxSubarrays(self, nums: List[int]) -> int:cnt = 0is_start = Truefor x in nums:if is_start:s = xis_start = Falseelse:s = s & xif s == 0:cnt += 1is_start = Truereturn max(cnt, 1)

提交代碼評(píng)測(cè)得到：耗時(shí)806ms，占用內(nèi)存26.8MB。