漫画算法（6）- 算法的实际应用

Bitmap

public class MyBitmap {

    // 一个long类型元素，对应64位二进制
    private long[] words;
    // bitmap的位数大小
    private int size;

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

    /**
     * 判断bitmap某一位的状态
     *
     * @param bitIndex 位图的第bitIndex位
     */
    public boolean getBit(int bitIndex) {
        if (bitIndex < 0 || bitIndex > size - 1) {
            throw new IndexOutOfBoundsException("超过bitmap有效范围");
        }
        int wordIndex = getWordIndex(bitIndex);
        return (words[wordIndex] & (1L << bitIndex)) != 0;
    }

    /**
     * 把bitmap某一位设为真
     *
     * @param bitIndex 位图的第bitIndex位
     */
    public void setBit(int bitIndex) {
        if (bitIndex < 0 || bitIndex > size - 1) {
            throw new IndexOutOfBoundsException("超过bitmap有效范围");
        }
        int wordIndex = getWordIndex(bitIndex);
        words[wordIndex] |= (1L << bitIndex);
    }

    /**
     * 定位bitmap某一位所对应的word
     *
     * @param bitIndex 位图的第bitIndex位
     */
    private int getWordIndex(int bitIndex) {
        // 右移6位，相当于除以64
        return bitIndex >> 6;
    }

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

LRU算法

/*
    在 LRU 算法中，使用了一种数据结构叫做哈希链表。
    Java 中的 LinkedHashMap 已经对哈希链表做了很好地实现。
    缓存数据库 Redis 底层也实现了类似 LRU 的回收算法。
*/
public class LRUCache {

    private Node head;
    private Node end;
    // 缓存存储上限
    private int limit;

    private HashMap<String, Node> hashMap;

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

    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if (node == null) {
            // 如果key不存在，插入key-value
            if (hashMap.size() >= limit) {
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node = new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        } else {
            // 如果key存在，刷新key-value
            node.value = value;
            refreshNode(node);
        }
    }

    /**
     * 刷新被访问的节点位置
     *
     * @param node 被访问的节点
     */
    private void refreshNode(Node node) {
        // 如果访问的是尾节点，无需移动节点
        if (node == end) {
            return;
        }
        removeNode(node);
        addNode(node);
    }

    /**
     * 删除节点
     *
     * @param node 要删除的节点
     */
    private String removeNode(Node node) {
        if (node == head && node == end) {
            // 移除唯一的节点
            head = null;
            end = null;
        } else if (node == end) {
            // 移除尾节点
            end = end.pre;
            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 addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if (head == null) {
            head = node;
        }
    }

    class Node {
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        public Node pre;
        public Node next;
        public String key;
        public String value;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001", "用户1信息");
        lruCache.put("002", "用户2信息");
        lruCache.put("003", "用户3信息");
        lruCache.put("004", "用户4信息");
        lruCache.put("005", "用户5信息");
        System.out.println(lruCache.get("002"));
        lruCache.put("004", "用户4信息更新");
        lruCache.put("006", "用户6信息");
        System.out.println(lruCache.get("001"));
        System.out.println(lruCache.get("006"));
    }
}

有环链表

/*
    A*寻路算法的基本思想，以估值高低来决定搜索优先次序的方法，被称为启发式搜索。
*/
public class AStar {

    // 迷宫地图
    public 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}
    };

