MyBitmap

public class MyBitmap {//每一個word是一個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位，相當于除以64return 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(78));}}

LRUCache算法

import java.util.HashMap;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-valueif (hashMap.size() >= limit) {String oldKey = removeNode(head);hashMap.remove(oldKey);}node = new Node(key, value);addNode(node);hashMap.put(key, node);}else {//如果key存在，刷新key-valuenode.value = value;refreshNode(node);}}public void remove(String key) {Node node = hashMap.get(key);if(node == null){return;}removeNode(node);hashMap.remove(key);}/*** 刷新被訪問的節點位置* @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信息");lruCache.get("002");lruCache.put("004", "用戶4信息更新");lruCache.put("006", "用戶6信息");System.out.println(lruCache.get("001"));System.out.println(lruCache.get("006"));} }

A*搜索算法

import java.util.ArrayList; import java.util.List;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>();//把起點加入 openListopenList.add(start);//主循環，每一輪檢查一個當前方格節點while (openList.size() > 0) {// 在openList中查找 F值最小的節點作為當前方格節點Grid currentGrid = findMinGird(openList);// 當前方格節點從openList中移除openList.remove(currentGrid);// 當前方格節點進入 closeListcloseList.add(currentGrid);// 找到所有鄰近節點List<Grid> neighbors = findNeighbors(currentGrid, openList, closeList);for (Grid grid : neighbors) {//鄰近節點不在openList中，標記父親、G、H、F，并放入openListgrid.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();}} }

發紅包算法

import java.math.BigDecimal; import java.util.*;public class Redpackage {/*** 拆分紅包* @param totalAmount 總金額（以分為單位）* @param totalPeopleNum 總人數*/public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum){List<Integer> amountList = new ArrayList<Integer>();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<Integer>();Set<Integer> segments = new HashSet<Integer>();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<Integer>(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)));}} }

總結

以上是生活随笔為你收集整理的《漫画算法》源码整理-7的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。