华为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;
    }
}