华为OD机试 - 消消乐能量碰撞（Python/JS/C/C++ 新系统 100分）

华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述在一个充满魔法能量的消除游戏中一排排不同颜色的能量球代表不同质量/能量值静止在网格中。当玩家触发消除机制时相邻的能量球会发生相互碰撞。消除规则碰撞机制当两个相邻的能量球相遇时系统会根据它们的能量值质量进行判断。强弱判定如果两个能量球的能量值不同能量值较低的那个球会被对手的能量波吞噬从而消除。同归于尽如果两个能量球的能量值完全相同它们会引发剧烈的能量湮灭反应导致两者同时被消除。幸存条件只有能量值足够高且未发生碰撞或碰撞后存活的能量球才能留在场上继续等待下一轮消除。题目目标给定一排初始的能量球序列请模拟上述消除过程找出最终留在场上的所有能量球及其顺序。约束能量球的个数不超过 1000 个能量球的能量值是非负整数最大不超过 10000二、输入描述输入为一行字符串格式为n a1,a2,a3,...,an其中 n 表示能量球的数量方括号内为初始能量球序列的数值列表。三、输出描述输出最终留在场上的所有能量球序列以数组形式表示格式为 b1,b2,…,bm。四、测试用例测试用例11、输入53,5,5,2,32、输出33、说明3 留下5 3留下 55 5两个都消除2 留下3 2最终留下 3测试用例21、输入61,2,2,1,3,42、输出43、说明12 1 → 22 2 → 全部消失13 1 → 34 3 → 4最终输出 4。五、解题思路处理每个新能量球 current 时只需要关心当前场上是否存在一个幸存球 survivor当前没有幸存球current 直接留下。current survivor两个球同时消除场上为空。current survivor原幸存球被消除current 成为新幸存球。current survivor新球被消除原幸存球继续存在。为什么只保存一个变量就够因为每次新球与当前幸存球碰撞后结果只可能是留下其中一个两个都消失。因此任意时刻场上最多只有一个有效幸存球没有必要使用栈、队列或数组保存中间状态。六、Python算法源码importsysdefmain():linessys.stdin.read().splitlines()nint(lines[0].strip())linelines[1].strip()iflen(lines)1elsehas_survivorFalsesurvivor0ifn0andline:numsline.split(,)foriinrange(n):currentint(nums[i].strip())ifnothas_survivor:# 当前没有幸存球# 新球直接成为当前幸存球。survivorcurrent has_survivorTrueelifcurrentsurvivor:# 两个能量球数值相同# 两者同时消除场上重新为空。has_survivorFalseelifcurrentsurvivor:# 新球能量更高# 原幸存球被消除新球成为新的幸存球。survivorcurrent# current survivor 时# 新球被原幸存球消除因此不需要修改 survivor。ifhas_survivor:print(survivor)else:print()if__name____main__:main()七、JavaScript算法源码constfsrequire(fs);constinputfs.readFileSync(0,utf8).split(/\r?\n/);constnNumber((input[0]||).trim());constline(input[1]||).trim();lethasSurvivorfalse;letsurvivor0;if(n0line.length0){constnumsline.split(,);for(leti0;in;i){constcurrentNumber(nums[i].trim());if(!hasSurvivor){// 当前没有幸存球// 新进入的球直接成为当前幸存球。survivorcurrent;hasSurvivortrue;}elseif(currentsurvivor){// 能量值完全相同// 两个球同时消除。hasSurvivorfalse;}elseif(currentsurvivor){// 新球能量更高// 原幸存球被消除新球成为幸存球。survivorcurrent;}// current survivor 时// 新球被消除原 survivor 不变。}}console.log(hasSurvivor?survivor:);八、C算法源码#includestdio.h#includestdlib.h#includestring.hintmain(void){intn;if(scanf(%d,n)!1){return0;}/* * 清理读取 n 之后直到当前行末尾的字符 * 防止下面的 fgets 直接读到残留的换行符。 */intch;while((chgetchar())!\nch!EOF){}/* * n 最大为 1000每个数最大 10000 * 加上逗号后 12000 字符空间已经足够。 */charline[12000];if(fgets(line,sizeof(line),stdin)NULL){line[0]\0;}inthasSurvivor0;intsurvivor0;/* * strtok 按照逗号切分输入数据。 * 同时把 \\r 和 \\n 作为分隔符 * 兼容不同系统的换行格式。 */char*tokenstrtok(line,,\r\n);for(inti0;intoken!NULL;i){intcurrentatoi(token);if(!hasSurvivor){// 当前没有幸存球新球直接留下。survivorcurrent;hasSurvivor1;}elseif(currentsurvivor){// 两球能量相同同归于尽。hasSurvivor0;}elseif(currentsurvivor){// 新球更强消除原幸存球// 新球成为新的幸存球。survivorcurrent;}/* * current survivor 时 * 新球被消除因此 survivor 保持不变。 */tokenstrtok(NULL,,\r\n);}if(hasSurvivor){printf(%d\n,survivor);}else{printf(\n);}return0;}九、C算法源码#includeiostream#includesstream#includestring#includelimitsusingnamespacestd;intmain(){intn;cinn;// 清除读取 n 后剩余的换行内容// 防止 getline 直接读到一个空字符串。cin.ignore(numeric_limitsstreamsize::max(),\n);string line;getline(cin,line);stringstreamss(line);boolhasSurvivorfalse;intsurvivor0;for(inti0;in;i){string token;// 每次读取一个以逗号分隔的能量值。getline(ss,token,,);intcurrentstoi(token);if(!hasSurvivor){// 当前没有幸存球// 新球直接成为当前幸存球。survivorcurrent;hasSurvivortrue;}elseif(currentsurvivor){// 能量相同两球同时消除。hasSurvivorfalse;}elseif(currentsurvivor){// 新球更强// 原幸存球被消除新球成为新的幸存球。survivorcurrent;}// current survivor 时// 新球被消除原 survivor 不发生变化。}if(hasSurvivor){coutsurvivor\n;}else{cout\n;}return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。