常见算法合集[java源码+持续更新中...]

一、引子

本文搜集从各种资源上搜集高频面试算法，慢慢填充...每个算法都亲测可运行，原理有注释。Talk is cheap,show me the code! 走你~

二、常见算法

2.1 判断单向链表是否有环

package study.algorithm.interview;

/**
 * 判断单向链表是否有环? <p>Q1:判断是否有环？ isCycle </> <p>Q2：环长？ count </> <p>Q3: 相遇点？ p1.data </> <p>Q4：入环点？ 头结点到入环点距离为D，入环点到相遇点距离为S1，相遇点再次回到入环点距离为S2.
 * 相遇时p1走了：D+s1,p2走了D+s1+n(s1+s2),n表示被套的圈数。 由于P2速度是P1两倍，D+s1+n(s1+s2)=2（D+s1）--》D=(n-1)(s1+s2)+s2， 即：从相遇点开始，环绕n-1圈，再次回到入环点距离。
 * 最终：只需要一个指针从头结点开始，一个指针从相遇点开始，步长都=1，这次相遇的点即为入环节点</>
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）,2个指针
 *
 * @author denny
 * @date 2019/9/4 上午10:07
 */
public class LinkedListIsCycle {

    /**
     * 判断是否有环： 1.有环返回相遇点 2.无环返回空
     *
     * @param head 头结点
     * @return
     */
    private static Node isCycle(Node head) {
        Node p1 = head;
        Node p2 = head;
        // 前进次数
        int count = 0;
        while (p2 != null && p2.next != null) {
            // P1每次前进1步
            p1 = p1.next;
            // p2每次前进2步
            p2 = p2.next.next;
            count++;
            if (p1 == p2) {
                System.out.println("1.环长=速度差*前进次数=（2-1）*前进次数=count=" + count);
                System.out.println("2.相遇点=" + p1.data);
                return p1;
            }
        }
        return null;
    }

