记录华为面试
机试
1. 报文重排序
题目描述
对报文进行重传和重排序是常用的可靠性机制，重传缓中区内有一定数量的子报文，每个子报文在原始报文中的顺序已知，现在需要恢复出原始报文。
输入描述
输入第一行为N，表示子报文的个数，0<N≤1000。
输入第二行为N个子报文，以空格分开，子报文格式为：
字符串报文内容+后缀顺序索引
字符串报文内容由[a-z,A-Z]组成，后缀为整型值，表示顺序。 顺序值唯一，不重复。
输出描述
输出恢复出的原始报文，按照每个子报文的顺序的升序排序恢复出原始报文，顺序后缀需要从恢复出的报文中删除掉
样例
// 输入
4
rolling3 stone4 like1 a2
// 输出
like a rolling stone
说明
4个子报文的内容分别为"rolling”，"stone”，"like”，"a"，顺序值分别为3，4，1，2，按照顺序值升序并删除顺序后缀，得到恢复的原始报文:"like a rolling stone“
// 输入
8
gifts6 and7 Exchanging1 all2 precious5 thins8 kinds3 of4
// 输出
Exchanging all kinds of precious gifts and things
public class Solution3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] ss = sc.nextLine().split(" ");
HashMap<Integer, String> map = new HashMap<>();
for(int i = 0; i < ss.length; i++) {
for(int j = 0; j < ss[i].length(); j++) {
if(Character.isDigit(ss[i].charAt(j))) {
map.put(Integer.parseInt(ss[i].substring(j)), ss[i].substring(0,j));
break;
}
}
}
for(int i : map.keySet()) {
System.out.print(map.get(i) + " ");
}
}
}
}
2. 找车位
题目描述
停车场有一横排车位，0代表没有停车，1代表有车。至少停了一辆车在车位上，也至少有一个空位没有停车。
为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的距离是最大的，返回此时的最大距离。
输入描述
- 一个用半角逗号分割的停车标识字符串，停车标识为0或1，0为空位，1为已停车。
- 停车位最多100个。
// 跟我机考时的回答有出入，不能保证ak
public class Solution4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 0,0,1,1,0,1,0,0,0,0,1
while(sc.hasNext()) {
String[] ss = sc.nextLine().split(",");
int max = 0, distance = 0;
int leftZeros = 0, rightZeros = 0;
int leftFlag = 0, rightFlag = 1;
for (int i = 0; i < ss.length; i++) {
if("0".equals(ss[i])) {
distance++;
max = Math.max(max, distance);
if(leftFlag == 0) {
leftZeros++;
}
rightZeros++;
} else {
distance = 0;
leftFlag = 1;
rightZeros = 0;
}
}
// System.out.println(max + " " + leftZeros + " " + rightZeros);
System.out.println(Math.max(Math.max((max - 1) / 2, leftZeros - 1), rightZeros - 1));
}
}
}
3. 篮球比赛
题目描述
篮球（5V5）比赛中，每个球员拥有一个战斗力，每个队伍的所有球员战斗力之和为该队伍的总体战斗力。现有10个球员准备分为两队进行训练赛，教练希望2个队伍的战斗力差值能够尽可能的小，以达到最佳训练效果。给出10个球员的战斗力，如果你是教练，你该如何分队，才能达到最佳训练效果？请输出该分队方案下的最小战斗力差值。
示例1：
// 输入
10 9 8 7 6 5 4 3 2 1
1
// 输出
1
1
说明
1 2 5 9 10分为一队，3 4 6 7 8分为一队，两队战斗力之差最小，输出差值1。备注：球员分队方案不唯一，但最小战斗力差值固定是1
public class Solution5 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int[] members = new int[10];
int sum = 0;
for(int i = 0; i < 10; i++) {
members[i] = sc.nextInt();
sum += members[i];
}
int count = 5;
int res = Integer.MAX_VALUE;
res = backtrack(members, 0, count, sum, res);
System.out.println(res);
}
}
public static int backtrack(int[] members, int index, int count, int sum, int res) {
if(count == 0) {
return Math.abs(sum);
}
for(int i = index + 1; i < 10; i++) {
res = Math.min(backtrack(members, i, count - 1, sum - members[i] * 2, res), res);
}
return res;
}
}
技术面一面
一串字符串由 "1-10""A-Z" 组成，各字符之间由 "," 隔开，找到最大连续的子串。（10后面的字符是A）
示例1：
// 输入
1,2,3,4,5,7,8
// 输出
1 2 3 4 5
public class Solution {
// 主函数，处理输入输出，遍历字符串找到最大连续字串
// 通过指针移动找到连续字串，max记录下最长字串长度，left、right记录最长字串的左右边界
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String[] ss = sc.nextLine().split(",");
int index = 0;
int max = 0;
int left = 0, right = 0;
for (int i = 0; i < ss.length; i++) {
if (isSubSequence(ss, index, i)) {
if (max < i - index) {
max = i - index;
left = index;
right = i;
}
} else {
index = i;
}
}
for(int i = left; i <= right; i++) {
System.out.print(ss[i] + " ");
}
}
}
// 判断是否连续字串
public static boolean isSubSequence(String[] ss, int left, int right) {
for(int i = left; i < right; i++) {
if(!isNextValue(ss[i], ss[i + 1])) {
return false;
}
}
return true;
}
// 判断两个字符是否顺序关系
public static boolean isNextValue(String s1, String s2) {
if("10".equals(s1)) {
return "A".equals(s2);
}
if(s1.charAt(0) + 1 == s2.charAt(0)){
return true;
}
return false;
}
}
技术面一面
一队士兵排成一排，身穿绿色跟黑色衣服，如果可以随便将一个士兵移除队伍，那么求最长的连续绿色衣服的士兵队伍。
public class Solution1 {
public static void main(String[] args) {
// 模拟士兵队伍，绿色衣服记为1，黑色衣服记为0
String s = "111101110111110";
int left = 0, right = 0, len = s.length(), max = 0, count = 0, start = 0;
for(int i = 0; i < len; i++) {
if(s.charAt(i) == '0') {
count++;
}
if(count <= 1) {
if(max < i - start + 1) {
max = i - start + 1;
left = start;
right = i;
}
}
while(count > 1) {
if (s.charAt(start) == '0') {
count--;
}
start++;
}
}
int cnt = 0;
for(int i = left; i <= right; i++) {
if(s.charAt(i) == '1') {
cnt++;
}
}
System.out.println(cnt);
}
}