首页 > 其他分享 >力扣---2155. 分组得分最高的所有下标

力扣---2155. 分组得分最高的所有下标

时间:2023-02-10 21:55:40浏览次数:49  
标签:力扣 下标 nums int --- 2155 numsright numsleft 数组

给你一个下标从 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 <= 105
    nums[i] 为 0 或 1

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/all-divisions-with-the-highest-score-of-a-binary-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

一开始想要只遍历一遍解决,结果没想出来,优化了一下遍历三遍的思路,遍历两遍解决。

第一遍遍历求出每个位置左边数组对应下标的值。而右边数组最大值可以通过nums数组的长度减去最后一个下标处左边数组和来得出(nums数组不是0就是1,右数组理论上的最大值就是数组长度,减去0的数量自然就是右数组的最大值)。

接下来再次遍历一遍nums数组,每遇到一次1,right--,维护一个max值,如果当前左数组加右数组值的和大于max,则更新max并将此处下标存入res,若等于max,则直接存入res。

class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int[] left = new int[nums.length];
        left[0] = nums[0] == 0 ? 1 : 0;
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] == 0) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = left[i - 1];
            }
        }
        List<Integer> res = new ArrayList<>();
        res.add(0);
        int right = nums.length - left[nums.length - 1];
        int max = right;
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] == 1) {
                right --;
            }
            int tem = left[i] + right;
            if (tem == max) {
                res.add(i + 1);
            } else if (tem > max) {
                max = tem;
                res = new ArrayList<>();
                res.add(i + 1);
            }
        }
        return res;
    }
}

 

 再看一眼官解,用了前缀和,只需要遍历一次,厉害。

官解没有java代码,把c++代码抄过来改一改就行。

class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int n = nums.length;
        // best 为历史最大值
        int presum = 0, best = 0;
        // ans 为历史最大值的下标
        List<Integer> ans = new ArrayList<>();
        ans.add(0);
        for (int i = 0; i < n; i ++) {
            if (nums[i] == 0) {
                presum ++;
                if (presum > best) {
                    best = presum;
                    ans = new ArrayList<>();
                    ans.add(i + 1);
                }
                else if (presum == best) {
                    ans.add(i + 1);
                }
            }
            else {
                presum --;
            }
        }
        return ans;
    }
};

 

标签:力扣,下标,nums,int,---,2155,numsright,numsleft,数组
From: https://www.cnblogs.com/allWu/p/17110373.html

相关文章

  • 关于Java基础-第四天的复习总结
    1.数组1.1什么是数组【理解】数组就是存储数据长度固定的容器,存储多个数据的数据类型要一致。1.2数组定义格式【记忆】1.2.1第一种数据类型[]数组名示例:int[]......
  • 关于Java基础-第五天的复习笔记
    1.方法概述1.1方法的概念(理解)方法(method)是将具有独立功能的代码块组织成为一个整体,使其具有特殊功能的代码集注意:方法必须先创建才可以使用,该过程成为方法定义......
  • 2023-02-10 java方法快速入门
    1.java方法快速入门使用点击查看代码publicclassmethodone{publicstaticvoidmain(String[]args){Personone=newPerson();one.speak......
  • kx00016-顺序表--用C语言实现:多种方法合并2个非递减顺序表
    一、顺序表结构定义#defineINIT_SIZE10 //顺序表初始容量typedefvoid(myOpFunType)(void*); //定义操作函数类型typedefintseqType; //定义顺序表元素类型......
  • 关于Java基础复习-第二天的总结笔记
    0、类型转换问题类型转换(理解)在Java中,会存在不同类型的数据需要一起参与运算,所以这些数据类型之间是需要相互转换的,分为两种情况:自动类型转换和强制类型转换。自动类型......
  • 搜索清空时el-date-picker报错问题
    change回调函数加个参数,清空时参数会是null,v-model的数据也是null,把v-model的数据设置为空数据,不在报错。<divclass="block"><el-date-pickerv-mode......
  • Dev-C++ 安装教程
    下载地址:https://sourceforge.net/projects/orwelldevcpp/下载完成,在指定的下载位置有一个安装包:双击开始安装程序安装是默认英文安装即可,在启动后可以配置为简体......
  • MySQL - B+树
    B+树一个m阶的B+树具有如下几个特征:有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。所有的叶子结点中包含......
  • 项目管理-任务分解
    一、为什么要任务分解1、情景在做项目过程中,经常出现下面几种情况:(1)研发说:“由于我当初写开发方案时没想到这个地方这么复杂(或者这里隐藏了很多需要开发的......
  • Jedis-连接池,连接池工具类
    Jedis-连接池jedis连接池:JedisPool/***jedis连接池使用*/@Testpublicvoidtest7(){//0.创建一个配置对象JedisPoolConfig......