前言

前些日子面试了荣耀终端，面试过程是比较漫长的，但结果还是比较满意的。

目前已全部面试通过，处于等offer的阶段。

荣耀面试总共分为下面几部分：

上机心理测评（填一些心理测试题）；
上机试题；
技术一面；
技术二面；
HR面试；
综合面试。

其实上机试题完就想找时间整理下自己做的两道机试题，但苦于前面一直腾不出太多时间。

正文

好了，废话不多说，我下面直接分享下我上机实验的两道试题吧。

试题一

题目

题目大意如下：

现定义一种字符编码，编码格式为：
9个字符为一个编码组；
第一个字符表示之后8个字符的字节序，‘0’表示小端，‘1’表示大端；
编码之后按照大端排序；
例如编码组：‘012345678’，解析之后为’87654321’，‘112345678’，解析之后为’12345678’；

输入：
第一行输入字符串中编码组个数N；
第二行为字符串；
输出：
输出只有一行，包含N个编码组的解析结果，按照大端排序，每一个编码组结果以一个空格分开，行末没有空格。

样例：
输入：

2
0abcdefgh1abcdefgh

输出：

hgfedcba abcdefgh

分析

可以看到这道题主要考察字符串解析以及字符串逆序等内容。

当时在做试题的时候，写下的代码如下：

public class MyDemo1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        String b = in.next();

        boolean flag = b.startsWith("0")||b.startsWith("1");
        boolean flag1 = b.length()/9 == a;


        if(!flag||(!flag1)){
            throw new RuntimeException("参数错误");
        }
        StringBuilder stringBuilder = new StringBuilder();

        int p = 0;
        for (int i=0;i<a;i++){
            String sub = b.substring(p,p+9);
            if(sub.startsWith("0")){
                //倒叙
                sub = sub.substring(1);
                char[] c = sub.toCharArray();
                StringBuilder sb = new StringBuilder();
                for (int i1 = c.length - 1; i1 >= 0; i1--) {
                    sb.append(c[i1]);
                }
                stringBuilder.append(sb).append(" ");
            }else {
                stringBuilder.append(sub.substring(1)).append(" ");
            }
            p=p+9;
        }
        System.out.println(stringBuilder.toString());
    }
}

PS：因为考试时允许使用本地IDEA，我是在本地IDEA上编码完成放到试卷上的。因此我IDEA上还保留着之前试题的代码。

通过上述代码可以了解到我的简单思路：

校验（需要保证每9个字符一组，编码个数和算出来的相等）；
拆分（根据’0’与’1’来进行拆分，即大端小端）；
小端的话字符串顺序要倒过来（倒序时使用了StringBuilder进行辅助）。

优化

上面的代码看了一下，自己对其还是不太满意的，现在时间充裕，我们就来优化一下。

我上述代码有四个问题，如下图：

一些判断可以整合；
除法精度问题；
if(sub.startsWith("0"))后接else，如果输入的一个串不是0，那么会进入1的逻辑（大端）,这就会有问题；
字符串倒序这块，有没有更好的处理方法？

我们带着这些问题，重新编写代码。

public class MyPrefectDemo1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        String b = in.next();

        //更严谨的校验
        boolean flag = b.length() / 9 == a && b.length() % 9 ==0;
        if(!flag){
            throw new RuntimeException("参数错误");
        }

        StringBuilder sb = new StringBuilder();

        int p = 0;
        for (int i = 0; i < a; i++) {
            String sub = b.substring(p,p+9);
            if(sub.startsWith("0")){
                //小端模式，需要翻转
                sub = sub.substring(1);
                //字符串翻转
                sb.append(new StringBuilder(sub).reverse()).append(" ");
            }else if(sub.startsWith("1")){
                //大端模式
                sb.append(sub.substring(1)).append(" ");
            }else{
                //既不为0也不为1的处理
                throw new RuntimeException("参数错误");
            }
            p+=9;
        }
        System.out.println(sb.toString());
    }
}

上述代码我把出现的问题都修复了，并且了解到了AbstractStringBuilder类中的reverse方法，可以实现字符串的翻转。

AbstractStringBuilder是StringBuffer和StringBuilder的父类，我们来看下它是如何实现字符串翻转的。

可以看到字符串翻转时，只需要循环一半长度，而后进行交换即可，同时代码里还处理了unicode的情况。

