漫画算法（5）- 面试中的算法

有环链表

public class LinkedListCycle {

    /**
     * 判断是否有环
     *
     * @param head 链表头节点
     */
    public static boolean isCycle(Node head) {
        Node p1 = head;
        Node p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 链表节点
     */
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) throws Exception {
        Node node1 = new Node(5);
        Node node2 = new Node(3);
        Node node3 = new Node(7);
        Node node4 = new Node(2);
        Node node5 = new Node(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node2;

        System.out.println(isCycle(node1));
    }
}

最小栈

public class MinStack {

    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    /**
     * 入栈操作
     *
     * @param element 入栈的元素
     */
    public void push(int element) {
        mainStack.push(element);
        // 如果辅助栈为空，或新元素小于等于辅助栈栈顶，则新元素压入辅助栈
        if (minStack.empty() || element <= minStack.peek()) {
            minStack.push(element);
        }
    }

    /**
     * 出栈操作
     */
    public Integer pop() {
        // 如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        return mainStack.pop();
    }

    /**
     * 获取栈的最小元素
     */
    public int getMin() throws Exception {
        if (mainStack.empty()) {
            throw new Exception("stack is empty");
        }

        return minStack.peek();
    }

    public static void main(String[] args) throws Exception {
        MinStack stack = new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());
    }
}

最大公约数

public class GreatestCommonDivisor {

    public static int getGreatestCommonDivisor(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        for (int i = small / 2; i > 1; i--) {
            if (small % i == 0 && big % i == 0) {
                return i;
            }
        }
        return 1;
    }

    // 辗转相除法
    public static int getGreatestCommonDivisorV2(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisorV2(big % small, small);
    }

    // 更相减损术
    public static int getGreatestCommonDivisorV3(int a, int b) {
        if (a == b) {
            return a;
        }
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        return getGreatestCommonDivisorV3(big - small, small);
    }

    public static int gcd(int a, int b) {
        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return gcd(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        } else {
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return gcd(big - small, small);
        }
    }

    public static void main(String[] args) {
        System.out.println(gcd(25, 5));
        System.out.println(gcd(100, 80));
        System.out.println(gcd(27, 14));
    }
}

2的整数次幂

/*
    方法：位运算（n & n-1）
*/
public class PowerOf2 {

    public static boolean isPowerOf2(int num) {
        int temp = 1;
        while (temp <= num) {
            if (temp == num) {
                return true;
            }
            temp = temp * 2;
        }
        return false;
    }

    public static boolean isPowerOf2V2(int num) {
        int temp = 1;
        while (temp <= num) {
            if (temp == num) {
                return true;
            }
            temp = temp << 1;
        }
        return false;
    }

    // n & (n-1): 整数不是 2 的整数次幂，结果一定不是 0
    public static boolean isPowerOf2V3(int num) {
        return (num & num - 1) == 0;
    }

    public static void main(String[] args) {
        System.out.println(isPowerOf2V3(32));
        System.out.println(isPowerOf2V3(19));
    }
}

最大相邻差

/*
    无序整形数组，求出该数组排序后的任意两个相邻元素的最大差值。
    方法：桶排序
*/
public class MaxSortedDistance {

    public static int getMaxSortedDistance(int[] array) {

        // 1.得到数列的最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        int d = max - min;
        // 如果max == min，说明数组所有元素都相等，返回0
        if (d == 0) {
            return 0;
        }

        // 2.初始化桶
        int bucketNum = array.length;
        Bucket[] buckets = new Bucket[bucketNum];
        for (int i = 0; i < bucketNum; i++) {
            buckets[i] = new Bucket();
        }

        // 3.遍历原始数组，填充桶中的最大值和最小值
        for (int i = 0; i < array.length; i++) {
            // 确定数组元素的桶下标
            int index = ((array[i] - min) * (bucketNum - 1) / d);
            if (buckets[index].min == null || buckets[index].min > array[i]) {
                buckets[index].min = array[i];
            }
            if (buckets[index].max == null || buckets[index].max < array[i]) {
                buckets[index].max = array[i];
            }
        }

        // 4.遍历桶，找到最大差值
        int leftMax = buckets[0].max;
        int maxDistance = 0;
        for (int i = 1; i < buckets.length; i++) {
            if (buckets[i].min == null) {
                continue;
            }
            if (buckets[i].min - leftMax > maxDistance) {
                maxDistance = buckets[i].min - leftMax;
            }
            leftMax = buckets[i].max;
        }

        return maxDistance;
    }

    /**
     * 桶
     */
    private static class Bucket {
        Integer min;
        Integer max;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 6, 3, 4, 5, 10, 9};
        System.out.println(getMaxSortedDistance(array));
    }
}

用栈实现队列

public class StackQueue {

    private Stack<Integer> stackA = new Stack<>();
    private Stack<Integer> stackB = new Stack<>();

    /**
     * 入队操作
     *
     * @param element 入队的元素
     */
    public void enQueue(int element) {
        stackA.push(element);
    }