    /**
     * 获取环入口
     *
     * @param head 头结点
     * @return
     */
    private static Node getCycleIn(Node head) {
        // 是否有环
        Node touch = isCycle(head);
        Node p1 = head;

        // 有环，只需要一个指针从头结点开始，一个指针从相遇点开始，步长都=1，这次相遇的点即为入环节点
        if (touch != null) {
            while (touch != null && p1 != null) {
                touch = touch.next;
                p1 = p1.next;
                if (p1 == touch) {
                    return p1;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        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;
        Node in = getCycleIn(node1);
        System.out.println(in != null ? "有环返回入口：" + in.data : "无环");
    }

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

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

}

 

2.2 最小栈的实现

package study.algorithm.interview;

import java.util.Stack;

/**
 * 求最小栈：实现入栈、出栈、取最小值。
 * 时间复杂度都是O（1），最坏情况空间复杂度是O（n）
 *
 * @author denny
 * @date 2019/9/4 下午2:37
 */
public class MinStack {

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

    /**
     * 入栈
     *
     * @param element
     */
    private void push(int element) {
        mainStack.push(element);
        //如果最小栈为空，或者新元素<=栈顶最小值，则入最小栈
        if (minStack.empty() || element <= minStack.peek()) {
            minStack.push(element);
        }
    }

    /**
     * 出栈
     *
     * @return
     */
    private Integer pop() {
        // 如果主栈栈顶元素和最小栈元素相等，最小栈出栈
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        // 主栈出栈
        return mainStack.pop();
    }

    /**
     * 取最小值
     *
     * @return
     * @throws Exception
     */
    private Integer getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(3);
        stack.push(2);
        stack.push(4);
        stack.push(1);
        stack.push(5);
        //主栈：32415 最小栈：321
        System.out.println("min=" + stack.getMin());
        stack.pop();
        stack.pop();
        System.out.println("min=" + stack.getMin());
    }
}

 

2.3 求2个整数的最大公约数

package study.algorithm.interview;

/**
 * 求2个整数的最大公约数 <p>1.暴力枚举法：时间复杂度O(min(a,b))</> <p>2.辗转相除法（欧几里得算法）: O(log(max(a,b))),但是取模运算性能较差</> <p>3.更相减损术：避免了取模运算，但性能不稳定，最坏时间复杂度：O（max(a,b)）</>
 * <p>4.更相减损术与位移结合:避免了取模运算，算法稳定，时间复杂度O（log(max(a,b))）</>
 *
 * @author denny
 * @date 2019/9/4 下午3:22
 */
public class GreatestCommonDivisor {

    /**
     * 暴力枚举法
     *
     * @param a
     * @param b
     * @return
     */
    private static int getGCD(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        // 能整除，直接返回
        if (big % small == 0) {
            return small;
        }
        // 从较小整数的一半开始~1，试图找到一个整数i，能被a和b同时整除。
        for (int i = small / 2; i > 1; i--) {
            if (small % i == 0 && big % i == 0) {
                return i;
            }
        }
        return 1;
    }

    /**
     * 辗转相除法(欧几里得算法):两个正整数a>b,最大公约数=a/b的余数c和b之间的最大公约数，一直到可以整除为止
     *
     * @param a
     * @param b
     * @return
     */
    private static int getGCD2(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;

        // 能整除，直接返回
        if (big % small == 0) {
            return small;
        }

        return getGCD2(big % small, small);
    }

    /**
     * 更相减损术：两个正整数a>b,最大公约数=a-b和b之间的最大公约数,一直到两个数相等为止。
     *
     * @param a
     * @param b
     * @return
     */
    private static int getGCD3(int a, int b) {
        if (a == b) {
            return a;
        }

        int big = a > b ? a : b;
        int small = a < b ? a : b;

        return getGCD3(big - small, small);
    }

    /**
     * 更相减损术结合位移
     *
     * @param a
     * @param b
     * @return
     */
    private static int getGCD4(int a, int b) {
        if (a == b) {
            return a;
        }
        // 都是偶数,gcd(a,b)=2*gcd(a/2,b/2)=gcd(a>>1,b>>1)<<1
        if ((a & 1) == 0 && (b & 1) == 0) {
            return getGCD4(a >> 1, b >> 1) << 1;
            // a是偶数，b是奇数,gcd(a,b)=gcd(a/2,b)=gcd(a>>1,b)
        } else if ((a & 1) == 0 && (b & 1) == 1) {
            return getGCD4(a >> 1, b);
            // a是奇数，b是偶数
        } else if ((a & 1) == 1 && (b & 1) == 0) {
            return getGCD4(a, b >> 1);
            // 都是奇数
        } else {
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return getGCD4(big - small, small);
        }

    }

    public static void main(String[] args) {
        System.out.println("最大公约数=" + getGCD4(99, 21));
    }
}

 

2.4 判断是否是2的整数次幂

package study.algorithm.interview;

/**
 * 判断是否是2的整数次幂：时间复杂度
 * 时间复杂度是O（1）
 *
 * @author denny
 * @date 2019/9/4 下午5:18
 */
public class PowerOf2 {

    /**
     * 判断是否是2的整数次幂： 2的整数次幂转换成二进制（1+n个0）& 二进制-1（n个1）=0
     * @param num
     * @param a
     * @return boolean
     * @author denny
     * @date 2019/9/5 上午11:14
     */
    private static boolean isPowerOf2(int num, int a) {
        return (num & (num - 1)) == 0;
    }

    public static void main(String[] args) {
        System.out.println("是否2的整数次幂=" + isPowerOf2(16, 1));
    }
}

 

2.5 无序数组排序后的最大相邻差

package study.algorithm.interview;

/**
 * 无序数组排序后的最大相邻差： 使用桶排序思想，每个桶元素遍历一遍即可，不需要再排序，
 * 时间复杂度O（n）
 *
 * @author denny
 * @date 2019/9/4 下午5:38
 */
public class MaxSortedDistance {

    private static class Bucket {
        Integer max;
        Integer min;
    }

    private static int getMaxSortedDistance(int[] array) {
        //1.求最大值最小值
        int max = array[0];
        int min = array[0];
        for (int i = 0; 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++) {
            // 桶下标=当前元素偏移量/跨度  跨度=总偏移量/桶数-1
            int index = (array[i] - min) / (d / (bucketNum - 1));
            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;
            }
            // 更新左边最大值为当前桶max
            leftMax = buckets[i].max;
        }
        return maxDistance;
    }

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

2.6 栈实现队列

package study.algorithm.interview;

import java.util.Stack;

/**
 * 栈实现队列：
 * 时间复杂度：入队O(1) 出队O(1)（均摊时间复杂度）
 *
 * @author denny
 * @date 2019/9/5 上午11:14
 */
public class StackQueue {
    // 入队
    private Stack<Integer> stackIn = new Stack<>();
    // 出队
    private Stack<Integer> stackOut = new Stack<>();

    /**
     * 入队：直接入栈
     *
     * @param element
     */
    private void enQueue(int element) {
        stackIn.push(element);
    }

    /**
     * 出队
     *
     * @return
     */
    private Integer deQueue() {
        // 出队为空
        if (stackOut.isEmpty()) {
            // 如果入队为空，直接返回空
            if (stackIn.isEmpty()) {
                return null;
            }
            // 入队不为空，IN元素全部转移到OUT
            transfer();
        }
        // 出队不为空，直接弹出
        return stackOut.pop();
    }

    /**
     * 入队元素转到出队
     */
    private void transfer() {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }

    public static void main(String[] args) {
        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());

    }

}

2.7 寻找全排列的下一个数

package study.algorithm.interview;

import com.alibaba.fastjson.JSONObject;

import java.util.Arrays;

/**
 * 寻找全排列的下一个数，又叫字典序算法，时间复杂度为O（n） 全排列：12345->54321
 * 核心原理：
 * 1.最后2位交换行不行？不行再最后3位.....从右往左找相邻array[index]>array[index-1] ，
 * 2.index-1和逆序列，从右往左中第一个比它大的值，交换 因为越往左边，交换后数越大，只有第一个才满足相邻。
 * 例如 12345-》12354   12354-第一步找到54数列，交换3和4-》12453--》12435
 * 12765->15762->15267
 * 时间复杂度：O（n）
 *
 * @author denny
 * @date 2019/9/5 下午2:18
 */
public class FindNextSortedNumber {

