【华为OD题库-051】不开心的小朋友-java

本文主要是介绍【华为OD题库-051】不开心的小朋友-java，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

游乐场里增加了一批摇摇车，非常受小朋友欢迎，但是每辆摇摇车同时只能有一个小朋友使用，如果没有空余的摇摇车，需要排队等候，或者直接离开，最后没有玩上的小朋友会非常不开心。
请根据今天小朋友的来去情况，统计不开心的小朋友数量
1.摇摇车数量为N，范围是:1<=N<10;
2每个小朋友都对应一个编码，编码是不重复的数字，今天小朋友的来去情况，可以使用编码表示为:1 1 2 3 2 3。(若小朋友离去之前有空闲的摇摇车，则代表玩耍后离开;不考虑小朋友多次玩的情况)。小朋友数量≤100
3.题目保证所有输入数据无异常且范围满足上述说明
输入描述
第一行:摇摇车数量
第二行:小朋友来去情况
输出描述
返回不开心的小朋友数量
示例1:
输入
1
1 2 1 2
输出
0
说明
第一行，1个摇摇车
第二行，1号来2号来(排队)1号走2号走(1号走后摇摇车已有空闲，所以玩后离开)
示例2:
输入
1
1 2 2 3 1 3
输出
1
说明
第一行，1个摇摇车
第二行，1号来2号来(排队)2号走(不开心离开)3号来(排队)1号走3号走(1号走后摇摇车已有空闲，所以玩后离开)

思路

使用states数组记录各小朋友的状态：0代表初始状态，1代表坐过，2代表排队中
使用queue记录排队中的小朋友
将摇摇车数量记为n，小朋友来去情况记录为nums数组
遍历nums：

如果states[nums[i]-1]为0，代表这个小朋友刚来：

此时判断，n的数量是否大于0，如果大于0，可以直接坐车，即states[nums[i]-1]=1
否则，该小朋友只能排队，即：states[nums[i]-1]=2，queue中加入该小朋友

如果states[nums[i]-1]==2，说明该小朋友在排队中，此时离开，代表没坐到摇摇车，小朋友不开心离队，结果res+1，queue移出该小朋友
如果states[nums[i]-1]==1，说明该小朋友已经坐过，此时离开，需要安排queue中下一个排队的小朋友来坐车，如果此时queue为空，那么就出现了空余摇摇车，此时n需要+1。

此案例了解到：对于LinkedList实现的对列，如果移出了中间元素，那么它还是遵循先入先出的原则的。

题解

package hwod;import java.util.*;public class LittleFriend {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();System.out.println(littleFriend(nums, n));}private static int littleFriend(int[] nums, int n) {int[] states = new int[nums.length / 2];//标记坐过还是没有坐过，1坐过，0刚来,2：排队中Queue<Integer> queue = new LinkedList<>();int res = 0;for (int i = 0; i < nums.length; i++) {if (states[nums[i] - 1] == 0) {//刚来if (n > 0) {n--;states[nums[i] - 1] = 1;} else {queue.add(nums[i]);states[nums[i] - 1] = 2;}} else if (states[nums[i] - 1] == 2) {//排队时直接离开，说明没坐到queue.remove(nums[i]);res++;} else {//坐过后离开，下一个排队的小朋友来坐车if (!queue.isEmpty()) states[queue.poll() - 1] = 1;else n++;}}return res;}}