    /**
     * 出队操作
     */
    public Integer deQueue() {
        if (stackB.isEmpty()) {
            if (stackA.isEmpty()) {
                return null;
            }
            while (!stackA.isEmpty()) {
                stackB.push(stackA.pop());
            }
        }
        return stackB.pop();
    }

    public static void main(String[] args) throws Exception {
        StackQueue stackQueue = new StackQueue();
        stackQueue.enQueue(1);
        stackQueue.enQueue(2);
        stackQueue.enQueue(3);
        System.out.println(stackQueue.deQueue());
        System.out.println(stackQueue.deQueue());
        stackQueue.enQueue(4);
        System.out.println(stackQueue.deQueue());
        System.out.println(stackQueue.deQueue());
    }
}

寻找全排列的下一个数

/*
    方法：字典序算法
*/
public class FindNearestNumber {

    public static int[] findNearestNumber(int[] numbers) {
        // 1.从后向前查看逆序区域，找到逆序区域的前一位，即为数字置换的边界
        int index = findTransferPoint(numbers);
        // 如果数字置换边界是0，说明整个数组已经逆序，返回null
        if (index == 0) {
            return null;
        }
        // 2.把逆序区域的前一位和逆序区域中略大于它的数字交换位置
        // 拷贝入参，避免直接修改入参
        int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
        numbersCopy = exchangeHead(numbersCopy, index);
        outputNumbers(numbersCopy);
        // 3.把原来的逆序区域转为顺序
        numbersCopy = reverse(numbersCopy, index);
        outputNumbers(numbersCopy);
        return numbersCopy;
    }

    private static int findTransferPoint(int[] numbers) {
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i] > numbers[i - 1]) {
                return i;
            }
        }
        return 0;
    }

    private static int[] exchangeHead(int[] numbers, int index) {
        int head = numbers[index - 1];
        for (int i = numbers.length - 1; i > 0; i--) {
            if (head < numbers[i]) {
                numbers[index - 1] = numbers[i];
                numbers[i] = head;
                break;
            }
        }
        return numbers;
    }

    private static int[] reverse(int[] num, int index) {
        for (int i = index, j = num.length - 1; i < j; i++, j--) {
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
        return num;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        // 打印12345之后的10个全排列整数
        for (int i = 0; i < 10; i++) {
            System.out.printf("第%d轮\n", i);
            numbers = findNearestNumber(numbers);
            outputNumbers(numbers);
            System.out.println("------");
        }
    }

    // 输出数组
    private static void outputNumbers(int[] numbers) {
        for (int i : numbers) {
            System.out.print(i);
        }
        System.out.println();
    }
}

删去k个数字后的最小值

/*
    方法：贪心算法（依次求得局部最优解，最终得到全局最优解）
*/
public class RemoveKDigits {

    /**
     * 删除整数的k个数字，获得删除后的最小值
     *
     * @param num 原整数
     * @param k   删除数量
     */
    public static String removeKDigits(String num, int k) {
        for (int i = 0; i < k; i++) {
            boolean hasCut = false;
            // 从左向右遍历，找到比自己右侧数字大的数字并删除
            for (int j = 0; j < num.length() - 1; j++) {
                if (num.charAt(j) > num.charAt(j + 1)) {
                    num = num.substring(0, j) + num.substring(j + 1, num.length());
                    hasCut = true;
                    break;
                }
            }
            // 如果没有找到要删除的数字，则删除最后一个数字
            if (!hasCut) {
                num = num.substring(0, num.length() - 1);
            }
        }
        // 清除整数左侧的数字0
        int start = 0;
        for (int j = 0; j < num.length() - 1; j++) {
            if (num.charAt(j) != '0') {
                break;
            }
            start++;
        }
        num = num.substring(start, num.length());
        // 如果整数的所有数字都被删除了，直接返回0
        if (num.length() == 0) {
            return "0";
        }
        return num;
    }

    /**
     * 删除整数的k个数字，获得删除后的最小值
     *
     * @param num 原整数
     * @param k   删除数量
     */
    public static String removeKDigitsV2(String num, int k) {
        // 新整数的最终长度 = 原整数长度 - k
        int newLength = num.length() - k;
        // 创建一个栈，用于接收所有的数字
        char[] stack = new char[num.length()];
        int top = 0;
        for (int i = 0; i < num.length(); ++i) {
            // 遍历当前数字
            char c = num.charAt(i);
            // 当栈顶数字大于遍历到的当前数字，栈顶数字出栈
            while (top > 0 && stack[top - 1] > c && k > 0) {
                top -= 1;
                k -= 1;
            }
            // 如果遇到数字0，且栈为空，0不入栈
            if ('0' == c && top == 0) {
                newLength--;
                if (newLength <= 0) {
                    return "0";
                }
                continue;
            }
            // 遍历到的当前数字入栈
            stack[top++] = c;
        }
        // 用栈构建新的整数字符串
        return newLength <= 0 ? "0" : new String(stack, 0, newLength);
    }

    public static void main(String[] args) {
        System.out.println(removeKDigits("1593212", 3));
        System.out.println(removeKDigits("30200", 1));
        System.out.println(removeKDigits("10", 2));
        System.out.println(removeKDigits("541270936", 3));
        System.out.println(removeKDigits("1593212", 4));
        System.out.println(removeKDigits("1000020000000010", 2));
    }
}