    private static int[] findNextSortedNumber(int[] numbers) {
        // 1.找到置换边界：从后向前查看逆序区域，找到逆序区域的第一位
        int index = findTransferPoint(numbers);
        System.out.println("index=" + index);
        // 整个数组逆序，没有更大的数了
        if (index == 0) {
            return null;
        }

        // copy一个新的数组，避免修改入参
        int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
        // 2.把逆序区域的前一位和逆序区域中大于它的最小数交换位置
        exchangHead(numbersCopy, index);

        // 3.把原来的逆序转为顺序
        reverse(numbersCopy, index);
        return numbersCopy;
    }

    /**
     * 找到置换边界
     *
     * @param numbers
     * @return
     */
    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;
    }

    /**
     * 把逆序区域的前一位和逆序区域中大于它的最小数交换位置
     *
     * @param numbers
     * @param index
     * @return
     */
    private static int[] exchangHead(int[] numbers, int index) {
        // 逆序区域前一位
        int head = numbers[index - 1];
        // 从后往前遍历
        for (int i = numbers.length - 1; i > 0; i--) {
            // 找到第一个大于head的数，和head交换。因为是逆序区域，第一个数就是最小数，所以找到第一个大于head的数，就是比head大的数中的最小数
            if (head < numbers[i]) {
                numbers[index - 1] = numbers[i];
                numbers[i] = head;
                break;
            }
        }
        return numbers;
    }

    /**
     * 逆序
     *
     * @param num
     * @param index
     * @return
     */
    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, 5, 4};

        numbers = findNextSortedNumber(numbers);
        System.out.println(JSONObject.toJSONString(numbers));

    }
}

2.8 删除整数的k个数字，使得留下的数字最小

package study.algorithm.interview;

/**
 * 删除整数的k个数字，使得留下的数字最小
 * 时间复杂度：O（n）
 *
 * @author denny
 * @date 2019/9/5 下午4:43
 */
public class removeKDigits {

