深圳的设计网站,谷歌浏览器下载手机版官网,西安 网站空间,wordpress 流量数据库题目部分
题目阿里巴巴找黄金宝箱#xff08;1#xff09;难度易题目说明一贫如洗的樵夫阿里巴巴在去砍柴的路上#xff0c;无意中发现了强盗集团的藏宝地#xff0c;藏宝地有编号从 0 ~ N 的箱子#xff0c;每个箱子上面贴有一个数字#xff0c;箱子中可能有一个黄金宝…题目部分
题目阿里巴巴找黄金宝箱1难度易题目说明一贫如洗的樵夫阿里巴巴在去砍柴的路上无意中发现了强盗集团的藏宝地藏宝地有编号从 0 ~ N 的箱子每个箱子上面贴有一个数字箱子中可能有一个黄金宝箱。 黄金宝箱满足排在它之前的所有箱子数字和等于排在它之后的所有箱子数字之和第一个箱子左边部分的数字和定义为0最后一个箱子右边部分的数字和定义为0。 请帮阿里巴巴找到黄金宝箱输出第一个满足条件的黄金宝箱编号如果不存在黄金宝箱请返回 -1 。输入描述箱子上贴的数字列表使用逗号分隔例如 1,-1,0。 宝箱的数量不小于 1 个不超过 10000。 宝箱上贴的数值范围不低于 -1000不超过 1000。输出描述第一个黄金宝箱的编号。补充说明无------------------------------------------------------示例示例1输入2,5,-1,8,6输出3说明下标 3 之前的数字之和为 2 5 (-1) 6。 下标 3 之后的数字之和为 6。示例2输入8,9输出-1说明不存在符合要求的位置。示例2输入11输出0说明下标 0 之前的数字之和为 0。 下标 0 之后的数字之和为 0。 解读与分析
题目解读
一组整型数字找出一个数字的下标使其左边的数字之和等于右边数字之和。如果找不到输出 -1。
分析与思路
此题思路比较简单先计算所有数字之和然后从小到大逐个遍历数字下标。在遍历过程中如果下标左边的数字之和和下标右边的数字之和相等则输出其下标。如果遍历完后仍旧找不到则输出 -1。
在遍历过程中求左右之和时只需要根据前一个下标的和计算增量即可不需要全量计算。
在计算过程中会遍历 2 次整型数字第一次求和第一次寻找符合要求的下标。时间复杂度为 O(n)空间复杂度为 O(n)。 代码实现
Java代码
import java.util.Scanner;/*** 阿里巴巴找黄金宝箱1* since 2023.10.11* version 0.1* author Frank**/
public class AlibabaFindGold1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();String[] strNumber input.split( , );processAlibabaFindGold1( strNumber );}}private static void processAlibabaFindGold1( String[] strNumber ){int sum 0;int[] numbers new int[strNumber.length];for( int i 0; i strNumber.length; i ){numbers[i] Integer.parseInt( strNumber[i] );sum numbers[i];}int leftSum 0;int rightSum sum;for( int i 0; i numbers.length; i ){if( i 1 ){leftSum numbers[ i - 1 ];} rightSum - numbers[i];if( leftSum rightSum ){System.out.println( i );return;}}System.out.println( -1 );}
} JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {var strNumber line.split(,);processAlibabaFindGold1(strNumber);}
}();function processAlibabaFindGold1(strNumber) {var sum 0;var numbers new Array( strNumber.length );for (var i 0; i strNumber.length; i) {numbers[i] parseInt(strNumber[i]);sum numbers[i];}var leftSum 0;var rightSum sum;for (var i 0; i numbers.length; i) {if (i 1) {leftSum numbers[i - 1];}rightSum - numbers[i];if (leftSum rightSum) {console.log(i);return;}}console.log(-1);
} (完)
