Hurley's 校招面经

# 非互联网企业笔试题

总的来说，非互联网企业，包括银行、运营商等公司的笔试编程题相对还是简单的，很多都是大一接触到的，例如斐波那契数列等类型的题。然而，由于太久未看到这些基础的提醒，在一时间也有可能会反应不过来。毕竟，时间是有限的。因此，在这里做一个简单的汇总和说明。

# 定义一个小顶堆

# 手写一个循环队列

代码位于：https://github.com/HurleyJames/MyLeetCode/tree/master/src/basic/LoopQueue

一个队列是实行先进先出的原则，需要加上 front 和 rear 两个变量分别代表在数组中的位置，初值为 0。

在非空队列中，front 指向队首元素，rear 指向队尾元素的下一个存储位置。

循环队列中会有一个问题：无法区分队空和队满的状态，因为条件都是rear == front。

所以这里少使用一个存储单元，即队空的条件为rear == front，队满的条件是front == (rear + 1) % maxSize。

编写队列接口，主要要实现入队、出队、长度、是否为空等方法。

public interface IQueue {
    public void clear();
    public boolean isEmpty();
    public int length();
    public Object peek();
    public void offer(Object x) throws Exception;
    public Object poll();
    public void display();
}

# 求两数的最大公约数和最小公倍数

代码位于：https://github.com/HurleyJames/MyLeetCode/blob/master/src/basic/GCDAndLCM.java

这道题实际上就是实现现实中的求最大公约数和最小公倍数。那么，有些规律需要掌握，例如最小公倍数就等于两个数相乘再除以最大公约数，所以这道题的关键就是求最大公约数。

最大公约数即是用两个数中的更大的数除以最小的数取余数，然后反复除以，直到没有余数为止。有时会因为余数已经小于除数，所以需要更换位置。

public static int deff(int x, int y) {
    int t;
    if (x < y) {
        // 设计成 x 始终大于 y
        t = x;
        x = y;
        y = t;
    }

    while (y != 0) {
        if (x == y) {
            return x;
        }
        else {
            int k = x % y;
            x = y;
            y = k;
        }
    }
    return x;
}

# 去除特殊符号后的字符串再根据 ASCII 码值排序

代码位于：https://github.com/HurleyJames/MyLeetCode/blob/master/src/basic/ASCIISort.java

首先要掌握 ASCII 值的概念和规律。常见的 ASCII 值的大小顺序规律是：0～9 < A~Z < a~z。即数字要比字母小，大小字母要比小写字母小。

几个常见的 ASCII 值有：“A”：65， “a”：97，“0”：48

public static String ASCIISort(String str) {
    // 将字符串拆分成一个个字符
    char[] test = new char[str.length()];
    StringBuilder sb = new StringBuilder();
    while (true) {
        String a = str;
        for (int i = 0; i < str.length(); i++) {
            test[i] = a.charAt(i);
        }
        // 数组排序
        Arrays.sort(test);
        for (int i = 0; i < test.length; i++) {
            // 添加会 StringBuilder 里
            sb.append(test[i]);
        }
        // trim() 是用来删除字符串的首尾空白符
        String trim = sb.toString().trim();
        return trim;
    }
}

然后定义去除特殊字符的方法，运用正则表达式。

public static String replaceString(String str) {
    // 运用正则表达式
    String regEx = "[\\n`~!@#$%^&*()+=|{}':;',\\\\[\\\\].<>/?~！@#￥%……&*（）——+|{}【】‘；：”“’。， 、？]";

    Pattern p = Pattern.compile(regEx);
    Matcher m = p.matcher(str);
    String string = "";
    string = m.replaceAll(string).trim();
    System.out.println(string);
    return string;
}

# 递归实现字符串反转

代码位于：https://github.com/HurleyJames/MyLeetCode/blob/master/src/basic/ReverseStr.java

public static String reverse(String originStr) {
    if (originStr == null || originStr.length() <= 1) {
        return originStr;
    }
//        System.out.println(originStr.substring(1));
//        System.out.println(originStr.charAt(0));
    // 递归截取第一个字符，然后递归依次相加
    return reverse(originStr.substring(1)) + originStr.charAt(0);
}

假设字符串为"123a6"，那么substring(1)的作用是截取掉第 1 个字符后剩下的字符串，charAt(0)是获得第一个字符。

所以顺序会是：

23a6123a6\quad1
⇓\Downarrow
3a623a6\quad2
⇓\Downarrow
a63a6\quad3
⇓\Downarrow
6a6\quad a
⇓\Downarrow
6\quad6

所以按照递归从后往前相加的顺序，就变成6 + a + 3 + 2 + 1，反转字符串后的最终结果就是6a321。

# 两个有序数组的交集

代码位于：https://github.com/HurleyJames/MyLeetCode/blob/master/src/basic/Intersection.java

对于两个有序的数组，如何寻找它们之间的公共元素呢？