    /**
     * 删除整数的k个数字，使得留下的数字最小
     *
     * @param num
     * @param k
     * @return
     */
    private static String removeKDigits(String num, int k) {
        // 新长度
        int newLength = num.length() - k;
        // 创建栈，接收所有数字
        char[] stack = new char[num.length()];
        int top = 0;
        // 遍历，一开始先入栈第一个数字。第一轮循环先给stack入栈一个数，且top++,往后循环，top-1才是栈顶
        for (int i = 0; i < num.length(); ++i) {
            // 当前数字
            char c = num.charAt(i);
            // 当栈顶数字 > 当前数字时，栈顶数字出栈，只要没删除够K个就一直往左边删除
            while (top > 0 && stack[top - 1] > c && k > 0) {
                // 这里top-1，就是出栈，忽略top
                top -= 1;
                k -= 1;
            }
            // 后一个数字入栈
            stack[top++] = c;
        }
        // 找到栈中第一个非0数字的位置，以此构建新的字符串0000123->123
        int offset = 0;
        while (offset < newLength && stack[offset] == '0') {
            offset++;
        }
        return offset == newLength ? "0" : new String(stack, offset, newLength - offset);
    }

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

2.9 大整数相加求和

package study.algorithm.interview;

/**
 * 大整数相加求和：可优化点：int -21-21亿，9位数妥妥的计算。拆分大整数每9位数一个元素，分别求和。效率可极大提升。
 * 时间复杂度：O（n）
 *
 * @author denny
 * @date 2019/9/5 下午5:50
 */
public class BigNumberSum {
    private static String bigNumberSum(String bigA, String bigB) {
        // 1.把2个大整数用数组逆序存储，数组长度等于较大整数位数+1
        int maxLength = bigA.length() > bigB.length() ? bigA.length() : bigB.length();
        int[] arrayA = new int[maxLength + 1];
        for (int i = 0; i < bigA.length(); i++) {
            arrayA[i] = bigA.charAt(bigA.length() - 1 - i) - '0';
        }
        int[] arrayB = new int[maxLength + 1];
        for (int i = 0; i < bigB.length(); i++) {
            arrayB[i] = bigB.charAt(bigB.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.转成数组
        StringBuilder stringBuilder = new StringBuilder();
        // 是否找到大整数的最高有效位
        boolean findFirst = false;
        // 倒序遍历，即从最高位开始找非零数，找到一个就可以开始append了
        for (int i = result.length - 1; i >= 0; i--) {
            if (!findFirst) {
                if (result[i] == 0) {
                    continue;
                }
                findFirst = true;
            }
            stringBuilder.append(result[i]);
        }
        return stringBuilder.toString();

    }

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

2.10 求解金矿问题

package study.algorithm.interview;

/**
 * 求金矿最优收益（动态规划）
 * 时间复杂度：O(n*w)n为人数 w为金矿数
 * 空间复杂度：O（n）
 *
 * @author denny
 * @date 2019/9/6 下午4:21
 */
public class GetMaxGold {

    /**
     * 求金矿最优收益
     *
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿金子储藏量
     * @return
     */
    private static int getMaxGold(int w, int[] p, int[] g) {
        // 构造数组
        int[] results = new int[w + 1];
        // 遍历所有金矿
        for (int i = 1; i < g.length; i++) {
            // 遍历人数：w->1
            for (int j = w; j >= 1; j--) {
                // 如果人数够这个金矿所需的人数，i-1是因为下标从0开始
                if (j >= p[i - 1]) {
                    // 当前人数，最大收益=Max(采用当前矿，不采用当前矿)
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        // 返回最后一个格子的值
        return results[w];
    }

    public static void main(String[] args) {
        System.out.println(getMaxGold(10, new int[] {5, 5, 3, 4, 3}, new int[] {400, 500, 200, 300, 350}));
    }
}

2.11 寻找缺失的整数

package study.algorithm.interview;

import java.util.ArrayList;
import java.util.List;

/**
 * 无序数组里有99个不重复整数，1-100，缺少一个。如何找到这个缺失的整数？
 *
 * @author denny
 * @date 2019/9/9 上午11:05
 */
public class FindLostNum {
    /**
     * 直接求和然后遍历减去全部元素即可 时间复杂度：O（1） 空间复杂度：
     *
     * @param array
     * @return
     */
    private static int findLostNum(Integer[] array) {
        // 1-100求和
        int sum = ((1 + 100) * 100) / 2;
        for (int a : array) {
            sum -= a;
        }
        return sum;
    }

    /**
     * 一个无序数组里有若干个正整数，范围是1~100，其中98个整数都出现了偶数次。只有2个整数出现了奇数次，求奇数次整数？ 利用异或运算的"相同为0，不同为1"，出现偶数次的偶数异或变0，最后只有奇数次的整数留下。 时间复杂度：O(n) 空间复杂度：O(1)
     *
     * @param array
     * @return
     */
    private static int[] findLostNum2(Integer[] array) {
        // 存储2个出现奇数次的整数
        int result[] = new int[2];
        // 第一次进行整体异或运算
        int xorResult = 0;
        for (int i = 0; i < array.length; i++) {
            xorResult ^= array[i];
        }
        //确定2个整数的不同位，以此来做分组
        int separtor = 1;
        //xorResult=0000 0110B ,A^B=>倒数第二位=1即，倒数第二位不同。一个是0一个是1.=》原数组可拆分成2个，一组倒数第二位是0，一组是1。& 01 、10 倒数第二位为1，separtor左移一位
        while (0 == (xorResult & separtor)) {
            separtor <<= 1;
        }
        //第二次分组进行异或运算
        for (int i = 0; i < array.length; i++) {
            // 按位与 10 ==0一组，一直异或计算，就是那个奇数次整数（因为偶数次整数，异或后=1相互抵消掉了）
            if (0 == (array[i] & separtor)) {
                result[0] ^= array[i];
                // 按位与 10 !=0另一组，一直异或计算，就是那个奇数次整数
            } else {
                result[1] ^= array[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        // 除了85，其它赋值
        for (int i = 0; i < 100; i++) {
            list.add(i + 1);
        }
        list.remove(10);
        System.out.println("缺失的数=" + findLostNum(list.toArray(new Integer[99])));

        Integer[] array = new Integer[] {4, 1, 2, 2, 5, 1, 4, 3};
        int[] result = findLostNum2(array);
        System.out.println(result[0] + "," + result[1]);
    }
}

2.12 位图Bitmap的实现

package study.algorithm.interview;

/**
 * 实现一个位图BitMap（海量数据查找、去重存储）
 *
 * @author denny
 * @date 2019/9/9 下午4:04
 */
public class MyBitMap {
    // 64位二进制数据
    private long[] words;
    // Bitmap的位数
    private int size;

    public MyBitMap(int size) {
        this.size = size;
        this.words = new long[getWordIndex(size - 1) + 1];
    }

    /**
     * 判断某一位的状态
     *
     * @param index
     * @return
     */
    public boolean getBit(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("index 无效！");
        }
        int wordIndex = getWordIndex(index);
        // 位与:都是1才是1，否则是0.   index对应值为1返回true
        return (words[wordIndex] & (1L << index)) != 0;
    }

    /**
     * 设置bitmap 在index处为1（true）
     *
     * @param index
     */
    public void setBit(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("index 无效！");
        }
        int wordIndex = getWordIndex(index);
        // 位或：只要有一个1就是1，2个0才是0 ，因为1L << index就是1，所以|=就是在index位置，赋值1
        words[wordIndex] |= (1L << index);
    }

    /**
     * 定位Bitmap某一位对应的word
     *
     * @param index
     * @return
     */
    private int getWordIndex(int index) {
        // 右移6位即除以64
        return index >> 6;
    }

    public static void main(String[] args) {
        MyBitMap bitMap = new MyBitMap(128);
        bitMap.setBit(126);
        bitMap.setBit(88);
        System.out.println(bitMap.getBit(126));
        System.out.println(bitMap.getBit(88));
    }

}

2.13 LRU算法的实现

package study.algorithm.interview;

import study.algorithm.base.Node;

import java.util.HashMap;

/**
 * LRU（Least Recently Used）最近最少使用算法(非线程安全) head（最少使用）<-->*<-->*<-->end(最近使用) 注：JDK中LinkedHashMap实现了LRU哈希链表，构造方法：LinkedHashMap(int
 * initialCapacity容量,float
 * loadFactor负载,boolean accessOrder是否LRU访问顺序，true代表LRU)
 *
 * @author denny
 * @date 2019/9/9 下午6:01
 */
public class LRUCache {

    // 双向链表头节点（最后时间）
    private Node head;
    // 双向链表尾节点（最早时间）
    private Node end;
    // 缓存储存上限
    private int limit;
    // 无序key-value映射。只有put操作才会写hashMap
    private HashMap<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    /**
     * 插入
     *
     * @param key
     * @param value
     */
    public void put(String key, String value) {
        Node node = hashMap.get(key);
        // key 不存在，插入新节点
        if (node == null) {
            // 达到容量上限
            if (hashMap.size() >= limit) {
                // 移除头结点
                String oldKey = removeNode(head);
                //同步hashMap
                hashMap.remove(oldKey);
            }
            // 构造节点
            node = new Node(key, value);
            // 添加到尾节点
            addNodeToEnd(node);
            // 同步hashmap
            hashMap.put(key, node);
        } else {
            // key存在，刷新key-value
            node.value = value;
            // 刷新被访问节点的位置
            refreshNode(node);
        }
    }

    /**
     * 获取
     *
     * @param key
     * @return
     */
    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        //刷新节点（提升该节点为尾结点，即最新使用节点）
        refreshNode(node);
        return node.value;
    }

    /**
     * 刷新被访问节点的位置
     *
     * @param node
     */
    private void refreshNode(Node node) {
        // 如果访问的是尾结点，则无须移动节点
        if (node == end) {
            return;
        }
        //移除节点
        removeNode(node);
        //尾部插入节点,代表最新使用
        addNodeToEnd(node);
    }

    /**
     * 移除节点
     *
     * @param node
     * @return
     */
    private String removeNode(Node node) {
        // 如果就一个节点，把头尾节点置空
        if (node == head && node == end) {
            head = null;
            end = null;
        } else if (node == end) {
            // 移除尾结点
            end = end.next;
            end.next = null;
        } else if (node == head) {
            //移除头结点
            head = head.next;
            head.pre = null;
        } else {
            // 移除中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 尾部插入节点
     *
     * @param node
     */
    private void addNodeToEnd(Node node) {
        if (head == null && end == null) {
            head = node;
            end = node;
        }
        // 添加节点
        end.next = node;
        // pre=之前的end
        node.pre = end;
        // node next不存在
        node.next = null;
        // 新节点为尾结点
        end = node;
    }

    public static void printLRUCache(LRUCache lruCache) {
        for (Node node = lruCache.head; node != null; node = node.next) {
            System.out.println("key=" + node.key + ",value=" + node.value);
        }
        System.out.println("===========================");
    }

    public static void main(String[] args) {
        // 构造一个容量为5的LRU缓存
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001", "value1");
        lruCache.put("002", "value2");
        lruCache.put("003", "value3");
        lruCache.put("004", "value4");
        lruCache.put("005", "value5");
        // 打印
        System.out.println("1. 插入 5个节点");
        printLRUCache(lruCache);

        // 002到尾结点
        lruCache.get("002");
        // 打印
        System.out.println("2. 002到尾结点");
        printLRUCache(lruCache);

        // 004到尾结点，且value更新
        lruCache.put("004", "value4更新");
        // 打印
        System.out.println("3. 004到尾结点，且value更新");
        printLRUCache(lruCache);

        // 001倍移除，006在尾结点
        lruCache.put("006", "value6");
        // 打印
        System.out.println("4. 超长，001倍移除，006在尾结点");
        printLRUCache(lruCache);
    }

}

2.14 A*寻路算法

package study.algorithm.interview;

import java.util.ArrayList;
import java.util.List;

/**
 *  A*寻路算法
 * @author denny
 * @date 2019/9/10 下午5:28
 */
public class AStarSearch {

    /**
     * 迷宫地图，1代表障碍物不可走 0代表可走
     */
    private static final int[][] MAZE={
        {0,0,0,0,0,0,0},
        {0,0,0,1,0,0,0},
        {0,0,0,1,0,0,0},
        {0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0}
    };

    static class Grid{
        // X轴坐标
        public int x;
        // Y轴坐标
        public int y;
        // 从起点走到当前格子的成本（一开始，当前格子=起点，往后走一步，下一个格子就是当前格子）
        public int g;
        // 在不考虑障碍情况下，从当前格子走到目标格子的步数
        public int h;
        // f=g+h，从起点到当前格子，再从当前格子走到目标格子的总步数
        public int f;
        public Grid parent;

        public Grid(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void initGrid(Grid parent,Grid end){
            //标记父格子，用来记录轨迹
            this.parent=parent;
            if(parent!=null){
                this.g = parent.g+1;
            }else {
                this.g=1;
            }
            this.h = Math.abs(this.x-end.x)+Math.abs(this.y-end.y);
            this.f = this.g+this.h;
        }
    }

    /**
     * A*寻路主逻辑
     * @param start 起点
     * @param end 终点
     * @return
     */
    public static Grid aStarSearch(Grid start,Grid end){
        // 可走list
        List<Grid> openList = new ArrayList<>();
        // 已走list
        List<Grid> closeList = new ArrayList<>();
        // 把起点加入openList
        openList.add(start);
        // 可走list不为空，一直循环
        while(openList.size()>0){
            // 在openList中查找F值最小的节点，将其作为当前格子节点
            Grid currentGrid = findMinGird(openList);
            // 将选中格子从openList中移除
            openList.remove(currentGrid);
            // 将选中格子塞进closeList
            closeList.add(currentGrid);
            // 找到所有邻近节点
            List<Grid> neighbors = findNeighbors(currentGrid,openList,closeList);
            for(Grid grid:neighbors){
                // 邻近节点不在可走list中，标记"父节点"，GHF，并放入可走格子list
                if(!openList.contains(grid)){
                    grid.initGrid(currentGrid,end);
                    openList.add(grid);
                }
            }
            // 如果终点在openList中，直接返回终点格子
            for(Grid grid:openList){
                if((grid.x==end.x) && (grid.y==end.y)){
                    return grid;
                }
            }
        }
        // 找不到路径，终点不可达
        return null;
    }

    /**
     * 求当前可走格子的最小f的格子
     * @param openList
     * @return
     */
    private static Grid findMinGird(List<Grid> openList){
        Grid tempGrid = openList.get(0);
        // 遍历求最小f的Grid
        for (Grid grid : openList){
            if(grid.f< tempGrid.f){
                tempGrid =grid;
            }
        }
        return tempGrid;
    }

    /**
     * 查找可以走的格子集合
     * @param grid 当前格子
     * @param openList 可走list
     * @param closeList 已走list
     * @return
     */
    private static ArrayList<Grid> findNeighbors(Grid grid,List<Grid> openList,List<Grid> closeList){
        ArrayList<Grid> grids = new ArrayList<>();
        if(isValidGrid(grid.x,grid.y-1,openList,closeList)){
            grids.add(new Grid(grid.x,grid.y-1));
        }
        if(isValidGrid(grid.x,grid.y+1,openList,closeList)){
            grids.add(new Grid(grid.x,grid.y+1));
        }
        if(isValidGrid(grid.x-1,grid.y,openList,closeList)){
            grids.add(new Grid(grid.x-1,grid.y));
        }
        if(isValidGrid(grid.x+1,grid.y,openList,closeList)){
            grids.add(new Grid(grid.x+1,grid.y));
        }
        return grids;
    }

    /**
     * 非法校验
     * @param x
     * @param y
     * @param openList
     * @param closeList
     * @return
     */
    private static boolean isValidGrid(int x,int y,List<Grid> openList,List<Grid> closeList){
        // 坐标有效校验
        if(x<0 || x>=MAZE.length || y<0 || y>=MAZE[0].length){
            return false;
        }
        // 存在障碍物，非法
        if(MAZE[x][y]==1){
            return false;
        }
        // 已经在openList中，已判断过
        if(containGrid(openList,x,y)){
            return false;
        }
        // 已经在closeList中,已走过
        if(containGrid(closeList,x,y)){
            return false;
        }
        return true;
    }

    /**
     * 是否包含坐标对应的格子
     * @param grids
     * @param x
     * @param y
     * @return
     */
    private static boolean containGrid(List<Grid> grids,int x,int y){
        for(Grid grid:grids){
            if((grid.x==x) && (grid.y==y)){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Grid start = new Grid(2,1);
        Grid end = new Grid(2,5);
        // 搜索迷宫终点
        Grid resultGrid = aStarSearch(start,end);
        //回溯迷宫路径
        List<Grid> path = new ArrayList<>();
        // 追溯parent
        while(resultGrid!=null){
            path.add(new Grid(resultGrid.x,resultGrid.y));
            resultGrid =resultGrid.parent;
        }
        // 行遍历
        for(int i=0;i<MAZE.length;i++){
            // 列遍历
            for(int j=0;j<MAZE[0].length;j++){
                // 路径打印
                if(containGrid(path,i,j)){
                    System.out.print("*,");
                } else {
                    System.out.print(MAZE[i][j]+",");
                }
            }
            System.out.println();
        }



    }


}

 2.15 红包拆分算法

package study.algorithm.interview;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * 红包拆分算法
 * 要求：
 * 1.每个人至少抢到一分钱。
 * 2.所有人抢到金额之和等于红包金额，不能超过，也不能少于。
 * 3.要保证所有人抢到金额的几率相等。
 *
 * @author denny
 * @date 2019/9/11 上午10:37
 */
public class RedPackage {

    /**
     * 拆分红包：二分均值法（每次抢红包的平均值是相等的）
     * 注：除最后一个红包外，其它红包<剩余人均金额的2倍，不算完全自由随机抢红包
     * @param totalAMount    总金额，单位：分
     * @param totalPeopleNum 总人数
     * @return
     */
    public static List<Integer> divideRedPackage(Integer totalAMount, Integer totalPeopleNum) {
        List<Integer> amountList = new ArrayList<>();
        // 余额
        Integer restAmount = totalAMount;
        // 没抢人数
        Integer restPeopleNum = totalPeopleNum;
        Random random = new Random();
        // 遍历totalPeopleNum-1遍，最后一个人直接把余下的红包都给他
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            // [1,剩余人均金额的2倍-1]
            int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
            restAmount -= amount;
            restPeopleNum--;
            amountList.add(amount);
        }
        // 最后一个人，余下的红包都给他
        amountList.add(restAmount);
        return amountList;
    }

    /**
     * 线段切割法：红包金额随机性好 1.当随机切割点出现重复时，再继续随机一个
     *
     * @param totalAmount
     * @param totalPeopleNum
     * @return
     */
    public static List<Integer> divideRedPackage2(Integer totalAmount, Integer totalPeopleNum) {
        // 切割点list
        List<Integer> indexList = new ArrayList<>();
        // 红包list
        List<Integer> amountList = new ArrayList<>();
        Random random = new Random();

        // 构造n-1个切割点
        while (indexList.size() <= totalPeopleNum - 1) {
            // 总金额随机+1分
            int i = random.nextInt(totalAmount - 1) + 1;
            // i不在list中，非重复切割添加到集合
            if (indexList.indexOf(i) < 0) {
                indexList.add(i);
            }
        }
        // 排序.升序排列，从小到大，刚好n-1个切割点把总金额切割成n份。
        Collections.sort(indexList);
        // 上一次index
        int flag = 0;
        // 红包之和
        int fl = 0;
        // 遍历全部切割点
        for (int i = 0; i < indexList.size(); i++) {
            // 当前红包=index-上一次index
            int temp = indexList.get(i) - flag;
            // 记录index
            flag = indexList.get(i);
            // 求和
            fl += temp;
            // 当前红包添加进list
            amountList.add(temp);
        }
        //最后一个红包=总金额-已发红包之和
        amountList.add(totalAmount - fl);
        return amountList;
    }

    public static void main(String[] args) {
        //1.=====二分均值法======
        System.out.println("========二分均值法===========");
        // 把10元红包拆分给10个人
        List<Integer> amountList = divideRedPackage(1000, 10);
        for (Integer amount : amountList) {
            System.out.println("抢到金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
        }

        System.out.println("===================");
        //2.=====线段切割法======
        System.out.println("========线段切割法===========");
        List<Integer> amountList2 = divideRedPackage2(1000, 10);
        BigDecimal total = BigDecimal.ZERO;
        for (Integer amount : amountList2) {
            total = total.add(new BigDecimal(amount));
            System.out.println("抢到金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
        }
        System.out.println("总金额=" + total + "分");
    }


}

 

 

 

 

 

=====参考=====

书籍：《漫画算法》