常用算法

动态规划经典例题（斐波那契数列） 贪心思想分配饼干不重叠的区间个数根据身高和序号重组队列 二分查找求开方有序数组中的单一元素查找区间 分治搜索BFSDFS 链表反转链表合并两个排序的链表 排序冒泡排序选择排序插入排序快速排序归并排序 刷题技巧： 1.审题先判断陷阱。 看到题目第一先看是否有时间复杂度、空间复杂度的要求。（比如大数问题、递归多了栈溢出等问题） 根据自己猜测判断使用简单方法，还是复杂方法来做。 然后再顺便看下是否需要判断边界条件（一般都需要出错判断） 有时间复杂度要求的，可以优化排序、动态规划、以空间换时间等 有空间复杂度要求的，可以用循环代替递归、动态规划代替递归等 这里讲下为什么不说贪心，第一理论上所有贪心可以解决的问题都可以用动态规划来做，第二正因如此，许多公司难题也就只考到了动态规划。 所以请一定一定要掌握 动态规划。 2、重点掌握的几个算法 快排和归并排序、深度和广度遍历、二分查找（能手撕）、动态规划、回溯法。 部分例题来自 LeetCode。

动态规划

经典例题（斐波那契数列）

现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39。

function fibonacci(n) { var n1 = 1, n2 = 1, sum; for (let i = 2; i < n; i++) { sum = n1 + n2 n1 = n2 n2 = sum } return sum } fibonacci(30)

贪心思想

分配饼干

例题：每个孩子都有一个满足度 grid，每个饼干都有一个大小 size，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。 1.给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足度比较大的孩子。 2.因为满足度最小的孩子最容易得到满足，所以先满足满足度最小的孩子。

var findContentChildren = function(g, s) { if(g ==null || s ==null) return 0; g= g.sort((a,b)=> a-b); s= s.sort((a,b)=> a-b); let i =0,j=0; while(i<g.length && j< s.length){ if(g[i] <=s[j]){ i++; } j++; } return i; };

不重叠的区间个数

例题：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 详解：该题是典型的调度问题，通过贪心算法可找到最优解，主要思路是确保每次剩下的区间可选的余地最大，因此每次选择end的值最小的区间.

var eraseOverlapIntervals = function(intervals) { if(intervals.length ===0) return 0; intervals= intervals.sort((a,b) => a[1]-b[1]); let end =intervals[0][1]; let cnt=0; for(let i=1;i<intervals.length;i++){ if(intervals[i][0]<end){ cnt ++; }else{ end =intervals[i][1]; } } return cnt; };

根据身高和序号重组队列

例题：一个学生用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个学生的身高比他高或者和他一样高。 先根据身高由高到低排序，如果个子一样，则按照k从小到大排列。 步骤分解：

原始输入： [[7,0] [4,4] [7,1] [5,0] [6,1] [5,2]] sort处理： [[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]] 遍历people： ===== i=0 ↓：p[0] 应该在index=0的位置 [[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]] [[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]] ok ===== i=1 ↓：p[1]应该在index=1的位置 [[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]] [[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]] ok ===== i=2 ↓：p[2]应该在index=1的位置 [[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]] [[7 0] [6 1] [7 1] [5 0] [5 2] [4 4]] ok ===== i=3 ↓：p[3]应该在index=0的位置 [[7 0] [6 1] [7 1] [5 0] [5 2] [4 4]] [[5 0] [7 0] [6 1] [7 1] [5 2] [4 4]] ok ===== i=4 ↓：p[4]应该在index=2的位置 [[5 0] [7 0] [6 1] [7 1] [5 2] [4 4]] [[5 0] [7 0] [5 2] [6 1] [7 1] [4 4]] ok ===== i=5 ↓：p[5]应该在index=4的位置 [[5 0] [7 0] [5 2] [6 1] [7 1] [4 4]] [[5 0] [7 0] [5 2] [6 1] [4 4] [7 1]] ok 最终结果： [[5 0] [7 0] [5 2] [6 1] [4 4] [7 1]]

代码块：

