2017小米校园招聘笔试题

句子反转
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定一个句子（只包含字母和空格）， 将句子中的单词位置反转，单词用空格分割, 单词之间只有一个空格，前后没有空格。
比如：
（1） “hello xiao mi”-> “mi xiao hello”
输入
输入数据有多组，每组占一行，包含一个句子(句子长度小于1000个字符)
输出
对于每个测试示例，要求输出句子中单词反转后形成的句子

样例输入
hello xiao mi
样例输出
mi xiao hello

import java.util.Scanner;

public class Main {

    public static void main(String[] arg) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String str = scan.nextLine();
            String[] ss = str.split(" ");
            for (int i = str.length() - 1; i >= 0; i--) {
                System.out.println(ss[i]);
            }
        }
        scan.close();
    }

}

2、

树的高度
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度
输入
输入的第一行表示节点的个数n（1<=n<=1000，节点的编号为0到n-1）组成，
下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号
输出
输出树的高度，为一个整数

样例输入
5
0 1
0 2
1 3
1 4
样例输出
3

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int maxDepth;

    private static void init(int[][] matrix,int n) {
        for (int i = 0; i < n; i++) {
            matrix[i][0] = -1;
            matrix[i][1] = -1;
        }
    }

    public static void main(String[] arg) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            maxDepth = 0;
            int n = scan.nextInt();
            int[][] matrix = new int[n][2];
            init(matrix,n);
            int[] fathers = new int[n];
            Arrays.fill(fathers,-1);
            for (int i = 0,s = n - 1; i < s; i++) {
                int x = scan.nextInt();
                int y = scan.nextInt();
                if (matrix[x][0] == -1) {
                    matrix[x][0] = y;
                }else {
                    matrix[x][1] = y;
                }
                fathers[y] = x;
            }
            int root = -1;
            for (int i = 0; i < n; i++) {
                if (fathers[i] == -1) {
                    root = i;
                }
            }
            dfs(matrix,root,1);
            System.out.println(maxDepth);
        }
        scan.close();
    }

    private static void dfs(int[][] matrix,int father,int depth) {
        if (matrix[father][0] == -1 && matrix[father][1] == -1) {
            maxDepth = Math.max(maxDepth,depth);
            //System.out.println(depth);
            return;
       }
        for (int i = 0; i < 2; i++) {
            if (matrix[father][i] != - 1) {
                dfs(matrix,matrix[father][i],depth +1);
            }
        }
    }

}

3、

电话号码分身
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
继MIUI8推出手机分身功能之后，MIUI9计划推出一个电话号码分身的功能：首先将电话号码中的每个数字加上8取个位，然后使用对应的大写字母代替
（”ZERO”, “ONE”, “TWO”, “THREE”, “FOUR”,
“FIVE”, “SIX”, “SEVEN”, “EIGHT”, “NINE”），
然后随机打乱这些字母，所生成的字符串即为电话号码对应的分身。
输入
第一行是一个整数T（1<=T<=100)表示测试样例数；接下来T行，每行给定一个分身后的电话号码的分身（长度在3到10000之间）。
输出
输出T行，分别对应输入中每行字符串对应的分身前的最小电话号码（允许前导0）。

样例输入
4
EIGHT
ZEROTWOONE
OHWETENRTEO
OHEWTIEGTHENRTEO
样例输出
0
234
345
0345

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static char[] numbers = {
            '2', '3', '4', '5', '6', '7', '8', '9', '0', '1'
    };

    public static void main(String[] arg) {
        Scanner scan = new Scanner(System.in);
        String t = scan.nextLine();
        int test = Integer.parseInt(t);
        while (test > 0) {
            --test;
            String str = scan.nextLine();
            char[] telephone = solve(str);
            System.out.println(telephone);
        }
        scan.close();
    }

    private static char[] solve(String str) {
        int len = str.length();
        int[] letters = new int[126];
        for (int i = 0; i < len; i++) {
            ++letters[str.charAt(i)];
        }
        int[] num = new int[10];
        num[0] = letters['Z'];
        num[2] = letters['W'];
        num[4] = letters['U'];
        num[6] = letters['X'];
        num[8] = letters['G'];
        num[3] = letters['H'] - num[8];
        num[5] = letters['F'] - num[4];
        num[7] = letters['S'] - num[6];
        num[1] = letters['O'] - num[0] - num[2] - num[4];
        num[9] = letters['I'] - num[5] - num[6] - num[8];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            while (num[i] > 0) {
                sb.append(numbers[i]);
                --num[i];
            }
        }
        String telephone = sb.toString();
        char[] arr = telephone.toCharArray();
        Arrays.sort(arr);
        return arr;
    }
}