面试--- 常用算法总结
算法一般都是，数组排序, 数据查找， 数据计算 ，链表 , 拷贝。。。
开发来说，算法起码要会简单的常规的，真正的算法工程师才要懂那些难的。。。
力扣平台上很多算法总结
https://leetcode-cn.com/
常用的排序算法
https://developer.aliyun.com/article/772212?spm=5176.11533457.J_1089570.48.17ed5333JGS7fc
排序
一 冒泡
1 原理
通过多次嵌套循环比对交换位置；最终将有序的小的数字排在前面，大的排在后面；每一趟排序完成后会确定一个数字的最终位置。
冒泡这种算法时间复杂度高，当需要排序的元素较多时，程序运行时间很长。
2 demo
js 实现
let arr=[6,3,8,2,9,1];
let temp=0;
for(let i=0;i
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
console.log(arr);
java 实现
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for (int i = 0; i < nums.length - 1; i++) {//嵌套循环外部循环一次，内部循环全部
for (int j = 0; j < nums.length - i - 1; j++) {//以内部循环为准比对，但是要每次减掉外部的循环的次数缩小范围
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}3 demo
冒泡let maopao=(nums)=>{
//let aNew=[];
for(let i=0;i
for(let j=i+1;j
temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
//aNew.push(temp);
}
console.log(nums);
}
动画演示
二 快排--常问
1 原理
就是一个无序的数组，拿一个数(第一个或最后一个)当作参考；
用双向游标i/j进行排序(分别从左向右找比基数大的一个数；从右往做找比基数小的一个数；把2个数字交换位置，重复执行知道游标相等)后，
把所有比他小的放到左边，比他大的放到右边； 然后分别对左右两边数组通过递归的方法，重复上述动作排序。
PS:基准总是取序列开头的元素. 快排是对冒泡排序算法的一种改进。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
核心思路 ：
1. 在数组中选一个基准数（通常为数组第一个）；
2 用双向游标i/j进行排序(分别从左向右找比基数大的一个数；从右往做找比基数小的一个数；把2个数字交换位置，重复执行知道游标相等)
3. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；
4. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。
快排 ：就是在无序数组中循找 基数正确位置的过程。
1 选一个基数一般都是第一个，临时存起来。
2 2个游标循环迭代 ，j先从右到左 把比基数小的都放到基数左边； i在从左到右把比基数大的都放到基数右边。
3 直到 i==j 结束，此时i的位置就是 基数应该放的位置 ，基数赋值给 [i]=temp 。
4 左右两部分分别 迭代重复上述的动作 直到每个子集只有一个元素，即为全部有序。
2 demo
console.time("快排"); //可以记录开始执行时间
function quicksort(a,left,right){
if(left>right){ //一定要有这个判断，因为有递归left和i-1，若没有这个判断条件，该函数会进入无限死错位递归
return;
}
var i=left,
j=right,
jizhun=a[left]; //基准总是取序列开头的元素
while(i!=j){ //该while的功能为每一趟进行的多次比较和交换最终找到位置k。当i==j时意味着找到k位置了
while(a[j]>=jizhun&&i
a[i]=a[j];
a[j]=t
}
}
a[left]=a[i];//交换基准数和k位置上的数
a[i]=jizhun;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
var array=[4,7,2,8,3,9,12];
console.log(quicksort(array,0,array.length-1));//排完序后再看array是[2, 3, 4, 7, 8, 9, 12]
console.timeEnd("快排"); //可以记录结束执行时间
或者自己理解的写法>>>
let testSor=(nums,i,j)=>{//数组和 从右到左的结束位置 j-- ，从左到右开始位置 i++；目的寻找基数的正确位置
let first=nums[i]; //一般数组第一个作为基数比对
while(i
j--;
}
nums[i]=nums[j]; //当比基数小就替换到左边
if(i
}
nums[j]=nums[i]; //比基数大就替换到右边
}
nums[i]=first; //i===j的时候跳出循环
return i; //当前位置就是 基数的位置
}
let digui=(nums,i,j)=>{//递归
if(i
digui(nums,i,curIndex-1); //左边都是比基数小的，所以位置到基数位置curIndex-1 截止
digui(nums,curIndex+1,j); //右边都是比基数大的，所以位置从基数curIndex+1 开始
}
}
// 测试
let nums=[5,6,6,2,9,3];
digui(nums,0,nums.length-1);
console.log(nums);
三 插入排序
无序数组最终变成有序数组，不是说插入一个数字。
思路：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素比较，如果第一个该元素（已排序）大于新元素，将第一个元素和新元素替换位置；
- 重复(循环)步骤2，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。 也就是新元素后面的元素和它继续比对。
动画演示
demo
protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = 0; i < nums.length - 1; i++) { // 核心思路是拿当前值(从第一个开始) 和 下一个值进行比较。整个过程循环。//当前值下标(因为下标会变化所以不用直接赋值) int preIndex = i;
//下一个值 int curr = nums[i + 1];
//当下个值比当前值小 进行数字交换 while (preIndex >= 0 && curr < nums[preIndex]) { // 第一步： 把当前值替换给下一个值 nums[preIndex + 1] = nums[preIndex];
//第二步，移动下标，为了把后面的值付给当前值 preIndex--; } // 后面的值替换给当前值， 整个就进行了替换 nums[preIndex + 1] = curr; } }
查找
一 二分法查找
1 原理
需要是有序的数组， 那要查找的值，和序列最中间的值对比，(加入是升序)，那么小于对比的值 就往前面查找，
如果大于这个值，就往后面查找。
取中间值为比较对象，若等于关键字，则查找成功；若大于关键字，则在比较对象的左半区继续查找；若小于关键字，则在比较对象的右半区继续查找。不断重复上述过程直到查找成功，若所有查找区域无记录则查找失败。
2 demo
private int halfSearch(int[] arr, int target){
int min = 0;//数组最小索引
int max = arr.length - 1;//数组最大索引
int mid = (min + max) / 2;//数组中间索引
int i = 0;
while(true){
System.out.println("第" + ++i + "次,min:" + min + ";mid:" + mid + ";max:" + max);
//跟中间值进行比较
if (target > arr[mid]) {
min = mid + 1;
}
else if (target < arr[mid]) {
max = mid - 1;
}
else if(target == arr[mid]){
return mid;
}
//重新取中间索引
mid = (min + max) / 2;
//如果最小索引大于最大索引说明有问题，直接返回
if (min > max) {
return -1;
}
}
}
测试：：：
int[] arr = {10, 12, 15, 17, 19, 20, 22, 23, 24, 25, 30, 31, 32, 33, 34, 35, 40, 41, 42, 43, 44, 45, 46};
int target = 32;
int index = halfSearch(arr, target);
System.out.println(index);
或者>>>>
let str=(nums,target)=>{
let start=0, end=nums.length-1, mid=Math.floor(start+end)/2;
while(start<=end){
if(target===nums[mid]){ return mid;}
if(target>nums[mid]){
start=mid+1;
}else{
end=mid-1;
}
}
}
或者>>>>
let testNums= (arr,num)=>{
let
st = 0,
end = arr.length-1;
while(st<=end){
let mid = Math.floor((st+end)/2); //因为每次循环st和end都在变化 ，mid位置也在变化 所以要放到循环里面
if(num==arr[mid]){
return mid;
}else if(num>arr[mid]){
st = mid+1;
}else{
end = mid-1;
}
}
}
计算
一 计算2数之和，从数组中找出2个数字加起来等于目标值
let testReulst=(nums,target)=>{ //nums数组[],target和值
let maps=new Map(); //es6的动态hash表，set/get/has
for(let i=0;i
if(mus>0){ //比target小可能加起来
if(!maps.has(mus)) //如果没有说明当前被减掉的nums[i]在加上另外一个数字可以等于target
{
maps.set(nums[i],i); //关键2---先确定其中一个值，比如9-2=7
}
else{
return [maps.get(mus),i] //关键3---找到另外一个数字(当前的nums[i])和之前存的数字的下标，比如9-7=2;
}
}
}
} 二 数组/集合反转 算法 ps: 集合内容反转直接用自带的 .reverse() 或者 先循环找到下标index后在一个个的加入到新的数组； 集合转成字符串直接.toString ; 字符串转成集合直接for循环字符串然后一个个的加入到数组中； let testNums=(a)=>{
let inde=[];
for(let i=0;i
}
let news=[];
for(let j=0;j
news.push(a[inde[j]]);
}
}
三 判断是否是回文数
let testNum=(nums)=>{
let numStr=[...String(nums)] // 回文数，从左到右，从右到左 数字都是一样的；(负数不一样) ; 先数字转字符串到数组,然后从前到后从后到前循环比对，只要有一个不同就是错的
for(let i=0,j=numStr.length-1;i
if(numStr[i]!==numStr[j]){
return false
}
}
return true
}
或者
let isPalind = function(x) {
let str=`${Math.abs(x)}`; //先吧数字转成字符串 ，方式 1 后面+'' 2 String(x) 3 `${Math.abs(x)}`
let strNums=str.split(''); //字符串转成数组 ,方式 1 split('') 2 for循环字符串然后把值加到一个新集合 3 [...String(x)] 解构，数字的话需要先String
let newX=strNums.reverse(); // 回文数从左到右，从右到左 都是一样的，那么反转后也是一样的！ 数组反转
return Number(newX.join(''))==x //兼容负数，转成数字后和原数据比对
};
链表
三 反转链表
let testList=(lists)=>{ //链表不像数组没有索引，只能通过next来遍历，改变next之前要存起来
let temp,pre=null,cur=lists; //当next是null的时候完毕，pre赋给next
while(cur.next!==null){
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
或者 解构的方式
var reverseList = function(head) {
[curr, pre] = [head, null];
while(curr) [curr.next, pre, curr] = [pre, curr, curr.next];
return pre;
};
四 实现链表的核心思路
实现连表核心思路： 实现一个ArrayList 里面有一个方法比如find, findLast 等 比如 var myList = new ArrayList()
var arr = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
arr.forEach(item => myList.append(item)) , 链表中的节点类型描述如下：
class Node {
constructor(data) {
this.data = data; // 节点的数据域
this.prev = null; // 节点的指针域
this.next = null; // 节点的指针域
}
}
用prev和next两个指针域是为了实现双向链表，
在实现单链表时，prev指针并没有用到。
单链表是使用带有表头节点的形式来实现的;
实现其中方法的核心思想： 当前节点的next指针不为空就一直向下遍历。
例如 findLast() {
let currNode = this.head;
while (currNode.next) {
currNode = currNode.next;
}
return currNode;
}
// 在尾部添加元素 ，也是给next节点
append(element) {
let newNode = new Node(element);
let currNode = this.findLast();
currNode.next = newNode;
this.size++;
}
拷贝
一 浅拷贝：
只拷贝了原对象的地址，新对象和原对象指向同一个引用，改变其中一个另外一个会发生变化。
常用的方式 1 对象复制 2 Object.assign() 3 ...obj 扩展运算符
方式 1 对象/数组赋值 let a=[1,2,3] ; let b=a; b[0]=9; console.log(b); --[9,2,3] ; console.log(a); ---[9,2,3] 2 Object.assign 3 ...扩展运算符
二 深拷贝
深拷贝-----深拷贝主要是将另一个对象的属性值拷贝过来之后，另一个对象的属性值并不受到影响，因为此时它自己在堆中开辟了自己的内存区域，不受外界干扰。
浅拷贝主要拷贝的是对象的引用值，当改变对象的值，另一个对象的值也会发生变化。
方式 一 ...扩展运算符： let a=[1,2,3] ; let b=[...a]; b[0]=9; console.log(b); --[9,2,3] ; console.log(a); ---[1,2,3] b是分配了独立的内存地址，修改不会影响到a
方式二 Object.assign： let o={'a':1,'b':2,'c':3}; let b=Object.assign({},o); b.a=9; console.log(b.a); console.log(o.a);
方式三 slice截取： let a=[1,2,3] ; let b=a.slice(); b[0]=9; console.log(b[0]); console.log(a[0]);
方式四 数组concat： let a=[1,2,3]; let b=[] ; let c=b.concat(a); c[0]=6; console.log(a[0]); console.log(c[0]);
方式五 for循环 但是这5种方式都是简单深度拷贝 ，只能拷贝一层节点。 当对象里面 还有对象 {a:1,b:{d:1,e:2},c:9} ； 数组里面还嵌套的数组 [1,[3,4],2,3,4] 只能拷贝一层的节点，里面的无法深拷贝，值变化会影响另外一个。
方式六 粗暴深拷贝 粗暴深拷贝(抛弃对象的constructor)
使用jsON.stringify和jsON.parse实现深拷贝：JSON.stringify把对象转成字符串，再用JSON.parse把字符串转成新的对象；
缺陷：它会抛弃对象的constructor，深拷贝之后，不管这个对象原来的构造函数是什么，在深拷贝之后都会变成Object；这种方法能正确处理的对象只有 Number, String, Boolean, Array, 扁平对象，也就是说，只有可以转成JSON格式的对象才可以这样用，像function没办法转成JSON；
function deepCopy(obj1){
let _obj = JSON.stringify(obj1);
let obj2 = JSON.parse(_obj);
return obj2;
}
var aa = [1, [1, 2], 3, 4];
var bb = deepCopy(aa);
bb[1][0] = 2;
console.log(aa); // 1,1,2,3,4
console.log(bb); // 2,2,2,3,4
方式七 复杂深拷贝(相对完美)
递归拷贝实现深拷贝，解决循环引用问题 。
/** * 判断是否是基本数据类型 * @param value */
function isPrimitive(value){
return (typeof value === 'string' || typeof value === 'number' || typeof value === 'symbol' || typeof value === 'boolean') }
/** * 判断是否是一个js对象 * @param value */
function isObject(value){ return Object.prototype.toString.call(value) === "[object Object]" }
/** * 深拷贝一个值 * @param value */
function cloneDeep(value){ // 记录被拷贝的值，避免循环引用的出现
let memo = {};
function baseClone(value){
let res; // 如果是基本数据类型，则直接返回
if(isPrimitive(value)){ return value; // 如果是引用数据类型，我们浅拷贝一个新值来代替原来的值
}else if(Array.isArray(value))
{ res = [...value]; }
else if(isObject(value))
{ res = {...value}; } // 检测我们浅拷贝的这个对象的属性值有没有是引用数据类型。如果是，则递归拷贝
Reflect.ownKeys(res).forEach(key=>{
if(typeof res[key] === "object" && res[key]!== null){ //此处我们用memo来记录已经被拷贝过的引用地址。以此来解决循环引用的问题
if(memo[res[key]]){ res[key] = memo[res[key]]; }
else{ memo[res[key]] = res[key]; res[key] = baseClone(res[key])
}
}
})
return res;
}
return baseClone(value)
}
测试>>>
var objects = [1,{ 'a': 1 }, { 'b': 2 }];
var deep = cloneDeep(objects);
deep[0] = 2;
deep[1].a = 2;
console.log(objects[0]);//1
console.log(deep[0]);//2
console.log(objects[1].a);//1
console.log(deep[1].a);//2
二叉树
核心是
1 搞清反转二叉树的 对象数据结构 ，都有value值和left节点和right节点
2 思想是左右节点交互
3 递归调用
4 如果是用迭代 ，首先就要把二叉树转成数组 ---[tree]
5 然后for循环 数组，拿到里面的item 。
item里面有left/right节点 进行交换。
同时把子节点left/right 对象 在加入到最新的集合中 。 最新集合再拿去循环遍历交换。
一 二叉树反转
const demo1={
val:8,
left:{val:6,left:null,right:null},
right:{val:7,left:null,right:null}
}
let testNums=function(tree){
let temp=tree.left;
tree.left=tree.right;
tree.right=temp;
return tree;
}
let fuzha=(trees)=>{ // 复杂递归
if(!trees){return null;}
let temp=fuzha(trees.left);
trees.left=fuzha(trees.right);
trees.right=temp;
return trees;
}
二 平行二叉树
平衡二叉树: 就是left比自己val小,right比自己val 大 。 结合反转二叉树 应该可以理解
----这是它跟普通二叉树的唯一差别。
深度遍历 (从子节点--->根节点)
1 深度就是访问一个节点，先访问他的子节点，到了子节点，又去访问子节点的子节点，所以会一直跑到最深的地方去.
2 最深的那个访问完了，就会访问他的兄弟，他的兄弟访问完了，就会回退到访问他们的父节点（也就是次深的节点).
3 次深的访问完了，就会访问次深的兄弟，完了再向上，一直回到根节点。
如果是二叉树，这个里面还有前序，中序，后续，无非就是在访问子节点前访问当前节点，或者子节点中访问，或者访问子节点后访问.
前端实际业务里，子节点一般都是数组，所以不太碰到中序，前序、后序还是会有的。
广度遍历 (根节点--->子节点)
1 广度：定义一个队列，先把根节点放进去，搞一重while循环，条件是数组里还有节点，每一次从队列里拿出第一个，然后访问他，然后把他的子节点全部放进队列，然后进入下一次while，知道队列里的节点为空，就结束了。
总结：
1 深度就是先访问子节点，一层一层往里面访问，最后在到根节点；
3 广度就是搞个队列，把子节点存起来，每次访问队列里面的一个（找子节点），然后再把子节点存起来，直到队列为空。
其他
队列： 先进先出 ，数组push进 ，shift出 ；
堆栈：后进先出 ， 数组push进 , pop出。
动态规划： 就是反转递归 ，比较难。
map原理：map的时间复杂度是O1， 数组是On。
最后：
常用的东西，比如ES6，react vue用法，防抖节流之类的，要张口就来；
什么react原理，webpack原理，基础算法，最好装一装。