很容易想到的一个方法就是双重循环，然后条件语句判断元素是否相等，但如果要求时间复杂度不能超过O(n)O(n)呢？

所以这时候有序就成了一个非常关键的条件。因为有序，所以当a[i] > b[j]时，我们就可以让a[i]与b[j + 1]进行比较；反之，则是a[i + 1]与b[j]进行比较。那么，我们只需要在一个循环里完成就可以了。

public static List<Integer> intersection(int[] a, int[] b, List<Integer> lists) {
    int i = 0, j = 0;
    int len1 = a.length - 1;
    int len2 = b.length - 1;
    while (i < len1 || j < len2) {
        if (a[i] == b[j]) {
            lists.add(a[i]);
            i++;
            j++;
        } else if (a[i] > b[j]) {
            j++;
        } else {
            i++;
        }
    }
    return lists;
}

因为使用的是while循环，所以为了防止数组越界，需要将数组的长度减 1。当满足某个条件时，就把数组的 index 往后移一位。

然而，上面这个方法适用于「两个数组长度接近的情况」，这样比较的过程就不会做很多无用功。如果两个数组之间的长度相差很大，那么可以直接遍历较短数组的元素，然后在长数组中对该元素进行查找，如果查找到，就说明是公共元素，反之则不是。这个思路就更加简单了。

public static List<Integer> binaryIntersection(int[] a, int[] b, List<Integer> lists) {
    int[] longArray;
    int[] shortArray;
    if (a.length <= b.length) {
        shortArray = a;
        longArray = b;
    } else {
        shortArray = b;
        longArray = a;
    }
    // 遍历短的数组
    for (int i = 0; i < shortArray.length; i++) {
        // 使用短数组中的每一个元素在长数组中进行二分查找，如果查找到了，说明有公共元素
        int result = Arrays.binarySearch(longArray, shortArray[i]);
        if (result > 0) {
            lists.add(longArray[result]);
        }
    }
    return lists;
}

# 猴子吃桃问题

猴子第一天摘下 N 个桃子，当时就吃了一半，还不过瘾，就又吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第 n 天在想吃的时候就剩一个桃子了,求第一天共摘下来多少个桃子？

通过描述可以发现，递推公式是f(n)=(f(n+1)+1)∗2f(n)=(f(n+1)+1)*2，当 n 等于 1 时，就是第一个摘下来的桃子数量。

private static int eat(int n) {
    int i = 1;
    int x = 1;
    while (i < n) {
        x = (x + 1) * 2;
        i++;
    }
    return x;
}

# 简单找零钱算法

# 青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解题思路：

当 n>2 时，第一次跳的时候就有两种不同的选择：

一是第一次只跳 1 级，此时跳法数目等于剩下的 n-1 级台阶的跳法数目，即f(n−1)f(n-1)

二是第一次跳 2 级，此时跳法数目等于后面剩下的 n-2 级台阶的跳法数目，即f(n−2)f(n-2)

因此，n 级台阶的跳法总数目f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)

public static int frogJump(int n) {
    if (n == 0 || n < 0) {
        return 0;
    } else if (n == 1 || n == 2) {
        return n;
    } else {
        // 通过观察，发现其实一个 f(n)=f(n-1)+f(n-2) 的规律
        return frogJump(n - 1) + frogJump(n - 2);
    }
}

# 男女排队问题

幼儿园有 n 个小朋友排为一个队伍，男生用 “B” 表示，女生用 “G” 表示。当男女同挨着时便会发生矛盾。需要对所排的队伍进行调整，每次调整只能让相邻的小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：GGBGG->GGBGB->GGGBB 这样就能使之前的两处男女相邻变为一处男女相邻，需要调整队形两次 程序输入：输入一个数据包括一个长度为N且只包含 Ｇ 和 Ｂ 的字符串。 输入：ＧＧＢＢＧ 输出：２

这道题的思路主要是有两种情况来解决：

  • 将所有的 G 排在前面，每次都移动 G
  • 将所有的 B 排在前面，每次都移动 B

最后再比较两种情况下的移动次数，选择最少的。

public int lineup(String peoples) {
    // write code here
    int numG = 0;
    int numB = 0;
    int len = peoples.length();
    // 将字符串转化为字符数组
    char[] line = peoples.toCharArray();
    int k = 0;
    for (int i = 0; i < len; i++) {
        // 每次都移动 B，将所有的 B 移到前面，G 移到后面
        if (line[i] == 'B') {
            // 将 B 移动到前面所需要的次数
            numB = numB + i - k;
            k++;
        }
    }
    k = 0;
    for (int j = 0; j < len; j++) {
        // 每次都移动 G，将所有的 G 移到前面，B 移到后面
        if (line[j] == 'G') {
            // 将 G 移动到前面所需要的次数
            numG = numG + j - k;
            k++;
        }
    }
    // 判断移动 G 和移动 B 哪个次数最少，返回最少的次数
    return numG > numB ? numB : numG;
}

# 求两个日期之间的工作日

←