华为OD题目： 新员工座位安排系统_华为新员工座位系统

新员工座位安排系统

知识点数组统计 哈希表 左右数组
时间限制: 1s 空间限制: 256MB 限定语言: 不限

题目描述:
工位由序列F1,F2…Fn组成，Fi值为0、1或2。其中0代表空置，1代表有人，2代表障碍物.
1、某一空位的友好度为左右连续老员工数之和
2、为方便新员工学习求助，优先安排友好度高的空位给出工位序列，求所有空位中友好度的最大值.

输入描述:
第一行为工位序列: F1.F2…Fn组成，1<=n<=100000，Fi值为0、1或2。其中0代表空置，1代码有人，2代表障碍物其中0代表空置，1代码有人，2代表障碍物。
输出描述:
所有空位中友好度的最大值。如果没有空位，返回0

示例1
输入:
0 1 0
输出:
1

说明:
第1个位置和第3个位置，友好度均为1

示例2
输入:
1 1 0 1 2 1 0
输出:
3

说明:
第3个位置友好度为3。因障碍物隔断，左边得2分，右边只能得1分

解题思路:

• 直接正向遍历一遍，反向遍历一遍，遇到0，就把连续1的值记录下来,
• 用两个map存放，key是0的下标，value是连续1的个数，
• 将正向和反向map，对应的0，左右加起来取最大值

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strings = str.split(" ");

        Map<Integer, Integer> leftToRight = new HashMap<>();
        Map<Integer, Integer> rightToLeft = new HashMap<>();
        //正向遍历,只要num是1，sum就+1，只要不是1，sum则置为0
        int sum = 0;
        for (int i = 0; i < strings.length; i++) {
            int num = Integer.parseInt(strings[i]);
            if (num == 1) {
                sum++;
            } else if (num == 0) {
                leftToRight.put(i, sum);
                sum = 0;
            }else {
                sum = 0;
            }
        }

        sum = 0;
        //反向遍历，从右往左
        for (int i = strings.length - 1; i >= 0; i--) {
            int num = Integer.parseInt(strings[i]);
            if (num == 1) {
                sum++;
            } else if (num == 0) {
                rightToLeft.put(i, sum);
                sum = 0;
            }else {
                sum = 0;
            }
        }

        int max = 0;
        for (int key : leftToRight.keySet()) {
            int val = leftToRight.get(key) + rightToLeft.get(key);
            max = Math.max(val, max);
        }
        System.out.println(max);

    }
}
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
42
43
44
45
46