试题二

题目

查找组成一个偶数最接近的两个素数。

任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。

如果找不到或者输入错误，返回0即可。

样例：

输入：

6

输出：

3 3

分析

这道题目主要考察对素数的认知和二分法的概念。

当时在做试题时，我提交的代码如下：

public class MyDemo2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();

        //k为偶数
        if(k%2!=0){
            System.out.println(0);
            return;
        }

        int half = k/2;
        while (half >0){
            if(isPrime(half)){
                if(isPrime(k-half)){
                    System.out.println(half+" "+(k-half));
                    return;
                }
            }
            half--;
        }
        System.out.println(0);

    }

    public static boolean isPrime(int x){
        for (int i=2;i<x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}

通过上述代码可以了解到我的思路：

校验输入；
需要提供一个判断素数的方法；
对提供的偶数进行二分法处理，而后判断得到的两个值是否符合条件。

优化

上述代码有没有可以优化的地方呢？我们来看一下。

优化点一

首先关于素数的校验，经过网上查阅，我发现我是使用了一种可以说是最慢的处理方法。

判断一个数是不是素数，通常情况下有3种方法。

暴力求解法

也就是上面我用到的方法。代码如下：

public static boolean isPrime1(int x){
    if(x < 2){
        return false;
    }else if(x == 2){
        return true;
    }
    for (int i=2;i<x;i++){
        if(x % i==0){
            return false;
        }
    }
    return true;
}

这种方法从2遍历到n-1，然后依次判断，时间复杂度为O(n)。

二分开方遍历法

额，这个名字起得也不太好，方法的主要内容如下：

1	一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于 sqrt (n)，一个大于等于 sqrt (n)

我们以素数17来看，它能被分成1和17，sqrt(17)=4.123......。

我们再以16来举例，它可以被分成4和4、2和8、1和16，它们均一个小于等于sqrt(16)，一个大于等于sqrt(16)。

依据这个原理，我们只需从2遍历到sqrt(n)即可，代码如下：

public static boolean isPrime2(int x){
    if (x < 2) {
        return false;
    } else if (x == 2) {
        return true;
    }

    int temp = (int) Math.sqrt(x);
    for (int i = 2; i <= temp; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

可以看到这种方法的时间复杂度为O(sqrt(N))，相较于第一种暴力破解法会好很多。

六步循环法

素数分布是否有规律呢？我们来看下：

1	大于等于 5 的质数一定和 6 的倍数相邻。

比如 5 和 7，11 和 13，17 和 19等。

下面我们来证明一下。

证明：令 x=1，则大于等于 5 的自然数表示如下：

1	6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ......

可以看到，如果一个数不在6的倍数的两侧，则其可以如下表示：

1	6x+2，6x+3，6x+4,6(x+1)+2,6(x+1)+3,6(x+1)+4 ......

它们可以进行如下转换:

1	6x+2 = 2(3x+1) , 6x+3 = 3(2x+1) , 6x+4 = 2(3x+2) ......

它们一定不是素数！
同时 6x = 2 * 3x ，因此 6x 也不是素数。
所以我们只需要判断6x-1，6x+1，6(x+1)-1,6(x+1)+1 ......这些数据是否为素数即可。

因此可以设置循环步长为6，从2循环到sqrt(n)即可。

public static boolean isPrime3(int x){
    // 小于5的素数只有2和3
    if (x < 5) {
        if (x==2 || x==3) {
            return true;
        } else {
            return false;
        }
    }
    // 如果该数不在6的两侧，则一定不是素数
    if (x % 6 != 1 && x%6 != 5) {
        return false;
    }
    int temp = (int)Math.sqrt(x);
    // 循环步长为6，每次判断i和i+2
    for (int i=5; i<=temp; i+=6) {
        if (x%i == 0 || x%(i+2)==0) {
            return false;
        }
    }
    return true;
}

这种方法比上一种方法更快，我们来简单看下它们的效率。

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    long start3 = System.currentTimeMillis();
    //生成 1-1000000 之间的素数。
    for (int i = 0; i < 1000000; i++) {
        if(isPrime3(i)){
            list.add(i);
        }
    }
    long end3 = System.currentTimeMillis();
    System.out.println("生成素数耗时："+ (end3-start3)+"ms");

    long start = System.currentTimeMillis();
    for (Integer integer : list) {
        if(!isPrime1(integer)){
            throw new RuntimeException("数据有问题");
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("暴力求解法耗时："+ (end-start)+"ms");

    long start1 = System.currentTimeMillis();
    for (Integer integer : list) {
        if(!isPrime2(integer)){
            throw new RuntimeException("数据有问题");
        }
    }
    long end1 = System.currentTimeMillis();
    System.out.println("二分开方遍历法耗时："+ (end1-start1)+"ms");

    long start2 = System.currentTimeMillis();
    for (Integer integer : list) {
        if(!isPrime3(integer)){
            throw new RuntimeException("数据有问题");
        }
    }
    long end2 = System.currentTimeMillis();
    System.out.println("6步循环法耗时："+ (end2-start2)+"ms");
}

最后运行后结果如下：

可以看到最后一种方法是相当快的。

优化点二

回到我们的试题，确定了判断素数的方法，我们再来看下还是否可以进行优化。

上面我们对于一个偶数，寻找其两个相近素数，用二分法来进行的处理，只需要找最多一半的数据。

我们通过上面寻找素数的方法，也可以不用一步步的寻找，部分数据可以跳过。

我们来看下有几种情况可以多跳一些数据。我们可以根据表格来看下。

数据	6x-1	6x	6x+1	6x+2	6x+3	6x+4	6x+5 或 6(x+1)-1	6(x+1)	6(x+1)+1
x=1	5	6	7	8	9	10	11	12	13
x=6	35	36	37	38	39	40	41	42	43
x=10	59	60	61	62	63	64	65	66	67
x=15	89	90	91	92	93	94	95	96	97

我们看上面表格数据，根据六步循环法我们知道，寻找素数时我们最多是可以跳6位的。

有下面几种情况，我们都来看下：

我们将偶数 k 二分后 , 其一半 half 不是素数 ：
- 如果half 是6的倍数，但是6x+1 也是有素数可能，所以还是要half++，不能跳；
- 如果half+1 是6的倍数，以上面x=6举例，half=35不是素数，half+1=36，这种情况我们可以直接跳过6x，判断6x+1，即 half+=2；
- 如果half+2 是 6的倍数，以上面x=6举例，此时half=40，这种情况我们可以跳1步，即half+=1；
- 如果half+3 是 6的倍数，以上面x=6举例，此时half=39，这种情况我们可以跳2步，即half+=2；
- 如果half+4 是 6的倍数，以上面x=6举例，此时half=38，这种情况我们可以跳3步，即half+=3；
- 如果half-1 是 6的倍数，还是以上面x=6举例，此时half = 37，这种情况下我们可以直接跳4步，判断41是否符合条件，即half+=4;
- 如果half-2 是 6的倍数，以上面x=6举例，此时half=38，这种情况我们可以跳3步，即half+=3；
- 如果half-3 是 6的倍数，以上面x=6举例，此时half=39，这种情况我们可以跳2步，即half+=2；
- 如果half-4 是 6的倍数，以上面x=6举例，此时half=40，这种情况我们可以跳1步，即half+=1；
- 其实说了这么多，就是和half除6的余数有关系。
- 如果余4，就可以跳3步；如果余3，就可以跳2步；如果余2，就可以跳1步；如果余1，也是跳1步；如果余0，也是跳1步；
- 如果余5呢？我们以x=10为例， 6x+5 = 65 % 6 = 5，它也符合我们的half不是素数，可以看到我们也是只能跳2步，到 half=67。
需要注意上述规则是针对于大于5的素数得出来的，也就是 half不是素数，则half应该大于等于6。
我举个例子，比如 k=8 ，可以得到half = 4，按照1的规则，余数为4，需要跳3个，half+3 = 7 ,k-half = 8-7 =1 不是素数，这样就找不到合适的素数对了，其实 8 = 3+5 ，half=4的时候只能跳一个，也就是我们需要保证half >=6 这个条件。
如果**half是素数，但是k-half不是素数**呢？
这种情况要比上面简单些，如何理解呢？因为针对于大于等于5的素数，其只可能出现在6x-1和6x+1这两个里面。
如果是6x-1即除6余数为5，那么可以跳2个，到6x+1，即 half+=2;
如果是6x+1即除6余数为1，那么可以跳4个，到6(x+1)-1，即half+=4;
如果**half是素数，但是k-half是素数**呢？
那就找到满足条件的数据了，因为我们是从中间开始查找，找到的第一组素数一定是相差最小的。

故二分法核心代码优化如下：

int half = k/2;
while (half < k){
    if(isPrime3(half)){
        if(isPrime3(k-half)){
            //全部为素数，返回结果
            System.out.println(k +" = "+ (k-half)+" + "+half);
            return;
        }else{
            // half 是素数，但是 k-half 不是素数
            if(half >= 5){
                //针对于大于5的素数
                int m = half % 6;
                if(m==5){
                    half+=2;
                }else if(m==1){
                    half+=4;
                }else {
                    //理论上不会有数据
                    System.out.println("half = " + half);
                    half++;
                }
            }else{
                //否则还是一个个跳
                half ++;
            }
        }
    }else{
        // half 不是素数，寻找下一个判断位置
        if(half >= 6){
            // half >=6 就可以使用此规则
            int m = half % 6;
            if(m == 4){
                half+=3;
            }else if(m==3 || m==5){
                half+=2;
            }else{
                half++;
            }
        }else {
            //否则还是一个个跳
            half++;
        }

    }
}

优化点三

因为输入要求为偶数，我们对输入数字有个校验。原来代码如下：

//k为偶数
if(k%2!=0){
    System.out.println(0);
    return;
}

我们可以使用位运算来提高下效率。

我们知道，对于偶数来说，其二进制末尾一定为0。对于奇数来说，其末尾一定为1。

十进制	二进制
2	10
100	1100100
200	11001000
7	111
99	1100011
233	11101001

……

当我们与1进行按位’”与”运算时，对于偶数，其总等于0；对于奇数，其总等于1。

与（&）运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;

我们来看下：

对于偶数：

2 & 1 = 10 & 01 = 00
100 & 1 = 1100100 & 0000001 = 0000000
200 & 1 = 11001000 = 00000001 = 00000000
……

对于奇数：

7 & 1 = 111 & 001 = 001
99 & 1 = 1100011 & 0000001 = 0000001
233 & 1 = 11101001 & 00000001 = 00000001
…….

所以偶数校验可以如下判断：

//k为偶数
if((k & 1) == 1){
    System.out.println(0);
    return;
}

因此，最后的代码如下：

public static void search(int k){
    //k为偶数
    if((k & 1) == 1){
        System.out.println(0);
        return;
    }

    int half = k/2;
    while (half < k){
        if(isPrime3(half)){
            if(isPrime3(k-half)){
                //全部为素数，返回结果
                System.out.println(k +" = "+ (k-half)+" + "+half);
                return;
            }else{
                // half 是素数，但是 k-half 不是素数
                if(half >= 5){
                    //针对于大于5的素数
                    int m = half % 6;
                    if(m==5){
                        half+=2;
                    }else if(m==1){
                        half+=4;
                    }else {
                        //理论上不会有数据
                        System.out.println("half = " + half);
                        half++;
                    }
                }else{
                    //否则还是一个个跳
                    half ++;
                }
            }
        }else{
            // half 不是素数，寻找下一个判断位置
            if(half >= 6){
                // half >=6 就可以使用此规则
                int m = half % 6;
                if(m == 4){
                    half+=3;
                }else if(m==3 || m==5){
                    half+=2;
                }else{
                    half++;
                }
            }else {
                //否则还是一个个跳
                half++;
            }

        }
    }
    System.out.println(0);
}

我们准备一些数据来测试一下。

public static void main(String[] args) {
    //speedTest();
    //search(70);

    List<Integer> list = new ArrayList<>();
    //生成 4-1000 之间的偶数。
    for (int i = 4; i <= 1000; i++) {
        if((i & 1) == 0){
            list.add(i);
        }
    }
    for (Integer integer : list) {
        search(integer);
    }
}

我们生成了 4 - 1000 之间的偶数，结果如下：

看了下结果是没什么问题的。

总结

上面两道就是我在机试中遇到的，总体上还是比较简单的。

当时由于考试，由于时间限制，思路比较狭隘，回过来看自己的代码还是有不少问题及优化点的。

以上就是本篇文章的全部内容。

参考资料

如何高效判断一个数是不是素数

SakuraTears的博客

荣耀上机试题两道分享

前言

正文

试题一

题目

分析

优化

试题二

题目

分析

优化