虽然学过java和Python,但是还是JavaScript比较熟练,因此算法学习全部用JavaScript来写
算法不会被程序语言所限制,也不会一个实现只有一个算法
常见数据结构(数组,列表,映射,堆栈,队列,哈希表,树,图)
算法(排序,双指针,查找,分治,动态规划,递归,回溯,贪心,位运算,DFS,BFS)
大O表示法是专门用来表示算法速度有多快的,不同算法所耗时间的时间增速度不同
一个算法执行的时间和解决问题的规模大小相关
假设一个列表有n个元素,遍历全部元素,要执行n次,大O表示法为O(n)
大O表示法不是表示消耗的时间,而是通过操作元素的次数决定的,一个优秀的算法操作元素次数肯定很少
时间复杂度:
O(1): Constant Complexity: Constant 常数复杂度 O(log n): Logarithmic Complexity: 对数复杂度 O(n): Linear Complexity: 线性时间复杂度 O(n^2): N square Complexity 平⽅方 O(n^3): N square Complexity ⽴立⽅方 O(2^n): Exponential Growth 指数 O(n!): Factorial 阶乘
算法的特点:有穷性(必须要在一定的时间内完成,不能无限循环),确定性(每一条指令都有明确的目的,不产生二义性),可行性(可以通过基础运算来实现),输入输出(要有0个或者多个输入,要有1个或者多个输出)
删除有序数组中的重复项
保证有序数组中的元素是不重复的,也就是说不存在重复的元素
有序数组中重复的肯定是挨着的,只需要遍历数组全部的元素,前面和后面进行比较,如果相同则删除后面的
例如:
let arr = function(nums) {
if(nums == null || nums.length == 0){
return 0
}
let b = 0
for(let a=0;a<nums.length;a++){
if(nums[b]!=nums[a]){
nums[++b] = nums[a]
}
}
return ++b
}
b作为覆盖,a作为查询,当b的值不等于a查询到的值时,b++的值等于a的值,等于的时候b不改变,当不相等再等于到b上
搜索数组的目标值,返回其索引值
通过有序整型数组和一个目标值,寻找目标值,并且返回其索引值,当目标值不存在时,返回-1
let search = function(nums, target) {
for(let a=0;a<nums.length;a++){
if(nums[a] == target){
return a
}
}
return -1
}
字符串反转
将数组nums里面的字符串,顺序倒过来,在不创建新数组的位置前提下
let reverseString = function(nums) {
var a=0,b=nums.length-1
while(a<b){
let temp =nums[a]
nums[a] = nums[b]
nums[b] = temp
a++
b--
}
}
二分查找
二分查找实质就是将数组分开,用中间的数值来对目标值进行比较,大了就是减,小了就加
一直找到最后的那个目标值,这个算法对比冒泡一个个查找更有效,因为其只需要遍历极少的次数
注意:二分查找必须是有序数组,无序数组没有用,因为它要一个个进行大小比较
像猜1到100的数,就可以从50开始比较,如果50大了,那么就是1到49之间有目标值,如果猜25,如果小了,那么就是26到49的之间有目标数,一直判断,直到等于目标值,依此类推,每次判断都会少一半的错误值,例如:n个元素的列表,二次查找的只需要log2n次就可以找到目标值(log是指对数,指的是对求幂的逆运算,例如6的3次方就是216,那么用对数表示为log6 216,求6要相乘几次才能得到216这个结果,结果为3)
例如:
function xyz(list,int){
var a = 0
var b = list.length -1
while (a <= b) {
var c = a + Math.floor((b - a) / 2)
if(list[c] < int){
a = c +1
}else if(list[c] > int){
b = c - 1
}else{
return c
}
}
return -1
}
var abc = [1,3,5,6,7,10,30,55,66,99,1234]
xyz(abc,99)
如果猜测的次数和列表长度相同,那么就是线性时间(linear time,O(n)),算法的运行时间会以不同的速度而增加,对数为O(log n )
选择排序(链表和数组)
链表指的是链表中的元素可以存储在内存的任何地方,链表的优点在于插入元素(删除元素),只需要O(1)就可以了,但是因为它索引的地址是随机的,因此读取一个元素,可能需要O(n)
数组的优点在于读取元素,只需要O(1)就可以了,而插入元素,就可能需要O(n)了,因为直接插入元素到数组,需要将后面的元素往后移动,而大0表示法是指最糟糕的情况,并不是一定要执行那么多次
注意:数组索引编号是从0开始的
选择排序的时间复杂度是O(n²),该算法是先在找到最大或者最小的元素,放在排序序列的起始位置,然后再从剩余的序列中继续寻找最大或者最小的元素,将其放在已经排序的序列的末尾,重复,一直到全部元素都排序完毕
例如:
function data(arr) {
const len = arr.length // 获取目标的长度
let minindex, temp // 定义最小索引和排序存储
for (let i = 0; i < len - 1; i++) {
minindex = i // 获取当前最小索引(待排序)
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minindex]) { // 寻找最小的数
minindex = j //将最小的数的索引进行存储
}
}
temp = arr[i] // 最小索引的值等于temp
arr[i] = arr[minindex] // 最小索引的值等于最小的数的索引
arr[minindex] = temp // 最小的数的索引等于temp
}
return arr
}
const abc =[1,3,5,2,9,4,6,10,7,18,8]
data(abc)
递归
“Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!”—Leigh caldwell
递归说白了就是递归函数自己调用自己,因为存在自己调用自己的情况,因此要确保递归函数在什么情况就应该停止,而不是无限循环下去,递归函数要有俩个条件,基线条件(base case)和递归条件(recursive),递归条件就是递归函数调用自己,基线条件是在什么条件下不再调用自己(例如将递归条件放在一个if判断中,当满足递归条件就递归,不满足就基线条件)
栈(call stack)
栈是一种数据结构,存在着转移控制权,转移数据,清除或者释放数据的特性(临时存储,压入,弹出),可以用来存储多个函数的变量,当需要该变量的时候插入,不需要就弹出,当栈很高的时候,会导致存储了大量函数要调用的变量,会占用大量的内存,因此在这种情况下循环或者尾递归可能更好
递归:如果一个函数可以在内部调用其本身,那么这个函数是递归函数,函数内部自己调用自己
递归效果和循环是一致的,所有递归容易出现栈溢出错误(stack overflow),需要加上退出条件return
例如:
var num = 1;
function hallo(){
console.log(num);
if(num == 10){
return;
}
num++;
hallo();
}
hallo();
递归求阶乘
阶乘:指的是一个正整数的阶乘是所有小于及等于该数的积,并且0的阶乘为1
function hallo(num){
if(num == 1){
return 1;
}
return num * hallo(num - 1)
}
console.log(hallo(10)) // 3628800
递归求斐波那契数列(兔子序列)
特点,第一个数加第二个数等于第三个数,第二个数加第三个数,依次类推
因此需要计算得到斐波那契数列对应数字,只需要指定位置的前两项(n-1,n-2)就可以得出第n个斐波那契数列对应的数字
例如:
function hallo(num){
if(num == 1 || num == 2){
return 1;
}
return hallo(num-1) + hallo(num-2);
}
console.log(hallo(10));
快速排序
divide and conquer(D&C):找出基数条件,分解问题(缩小问题的规模),一直到符合基数条件
注意:D&C定义要求每次递归调用,都必须缩小问题的规模,(缩小问题的规模可以依赖于欧几里得算法(求最大公约数的算法))
当基数条件为数组为空或者只有一个元素时,直接返回数组(因为不需要排序),因此快速排序的元素个数必须大于等于2
快速排序的工作原理就是从数组中选择一个元素,这个元素叫基准值(pivot),然后找到比基准值小的元素和比基准值大的元素,这时候有一个比基准值小的数值组成的子数组和一个比基准值大的数值组成的子数组,和一个基准值,这个被叫为分区(partitioning),如果子数组是有序的,直接左边子数组加基准值加右边子数组就完成排序了,如果不是有序的,那么将那俩个子数组进行快速排序,再合并(当子数组只有一个元素,那么就不需要进行排序了)
快速排序的时间复杂度取决于基准值,快速排序平均情况下,时间复杂度为O(n log n),一般情况下大O表示法会忽略常量(算法所需要的固定量),因为在数量很大的计算中,常量根本没有影响,但是当时间复杂度相同的时候,就可以看常量了,常量越小,算法的时间复杂度越小,最糟糕的情况下快速排序的时间复杂度为为O(n),而最佳情况下为O(log n)
散列表(散列映射,字典,关联数组)
散列函数:当输入一个数据,将返回一个数据,而且返回的数据是一致的(输入数据一样的情况下,得到的数据必须要一样,输入不同数据的时候,得到的数据也必须不一致),散列函数必须知道数组有多大(只返回有效数据),散列函数精确指出某个数据的存储位置,不需要查找,平均情况下时间复杂度为O(1)
散列表由键和值组成,当输出键或者值的时候,可以获得对应的值或者键,散列表可以用于避免出现重复数值,缓存(记住数据,避免重新计算数据或者重新处理数据)
注意:如果散列表存储的链表很长,那么散列表的速度将会变慢,而且还可能存在冲突(多个数据占用一个位置,如果要解决冲突,只能在这个位置上再建立一个链表,来存储多个数据)
填装因子:计算数组被占用的位置数,算法为散列表包含的元素数除以位置总数,得到的值为该散列表的填装因子,当填装因子大于1的时候,就表示该数组位置数不足,必须要添加位置(调整长度(resizing)),填装因子越小,出现冲突的可能就越小,散列表的性能就越高
广度优先搜索(breadth-first search,BFS)
广度优先搜索可以解决最短路径问题(shortest-path problem),用于图的查找算法
图由一个个节点和边组成,一个节点可能和多个节点之间直接相连,那么这些节点又被叫为邻居,图被用于模拟不同的东西是如何相连的
广度优先搜索可以解决图的两个问题,在某节点上,有前往某个节点的路径吗?和在某节点上,怎么前往某个节点最快,广度优先搜索的原理就是先搜索和起点直接连接的节点(一度关系),再查找二度关系(和二度关系有直接连接的节点),从起点开始向外延伸,如果目标在一度关系上,那么前往该目标的节点存在,而且可以直接前往,如果目标在二度关系上,那么找到二度关系于一度关系相连的路径上,这必须按照添加的顺序才能查找出来
队列(queue):一种先进先出的数据结构(First In First Out,FIFO),栈则是后进先出的数据结构(Last In First Out,LIFO)
深度优先算法
狄克斯特拉算法
贪婪算法
动态规划
K最近相邻算法
堆/栈/队列/优先级队列
链表/反向链表/Hash/二叉树/红黑树
大O标识法和时间复杂度