• 华为OD机考B卷 | 100分】阿里巴巴找黄金宝箱(JAVA题解——也许是全网最详)


    前言

    本人是算法小白,甚至也没有做过Leetcode。所以,我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。

    题干

    1. 题目描述

    一贫如洗的樵夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地,藏宝地有编号从0~N的箱子,每个箱子上面贴有一个数字,箱子中可能有一个黄金宝箱。黄金宝箱满足排在它之前的所有箱子数字和等于排在它之后的所有箱子数字和;
    1)第一个箱子左边部分的数字和定义为0:
    2)最后一个宝箱右边部分的数字和定义为0。
    请帮阿里巴巴找到黄金宝箱,输出第一个满足条件的黄金宝箱编号,如果不存在黄金宝箱,请返回-1。

    2. 输入描述

    箱子上贴的数字列表,使用逗号分隔,例如1,-1,0。
    宝箱的数量不小于1个,不超过10000
    宝箱上贴的数值范围不低于-1000,不超过1000

    3. 输出描述

    第一个黄金宝箱的编号

    4. 示例

    示例1:

    输入输出说明
    2,5,-1,8,63下标3之前的数字和为:2+5±1=6
    下标3之后的数字和为:6=6

    示例2:

    输入输出说明
    8,9-1不存在符号要求的位置

    示例3:

    输入输出说明
    110下标0之前的数字和为:0
    下标0之后的数字和为:0

    解答

    遇到的问题

    其实这个解题不难,我相信大部分人都能做到。我自己一开始的想法是,新增一个计算方法,累加指定范围的值。伪代码如下:

    int cal(int start, int end, int[] nums) {
    	int total = 0;
    	for(int i = start: start <= end; start++) {
    		total += num[i];
    	}
    	return num;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    然后从头开始循环遍历数组,然后使用上面这个方法每次累+一下,然后判断两边是否相等就好。我知道我这样虽然可以,但肯定不是最好的。接着我百度去看了别人的答案,让我突然有点醍醐灌顶的感觉(哈哈哈,其实每次看标准答案都有这种感觉)。
    但这一次,我突然有种【为什么要刷算法题】的感悟了,也许就是:打破常规思维。
    这个标准答案是:天枰法
    在这里插入图片描述

    解题思路

    1. 使用两个变量leftSumrightSum存储左值跟右值
    2. 先做一遍循环,累加所有数组中数的总和,作为右值(先把所有带有序号的石头放到天枰的左边)
    3. 然后开始第二个循环遍历,在循环中,按照如下步骤实现:
      • 右值 - 当前值(因为题干中对黄金宝箱的定义的意思,就是不包括当前值)
      • 判断右值与左值是否相等(因为题干中对黄金宝箱的定义的意思,就是不包括当前值)
      • 不相等,则左值 + 当前值(因为题干中对黄金宝箱的定义的意思,就是不包括当前值)
    4. 继续循环,直到找到或者结束位置

    考点总结

    移动指针(移动天枰)

    代码示例

    public class FindGoldChest {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String nextLine = scanner.nextLine();
            String[] split = nextLine.split(",");
            int[] goldChests = new int[nextLine.length()];
            for (int i = 0; i < split.length; i++) {
                goldChests[i] = Integer.valueOf(split[i]);
            }
    
            int goldChest = findGoldChest(goldChests);
            System.out.println(goldChest);
        }
    
     	/**
         * 寻找黄金宝箱
         *
         * @param goldChests 黄金宝箱数组
         * @return -1-没找到;其他-黄金宝箱所在下标
         */
        private static int findGoldChest(int[] goldChests) {
            int leftSum = 0;
            int rightSum = 0;
    
            // 先累加右值
            for (int goldCheste : goldChests) {
                rightSum += goldCheste;
            }
    
            for (int i = 0; i < goldChests.length; i++) {
                int goldChest = goldChests[i];
                rightSum -= goldChest;
                if (rightSum == leftSum) {
                    return i;
                }
    
                leftSum += goldChest;
            }
            return -1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
  • 相关阅读:
    当下互联网行业趋势,你顶得住吗?
    sqllibs 25-26关payload
    【十二】图解mybatis日志模块之设计模式
    【scikit-learn基础】--『分类模型评估』之系数分析
    App测试中ios和Android有哪些区别呢?
    Jenkins | 流水线构建使用expect免密交互时卡住,直接退出
    python第二节PyCharm创建项目和关联Anaconda以及设置PyCharm以及PyCharm常用快捷键
    玩转Matlab-Simscape(初级)- 10 - 基于COMSOL&Simulink 凸轮机构的控制仿真
    【斗破年番】火火小医仙幽会,彩鳞吃醋跟随,失身之事终暴露,蛇人族来算账
    vue中修改css的animation的@keyframe数值
  • 原文地址:https://blog.csdn.net/qq_32681589/article/details/133743516