本地网站搭建教程,创意字体,免费网页制作模板,网络营销服务的特点有哪些文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的二进制数组 nums #xff0c;数组长度为 n 。 nums 可以按下标 i#xff08; 0 i n #xff09;拆分成两个数组#xff08;可能为空#xff09;#xff1a;numsleft 和 numsright 。
numsleft 包含 nu…
文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的二进制数组 nums 数组长度为 n 。 nums 可以按下标 i 0 i n 拆分成两个数组可能为空numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素包括 0 和 i - 1 而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素包括 i 和 n - 1 。如果 i 0 numsleft 为 空 而 numsright 将包含 nums 中的所有元素。如果 i n numsleft 将包含 nums 中的所有元素而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1
输入nums [0,0,1,0]
输出[2,4]
解释按下标分组
- 0 numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 1 1 。
- 1 numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 1 2 。
- 2 numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 1 3 。
- 3 numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 0 2 。
- 4 numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 0 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意答案 [4,2] 也被视为正确答案。示例 2
输入nums [0,0,0]
输出[3]
解释按下标分组
- 0 numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 0 0 。
- 1 numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 0 1 。
- 2 numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 0 2 。
- 3 numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 0 3 。
只有下标 3 可以得到最高的分组得分 3 。示例 3
输入nums [1,1]
输出[0]
解释按下标分组
- 0 numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 2 2 。
- 1 numsleft 为 [1] 。numsright 为 [1] 。得分为 0 1 1 。
- 2 numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 0 0 。
只有下标 0 可以得到最高的分组得分 2 。提示
n nums.length
1 n 10^5
nums[i] 为 0 或 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/all-divisions-with-the-highest-score-of-a-binary-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
正向前缀和求左侧 0 的个数反向前缀和求右侧 1 的个数遍历求最大的和、及其 下标
class Solution:def maxScoreIndices(self, nums: List[int]) - List[int]:n len(nums)left0, right1 [0 for _ in range(n)], [0 for _ in range(n)]for i in range(n):left0[i] (0 if i0 else left0[i-1]) int(nums[i]0)for i in reversed(range(n)):right1[i] (0 if in-1 else right1[i1]) int(nums[i]1)maxscore 0idxs []for i in range(n1):score (0 if i0 else left0[i-1]) (0 if in else right1[i])if score maxscore:maxscore scoreidxs [i]elif score maxscore:idxs.append(i)return idxs1376 ms 30 MB Python3 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
