辽阳网站推广,张家港做企业网站,网络seo哈尔滨,wordpress外链过度插件诸神缄默不语-个人CSDN博文目录
哦这是我三年前写的#xff0c;我现在Java语法都快忘光了…… 反正之前的博文也发一下好了。这个因为我当年是用有道云笔记而不是直接用CSDN编辑器写的#xff0c;所以后面有些内容写乱了#xff0c;因为我现在猛的一看有点看不懂#xff0…诸神缄默不语-个人CSDN博文目录
哦这是我三年前写的我现在Java语法都快忘光了…… 反正之前的博文也发一下好了。这个因为我当年是用有道云笔记而不是直接用CSDN编辑器写的所以后面有些内容写乱了因为我现在猛的一看有点看不懂所以……等我过段时间看懂了再回来把排版重新改一下酱。 文章目录 Chapter1算法与数据结构常识Chapter2线性数据结构Chapter3树Chapter4排序算法1. 冒泡排序2. 快速排序3. 堆排序4. 计数排序4.1 原始版与优化step14.2 优化step2 5. 桶排序 Chapter5面试中的算法1. 如何判断链表有环1.1 方法一暴力遍历1.2 方法二哈希表1.3 方法三两个指针1.4 扩展问题环的长度1.5 扩展问题出入环节点 2. 最小栈2.1 有问题的方法把栈中的最小元素下标暂存起来2.2 方法存储栈中曾经的最小值 3. 最大公约数3.1 方法一暴力枚举法3.2 方法二辗转相除法/欧几里得算法3.3 方法三辗转相减法/更相减损法3.4 方法四移位运算 4. 2的整数次幂4.1 方法一暴力枚举法4.2 方法二 5. 无序数组排序后的最大相邻差5.1 方法一排序后求解5.2 方法二利用计数排序的思想5.3 方法三利用桶排序的思想 6. 用栈实现队列7. 寻找全排列的下一个数8. 删去k个数字后的最小值8.1 性能不好的代码8.2 优化后的代码 9. 如何实现大整数相加10. 如何求解金矿问题10.1 优化前的代码10.2 优化step110.3 优化step2 11. 寻找缺失的整数11.1 解法111.2 解法211.3 解法311.4 问题扩展step111.5 问题扩展step2 Chapter6算法的业务应用1. Bitmap算法/位图算法2. LRU算法3. A星寻路算法4. 红包算法方法1二倍均值法方法2线段切割法方法2线段切割法 Chapter1算法与数据结构常识
线性结构数组、链表 栈、队列、哈希表 树二叉树 二叉堆 图时间复杂度 - 基本操作执行次数 T n T_{n} Tn log 2 n \log_2{n} log2n - 渐进时间复杂度 大O表示法 最高阶项 若存在函数 f ( n ) f_{(n)} f(n)使得当 n → ∞ n\to\infty n→∞时 T ( n ) f ( n ) \frac{T_{(n)}}{f_{(n)}} f(n)T(n)的极限值为不等于0的常数则称 f ( n ) f_{(n)} f(n)是 T ( n ) T_{(n)} T(n)的同数量级函数。记作 T ( n ) O ( f ( n ) ) T_{(n)}O(f_{(n)}) T(n)O(f(n))称为 O ( f ( n ) ) O(f_{(n)}) O(f(n)) O O O为算法的渐进时间复杂度简称为时间复杂度空间复杂度 S ( n ) O ( f ( n ) ) S_{(n)}O(f_{(n)}) S(n)O(f(n))
空间性质空间复杂度常量空间 O ( 1 ) O(1) O(1)线性空间 O ( n ) O(n) O(n)二维空间 O ( n 2 ) O(n^2) O(n2)递归空间
Chapter2线性数据结构
数组array 顺序存储 顺序表 根据下标读取元素的方式随机读取 读取和更新的时间复杂度 O ( 1 ) O(1) O(1) 插入/删除 O ( n ) O(n) O(n) 读操作多写操作少链表 随机存储 2.1 单向链表
2.2 双向链表 链表
查找节点最坏的时间复杂度是 O ( n ) O(n) O(n)更新节点 O ( 1 ) O(1) O(1)插入节点尾部/头部/中间 插入 O ( 1 ) O(1) O(1)删除元素尾部/头部/中间 删除 O ( 1 ) O(1) O(1) Java自动化垃圾回收机制
物理结构和逻辑结构 栈FILO 最早进入的元素存放的位置栈底bottom最后进入的元素存放的位置栈顶top入栈push出栈pop O ( 1 ) O(1) O(1)用于对历史的回溯——递归、面包屑导航 队列FIFO 队列的出口端队头front队列的入口端队尾rear入队enque出队deque循环队列 O ( 1 ) O(1) O(1)用于对历史的回放——多线程中争夺公平锁的等待队列、爬虫实现网络抓取 双端队列deque 优先队列 谁的优先级最高谁先出队 散列表/哈希表 Key-Value 本质数组 哈希函数 Key和数组下标进行转换 取模 i n d e x H a s h C o d e ( K e y ) % A r r a y . l e n g t h indexHashCode(Key)\%Array.length indexHashCode(Key)%Array.length读get、写putentry接近 O ( 1 ) O(1) O(1)写操作哈希冲突 开放寻址法下一个空档位置 ThreadLocal链表法HashMap 扩容resize #mermaid-svg-vErXpD1BpiEFSmH3 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 .error-icon{fill:#552222;}#mermaid-svg-vErXpD1BpiEFSmH3 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-vErXpD1BpiEFSmH3 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-vErXpD1BpiEFSmH3 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-vErXpD1BpiEFSmH3 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-vErXpD1BpiEFSmH3 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-vErXpD1BpiEFSmH3 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-vErXpD1BpiEFSmH3 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-vErXpD1BpiEFSmH3 .marker.cross{stroke:#333333;}#mermaid-svg-vErXpD1BpiEFSmH3 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-vErXpD1BpiEFSmH3 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 .cluster-label text{fill:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 .cluster-label span{color:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 .label text,#mermaid-svg-vErXpD1BpiEFSmH3 span{fill:#333;color:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 .node rect,#mermaid-svg-vErXpD1BpiEFSmH3 .node circle,#mermaid-svg-vErXpD1BpiEFSmH3 .node ellipse,#mermaid-svg-vErXpD1BpiEFSmH3 .node polygon,#mermaid-svg-vErXpD1BpiEFSmH3 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-vErXpD1BpiEFSmH3 .node .label{text-align:center;}#mermaid-svg-vErXpD1BpiEFSmH3 .node.clickable{cursor:pointer;}#mermaid-svg-vErXpD1BpiEFSmH3 .arrowheadPath{fill:#333333;}#mermaid-svg-vErXpD1BpiEFSmH3 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-vErXpD1BpiEFSmH3 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-vErXpD1BpiEFSmH3 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-vErXpD1BpiEFSmH3 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-vErXpD1BpiEFSmH3 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-vErXpD1BpiEFSmH3 .cluster text{fill:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 .cluster span{color:#333;}#mermaid-svg-vErXpD1BpiEFSmH3 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-vErXpD1BpiEFSmH3 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 扩容 重新哈希 Chapter3树
树tree是n(n≥0)个节点的有限集。当n0时称为空树。在任意一个非空树中有如下特点 有且仅有一个特定的称为根的节点。当n1时其余节点可分为m(m0)个互不相交的有限集每一个集合的本身又是一个树并称为根的子树。
根节点root
叶子节点leaf
子树
层级
父节点parent
孩子节点child
兄弟节点sibling
最大层级数高度或深度二叉树每个节点最多有两个孩子节点
左孩子left child
右孩子right child满二叉树所有非叶子节点都存在左右孩子并且所有叶子节点都在同一层级上完全二叉树对一个有n个节点的二叉树按层级顺序编号则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为1到n的节点位置相同则这个二叉树为完全二叉树 完全二叉树是满二叉树缺最后几个叶子节点
二叉树的存储方式 3.1 链式存储结构 3.2 数组 parent 左孩子2parent1 右孩子2parent2 leftChild 父节点(leftChild-1)/2 应用二叉堆 二叉查找树 排序 (1)如果左子树不为空则左子树上所有节点的值均小于根节点的值 (2)如果右子树不为空则右子树上所有节点的值均大于根节点的值 (3)左、右子树也都是二叉查找树 节点分布相对均衡的二叉查找树搜索时间复杂度 O ( n ) O(n) O(n) 自平衡 二叉查找树的深度优先遍历 栈 前序遍历根节点、左子树、右子树中序遍历左子树、根节点、右子树后序遍历左子树、右子树、根节点 二叉查找树的广度优先遍历 队列 二叉堆 本质完全二叉树分类 (1)最大堆任何一个父节点的值都大于等于左、右子节点值 (2)最小堆任何一个父节点的值都小于等于左、右子节点值根节点堆顶数组存储 二叉堆的自我调整 插入 O ( log n ) O(\log{n}) O(logn)最后一个位置→上浮删除 O ( log n ) O(\log{n}) O(logn)删的是堆顶最后一个节点临时补到堆顶→下沉构建二叉堆 O ( n ) O(n) O(n)把无序的完全二叉树调整为二叉堆本质就是让所有非叶子节点依次“下沉”从最后一个非叶子节点开始 优先队列 最大优先队列当前最大的元素优先出队 最大堆最小优先队列当前最小的元素优先出队 最小堆
Chapter4排序算法
分类一
时间复杂度算法 O ( n 2 ) O(n^2) O(n2)冒泡、插入、选择、希尔 O ( n log n ) O(n\log{n}) O(nlogn)快速、堆、归并线性计数、桶、基数
快速排序最坏时间复杂度是 O ( n 2 ) O(n^2) O(n2)
分类二
稳定性算法稳定值相同的元素在排序后仍然保持着排序前的顺序不稳定 1. 冒泡排序
两两交换最大到最小稳定排序优化 有序标记isSorted数列有序区记录最后一次元素交换的位置 鸡尾酒排序双向 大部分元素已经有序的情况
2. 快速排序
交换排序 平均空间复杂度是 O ( log n ) O(\log{n}) O(logn)
基准元素的选择元素的交换 双边循环法左右两个指针同时比成则交换一边与基准元素比一边相靠最后与基准元素交换
public class Main {//递归实现双边循环法的快速排序public static void quickSort(int[] arr,int startIndex,int endIndex){//递归结束条件startIndex大于或等于endIndex时if(startIndexendIndex){return;}//得到基准元素位置int pivotIndexpartition(arr,startIndex,endIndex);//根据基准元素分成两部分进行递归排序quickSort(arr,startIndex,pivotIndex-1);quickSort(arr,pivotIndex1,endIndex);}/** 分治双边循环法* param arr 待交换的数组* param startIndex 起始下标* param endIndex 结束下标* */private static int partition(int[] arr,int startIndex,int endIndex){//取第1个位置也可以选择随机位置的元素作为基准元素int pivotarr[startIndex];int leftstartIndex;int rightendIndex;while(left!right){//控制right指针比较并左移while(leftrightarr[right]pivot){right--;}//控制left指针比较并右移while(leftrightarr[left]pivot){left;}//交换left和right指针所指向的元素if(leftright){int parr[left];arr[left]arr[right];arr[right]p;}}//pivot和指针重合点交换arr[startIndex]arr[left];arr[left]pivot;return left;}public static void main(String[] args) {int[] arrnew int[] {4,4,6,5,3,2,8,1};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}
}2.2.2 单边循环法用mark指针来标示小于基准元素的区域把小于基准元素的都放到此区域。最后把基准元素放到mark位置
//仅有partition函数变化
private static int partition(int[] arr,int startIndex,int endIndex){//取第1个位置也可以选择随机位置的元素作为基准元素int pivotarr[startIndex];int markstartIndex;for(int istartIndex1;iendIndex;i){if(arr[i]pivot){mark;int parr[mark];arr[mark]arr[i];arr[i]p;}}arr[startIndex]arr[mark];arr[mark]pivot;return mark;
}2.2.3 不用递归的方法
//仅有quickSort方法变化
public static void quickSort(int[] arr,int startIndex,int endIndex){//用一个集合栈来代替递归的函数栈StackMapString,Integer quickSortStacknew StackMapString,Integer();//整个数列的起止下标以哈希的形式入栈Map rootParamnew HashMap();rootParam.put(startIndex, startIndex);rootParam.put(endIndex, endIndex);quickSortStack.push(rootParam);//循环结束条件栈为空时while(!quickSortStack.isEmpty()){//栈顶元素出栈得到起止下标MapString,Integer paramquickSortStack.pop();//得到基准元素位置int pivotIndexpartition(arr,param.get(startIndex),param.get(endIndex));//根据基准元素分成两部分把每一部分的起止下标入栈if(param.get(startIndex)pivotIndex-1){MapString,Integer leftParamnew HashMapString,Integer();leftParam.put(startIndex, param.get(startIndex));leftParam.put(endIndex, pivotIndex-1);quickSortStack.push(leftParam);}if(pivotIndex1param.get(endIndex)){MapString,Integer rightParamnew HashMapString,Integer();rightParam.put(startIndex, pivotIndex1);rightParam.put(endIndex, param.get(endIndex));quickSortStack.push(rightParam);}}
}3. 堆排序
3.1 把无序数组构建成二叉堆。需要从小到大排序则构建成最大堆需要从大到小排序则构建成最小堆。 3.2 循环删除堆顶元素替换到二叉堆的末尾调整堆产生新的堆顶
public class Main {/*** “下沉”调整* param array 待调整的堆* param parentIndex 要下沉的父节点* param length 堆的有效大小*/public static void downAdjust(int[] array,int parentIndex,int length){//temp保存父节点值用于最后的赋值int temparray[parentIndex];int childIndex2*parentIndex1;while(childIndexlength){//如果有右孩子且右孩子大于左孩子的值则定位到右孩子if(childIndex1lengtharray[childIndex1]array[childIndex]){childIndex;}//如果父节点大于任何一个孩子的值则直接跳出if(temparray[childIndex])break;//无须真正交换单向赋值即可array[parentIndex]array[childIndex];parentIndexchildIndex;childIndex2*childIndex1;}array[parentIndex]temp;}/*** 堆排序升序* param array 待调整的堆*/public static void heapSort(int[] array){//1.把无序数组构建成最大堆for(int i(array.length-2)/2;i0;i--){downAdjust(array,i,array.length);}System.out.println(Arrays.toString(array));//2.循环删除堆顶元素移到集合尾部调整堆产生新的堆顶for(int iarray.length-1;i0;i--){//最后1个元素和第1个元素进行交换int temparray[i];array[i]array[0];array[0]temp;//“下沉”调整最大堆downAdjust(array,0,i);}}public static void main(String[] args){int[] arrnew int[] {1,3,2,6,5,7,8,9,10,0};heapSort(arr);System.out.println(Arrays.toString(arr));}
}堆排序 空间复杂度 O ( 1 ) O(1) O(1) 时间复杂度 第一步把无序数组构造成二叉堆 O ( n ) O(n) O(n) 第二步需要进行 n − 1 n-1 n−1次循环。每次循环调用一次downAdjust方法所以第2步的计算规模是 ( n − 1 ) × log n (n-1)\times\log{n} (n−1)×logn时间复杂度为 O ( n log n ) O(n\log{n}) O(nlogn) 两个步骤是并列关系所以整体的时间复杂度是 O ( n log n ) O(n\log{n}) O(nlogn)
4. 计数排序
4.1 原始版与优化step1
利用数组下标来确定元素的正确位置 (1)随机整数有取值范围建立长度为取值范围的数组 (2)遍历序列每一个元素对应下标的数组元素1 (3)遍历数组输出数组元素的下标值元素值为输出次数
public static int[] countSort(int[] array){//1.得到数列的最大值int maxarray[0];for(int i1;iarray.length;i){if(array[i]max){maxarray[i];}}//2.根据数列最大值确定统计数组的长度/* 算法改进step1用最大值-最小值1作为数组的长度* 数组的最小值作为偏移量用于统计整数在统计数组中的下标*/int[] countArraynew int[max1];//3.遍历数列填充统计数组for(int i0;iarray.length;i){countArray[array[i]];}//4.遍历统计数组输出结果int index0;int[] sortedArraynew int[array.length];for(int i0;icountArray.length;i){for(int j0;jcountArray[i];j){sortedArray[index]i;}}return sortedArray;
}public static void main(String[] args){int[] arraynew int[]{4,4,6,5,3,2,8,1,7,5,6,0,10};int[] sortedArraycountSort(array);System.out.println(Arrays.toString(sortedArray));
}4.2 优化step2
要求遵循原表固有顺序变成稳定排序
方法从统计数组的第2个元素开始每一个元素都加上前面所有元素之和
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XZjeDK0k-1595582632835)(漫画算法3.JPG)]
相加的目的让统计数组存储的元素值等于相应整数的最终排序位置的序号 接下来创建输出数组sortedArray长度和输入数列一致然后从后向前遍历输入数列。下标→位置统计数组相应-1
public static int[] countSort(int[] array){//1. 得到数列的最大值和最小值并算出差值int maxarray[0];int minarray[0];for(int i1;iarray.length;i){if(array[i]max){maxarray[i];}if(array[i]min){minarray[i];}}int dmax-min;//2. 创建统计数组并统计对应元素的个数int[] countArraynew int[d1];for(int i0;iarray.length;i){countArray[array[i]-min];}//3. 统计数组做变形后面的元素等于前面的元素之和for(int i1;icountArray.length;i){countArray[i]countArray[i-1];}//4. 倒序遍历原始数列从统计数组找到正确位置输出到结果数组int[] sortedArraynew int[array.length];for(int iarray.length-1;i0;i--){sortedArray[countArray[array[i]-min]-1]array[i];countArray[array[i]-min]--;}return sortedArray;
}public static void main(String[] args) {int[] arraynew int[]{95,94,91,98,99,90,99,93,91,92};int[] sortedArraycountSort(array);System.out.println(Arrays.toString(sortedArray));
}如果原始数列的规模是n最大和最小整数的差值是m时间复杂度是 O ( n m ) O(nm) O(nm)空间复杂度如果不考虑结果数组只考虑统计数组是 O ( m ) O(m) O(m)
5. 桶排序
每一个桶bucket代表一个区间范围里面可以承载一个或多个元素。步骤 2.1 step1分桶 2.2 step2把数列元素放进桶 2.3 step3对每个桶内部的元素分别进行排序 2.4 step4遍历桶输出所有元素
public static double[] bucketSort(double[] array){//1. 得到数列的最大值和最小值并算出差值double maxarray[0];double minarray[0];for(int i1;iarray.length;i){if(array[i]max){maxarray[i];}if(array[i]min){minarray[i];}}double dmax-min;//2. 初始化桶int bucketNumarray.length;ArrayListLinkedListDouble bucketListnew ArrayListLinkedListDouble(bucketNum);for(int i0;ibucketNum;i){bucketList.add(new LinkedListDouble());}//3. 遍历原始数组将每个元素放入桶中for(int i0;iarray.length;i){int num(int)((array[i]-min)*(bucketNum-1)/d);bucketList.get(num).add(array[i]);}//4. 对每个桶内部进行排序for(int i0;ibucketList.size();i){//JDK底层采用了归并排序或归并的优化版本Collections.sort(bucketList.get(i));}//5. 输出全部元素double[] sortedArraynew double[array.length];int index0;for(LinkedListDouble list:bucketList){for(double element:list){sortedArray[index]element;index;}}return sortedArray;
}public static void main(String[] args) {double[] arraynew double[]{4.12,6.421,0.0023,3.0,2.123,8.122,4.12,10.09};double[] sortedArraybucketSort(array);System.out.println(Arrays.toString(sortedArray));
}桶排序的性能并非绝对稳定。如果元素的分布极不均衡在极端情况下第一个桶中有n-1个元素最后一个桶中有1个元素。此时的时间复杂度将退化为 O ( n log n ) O(n\log{n}) O(nlogn)而且还白白创建了许多空桶。
Chapter5面试中的算法
1. 如何判断链表有环
单向链表
1.1 方法一暴力遍历
方法依次遍历节点每遍历一个新节点就从头检查新节点之前的所有节点用新节点和之前的所有节点作比较。如果发现新节点和之前的某个节点相同则说明该节点被遍历过2次链表有环。 时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1)
1.2 方法二哈希表
方法创建一个以节点ID为Key的HashSet集合用来存储曾经遍历过的节点。 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
1.3 方法三两个指针
方法首先创建2个指针p1和p2在Java里就是两个对象引用让它们同时指向这个链表的头节点。然后开始一个大循环在循环体中让指针p1每次向后移动1个节点让指针p2每次向后移动2个节点然后比较两个指针指向的节点是否相同。如果相同则可以判断出链表有环如果不同则继续下一次循环。 原理追及问题因为是环形的所以肯定能追上 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
/** 判断是否有环* param head 链表头节点* */
public static boolean isCycle(Node head){Node p1head;Node p2head;while(p2!nullp2.next!null){p1p1.next;p2p2.next.next;if(p1p2){return true;}}return false;
}/** 链表节点* */
public static class Node{int data;Node next;Node(int data){this.datadata;}
}public static void main(String[] args) {Node node1new Node(5);Node node2new Node(3);Node node3new Node(7);Node node4new Node(2);Node node5new Node(6);node1.nextnode2;node2.nextnode3;node3.nextnode4;node4.nextnode5;node5.nextnode2;System.out.println(isCycle(node1));
}1.4 扩展问题环的长度
方法当两个指针首次相遇证明链表有环的时候让两个指针从相遇点继续循环前进并统计前进的循环次数直到两个指针第2次相遇。此时统计出来的前进次数就是环长。
原理
指针p1每次走1步指针p2每次走2步两者的速度差是1步。当2个指针再次相遇时p2比p1多走了整整1圈。因此环长每一次速度差×前进次数前进次数
1.5 扩展问题出入环节点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sWGTmMQW-1595582632839)(漫画算法5.PNG)]
2. 最小栈
题目实现一个栈该栈带有出栈pop、入栈push、取最小元素getMin3个方法。要保证这3个方法的时间复杂度都是 O ( 1 ) O(1) O(1)
2.1 有问题的方法把栈中的最小元素下标暂存起来
问题这个元素出栈了咋办
2.2 方法存储栈中曾经的最小值
方法创建备胎栈B对每一个入栈的元素入栈最新的最小值/栈A出栈按情况让栈B出栈 最坏情况空间复杂度 O ( n ) O(n) O(n)
public static class MinStack{private StackInteger mainStacknew StackInteger();private StackInteger minStacknew StackInteger();/*** 入栈操作* param element 入栈的元素* */public void push(int element){mainStack.push(element);//如果辅助栈为空或者新元素小于或等于辅助栈栈顶则将新元素压入辅助栈if(minStack.empty()||elementminStack.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 stacknew 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());
}3. 最大公约数
题目求两个整数的最大公约数
3.1 方法一暴力枚举法
public static int getGreatestCommonDivisor(int a,int b){int bigab?a:b;int smallab?a:b;if(big%small0){return small;}for(int ismall/2;i1;i--){if(small%i0big%i0){return i;}}return 1;
}public static void main(String[] args){System.out.println(getGreatestCommonDivisor(25,5));System.out.println(getGreatestCommonDivisor(100,80));System.out.println(getGreatestCommonDivisor(27,14));
}时间复杂度 O ( m i n ( a , b ) ) O(min(a,b)) O(min(a,b))
3.2 方法二辗转相除法/欧几里得算法 秦九韶算法/霍纳算法 定理两个正整数a和bab它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
public static int getGrestestCommonDivisorV2(int a,int b){int bigab?a:b;int smallab?a:b;if(big%small0){return small;}return getGrestestCommonDivisorV2(big%small,small);
}public static void main(String[] args){System.out.println(getGrestestCommonDivisorV2(25,5));System.out.println(getGrestestCommonDivisorV2(100,80));System.out.println(getGrestestCommonDivisorV2(27,14));
}问题当两个整数较大时取模运算的性能会比较差。 时间复杂度可以近似为 O ( log ( m a x ( a , b ) ) ) O(\log{(max(a,b))}) O(log(max(a,b)))
3.3 方法三辗转相减法/更相减损法
定理两个正整数a和bab它们的最大公约数等于a-b的差值c和b之间的最大公约数。
public static int getGrestestCommonDivisorV3(int a,int b){if(ab){return a;}int bigab?a:b;int smallab?a:b;return getGrestestCommonDivisorV3(big-small,small);
}public static void main(String[] args){System.out.println(getGrestestCommonDivisorV3(25,5));System.out.println(getGrestestCommonDivisorV3(100,80));System.out.println(getGrestestCommonDivisorV3(27,14));
}问题更相减损术是不稳定的算法运算次数可能极多 最坏时间复杂度为 O ( m a x ( a , b ) ) O(max(a,b)) O(max(a,b))
3.4 方法四移位运算
当a和b均为偶数时gcd(a,b)2×gcd(a/2,b/2)2×gcd(a1,b1)。当a为奇数b为偶数时gcd(a,b)gcd(a,b/2)gcd(a,b1)。当a和b均为奇数时先利用更相减损术运算一次gcd(a,b)gcd(b,a-b)此时a-b必将为偶数然后又可以继续进行移位运算
public static int gcd(int a,int b){if(ab){return a;}if((a1)0(b1)0){ //都是偶数return gcd(a1,b1)1;}else if((a1)0(b1)!0){return gcd(a1,b);}else if((a1)!0(b1)0){return gcd(a,b1);}else{int bigab?a:b;int smallab?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));
}时间复杂度 O ( log ( m a x ( a , b ) ) ) O(\log{(max(a,b))}) O(log(max(a,b)))
4. 2的整数次幂
题目判断一个正整数是否是2的整数次幂
4.1 方法一暴力枚举法
public static boolean isPowerOf2(int num){int temp1;while(tempnum){if(tempnum){return true;}temp*2; //优化把乘以2的操作改成向左移位//temptemp1;}return false;
}public static void main(String[] args){System.out.println(isPowerOf2(32));System.out.println(isPowerOf2(19));
}时间复杂度 O ( log n ) O(\log{n}) O(logn)
4.2 方法二
如果一个整数是2的整数次幂那么当它转化成二进制时只有最高位是1其他位都是0。 这样的数一旦减1它的二进制数字就全部变成了1。 n(n-1)0
return (numnum-1)0;5. 无序数组排序后的最大相邻差
题目有一个无序整型数组如何求出该数组排序后的任意两个相邻元素的最大差值
5.1 方法一排序后求解
使用时间复杂度为 O ( n log n ) O(n\log{n}) O(nlogn)的排序算法如快排给原数组排序然后遍历求差。 时间复杂度 O ( n log n ) O(n\log{n}) O(nlogn) 在不改变原数组的情况下空间复杂度 O ( n ) O(n) O(n)
5.2 方法二利用计数排序的思想
利用计数排序的思想先求出原数组的最大值max与最小值min的区间长度kkmax-min1)以及偏移量dmin。创建一个长度为k的新数组Array。遍历原数组每遍历一个元素就把新数组Array对应下标的值1。遍历结束后Array的一部分元素值变成了1或更高的数值一部分元素值仍然是0。遍历新数组Array统计出Array中最大连续出现0值的次数1即为相邻元素最大差值。
问题数组元素可能差值悬殊
5.3 方法三利用桶排序的思想
利用桶排序的思想根据原数组的长度n创建出n个桶每一个桶代表一个区间范围。其中第一个桶从原数组的最小值min开始区间跨度是(max-min)/(n-1)。遍历原数组把原数组每一个元素插入到对应的桶中记录每一个桶的最大和最小值。遍历所有的桶统计出每一个桶的最大值和这个桶右侧非空桶的最小值的差数值最大的差即为原数组排序后的相邻最大差值。
时间复杂度 O ( n ) O(n) O(n)
public static int getMaxSortedDistance(int[] array){//1. 得到数列的最大值和最小值int maxarray[0];int minarray[0];for(int i1;iarray.length;i){if(array[i]max){maxarray[i];}if(array[i]min){minarray[i];}}int dmax-min;//如果max和min相等说明数组所有元素都相等返回0if(d0){return 0;}//2. 初始化桶int bucketNumarray.length;Bucket[] bucketsnew Bucket[bucketNum];for(int i0;ibucketNum;i){buckets[i]new Bucket();}//3. 遍历原始数组确定每个桶的最大最小值for(int i0;iarray.length;i){//确定数组元素所归属的桶下标int index((array[i]-min)*(bucketNum-1)/d);if(buckets[index].minnull||buckets[index].minarray[i]){buckets[index].minarray[i];}if(buckets[index].maxnull||buckets[index].maxarray[i]){buckets[index].maxarray[i];}}//4. 遍历桶找到最大差值int leftMaxbuckets[0].max;int maxDistance0;for(int i1;ibuckets.length;i){if(buckets[i].minnull){continue;}if(buckets[i].min-leftMaxmaxDistance){maxDistancebuckets[i].min-leftMax;}leftMaxbuckets[i].max;}return maxDistance;
}/*** 桶* */
private static class Bucket{Integer min;Integer max;
}public static void main(String[] args){int[] arraynew int[]{2,6,3,4,5,10,9};System.out.println(getMaxSortedDistance(array));
}6. 用栈实现队列
两个栈来来回回倒
static class StackQueue{private StackInteger stackAnew StackInteger();private StackInteger stackBnew StackInteger();/*** 入队操作* param element 入队的元素* */public void enQueue(int element){stackA.push(element);}/*** 出队操作* */public Integer deQueue(){if(stackB.isEmpty()){if(stackA.isEmpty()){return null;}transfer();}return stackB.pop();}/*** 栈A元素转移到栈B* */private void transfer(){while(!stackA.isEmpty()){stackB.push(stackA.pop());}}
}public static void main(String[] args){StackQueue stackQueuenew 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());
}入队操作的时间复杂度 O ( 1 ) O(1) O(1) 出队操作如果涉及元素迁移时间复杂度为 O ( n ) O(n) O(n)如果不用迁移时间复杂度为 O ( 1 ) O(1) O(1)
均摊时间复杂度 需要元素迁移的出队操作只有少数情况并且不可能连续出现其后的大多数出队操作都不需要元素迁移。 所以把时间均摊到每一次出队操作上面其时间复杂度是 O ( 1 ) O(1) O(1)。
7. 寻找全排列的下一个数
题目给出一个正整数找出这个正整数所有数字全排列的下一个数。
方法
从后向前查看逆序区域找到逆序区域的前一位也就是数字置换的边界。让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。把原来的逆序区域转为顺序状态。
//为方便数字的交换入参和返回值的类型都采用了整型数组
public static int[] findNearestNumber(int[] numbers){//1. 从后向前查看逆序区域找到逆序区域的前一位也就是数字置换的边界int indexfindTransferPoint(numbers);//如果数字置换边界是0说明整个数组已经逆序无法得到更大的相同数字组成的整数返回nullif(index0){return null;}//2. 把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置//复制并入参避免直接修改入参int[] numbersCopyArrays.copyOf(numbers, numbers.length);exchangeHead(numbersCopy,index);//3. 把原来的逆序区域转为顺序reverse(numbersCopy,index);return numbersCopy;
}private static int findTransferPoint(int[] numbers){for(int inumbers.length-1;i0;i--){if(numbers[i]numbers[i-1]){return i;}}return 0;
}private static int[] exchangeHead(int[] numbers,int index){int headnumbers[index-1];for(int inumbers.length-1;i0;i--){if(headnumbers[i]){numbers[index-1]numbers[i];numbers[i]head;break;}}return numbers;
}private static int[] reverse(int[] num,int index){for(int iindex,jnum.length-1;ij;i,j--){int tempnum[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 i0;i10;i){numbersfindNearestNumber(numbers);outputNumbers(numbers);}
}//输出数组
private static void outputNumbers(int[] numbers){for(int i:numbers){System.out.print(i);}System.out.println();
}解法名字典序算法 时间复杂度 O ( n ) O(n) O(n)
8. 删去k个数字后的最小值
问题给出一个整数从该整数中去掉k个数字要求剩下的数字形成的新整数尽可能小。给出的整数的大小可以超过long类型的数字范围
每一次删掉比右边数字大的数字第一个顺序的最后一个元素 依次求得局部最优解最终得到全局最优解的思想叫做贪心算法
8.1 性能不好的代码
/*** 删除整数的k个数字获得删除后的最小值* param num 原整数* param k 删除数量* */
public static String removeKDigits(String num,int k){String numNewnum;for(int i0;ik;i){boolean hasCutfalse;//从左向右遍历找到比自己右侧数字大的数字并删除for(int j0;jnumNew.length()-1;j){if(numNew.charAt(j)numNew.charAt(j1)){numNewnumNew.substring(0,j)numNew.substring(j1,numNew.length());hasCuttrue;break;}}//如果没有找到要删除的数字则删除最后一个数字if(!hasCut){numNewnumNew.substring(0,numNew.length()-1);}//清除整数左侧的数字0numNewremoveZero(numNew);}//如果整数的所有数字都被删除了直接返回0if(numNew.length()0){return 0;}return numNew;
}private static String removeZero(String num){for(int i0;inum.length()-1;i){if(num.charAt(0)!0){break;}numnum.substring(1,num.length());}return num;
}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));
}时间复杂度 O ( k n ) O(kn) O(kn) 缺点
每次内层循环都需要从头开始遍历所有数字应该停留在上一次删除的位置继续subString方法的时间复杂度是 O ( n ) O(n) O(n)性能不高
8.2 优化后的代码
/*** 删除整数的k个数字获得删除后的最小值* param num 原整数* param k 删除数量* */
public static String removeKDigits(String num,int k){//新整数的最终长度原整数长度-kint newLengthnum.length()-k;//创建一个栈用于接收所有的数字char[] stacknew char[num.length()];int top0;for(int i0;inum.length();i){//遍历当前数字char cnum.charAt(i);//当栈顶数字大于遍历到的当前数字时栈顶数字出栈相当于删除数字while(top0stack[top-1]ck0){top-1;k-1;}//遍历到的当前数字入栈stack[top]c;}//找到栈中第1个非零数字的位置以此构建新的整数字符串int offset0;while(offsetnewLengthstack[offset]0){offset;}return offsetnewLength?0:new String(stack,offset,newLength-offset);
}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));
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
9. 如何实现大整数相加
数组存储数位相加类似于列竖式
/*** 大整数求和* param bigNumberA 大整数A* param bigNumberB 大整数B* */
public static String bigNumberSum(String bigNumberA,String bigNumberB){//1. 把两个大整数用数组逆序存储数组长度等于较大整数位数1int maxLengthbigNumberA.length()bigNumberB.length()?bigNumberA.length():bigNumberB.length();int[] arrayAnew int[maxLength1];for(int i0;ibigNumberA.length();i){arrayA[i]bigNumberA.charAt(bigNumberA.length()-1-i)-0;}int[] arrayBnew int[maxLength1];for(int i0;ibigNumberB.length();i){arrayB[i]bigNumberB.charAt(bigNumberB.length()-1-i)-0;}//2. 构建result数组数组长度等于较大整数位数1int[] resultnew int[maxLength1];//3. 遍历数组按位相加for(int i0;iresult.length;i){int tempresult[i];temparrayA[i];temparrayB[i];//判断是否进位if(temp10){temptemp-10;result[i1]1;}result[i]temp;}//4. 把result数组再次逆序并转成StringStringBuilder sbnew StringBuilder();//是否找到大整数的最高有效位boolean findFirstfalse;for(int iresult.length-1;i0;i--){if(!findFirst){if(result[i]0){continue;}findFirsttrue;}sb.append(result[i]);}return sb.toString();
}public static void main(String[] args){System.out.println(bigNumberSum(426709752318,95481253129));
}时间复杂度 O ( n ) O(n) O(n)
优化不需要把原整数拆分得这么细只需要拆分到可以被直接计算的地步就可以了。 int最多可以有10位整数为防溢出可以把大整数的每9位作为一个元素进行加法运算。
10. 如何求解金矿问题
题目有位国王拥有5座金矿每座金矿的黄金储量不同需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金需要5个工人来挖掘有的金矿储量是200kg黄金需要3个工人来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖要么不挖不能派出一半人挖取一半的金矿。要求用程序求出要想得到尽可能多的黄金应该选择挖取哪几座金矿
标签动态规划 背包问题
最优子结构 边界 状态转移方程式
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZbTIVYdJ-1595582632843)(漫画算法6.png)]
10.1 优化前的代码
/*** 获得金矿最优收益* param w 工人数量* param n 可选金矿数量* param p 金矿开采所需的工人数量* param g 金矿储量* */
public static int getBestGoldMining(int w,int n,int[] p,int[] g){if(w0||n0){return 0;}if(wp[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 w10;int[] p{5,5,3,4,3};int[] g{400,500,200,300,350};System.out.println(最优收益getBestGoldMining(w,g.length,p,g));
}时间复杂度 O ( 2 n ) O(2^n) O(2n) 问题递归做了很多重复计算
10.2 优化step1
自底向上求解 以金矿为行工人人数为列逐一求解表格
/*** 获得金矿最优收益* param w 工人数量* param p 金矿开采所需的工人数量* param g 金矿储量* */
public static int getBestGoldMiningV2(int w,int[] p,int[] g){//创建表格int[][] resultTablenew int[g.length1][w1];//填充表格for(int i1;ig.length;i){for(int j1;jw;j){if(jp[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];
}时间复杂度 O ( n w ) O(nw) O(nw)
10.3 优化step2
在程序中并不需要保存整个表格无论金矿有多少座我们只保存1行的数据即可。在计算下一行时要从右向左统计把旧的数据一个一个替换掉。
/*** 获得金矿最优收益* param w 工人数量* param p 金矿开采所需的工人数量* param g 金矿储量* */
public static int getBestGoldMiningV3(int w,int[] p,int[] g){//创建当前结果int[] resultsnew int[w1];//填充一维数组for(int i1;ig.length;i){for(int jw;j1;j--){if(jp[i-1]){results[j]Math.max(results[j], results[j-p[i-1]]g[i-1]);}}}//返回最后1个格子的值return results[w];
}空间复杂度 O ( n ) O(n) O(n)
11. 寻找缺失的整数
问题在1个无序数组里有99个不重复的正整数范围是1 ~ 100唯独缺少1个1~100中的整数。如何找出这个缺失的整数
11.1 解法1
创建一个以1~100为Key的哈希表遍历数组删除元素对应的Key最后剩下的Key就是缺失的整数。 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
11.2 解法2
先把数组元素排序然后遍历如果发现两个相邻元素并不连续说明缺少的就是这两个元素之间的整数 时间复杂度 O ( n log n ) O(n\log{n}) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1)
11.3 解法3
先算出1~100的累加和然后再依次减去数组里的所有元素最后的差值就是所缺少的整数 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
11.4 问题扩展step1
题目一个无序数组里有若干个正整数范围是1~100其中99个整数都出现了偶数次只有1个整数出现了奇数次如何找到这个出现奇数次的整数
异或运算 同0异1 把数组里所有元素依次进行异或运算最后得到的就是那个整数 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
11.5 问题扩展step2
问题……如果数组里有2个整数出现了奇数次其他整数出现偶数次如何找出这两个整数呢
分治法 如果把数组分成两部分保证每一部分都包含1个出现奇数次的整数这样就与上一题的情况一样了 首先把数组元素依次进行异或运算最后结果中肯定至少有1个二进制位是1就用这个位置把数组分成两份就能把这两个要找的整数分开
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uOYZlpjp-1595582632846)(漫画算法7.png)]
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
public static int[] findLostNum(int[] array){//用于存储2个出现奇数次的整数int result[]new int[2];//第1次进行整体异或运算int xorResult0;for(int i0;iarray.length;i){xorResult^array[i];}//如果进行异或运算的结果为0则说明输入的数组不符合题目要求if(xorResult0){return null;}//确定2个整数的不同位以此来做分组int separator1;while(0(xorResultseparator)){separator1;}//第2次分组进行异或运算for(int i0;iarray.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[] resultfindLostNum(array);System.out.println(result[0], result[1]);
}Chapter6算法的业务应用
1. Bitmap算法/位图算法
用户标签→关系型数据库 Bitmap一块长度为10bit的内存空间算法用于对大量整数做去重和查询操作 用标签对应多个用户将其转为Bitmap做交集/并集 算法优势高性能的位运算 反向匹配全量的Bitmap异或
static class MyBitmap{//每一个word是一个long类型元素对应一个64位二进制数据private long[] words;//Bitmap的位数大小private int size;public MyBitmap(int size){this.sizesize;this.wordsnew long[(getWordIndex(size-1)1)];}/*** 判断Bitmap某一位的状态* param bitIndex 位图的第bitIndex位* */public boolean getBit(int bitIndex){if(bitIndex0||bitIndexsize-1){throw new IndexOutOfBoundsException(超过Bitmap有效范围);}int wordIndexgetWordIndex(bitIndex);return (words[wordIndex](1LbitIndex))!0;}/*** 把Bitmap某一位设置为true* param bitIndex 位图的第bitIndex位* */public void setBit(int bitIndex){if(bitIndex0||bitIndexsize-1){throw new IndexOutOfBoundsException(超过Bitmap有效范围);}int wordIndexgetWordIndex(bitIndex);words[wordIndex]|(1LbitIndex);}/*** 定位Bitmap某一位所对应的word* param bitIndex 位图的第bitIndex位* */private int getWordIndex(int bitIndex){//右移6位相当于除以64return bitIndex6;}
}public static void main(String[] args){MyBitmap bitMapnew MyBitmap(128);bitMap.setBit(126);bitMap.setBit(75);System.out.println(bitMap.getBit(126));System.out.println(bitMap.getBit(78));
}[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uP2R2Xxj-1595582632849)(漫画算法8.png)]
2. LRU算法
用哈希表做缓存哈希表过大
Least Recently Used 内存管理算法 假设长期不被使用的数据在未来被用到的几率也不大。因此当数据所占内存达到一定阈值时我们要移除掉最近最少被使用的数据。 数据结构——哈希链表
依靠哈希链表的有序性可以把Key-Value按照最后的使用时间进行排序。 大致来说就是把最近访问的用户添加/移动到最后面
Java里封装的轮子LinkedHashMap
static class LRUCache{private Node head;private Node end;//缓存存储上限private int limit;private HashMapString,Node hashMap;public LRUCache(int limit){this.limitlimit;hashMapnew HashMapString,Node();}public String get(String key){Node nodehashMap.get(key);if(nodenull){return null;}refreshNode(node);return node.value;}public void put(String key,String value){Node nodehashMap.get(key);if(nodenull){//如果Key不存在则插入Key-Valueif(hashMap.size()limit){String oldKeyremoveNode(head);hashMap.remove(oldKey);}nodenew Node(key,value);addNode(node);hashMap.put(key, node);}else{//如果Key存在则刷新Key-Valuenode.valuevalue;refreshNode(node);}}public void remove(String key){Node nodehashMap.get(key);removeNode(node);hashMap.remove(key);}/*** 刷新被访问的节点位置* param node 被访问的节点* */private void refreshNode(Node node){//如果访问的是尾节点则无需移动节点if(nodeend){return;}//移除节点removeNode(node);//重新插入节点addNode(node);}/*** 删除节点* param node 要删除的节点* */private String removeNode(Node node){if(nodeheadnodeend){//移除唯一的节点headnull;endnull;}else if(nodeend){//移除尾节点endend.pre;end.nextnull;}else if(nodehead){//移除头节点headhead.next;head.prenull;}else{//移除中间节点node.pre.nextnode.next;node.next.prenode.pre;}return node.key;}/*** 尾部插入节点* param node 要插入的节点* */private void addNode(Node node){if(end!null){end.nextnode;node.preend;node.nextnull;}endnode;if(headnull){headnode;}}class Node{Node(String key,String value){this.keykey;this.valuevalue;}public Node pre;public Node next;public String key;public String value;}
}public static void main(String[] args){LRUCache lruCachenew 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));
}注意这段代码不是线程安全的代码
对于用户系统的需求也可以使用缓存数据库Redis来实现Redis底层也实现了类似LRU的回收算法。
3. A星寻路算法
A*search algorithm
从起点绕过障碍物走到终点
OpenList可到达的格子 CloseList已到达的格子 FGH G从起点走到当前格子的成本也就是已经花费了多少步。 H在不考虑障碍的情况下从当前格子走到目标格子的距离也就是离目标还有多远。 FG和H的综合评估也就是从起点到达当前格子再从当前格子到达目标格子的总步数。
将起点放入OpenList→ 找出OpenList中F值最小的值作为当前格子将当前格子移入CloseList→将当前格子上下左右可到达的格子看它们是否在OpenList或CloseList中如果不在则将它们加入OpenList计算出相应的G、H、F值并把当前格子作为它们的“父节点”。循环 到达终点后顺着父节点依次回溯找到一条最佳路径
启发式搜索
//迷宫地图
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){ArrayListGrid openListnew ArrayListGrid();ArrayListGrid closeListnew ArrayListGrid();//把起点加入openListopenList.add(start);//主循环每一轮检查1个当前方格节点while(openList.size()0){//在openList中查找F值最小的节点将其作为当前方格节点Grid currentGridfindMinGird(openList);//将当前方格节点从openList中移除openList.remove(currentGrid);//当前方格节点进入closeListcloseList.add(currentGrid);//找到所有邻近节点ListGrid neighborsfindNeighbors(currentGrid,openList,closeList);for(Grid grid:neighbors){if(!openList.contains(grid)){//邻近节点不在openList中标记“父节点”、G、H、F并放入openListgrid.initGird(currentGrid,end);openList.add(grid);}}//如果终点在openList中直接返回终点格子for(Grid grid:openList){if((grid.xend.x)(grid.yend.y)){return grid;}}}//openList用尽仍然找不到终点说明终点不可到达返回空return null;
}private static Grid findMinGird(ArrayListGrid openList){Grid tempGridopenList.get(0);for(Grid grid:openList){if(grid.ftempGrid.f){tempGridgrid;}}return tempGrid;
}private static ArrayListGrid findNeighbors(Grid grid,ListGrid openList,ListGrid closeList){ArrayListGrid gridListnew ArrayListGrid();if(isValidGrid(grid.x,grid.y-1,openList,closeList)){gridList.add(new Grid(grid.x,grid.y-1));}if(isValidGrid(grid.x,grid.y1,openList,closeList)){gridList.add(new Grid(grid.x,grid.y1));}if(isValidGrid(grid.x-1,grid.y,openList,closeList)){gridList.add(new Grid(grid.x-1,grid.y));}if(isValidGrid(grid.x1,grid.y,openList,closeList)){gridList.add(new Grid(grid.x1,grid.y));}return gridList;
}private static boolean isValidGrid(int x,int y,ListGrid openList,ListGrid closeList){//是否超过边界if(x0||xMAZE.length||y0||yMAZE[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(ListGrid grids,int x,int y){for(Grid n:grids){if((n.xx)(n.yy)){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.xx;this.yy;}public void initGird(Grid parent,Grid end){this.parentparent;if(parent!null){this.gparent.g1;}else{this.g1;}this.hMath.abs(this.x-end.x)Math.abs(this.y-end.y);this.fthis.gthis.h;}
}public static void main(String[] args){//设置起点和终点Grid startGridnew Grid(2,1);Grid endGridnew Grid(2,5);//搜索迷宫终点Grid resultGridaStarSearch(startGrid,endGrid); //回溯迷宫路径ArrayListGrid pathnew ArrayListGrid();while(resultGrid!null){path.add(new Grid(resultGrid.x,resultGrid.y));resultGridresultGrid.parent;}//输出迷宫和路径路径用*表示for(int i0;iMAZE.length;i){for(int j0;jMAZE[0].length;j){if(containGrid(path,i,j)){System.out.print(*,);}else{System.out.print(MAZE[i][j],);}}System.out.println();}
}4. 红包算法
红包金额尽可能分布均衡为了避免高并发引起的一些问题先计算好每个红包拆除的金额并把它们放到一个队列里领取红包的用户要在队列中找到属于自己的那一份。公平
方法1二倍均值法
把每次随机金额的上限定为剩余人均金额的两倍
假设剩余红包金额为m元剩余人数为n 每次抢到的金额随机区间[0.01, m/n×2-0.01]元
保证了每次随机金额的均值是相等的
/*** 拆分红包* param totalAmount 总金额以分为单位* param totalPeopleNum 总人数* */
public static ListInteger divideRedPackage(Integer totalAmount,Integer totalPeopleNum){ListInteger amountListnew ArrayListInteger();Integer restAmounttotalAmount;Integer restPeopleNumtotalPeopleNum;Random randomnew Random();for(int i0;itotalPeopleNum-1;i){//随机范围[1剩余人均金额的2倍-1]分int amountrandom.nextInt(restAmount/restPeopleNum*2-1)1;restAmount-amount;restPeopleNum--;amountList.add(amount);}amountList.add(restAmount);return amountList;
}public static void main(String[] args){ListInteger amountListdivideRedPackage(1000,10);for(Integer amount:amountList){System.out.println(抢到金额new BigDecimal(amount).divide(new BigDecimal(100)));}
}方法2线段切割法
rid(2,1); Grid endGridnew Grid(2,5); //搜索迷宫终点 Grid resultGridaStarSearch(startGrid,endGrid); //回溯迷宫路径 ArrayList pathnew ArrayList(); while(resultGrid!null){ path.add(new Grid(resultGrid.x,resultGrid.y)); resultGridresultGrid.parent; } //输出迷宫和路径路径用表示 for(int i0;iMAZE.length;i){ for(int j0;jMAZE[0].length;j){ if(containGrid(path,i,j)){ System.out.print(,“); }else{ System.out.print(MAZE[i][j]”,); } } System.out.println(); } } ## 4. 红包算法
1. 红包金额尽可能分布均衡
2. 为了避免高并发引起的一些问题先计算好每个红包拆除的金额并把它们放到一个队列里领取红包的用户要在队列中找到属于自己的那一份。
3. 公平### 方法1二倍均值法
把每次随机金额的上限定为剩余人均金额的两倍假设剩余红包金额为m元剩余人数为n
每次抢到的金额随机区间[0.01, m/n×2-0.01]元保证了每次随机金额的均值是相等的java
/*** 拆分红包* param totalAmount 总金额以分为单位* param totalPeopleNum 总人数* */
public static ListInteger divideRedPackage(Integer totalAmount,Integer totalPeopleNum){ListInteger amountListnew ArrayListInteger();Integer restAmounttotalAmount;Integer restPeopleNumtotalPeopleNum;Random randomnew Random();for(int i0;itotalPeopleNum-1;i){//随机范围[1剩余人均金额的2倍-1]分int amountrandom.nextInt(restAmount/restPeopleNum*2-1)1;restAmount-amount;restPeopleNum--;amountList.add(amount);}amountList.add(restAmount);return amountList;
}public static void main(String[] args){ListInteger amountListdivideRedPackage(1000,10);for(Integer amount:amountList){System.out.println(抢到金额new BigDecimal(amount).divide(new BigDecimal(100)));}
}方法2线段切割法
将红包总金额想象成长线每个人抢到的金额是拆分出的子线段。每段长度由“切割点”决定。