大整数相加

/*
    把大整数按照数位来拆分，拆分到可以被直接计算即可。
    int 类型的取值范围是 -2147483648~2147483647，为了防止溢出，可以把大整数每 9 位作为数组的一个元素。
*/
public class BigNumberSum {

    /**
     * 大整数求和
     *
     * @param bigNumberA 大整数A
     * @param bigNumberB 大整数B
     */
    public static String bigNumberSum(String bigNumberA, String bigNumberB) {
        // 1.把两个大整数用数组逆序存储
        int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
        int[] arrayA = new int[maxLength + 1];
        for (int i = 0; i < bigNumberA.length(); i++) {
            arrayA[i] = bigNumberA.charAt(bigNumberA.length() - 1 - i) - '0';
        }
        int[] arrayB = new int[maxLength + 1];
        for (int i = 0; i < bigNumberB.length(); i++) {
            arrayB[i] = bigNumberB.charAt(bigNumberB.length() - 1 - i) - '0';
        }
        // 2.构建result数组
        int[] result = new int[maxLength + 1];
        // 3.遍历数组，按位相加
        for (int i = 0; i < result.length; i++) {
            int temp = result[i];
            temp += arrayA[i];
            temp += arrayB[i];
            // 判断是否进位
            if (temp >= 10) {
                temp = temp - 10;
                result[i + 1] = 1;
            }
            result[i] = temp;
        }
        // 4.把result数组再次逆序并转成String
        StringBuilder sb = new StringBuilder();
        // 是否找到大整数的最高有效位
        boolean findFirst = false;
        for (int i = result.length - 1; i >= 0; i--) {
            if (!findFirst) {
                if (result[i] == 0) {
                    continue;
                }
                findFirst = true;
            }
            sb.append(result[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(bigNumberSum("426709752318", "95481253129"));
    }
}

金矿问题

/*
    10 个工人在 5 个金矿中做出最优选择。
    方法：动态规划（自底向上求解，明确边界、状态转移方程式）
*/
public class GoldMining {

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param p 金矿开采所需工人数量
     * @param g 金矿储量
     */
    public static int getBestGoldMiningV3(int w, int[] p, int[] g) {
        // 创建当前结果
        int[] results = new int[w + 1];
        // 填充一维数组
        for (int i = 1; i <= g.length; i++) {
            for (int j = w; j >= 1; j--) {
                if (j >= p[i - 1]) {
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        // 返回最后一个格子的值
        return results[w];
    }

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param p 金矿开采所需工人数量
     * @param g 金矿储量
     */
    public static int getBestGoldMiningV2(int w, int[] p, int[] g) {
        //创建表格
        int[][] resultTable = new int[g.length + 1][w + 1];
        //填充表格
        for (int i = 1; i <= g.length; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < p[i - 1]) {
                    resultTable[i][j] = resultTable[i - 1][j];
                } else {
                    resultTable[i][j] = Math.max(resultTable[i - 1][j], resultTable[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        //返回最后一个格子的值
        return resultTable[g.length][w];
    }

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param n 可选金矿数量
     * @param p 金矿开采所需工人数量
     * @param g 金矿储量
     */
    public static int getBestGoldMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }
        if (w < p[n - 1]) {
            return getBestGoldMining(w, n - 1, p, g);
        }
        return Math.max(getBestGoldMining(w, n - 1, p, g), getBestGoldMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }


    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益：" + getBestGoldMining(w, g.length, p, g));
        System.out.println("最优收益：" + getBestGoldMiningV2(w, p, g));
        System.out.println("最优收益：" + getBestGoldMiningV3(w, p, g));
    }

}

缺失的整数

/*
    一个无序数组中有 99 个不重复的正整数，范围是 1~100
    （1）其中 99 个整数都出现了偶数次，只有 1 个整数出现了奇数次，该数是多少？
    （2）其中有 2 个整数出现了奇数次，其他整数出现了偶数次，该数是多少？
    方法：异或运算
*/
public class FindLostNum {

    public static int[] findLostNum(int[] array) {
        // 用于存储两个出现奇数次的整数
        int result[] = new int[2];
        // 第一次整体异或
        int xorResult = 0;
        for (int i = 0; i < array.length; i++) {
            xorResult ^= array[i];
        }
        // 如果异或结果为0，说明输入数组不符合题目
        if (xorResult == 0) {
            return null;
        }
        // 确定两个整数的不同位，做分组
        int separator = 1;
        while (0 == (xorResult & separator)) {
            separator <<= 1;
        }
        // 第二次分组异或
        for (int i = 0; i < array.length; i++) {
            if (0 == (array[i] & separator)) {
                result[0] ^= array[i];
            } else {
                result[1] ^= array[i];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] array = {4, 1, 2, 2, 5, 1, 4, 3};
        int[] result = findLostNum(array);
        System.out.println(result[0] + "," + result[1]);
    }
}

参考资料

《漫画算法》第 5 章