    /**
     * A星寻路主逻辑
     *
     * @param start 迷宫起点
     * @param end   迷宫终点
     */
    public static Grid aStarSearch(Grid start, Grid end) {
        ArrayList<Grid> openList = new ArrayList<Grid>();
        ArrayList<Grid> closeList = new ArrayList<Grid>();
        // 把起点加入 openList
        openList.add(start);
        // 主循环，每一轮检查一个当前方格节点
        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) {
                // 邻近节点不在openList中，标记父亲、G、H、F，并放入openList
                grid.initGrid(currentGrid, end);
                openList.add(grid);
            }
            // 如果终点在openList中，直接返回终点格子
            for (Grid grid : openList) {
                if ((grid.x == end.x) && (grid.y == end.y)) {
                    return grid;
                }
            }
        }
        // openList用尽，仍然找不到终点，说明终点不可到达，返回空
        return null;
    }

    private static Grid findMinGird(ArrayList<Grid> openList) {
        Grid tempGrid = openList.get(0);
        for (Grid grid : openList) {
            if (grid.f < tempGrid.f) {
                tempGrid = grid;
            }
        }
        return tempGrid;
    }

    private static ArrayList<Grid> findNeighbors(Grid grid, List<Grid> openList, List<Grid> closeList) {
        ArrayList<Grid> gridList = new ArrayList<Grid>();
        if (isValidGrid(grid.x, grid.y - 1, openList, closeList)) {
            gridList.add(new Grid(grid.x, grid.y - 1));
        }
        if (isValidGrid(grid.x, grid.y + 1, openList, closeList)) {
            gridList.add(new Grid(grid.x, grid.y + 1));
        }
        if (isValidGrid(grid.x - 1, grid.y, openList, closeList)) {
            gridList.add(new Grid(grid.x - 1, grid.y));
        }
        if (isValidGrid(grid.x + 1, grid.y, openList, closeList)) {
            gridList.add(new Grid(grid.x + 1, grid.y));
        }
        return gridList;
    }

    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;
    }

    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;
    }

    static class Grid {
        public int x;
        public int y;
        public int f;
        public int g;
        public int h;
        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;
            this.g = parent.g + 1;
            this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
            this.f = this.g + this.h;
        }
    }

    public static void main(String[] args) {
        // 设置起点和终点
        Grid startGrid = new Grid(2, 1);
        Grid endGrid = new Grid(2, 5);
        // 搜索迷宫终点
        Grid resultGrid = aStarSearch(startGrid, endGrid);
        // 回溯迷宫路径
        ArrayList<Grid> path = new ArrayList<Grid>();
        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();
        }
    }
}  

红包算法

public class Redpackage {

    /**
     * 拆分红包（二倍均值法）
     *
     * @param totalAmount    总金额（以分为单位）
     * @param totalPeopleNum 总人数
     */
    public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
        List<Integer> amountList = new ArrayList<>();
        Integer restAmount = totalAmount;
        Integer restPeopleNum = totalPeopleNum;
        Random random = new Random();
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            // 随机范围：[1，剩余人均金额的两倍)，左闭右开
            int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
            restAmount -= amount;
            restPeopleNum--;
            amountList.add(amount);
        }
        amountList.add(restAmount);
        return amountList;
    }

    /**
     * 拆分红包V2（线段切割法）
     *
     * @param totalAmount    总金额（以分为单位）
     * @param totalPeopleNum 总人数
     */
    public static List<Integer> divideRedPackageV2(Integer totalAmount, Integer totalPeopleNum) {
        List<Integer> amountList = new ArrayList<>();
        Set<Integer> segments = new HashSet<>();
        Random random = new Random();
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            int segment = random.nextInt(totalAmount - 2) + 1;
            int delta = random.nextInt(1) == 0 ? 1 : -1;
            while (segments.contains(segment) || segment == 0) {
                segment = (segment + delta) % totalAmount;
            }
            segments.add(segment);
        }

        List<Integer> segmentList = new ArrayList<>(segments);
        Collections.sort(segmentList);
        for (int i = 0; i < segmentList.size(); i++) {
            Integer amount;
            if (i == 0) {
                amount = segmentList.get(0);
            } else {
                amount = segmentList.get(i) - segmentList.get(i - 1);
            }
            amountList.add(amount);
        }
        amountList.add(totalAmount - segmentList.get(segmentList.size() - 1));

        return amountList;
    }

    public static void main(String[] args) {
        List<Integer> amountList = divideRedPackage(1000, 10);
        for (Integer amount : amountList) {
//            System.out.println("抢到金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
            System.out.println("抢到金额：" + new BigDecimal(amount));
        }
        System.out.println("------");
        amountList = divideRedPackageV2(1000, 10);
        for (Integer amount : amountList) {
//            System.out.println("抢到金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
            System.out.println("抢到金额：" + new BigDecimal(amount));
        }
    }
}

参考资料

《漫画算法》第 6 章