var reconstructQueue = function(people) { let ans=[] if(people.length ===0||people ==null ||people[0].length ===0) return []; people.sort((a,b) =>{ return a[0] == b[0]? a[1]-b[1]:b[0]-a[0]; //对比身高，相等就进行k进行升序，不相等，进行身高降序 }); people.forEach(item=>{ ans.splice(item[1],0,item) }) return ans; };

二分查找

二分法查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤： （1）首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。 （2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。 （3）如果某一步数组为空，则表示找不到目标元素。

//正常实现 function binary_search(nums,key){ var l=0,r=nums.length-1; while(l<r){ var m=l+(r-l)/2; if(nums[m]===key){ return m; }else if(nums[m] >key){ r= m-1; }else{ l= m+1; } } return -1; } //m计算方式： m=(l+r)/2; m=l+(r-l)/2; //未成功查找的返回值 循环退出时如果仍然没有查找key，那么表示查找失败。可以有两种返回值： -1：以一个错误码表示没有查找到key 1：将key插入到nums中的正确位置

求开方

题：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

var mySqrt = function(x) { if(x<=-1){ return x; } let l =0,r=x; while(1<r){ let m =Math.floor( l+(r-l)/2); let sqrt = x/m; if(sqrt == m){ return m; }else if(m >sqrt){ r =m -1; }else{ l= m+1; } } return r; };

有序数组中的单一元素

题目：给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 分析：将线性搜索转换为二分搜索，查看中间的元素来判断我们的答案在中间还是左边或右边。我们这个数组始终是奇数，因为只有一个元素出现一次，其余元素出现两次。 当我们从中心移除一对元素时发生的情况。将剩下左子数组和右子树组。 划分到底在左右哪个区间，判断依据就是数组的长度，偶数说明不在，奇数说明在里边。

var singleNonDuplicate = function(nums) { if(nums.length == 0) return null; let l=0,r =nums.length-1; while(l<=r){ let m =Math.floor(l+(r-l)/2); if(nums[m] == nums[m-1]){ if(m%2 == 0){ r=m-2; }else{ l =m+1; } }else if(nums[m] == nums[m+1]){ if (m %2 == 0) { l = m + 2 } else { r = m - 1 } }else{ return nums[m] } } return -1; };

查找区间

题目描述：给定一个有序数组 nums 和一个目标 target，要求找到 target 在 nums 中的第一个位置和最后一个位置。 分析：可以用二分查找找出第一个位置和最后一个位置，但是寻找的方法有所不同，需要实现两个二分查找。

var searchRange = function(nums, target) { let mid,midR,midL; function find(left,right,target){ while(left <= right){ mid = (left + right) >> 1; if(nums[mid]<= target){ left = mid+1; }else{ right = mid-1; } } return right } midR=find(0,nums.length-1,target); if (midR < 0 || nums[midR] !== target) return [-1, -1] midL= find(0,midR-1,target-1); return [midL+1,midR]; };

分治

基本思想：将一个规模为N的问题分解成K个规模较小的子问题，这些子问题相互独立且原问题性质相同。求出子问题的节，就可得到原问题的解。 题目：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 示例：

var generateTrees = function(n) { if(n === 0) return []; return generateSubtrees(1,n) }; function generateSubtrees(s,n){ let res=[]; if(s >n){ res.push(null); return res; } for(let i=s;i<=n;i++){ let left_trees = generateSubtrees(s, i - 1); let right_trees = generateSubtrees(i + 1, n); for(let left of left_trees){ for(let right of right_trees){ const root = new TreeNode(i); root.left = left; root.right = right; res.push(root) } } } return res; }

搜索

BFS

广度优先搜索一层一层地进行遍历，每层遍历都是以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。 第一层：

0 -> {6,2,1,5}

第二层：

6 -> {4}2 -> {}1 -> {}5 -> {3}

第三层：

4 -> {}3 -> {}

在程序实现 BFS 时需要考虑以下问题： 队列：用来存储每一轮遍历得到的节点； 标记：对于遍历过的节点，应该将它标记，防止重复遍历。

DFS

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

链表

链表——存储有序的元素集合，但内存中不是连续放置的。 **单向链表**

function LinkedList(){ function Node(data){ this.data =data; this.next =null } this.head =null//表头 this.length =0; //插入链表 LinkedList.prototype.append =function(data){ //判断是否添加的第一个节点 let newNode =new Node(data) if(this.length ==0){ this.head=newNode }else{ let current=this.head; while(current.next){ current =current.next; } cunrrent.next=newNode; } this.length++; } // insert 方法 LinkedList.prototype.insert = function (position, data) { if (position < 0 || position > this.length) return false let newNode = new Node(data) if (position == 0) { newNode.next = this.head this.head = newNode } else { let index = 0 let current = this.head let prev = null while (index++ < position) { prev = current current = current.next } newNode.next = current prev.next = newNode } this.length++ return true } // get方法 LinkedList.prototype.get = function (position) { if (position < 0 || position >= this.length) return null let index = 0 let current = this.head while (index++ < position){ current = current.next } return current.data } }

反转链表

例题：输入一个链表，反转链表后，输出新链表的表头。 分析：至少需要三个指针pPre(指向前一个结点)、pCurrent(指向当前的结点)、pNext(指向后一个结点)

function ListNode(x){ let pPre = null,pNext=null; while(pCurrent!= null){ pNext = pCurrent.next; pCurrent.next = pPre; pPre = pCurrent; pCurrent = pNext; } return pPre; }

合并两个排序的链表

例题：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 分析：两个链表都是单调递增的，只要不断比较他们的头结点就行。

function Merge(pHead1, pHead2) { let pMergeHead = null; if (pHead1 === null) return pHead2; if (pHead2 === null) return pHead1; if (pHead1.val < pHead2.val) { pMergeHead = pHead1; pMergeHead.next = Merge(pHead1.next, pHead2); } else { pMergeHead = pHead2; pMergeHead.next = Merge(pHead1, pHead2.next); } return pMergeHead; }

排序

冒泡排序

依次比较大小，小的大的进行位置的交换

/冒泡排序 function sortarr(arr){ for(let i=0;i<arr.length-1;i++){ for(let j =i;j<arr.length-1;j++){ if(arr[j] >arr[j+1]){ var temp = arr[j]; arr[j]=arrp[j+1]; arr[j+1]=temp; } } } return arr; };

选择排序

找到数据结构中最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，依次类推

function select_sort(arr){ for(let i =0;i<arr.length-1;i++){ for(let j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ [arr[j],arr[i]] =[arr[i],arr[j]] } } } return arr; }

插入排序

插入排序的工作原理就是将末排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入。

function insertSort(arr){ let len =arr.length; for(let i=1;i<len;i++){ let temp=arr[i]; let j=i-1;//默认已排序的元素 while (j>=0 && arr[j]>temp) { //在已排序好的队列中从后向前扫描 arr[j+1]=arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置 j--; } arr[j+1]=temp; } return arr; }

快速排序

快排是典型的“分而治之”，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。排序过程分为三步： (1)在数据集之中，选择一个元素作为“基准”(pivot)； (2)所有小于“基准”的元素，都移到“基准”的左边，所有大于“基准”的元素，都移到“基准”的右边； (3)对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 过程图示：

//快速排序 function quickSort(arr){ if(arr.length <= 1){ return arr; } var pivotIndex = Math.floor(arr.length/2); var pivot = arr.splice(pivotIndex ,1); var left = []; var right = []; for(var i=0;i<arr.length;i++){ if(arr[i]<pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } } return quickSort(left).concat([pivot],quickSort(right)); };

归并排序

归并的基本思想：先递归的分解数列，再合并数列； 图解：

//归并排序 function merge_Sort(arr){ if(arr.length == 1){ return arr; } var mid = Math.floor(arr.length/2); var left = arr.slice(0,mid); var right = arr.slice(mid); return Merge(merge_Sort(left),merge_Sort(right));//合并左右部分2 }; function Merge(a,b){ var n= a && a.length; var m= b && b.length; var c =[]; var i =0,j=0; while(i<n && j< m){ if(a[i] <b[j]){ c.push(a[i++]); }else{ c.push(b[j++]); } } while(i<n){ c.push(a[i++]); } while(j<m){ c.push(b[j++]); } console.log(“将数组”,a,’和’,b,’合并为’,c); return c; }

待更新…