算法
2019-09-22 12:15:24 1 举报AI智能生成
算法学习
作者其他创作
大纲/内容
排序算法
时间复杂度O(n² )
冒泡排序
算法过程：<br>1、大循环，从第一个元素i遍历到最后一个元素arr.length-1<br>2、小循环，从第一个元素j遍历到最后一个元素arr.length-i-1<br>3、大循环标记是否发生交换isSorted，isSorted为true则结束（优化点：确定是否提前结束循环）<br>4、小循环设置lastExchangeIndex，大循环确定有序边界sortBorder=lastExchangeIndex，j遍历到sortBorder（优化点：确定有序边界）
鸡尾酒排序：<br>1、大循环控制从i到数组最后一个元素的遍历；<br>2、小循环从左遍历到右，然后从右遍历到左
选择排序
插入排序
希尔排序
时间复杂度O(nlogn)
快速排序
算法过程：（核心点分治法）<br>1、随机选择一个基准点pivot<br>2、设定left、right指针，<br>如果left != right，则有以下判断：<br>①如果left <= pivot，left++;<br>②如果right > pivot，right--；<br>③都不符合，则把left和right的元素交换；<br>如果left == right，则把left和pivot元素交换，返回left下标；<br>3、把得到的left下标设为基准点pivot，<br>①startIndex，pivot-1的范围再继续做快速排序；<br>②pivot+1、endIndex的范围再继续做快速排序；<br>4、如果startIndex >= endIndex，则结束排序。
归并排序
堆排序
时间复杂度O(n)
计数排序
算法过程：<br>1、创建最大数-最小数的范围数组<br>2、遍历数组，把对应下标的数字+1<br>3、最后把每个数组元素+前一个数组元素的和作为当前元素的值<br>4、排序数组时，当前元素的值-1
缺点：<br>1、数据分布不平衡时，会创建很多没有用的数组空间<br>2、不是整数无法采用下标
桶排序
算法过程：<br>1、求出最大数、最小数<br>2、根据元素数量创建对应的桶<br>3、遍历原始数组，分配到各个桶，依据算法（每个元素-最小数）* 桶的数量-1 / (最大数-最小数）<br>4、对每个桶的元素进行排序<br>5、遍历桶得到结果
缺点：<br>1、数据分布不平衡时，一样会存在浪费空间
基数排序
面试题
如何判定一个链表是有环链表？
扩展：<br>1、如何求出环的长度？<br>2、如何求出入环节点？
算法：<br>1、设定两个指针p1、p2，p1指向元素next，p2指向元素next.next<br>2、当p2指向元素不为null，p2.next指向元素不为null，<br>则不停地检测p1，p2所指向元素是否相等，相等则有环
实现一个栈，<br>该栈带有出栈、入栈、取最小元素3个方法，<br>要保证这3个方法的时间复杂度都是O(1)？
算法：<br>1、栈A存储原始数组，栈B存储最小数<br>2、当出栈时，如果栈A和B的栈顶相同，则栈B出栈，当前栈顶仍然有最小元素
求出两个整数的最大公约数？
算法：<br>1、碾转相除法<br>2、更相减损术<br>3、更相减损术+移位算术
如何判断一个数是否为2的整数次幂？
算法：<br>1、num&num-1进行与运算，结果为0则符合
无序数组排序后的最大相邻差？
算法：<br>1、借助桶排序的算法，每个桶统计最大数和最小数<br>2、比较相邻两个不为空的桶的A、B，B的最小值减去A的最大值，就是最大相邻差
如何用栈实现队列？
算法：<br>1、栈A实现入队<br>2、栈A弹出栈的元素，作为栈B的入栈数据，栈B出栈实现出队
找出一个正整数所有数字全排列的下一个数？<br>（核心：字典序算法）
算法：<br>1、假设原始数组A，找出A中倒序的元素下标index<br>2、从A最后一个元素开始比较，比较index-1的元素X，如果X小于最后一个元素，<br>则交换元素<br>3、从A最后一个元素开始比较，比较index的元素Y，如果Y大于最后一个元素，<br>则交换元素<br>输出结果，即为全排列的下一个数
给出一个整数，删去k个数字后的最小值？<br>（核心：贪心算法）
普通算法：<br>1、把整数用数组A存储<br>2、循环K次，每次把A从左到右比较大小，<br>当左边元素大于右边元素时，则删掉左边的数字<br>3、打印数组得到结果
进阶算法：<br>1、创建一个整数字符串A长度的栈B，得到A.length-K后的新长度L<br>2、遍历A的元素X在栈B入栈<br>3、如果栈B栈顶的元素大于当前A遍历的元素X，则X覆盖栈顶的元素，相当于让B出栈<br>4、找到栈中第一个非零数字的位置Offset，截取栈B从Offset到L的范围数字，得到结果
如何实现大整数相加？
物理存储结构
数组
查找：时间复杂度O(1)<br>插入：时间复杂度O(n)<br>
扩容：<br>把原来的数组长度 x 2
链表
查找：时间复杂度O(n)<br>插入：时间复杂度O(1)<br>
逻辑存储结构
线性结构
栈
后进先出
队列
先进先出
哈希表
哈希函数：<br>对Key进行HashCode，得到一个数字下标
扩容：<br>把原来的数组长度 x 2，重新哈希取模
非线性结构
二叉树
二叉排序树:<br>时间复杂度O(logn)<br>最坏情况O(n)
满二叉树
完全二叉树
树的自平衡
红黑树
AVL树
树堆
遍历
深度优先遍历
前序遍历
每一个节点，递归实现根->左节点->右节点
中序遍历
每一个节点，递归实现左节点->根->右节点
后序遍历
每一个节点，递归实现左节点->右节点->根
广度优先遍历
层序遍历
借助队列实现，把树的根节点入队列，如果队列不为空，继续以下过程：<br>①输出当前队列的队首节点，查找该节点的左右节点，如果存在则入队列<br>②重复第一步
二叉堆
最大堆、最小堆：<br>插入元素进行比较上浮<br>删除元素进行比较下沉
优先队列
0 条评论
下一页
