辽宁省城乡住房建设厅网站,曹县网站建设,北京做网站建设价格,wordpress 动画特效Leetcode 2871. Split Array Into Maximum Number of Subarrays 1. 解题思路2. 代码实现 题目链接#xff1a;2871. Split Array Into Maximum Number of Subarrays
1. 解题思路
这一题实现上其实还是比较简单的#xff0c;就是一个贪婪算法#xff0c;主要就是思路上需要…Leetcode 2871. Split Array Into Maximum Number of Subarrays 1. 解题思路2. 代码实现 题目链接2871. Split Array Into Maximum Number of Subarrays
1. 解题思路
这一题实现上其实还是比较简单的就是一个贪婪算法主要就是思路上需要想想清楚。
显然如果所有数的与操作结果不为0那么要使得结果最小那么有且只有一种分法那就是完全不进行切割否则切割之后的两个子序列一定均不为0其和必然大于不切分的结果。
因此要考虑的就是所有数的与操作结果为0的情况此时必然有所有分割之后的子串的与操作结果均为0此时我们用一个贪婪算法找到所有切割之后与操作结果为0的子串即可。
2. 代码实现
给出python代码实现如下
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)提交代码评测得到耗时806ms占用内存26.8MB。
