华为5.6笔试思路 | 通过92%+25%+25%=217分
Java选手，感觉第三题又被卡IO了。因为心态很崩，所以【代码写的很乱很不优雅】，所以先说思路供讨论，代码统一放在本文最后。
第一题，通过92%：把二进制字符串还原出来，然后遍历每个0的位置，记录该0和每个1的位置差，作为一个集合。把这些集合取交集，然后取出里面最小的正数（如果有）和最大的负数（如果有）就行了。特殊情况：字符串全1或最终的交集中存在0。
第二题，通过25%（我感觉我思路对的但很多用例没通过）：自定义字符串加法。先在两个字符串前后补0，保证小数点是对齐的，然后定义竖式运算。最后得到的结果进行一些处理，如果不是以"0."开头则去掉开头的0，如果有小数点就去掉一些结尾的0，如果全去掉了那就把小数点也去掉。
第三题，通过25%（说超出CPU了，应该是卡IO？我用了Java快读都不行）：一个我认为非常简单的广度优先搜索，类似树的层序遍历。图的本质是某些点在全部时间有障碍，某些点在某些时间有障碍。维护遍历的轮次（类似二叉树的层数），然后用队列遍历即可。这里每个格子接下来可以走的点是【上下左右及自身，这5个点中在该轮次%3的时间点无障碍的】。如果遍历到终点就返回该轮轮次就行。可惜只过了25%。
眼眶写的夸夸疼，摆了
代码附录：
第一题
package test1else;
import java.util.*;
public class Main {
private static Map<Character, String> hexDigit = new HashMap<Character, String>() {{
put('0', "0000");
put('1', "0001");
put('2', "0010");
put('3', "0011");
put('4', "0100");
put('5', "0101");
put('6', "0110");
put('7', "0111");
put('8', "1000");
put('9', "1001");
put('A', "1010");
put('B', "1011");
put('C', "1100");
put('D', "1101");
put('E', "1110");
put('F', "1111");
}};
private static String getRes(int n, List<String> hexs) {
StringBuilder tmpValue = new StringBuilder();
for (String hex : hexs) for (int i = 2; i < hex.length(); ++i) tmpValue.append(hexDigit.get(hex.charAt(i)));
String value = tmpValue.substring(0, n);
List<String> output = new ArrayList<>();
if (isAllOne(value)) output.add("0");
else {
int resCnt = 0;
List<Integer> zeroIndex = new ArrayList<>();
for (int i = 0; i < n; ++i) if (value.charAt(i) == '0') zeroIndex.add(i);
Set<Integer> res = new TreeSet<>();
Map<Integer, Set<Integer>> ab = new HashMap<>();
for (int i = -n + 1; i <= n - 1; ++i) res.add(i);
for (int idx : zeroIndex) {
Set<Integer> tmp = new TreeSet<>();
for (int i = 0; i < n; ++i) {
if (value.charAt(i) == '1') {
tmp.add(idx - i);
if (!ab.containsKey(idx - i)) ab.put(idx - i, new TreeSet<>());
ab.get(idx - i).add(i);
}
}
res.retainAll(tmp);
}
if (res.contains(0)) output.add("0");
else {
for (int i = 1; i < n; ++i) {
if (res.contains(i)) {
++resCnt;
output.add("+" + i);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; ++j) sb.append(ab.get(i).contains(j) ? '1' : '0');
output.add(sb.toString());
break;
}
}
for (int i = -1; i >= -n + 1; --i) {
if (res.contains(i)) {
++resCnt;
output.add(Integer.toString(i));
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; ++j) sb.append(ab.get(i).contains(j) ? '1' : '0');
output.add(sb.toString());
break;
}
}
output.add(0, Integer.toString(resCnt));
}
}
return String.join("\n", output);
}
private static boolean isAllOne(String s) {
for (int i = 0; i < s.length(); ++i) if (s.charAt(i) == '0') return false;
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), tmp = n;
List<String> hexs = new ArrayList<>();
while (tmp > 0) {
hexs.add(in.next());
tmp -= 16;
}
System.out.println(getRes(n, hexs));
}
}
第二题
import java.util.*;
public class Main {
private static Map<Character, Map<Character, Integer>> sign = new HashMap<Character, Map<Character, Integer>>() {{
put('!', new HashMap<Character, Integer>() {
{
put('!', 0);
put('@', 13);
put('#', 4);
}
});
put('@', new HashMap<Character, Integer>() {
{
put('!', 13);
put('@', 7);
put('#', 20);
}
});
put('#', new HashMap<Character, Integer>() {
{
put('!', 4);
put('@', 20);
put('#', 5);
}
});
}};
private static String getRes(int n, String str) {
String[] parts = str.split("\\+");
StringBuilder sb0 = new StringBuilder().append(parts[0]), sb1 = new StringBuilder().append(parts[1]);
if (!parts[0].contains(".")) sb0.append(".0");
if (!parts[1].contains(".")) sb1.append(".0");
int p0 = sb0.indexOf("."), p1 = sb1.indexOf(".");
int r0 = sb0.length() - p0, r1 = sb1.length() - p1;
for (int i = 0; i < Math.max(r0, r1) - r0; ++i) sb0.append('0');
for (int i = 0; i < Math.max(r0, r1) - r1; ++i) sb1.append('0');
while (sb0.length() < sb1.length()) sb0.insert(0, '0');
while (sb1.length() < sb0.length()) sb1.insert(0, '0');
int jw = 0;
StringBuilder res = new StringBuilder();
for (int i = sb0.length() - 1; i >= 0; --i) {
char ch0 = sb0.charAt(i), ch1 = sb1.charAt(i);
if (ch0 == '.') res.insert(0, '.');
else {
int t;
if (ch0 >= '0' && ch0 <= '9') t = ch0 - '0' + ch1 - '0' + jw;
else t = sign.get(ch0).get(ch1);
res.insert(0, t % 10);
jw = t / 10;
}
}
if (jw != 0) res.insert(0, jw);
if (!res.toString().startsWith("0.")) while (res.charAt(0) == '0') res.replace(0, 1, "");
if (res.toString().contains(".")) {
while (res.charAt(res.length() - 1) == '0') res.replace(res.length() - 1, res.length(), "");
if (res.charAt(res.length() - 1) == '.') res.replace(res.length() - 1, res.length(), "");
}
return res.toString();
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String str = in.next();
System.out.println(getRes(n, str));
}
}
第三题
import java.io.*;
import java.util.*;
public class Main {
private static int getRes(int n, int[][] G, int[] start, int[] end, String[][] nones) {
if (eq(start, end)) return 0;
Queue<int[]> Q = new LinkedList<>();
Q.add(start);
int tune = 0;
while (!Q.isEmpty()) {
int cnt = Q.size();
++tune;
while (cnt-- > 0) {
int[] t = Q.poll();
if (eq(t, end)) return tune - 1;
List<int[]> neis = new ArrayList<int[]>() {{
add(new int[]{t[0], t[1]});
add(new int[]{t[0] - 1, t[1]});
add(new int[]{t[0] + 1, t[1]});
add(new int[]{t[0], t[1] - 1});
add(new int[]{t[0], t[1] + 1});
}};
for (int[] nei : neis) {
if (nei[0] < 0 || nei[0] >= n || nei[1] < 0 || nei[1] >= n) continue;
if (G[nei[0]][nei[1]] == 1) continue;
if (nones[nei[0]][nei[1]].charAt(tune % 3) == '1') continue;
Q.add(nei);
}
}
}
return -1;
}
private static boolean eq(int[] a, int[] b) {
return a[0] == b[0] && a[1] == b[1];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(br);
PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
int n = getInt(st), k = getInt(st);
int[][] G = new int[n][n];
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) G[i][j] = 0;
for (int i = 0; i < k; ++i) G[getInt(st)][getInt(st)] = 1;
int[] end = getIndex(st), start = getIndex(st);
String[][] nones = new String[n][n];
for (int i = 0; i < n; ++i) {
String str = br.readLine();
String[] tmp = str.split(" ");
System.arraycopy(tmp, 0, nones[i], 0, n);
}
pw.println(getRes(n, G, start, end, nones));
pw.flush();
}
private static int getInt(StreamTokenizer st) throws IOException {
st.nextToken();
return (int) st.nval;
}
private static int[] getIndex(StreamTokenizer st) throws IOException {
int[] res = new int[2];
res[0] = getInt(st);
res[1] = getInt(st);
return res;
}
}
投递字节跳动等公司6个岗位
