全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/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表示（不影响计数）
如例二：
1 1 0 1 2 1 0
处理一下：2 0 1 -1 1 0
遍历新的集合：
碰到0的时候进行处理：
1、如果0在开头，则判断后面是否为-1，如不是-1，则后面的数就是这个座位的友好度；
2、如果0在最后，则判断前面的是否为-1，如不是-1，则前面的数就是这个座位的好友度；
3、如果0在中间位置，则判断其前后位置是否为-1，如是-1，则作为0个处置；前后数的和就是这个位置的好友度；
考虑到只有一个座位时，最大好友度直接为0
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @title 新员工座位安排系统
* @Description 工位由序列F1, F2...Fn组成，Fi值为0、1或2。其中0代表空置，1代表有人，2代表障碍物。
* 1、某一空位的友好度为左右连续老员工数之和
* 2、为方便新员工学习求助，优先安排友好度高的空位
* 给出工位序列，求所有空位中友好度的最大值。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strings = sc.nextLine().split(" ");
List<Integer> list = new ArrayList<>();
int count = 0; //记录老员工的数量
for (int i = 0; i < strings.length; i++) {
if (strings[i].equals("1")) {
count++;
if (i == strings.length - 1) {
list.add(count); //添加老员工的数量
}
} else if (strings[i].equals("0")) {
if (count != 0) {
list.add(count); //添加老员工的数量
count = 0;
}
list.add(0); //空座位还是0
} else {
if (count != 0) {
list.add(count); //添加老员工的数量
count = 0;
}
list.add(-1); //2记做-1
}
}
int max = 0;
if (list.size() != 1) { //只有一个
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 0) {
int nums = 0;
if (i == 0) { //空座位在第一个
if (list.get(i + 1) != -1) { //空座位右侧不是障碍物
nums = list.get(i + 1);
}
} else if (i == list.size() - 1) { //空座位在最后一个
if (list.get(i - 1) != -1) { //空座位左侧不是障碍物
nums = list.get(i - 1);
}
} else {
if (list.get(i - 1) != -1) { //空座位左侧不是障碍物
nums += list.get(i - 1);
}
if (list.get(i + 1) != -1) { //空座位右侧不是障碍物
nums += list.get(i + 1);
}
}
max = Math.max(max, nums);
}
}
}
System.out.println(max);
}
}
代码实现二：
package com.codernav.demo.hwod.exam;
import java.util.Scanner;
/**
* @title 新员工座位安排系统
* @Description 工位由序列F1, F2...Fn组成，Fi值为0、1或2。其中0代表空置，1代表有人，2代表障碍物。
* 1、某一空位的友好度为左右连续老员工数之和
* 2、为方便新员工学习求助，优先安排友好度高的空位
* 给出工位序列，求所有空位中友好度的最大值。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static void main(String[] args) {
int max = 0, left = 0, right = 0;
Scanner sc = new Scanner(System.in);
String[] xu = sc.nextLine().split(" ");
for (int i = 0; i < xu.length; i++) {
if (xu[i].equals("1")) {
left++;
} else if (xu[i].equals("2")) {
left = 0;
} else if (xu[i].equals("0")) {
for (int j = i + 1; j < xu.length; j++) {
if (xu[j].equals("1")) {
right++;
} else if (xu[j].equals("0") || xu[j].equals("2")) {
break;
}
}
if (max < left + right) {
max = left + right;
}
right = 0;
left = 0;
}
}
System.out.println(max);
}
}
相关文章
