华为校招 - 通用软开 8月12日 笔试

我觉得这场笔试相对基础， 可能我抽题的运气比较好？记录一下供大家参考。
（看了8月5日的笔试题， 听说特坑，各种用例错误）

可，最后一题还是只通过了 75% 的 case，纠结四五十分钟也每天调出来，唉
ps ： 不要纠结代码效率， 笔试我怎么写顺手就怎么写了，主要因为菜。

一、找零钱

题目 ：

你是咖啡店店员卖咖啡 5块一杯。顾客排队买咖啡， 初始手里没零钱，判断你能否找零。钱的面值只有 5、10、20 三种。

输入 ：
5，5，5, 10

用户持币买咖啡的 ，金额队列。

输出 ：
true,4

全部能找零成功就返回 true 和 最后是第几号顾客。

不能找零成功，则返回 false，不能找零成功的顾客编号。

思路 ：
hashmap 使用， 特点就是麻烦！题干不好懂， 华为笔试通病……

package Huawei;

import Utils.PrintUtil;

import java.util.*;

public class Main1 {
    /**
     * A-Z 65-90 a-z 97-122 0-1 48-57
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String[] input = in.nextLine().split(",");
            int[] data = new int[input.length];
            for (int i = 0; i < input.length; i++) {
                data[i] = Integer.valueOf(input[i]);
            }

            HashMap<Integer,Integer> m = new HashMap<>();
            m.put(5,0);
            m.put(10,0);
            m.put(20,0);

            int index = 1;
            boolean b = true;
            for (int i = 0; i < data.length; i++) {
                int cur = data[i];
//                int total
                if ( cur == 5){
                    index++;
                    m.put(5,m.get(5) + 1);
                }else if (cur == 10){
                    if (m.get(5) > 0){
                        m.put(5, m.get(5) - 1);
                        m.put(10, m.get(10) + 1);
                        index++;
                    }else {
                        System.out.println("false," + index);
                        b = false;
                        break;
                    }
                }else if (cur == 20){
                    if (m.get(5) >= 3){
                        m.put(5,m.get(5)-3);
                        m.put(20,m.get(20)+1);
                        index++;
                        continue;
                    }else if (m.get(5) > 0 && m.get(10)>0){
                        m.put(5,m.get(5)-1);
                        m.put(10,m.get(10)-1);
                        m.put(20,m.get(20)+1);
                        index++;
                        continue;
                    }else {
                        System.out.println("false," + index);
                        b = false;
                        break;
                    }
                }else {
                    System.out.println("false," + index);
                    b = false;
                    break;
                }
            }
            if (b) System.out.println("true,"+ --index);
        }
    }

}

二、迷宫问题

题目 ：
（又给了一对情景， balabala）

本质是 ， 走迷宫，这次是 矩阵值为 1 的能走， 每次走的步数提前约定好（可变）。

输入：
2
3 5
1 0 1 1 1
0 0 1 0 1
1 0 1 0 1

第一行步长，剩下的是矩阵参数

输出：
true

思路 ：
经典回溯

package Huawei;

import java.util.*;


public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            int step = Integer.valueOf(in.nextLine());
            String[] line2 = in.nextLine().split(" ");
            int m = Integer.valueOf(line2[0]);
            int n = Integer.valueOf(line2[1]);
            int[][] matrix = new int[m][n];
            int[][] path = new int[m][n];

            for (int i = 0; i < m; i++) {
                String[] tempLine = in.nextLine().split(" ");
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = Integer.valueOf(tempLine[j]);
                }
            }

            int res = process(matrix,path,0,0,step)?1:0;
            System.out.println(res);
        }
    }

    private static boolean process(int[][] matrix, int[][] path, int x, int y , int step){

        if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length
        || matrix[x][y] == 0 || path[x][y] == 1) return false;

        if (x == matrix.length - 1 && y == matrix[0].length - 1) return true;

        path[x][y] = 1;

        if (process(matrix,path,x + step, y,step)
        ||process(matrix,path,x,y + step,step)
        ||process(matrix,path,x - step, y,step)
        ||process(matrix,path,x, y - step,step)
        ){
            return true;
        }else {
            path[x][y] = 0;
            return false;
        }
    }
}

三、X型输出字符串

题目 ：
（又又又又很晦涩，没见过， 也是自己刷题少…）
给一个字符串 s ，一个行宽 n 。 按 x型 把字符串排列好，再纵向遍历打印出来。。。

太绕了 举个例子：

输入：
abcdefg，3

过程 ：空格我暂用#
[a # b]
[# c #]
[d # e]
[# f #]
[g # #]

输出：
adgcfbe

大概是这个意思吧。
对了 ， 题目保证输入数据正确性

思路：
没啥思路。。所以，我硬生生把矩阵的高算出来了，用分组分块的方式……没眼看

（还没想清楚 25%的case 是啥情况）

package Huawei;

import Utils.PrintUtil;

import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String[] line = in.nextLine().split(",");
            String str = line[0];
            int n = Integer.valueOf(line[1]);

            // 计算矩阵高度 m
            int l = str.length();
            int i = l/(2*n - 3);
            int left = l%(2*n - 3);
            if (left >= n) i++;
            if (left%2 == 1) i++;
            int m = (l + i) / 2;

            //System.out.println(m);
            char[][] matrix = new char[m][n];
            int cur = 0;
            int strIndex = 0;
            for (int j = 0; j < m; j++) {

                for (int k = 0; k < n; k++) {
                    if ((k == cur || k == n-1-cur) && strIndex < l){
                        matrix[j][k] = str.charAt(strIndex++);
                    }
                }
                if (cur == n - 1){
                    cur = 1;
                }else {
                    cur++;
                }
            }
            //PrintUtil.printMatrix(matrix);
            String res = "";

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (matrix[k][j] != matrix[0][1]){
                        res += matrix[k][j];
                    }
                }
            }
            System.out.println(res);
        }
    }
}