热门标签
热门文章
- 1Cosmopedia: 如何为预训练构建大规模合成数据集
- 2深度学习目标检测：yolov5环境配置，适合0基础小白，超详细_yolov5环境搭建
- 3uni.app上传照片并将路径转换成base64传给后端_uniapp blob(url)转成base64
- 4ZZULIOJ21级新生周赛(1)——命题人：朱会东老师_zzuli21级新生周赛(2)f
- 5Vue点击外部空间隐藏div_vue 隐藏元素 保留高度
- 6NLP智能客服会颠覆传统人工客服吗？_咪咕nlp智能客服
- 7应急响应详解
- 8android5.x怎么修改屏幕亮度_android 屏幕亮度200 screenbrightness设置多少?
- 9.json格式是什么？如何快速打开.json文件？_.json.gz是什么文件
- 10AI大模型提示工程 ④：自然语言处理与生成的全面指南
当前位置: article > 正文
算法总结_o(n) 线性单循环,循环次数与问题规模相关,例如顺序查找
作者：爱喝兽奶帝天荒 | 2024-07-26 10:35:38
赞
踩
o(n) 线性单循环,循环次数与问题规模相关,例如顺序查找
衡量算法优劣的主要标准是时间复杂度和空间复杂度。
时间复杂度
1.如果运行时间是常数量级，则用常数1表示。
2.只保留时间函数的最高阶项
3.如果最高阶项存在，则省去最高阶项前面的系数
空间复杂度
1.常量空间，存储空间固定，和输入规模没有直接关系，O(1)
2.线性空间，分配的空间是线性的集合（如数组），大小和输入规模成正比，O(n)
3.二维空间，分配的空间是二维数组集合，集合的长度和宽度和输入规模成正比，O(n2)
4.递归空间，递归操作的内存空间和递归的深度成正比，线性的，O(n)
数组
数组在内存中顺序存储，可以实现逻辑上的顺序表。
内存是由一个个连续的内存单元组成，每一个内存单元都有自己的地址。
数组的优势在于查找劣势在于插入删除，适合读操作多，写操作少的场景。
链表
链表是一种在物理上非连续、非顺序的数据结构。
链表在内存中的存储方式是随机存储，灵活有效的利用零散的碎片空间。
链表适合频繁的插入删除元素。
栈和队列
栈是一种线性的数据结构，先进后出。
队列是一种线性数据结构，先进先出。
数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。
循环队列队尾指针指向的位置永远空出一位，队列的最大容量比数组长度小1。
双端队列，可以先进先出，也可以先进后出。
优先队列，优先级高的先出，基于二叉堆实现。
散列表
散列表也叫哈希表，提供键值的映射关系。
散列表本质上也是一个数组，通过哈希函数将keyh和数组下标进行转换。
java为例，每一个对象都有属于自己的hashcode,是一个整型变量。
最简单的转换是按照数组长度进行取模运算，index=HashCode(key)%Array.length
数组长度有限，当插入的数据越来越多，数组下表可能重复，叫哈希冲突。解决方法：开放寻址法和链表法。
开发寻址法(ThreadLocal)：下标占用，则寻找下一个空挡位置。
链表法（HashMap）:数组中的每一个元素不仅是一个Entry对象还都是一个链表的头结点。
对于JDK中的散列表实现类HashMap来说，影响其扩容的因素：
1.Capacity,HashMap的当前长度。
2.LoadFactor,HashMap的负载因子，默认值为0.75f
需要进行扩容的条件:HashMap.size >=Capacity*LoadFactor
扩容首先创建一个新的空数组长度是原先的两倍，遍历原数组重新Hash
jdk8的HashMap会把链表转化为红黑树。
树
树和图是非线性数据结构。
树的最大深度被称为树的高度或深度。
二叉树
二叉树的每个节点最多有两个孩子节点。
满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，所有叶子节点都在同一层级。
完全二叉树：对于n个节点的二叉树，按层级顺序编号，跟同样深度的满二叉树到n节点的位置相同。（跟满二叉树相比，最后节点之前的节点都齐全）
二叉树可以用链式存储结构，数组表示。
数组存储时，按照层级顺序把二叉树的节点放到数组的对于位置上，如果节点的孩子空缺，数组的相应位置也空出来。
数组存储时，如果父节点的下标是parent,左孩子的下标2*parent+1,右孩子的下标2 *parnet+2
二叉树最主要的应用在于查找操作和维持相对顺序。
二叉查找树（二叉排序树）：
1、如果左子树不为空，左子树上所有节点的值均小于根节点的值。
2、如果右子树不为空，右子树上所有节点的值均大于根节点的值。
3、左右子树都是二叉查找树。
对于节点相对均衡的二叉查找树搜索节点的时间复杂度是O(logn)，和树的深度一样。
深度优先遍历：（可用递归或栈实现）
前序遍历：根节点、左子树、右子树
中序遍历：左子树、根节点、右子树
后序遍历：左子树、右子树、根节点
//二叉树的非递归前序排列 public static void preOrderTraveralWithStack(TreeNode root){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode treeNode = root; while(treeNode!=null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(treeNode !=null){ System.out.println(treeNode.data); stack.push(treeNode); treeNode = treeNode.leftChild; } //如果节点没有做孩子，则弹出栈顶节点，访问节点右孩子 if(!stack.isEmpty()){ treeNode = stack.pop(); treeNode = treeNode.rightChild; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
广度优先遍历：层序遍历（可用队列实现）
//二叉树层序遍历
public static void levelOrderTraversal(TreeNode root){
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.println(node.data);
if(node.leftChild!=null){
queue.offer(node.leftChild);
}
if(node.rightChild != null){
queueu.offer(node.rightChild);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
二叉堆
二叉堆是一种完全二叉树。分为最大堆和最小堆。
最大堆的任何一个父节点的值都大于或等于他的左右子节点的值。
最小堆的任何一个父节点的值都小于或等于它的左右子节点的值。
二叉堆的根节点叫做堆顶，最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。
二叉堆的自我调整：
1.插入节点:插入完全二叉树最后一个位置，与父节点比较，交换位置上浮O(logn)
2.删除节点：删除处于堆顶的节点，将堆的最后一个节点临时补充，和左右孩子进行比较，更小（大）的交换，下沉。O(logn)
3.构建二叉堆：所有非叶子节点一次下沉。O(n)
二叉堆是顺序存储。
public static void main(String[] args) { int[] array =new int[]{1,3,2,6,5,7,8,9,10,0}; upAdjust(array); System.out.println(Arrays.toString(array)); array = new int[]{7,1,3,10,5,2,8,9,6}; buildHeap(array); System.out.println(Arrays.toString(array)); } /** * 上浮调整 * @param array 待调整的堆 */ public static void upAdjust(int[] array) { int childIndex = array.length -1; int parentIndex = (childIndex-1)/2; //temp保存插入的叶子节点值，用于最后的赋值 int temp = array[childIndex]; while(childIndex>0&&temp<array[parentIndex]){ array[childIndex] = array[parentIndex]; childIndex = parentIndex; parentIndex = (parentIndex-1)/2; } array[childIndex] = temp; } /** * 下沉调整 * @param array 待调整的堆 * @param parentIndex 要下沉的父节点 */ public static void downAdJust(int[] array,int parentIndex){ int temp = array[parentIndex]; int childIndex = 2*parentIndex+1; while(childIndex <array.length){ //如果有右孩子，且右孩子小于左孩子，定位到右孩子 if(childIndex+1<array.length && array[childIndex+1]<array[childIndex]){ childIndex++; } if(temp <array[childIndex]){ break; } array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = 2*childIndex+1; } array[parentIndex] = temp; } /** * 构建最小堆 * @param array 待调整的堆 */ public static void buildHeap(int[] array){ for(int i=(array.length-2)/2;i>=0;i--){ downAdJust(array,i); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
优先队列
最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。（最大堆实现）
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。（最小堆实现）
排序算法
时间复杂度O(n2):冒泡排序，选择排序，插入排序，希尔排序（希尔排序特殊性能略优于O（n2),比不上O(nlogn)）
时间复杂度O(nlogn):快速排序，归并排序，堆排序
时间复杂度线性：计数排序，桶排序，基数排序
根据稳定性排序算法分为，稳定排序，不稳定排序。
稳定排序：值相同的元素在排序后仍然保持排序前的顺序。
不稳定排序：值相同额元素在排序后打乱了排序前的顺序。
冒泡排序
//优化版，已经有序不在进行之后的排序，对于后面已经有序的也不再进行排序 public static void sort(int[] array){ int disOrderLast = array.length-1; for(int i=0;i<array.length-1;i++){ //有序标记，每一轮的初始值都是true boolean isSorted = true; //无序数列的边界，每次比较只需要比到这里结束 int sortBorder = disOrderLast; for(int j=0;j<sortBorder;j++){ int temp =0; if(array[j]>array[j+1]){ temp = array[j]; array[j]=array[j+1]; array[j+1] = temp; //因为元素有交换，所以不是有序的，标记变为false isSorted = false; //把无序数列的边界更新为最后一次交换元素的位置 disOrderLast = j; } } //如何已经有序，不在进行之后的排序 if(isSorted){ break; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
鸡尾酒排序
基于冒牌排序，第一轮从左往右排序，第二轮从右往左，第三轮从左往右。。。。
鸡尾酒排序在大部分元素已经有序的情况下，可以减少回合数，缺点代码量几乎增加一倍。
public static void sort2(int[] array){ int temp =0; for(int i=0;i<array.length/2;i++){ //有序标记，每一轮的初始值都是true boolean isSorted = true; //奇数轮，从左向右比较和交换 for(int j=0;j<array.length-1-i;j++){ if(array[j]>array[j+1]){ temp = array[j]; array[j]=array[j+1]; array[j+1] = temp; //因为元素有交换，所以不是有序的，标记变为false isSorted = false; } } //如何已经有序，不在进行之后的排序 if(isSorted){ break; } isSorted = true; //偶数轮，从右向左比较和交换 for(int j=array.length-2-i;j>i;j--){ if(array[j]<array[j-1]){ temp = array[j]; array[j]=array[j-1]; array[j-1] = temp; //因为元素有交换，所以不是有序的，标记变为false isSorted = false; } } //如何已经有序，不在进行之后的排序 if(isSorted){ break; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
快速排序
快速排序属于交换排序，每一轮挑选一个基础元素，让其他比它大的元素移动到数列一边，比它小的移动到另一边，拆解数列为两部分。
平均时间复杂度为O(nlong)，最坏为O(n2)
时间复杂度O(logn)
//快速排序递归实现 public static void quickSort(int[] arr,int startIndex,int endIndex){ if(startIndex>=endIndex){ return; } //得到基准元素 int pivotIndex = partition(arr,startIndex,endIndex); //根据基准元素，分成两部分进行递归排序 quickSort(arr,startIndex,pivotIndex-1); quickSort(arr,pivotIndex+1,endIndex); } /** * 分治（双边循环法） * @param arr * @param startIndex * @param endIndex */ public static int partition(int[] arr,int startIndex,int endIndex){ //取第一个位置（也可以随机）的元素作为基准元素 int pivot = arr[startIndex]; int left = startIndex; int right = endIndex; while(left!=right){ //控制right指针比较并左移 while(left<right && arr[right]>pivot){ right--; } while (left<right&& arr[left]<=pivot){ left++; } if(left<right){ int p = arr[left]; arr[left] = arr[right]; arr[right] =p; } } //pivot和指针重合点交换 arr[startIndex] = arr[left]; arr[left] = pivot; return left; } /** * 分治（单边循环法） * @param arr * @param startIndex * @param endIndex */ public static int partition2(int[] arr,int startIndex,int endIndex){ //取第一个位置（也可以随机）的元素作为基准元素 int pivot = arr[startIndex]; int mark = startIndex; for(int i=startIndex+1;i<=endIndex;i++){ if(arr[i]<pivot){ mark++; int p = arr[mark]; arr[mark]= arr[i]; arr[i] = p; } } arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
堆排序
堆排序：把无序数组构建成二叉堆，从小到大则为最大堆，从大到小则为最小堆；循环删除堆顶，替换到二叉堆末尾，调整堆产生新的堆顶。
堆排序时间复杂度O(nlogn),空间复杂度O(1)
/** * 下沉调整 * @param array 待调整的堆 * @param parentIndex 要下沉的父节点 */ public static void downAdJust(int[] array,int parentIndex,int length){ int temp = array[parentIndex]; int childIndex = 2*parentIndex+1; while(childIndex <length){ //如果有右孩子，且右孩子小于左孩子，定位到右孩子 if(childIndex+1<length && array[childIndex+1]<array[childIndex]){ childIndex++; } if(temp <array[childIndex]){ break; } array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = 2*childIndex+1; } array[parentIndex] = temp; } /** * 堆升序 * @param array */ public static void heapSort(int[] array){ //把无序数组构建成最大堆 for(int i=(array.length-2)/2;i>=0;i--){ downAdJust(array,i,array.length); } System.out.println(Arrays.toString(array)); for(int i=array.length-1;i>0;i--){ int temp = array[i]; array[i] =array[0]; array[0]= temp; downAdJust(array,0,i); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
计数排序
当数列最大和最小值差距过大时，并不适合使用计数排序。
当数列元素不是整数时，也不适合用计数排序。
public static int[] countSort(int[] array){ //得到数列的最大值和最小值，并计算差值 int max = array[0]; int min = array[0]; for(int i=0;i<array.length;i++){ if(max<array[i]){ max = array[i]; } if(min>array[i]){ min = array[i]; } } int d = max -min; //创建统计数组并统计对应元素的个数 int[] countArray = new int[d+1]; for(int i=0;i<array.length;i++){ countArray[array[i]-min]++; } //统计数组做变形，后面的元素等于前面元素之和，为了获得元素的位置 for(int i=1;i<countArray.length;i++){ countArray[i] +=countArray[i-1]; } //倒序遍历原始数列，从统计数组中找到正确位置，输出到结果数列 int[] sortedArray = new int[array.length]; for(int i =array.length-1;i>=0;i--){ sortedArray[countArray[array[i]-min]-1] = array[i]; countArray[array[i]-min]--; } return sortedArray; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
桶排序
桶排序创建若干个有区间范围的桶，分别对桶内进行排序，输出所有元素。
public static double[] bucketSort(double[] array){ double max = array[0]; double min = array[0]; for(int i=0;i<array.length;i++){ if(max<array[i]){ max = array[i]; } if(min>array[i]){ min = array[i]; } } double d = max -min; //初始化桶 int bucketNum = array.length; ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum); for(int i=0;i<bucketNum;i++){ bucketList.add(new LinkedList<Double>()); } //遍历原始数组，将每个元素放入桶中 for(int i=0;i<array.length;i++){ int num = (int) ((array[i]-min)*(bucketNum-1)/d); bucketList.get(num).add(array[i]); } //对每个桶内部进行排序 for(int i=0;i<bucketList.size();i++){ //JDK底层采用了归并排序或归并的优化版本 Collections.sort(bucketList.get(i)); } //输出全部元素 double[] sortedArray = new double[array.length]; int index =0; for(LinkedList<Double> list:bucketList){ for(double element:list){ sortedArray[index]=element; index++; } } return sortedArray; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
希尔排序
又称为缩小增量排序，基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。
static void shell_sort(int[] numbers, int start, int end) { int increment = end - start + 1; //初始化划分增量 int temp=0; do { //每次减小增量，直到increment = 1 increment = increment / 3 + 1; for (int i = start + increment; i <= end; ++i) { //对每个划分进行直接插入排序 if (numbers[i - increment] > numbers[i]) { temp = numbers[i]; int j = i - increment; do { //移动元素并寻找位置 numbers[j + increment] = numbers[j]; j -= increment; } while (j >= start && numbers[j] > temp); numbers[j + increment] = temp; //插入元素 } } } while (increment > 1); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
归并排序
建立在归并操作上的一种有效的排序算法。该算法是采用分治法。将一个数组不断拆分为2个数组，最后没法拆分然后向上合并数组。
/** * 递归使用归并排序，对arr[l...r]的范围进行排序（前闭区间，后闭区间） * @param arr 待排序数组 * @param left 数组左 * @param right */ private static void mergeSort(int[] arr, int left, int right) { //对于递归，要处理递归到底的判断，这里就是left>=right。 if( left >= right) return; int mid = (left+right)/2; mergeSort(arr, left, mid); mergeSort(arr, mid+1, right); merge(arr, left, mid, right); //将左右两部分，利用临时数组进行归并 } /** * 将arr[l...mid]和arr[mid+1...r]两部分进行归并 * @param arr * @param left * @param mid * @param right * i:临时数组左边比较的元素下标；j:临时数组右边比较的元素的下标；k:原数组将要放置的元素下标 */ private static void merge(int[] arr, int left, int mid, int right) { int[] aux = new int[right - left + 1]; //临时辅助数组 for (int i = left; i <= right; i++) aux[i - left] = arr[i]; /*减去的left是原数组相对于临时数组的偏移量*/ int i = left, j = mid + 1; for (int k = left; k <=right; k++) { if (i > mid) { //检查左下标是否越界 arr[k] = aux[j - left]; j++; } else if (j > right) { //检查右下标是否越界 arr[k] = aux[i - left]; i++; } else if (aux[i - left] <= aux[j - left]) { arr[k] = aux[i - left]; i++; } else { arr[k] = aux[j - left]; j++; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
查找算法
顺序查找
顺序查找适合于存储结构为顺序存储或链接存储的线性表
顺序查找也称为线性查找属于无序查找算法，时间复杂度O(n)
int sequenceSearch(int a[],int value,int n){
for(int i=0;i<n;i++){
if(a[i] == value){
return i;
}
}
return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
二分查找
元素必须是有序的，如果是无序的则要先进行排序操作。
也称为是折半查找，属于有序查找算法，时间复杂度为O(log2n)
//二分查找（折半查找） int BinarySearch1(int a[], int value, int n){ int low, high, mid; low = 0; high = n-1; while(low<=high) { mid = (low+high)/2; if(a[mid]==value) return mid; if(a[mid]>value) high = mid-1; if(a[mid]<value) low = mid+1; } return -1; } //二分查找，递归版本 int BinarySearch2(int a[], int value, int low, int high){ int mid = low+(high-low)/2; if(a[mid]==value) return mid; if(a[mid]>value) return BinarySearch2(a, value, low, mid-1); if(a[mid]<value) return BinarySearch2(a, value, mid+1, high); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
插值查找
基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
时间复杂度均为O(log2(log2n))
int InsertionSearch(int a[], int value, int low, int high)
{
int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
if(a[mid]==value)
return mid;
if(a[mid]>value)
return InsertionSearch(a, value, low, mid-1);
if(a[mid]<value)
return InsertionSearch(a, value, mid+1, high);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
知名算法
LRU算法/最近最少使用算法
使用哈希链表实现.
class Node{ public Node pre; public Node next; private String key; private String value; Node(String key,String value){ this.key = key; this.value = value; } } private Node head; private Node end; //缓存存储上限 private int limit; private HashMap<String,Node> hashMap; public LRUTest(int limit){ this.limit = limit; hashMap = new HashMap<>(); } 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); } } private void remove(String key){ Node node = hashMap.get(key); removeNode(node); hashMap.remove(key); } /** * 刷新被访问的节点位置 * @param node */ private void refreshNode(Node node) { //如果访问的是尾节点，则无需移动节点 if(node ==end){ return; } //移除及节点 removeNode(node); addNode(node); } /** * 删除节点 * @param node * @return */ 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(node != null){ end.next = node; node.pre = end; node.next = null; } end = node; if(head ==null){ head = node; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
面试中常见算法
如何判断链表有环
追及问题，定义2个指针，一个指针步长1，一个指针步长2，如果相遇则有环；第一次相遇到第二次相遇则为环长；头结点到入环点的距离等于首次相遇点回到入环点的距离，可得入环结点。
/**
*判断是否有环
*/
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(pi == p2){
return true;
}
}
return false;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
最小栈的实现
实现一个栈，有入栈，出栈，取最小元素，用两个栈实现,辅助栈存储最小元素。
private Stack<Integer> mainStack = new Stack<Integer>(); private Stack<Integer> minStack = new Stack<Integer>(); public void push(int element){ mainStack.push(element); //辅助栈为空或者新元素小于等于辅助栈栈顶，则新元素压入辅助栈 if(minStack.isEmpty()||element<=minStack.peek()){ minStack.push(element); } } public Integer pop(){ //如果出栈元素和辅助栈栈顶元素相同，辅助栈出栈 if(mainStack.peek().equals(minStack.peek())){ minStack.pop(); } return minStack.pop(); } public int getMin() throws Exception { if (mainStack.isEmpty()) { throw new Exception("stack is empty"); } return minStack.peek(); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
求出最大公约数
辗转相除法/欧几里得算法：两个正整数a,b(a>b),他们的公约数等于a除以b的余数c和b之间的最大公约数。（取模运算复杂）
更相减损术：两个正整数a,b(a>b),他们的公约数等于a-b的差c和较小数b的最大公约数。（性能不稳定）
//辗转相除法和更相减损术结合 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); }eles if((a&1)!=0 && (b&1)==0){ return gcd(a,b>>1); }else{ int big =a>b?a:b; int small = a>b?b:a; return gcd(big-small,small); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
判断一个数是否是2的整数次幂
计算n&(n-1)的结果是不是0
public static boolean isPowerOf2(int n){
return (n&(n-1)) == 0;
}
- 1
- 2
- 3
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/884823
推荐阅读
相关标签
