jessezhao1990 / algorithm Goto Github PK
View Code? Open in Web Editor NEW算法复习总结，用JavaScript实现
algorithm's People
Contributors
Stargazers
Watchers
Forkers
wang-yi-bit64 super-rain kevinyzy1 wangsen1989 letnoxn sjl421 king088 suviwang312 supernell tangkepengalgorithm's Issues
平衡二叉树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
var mark = true;
function treeDepth(root){
if(root === null) {
return 0;
}
var leftDepth = treeDepth(root.left);
var rightDepth = treeDepth(root.right);
var diff = leftDepth - rightDepth;
if(diff>1 || diff<-1){
mark = false;
}
return Math.max(leftDepth,rightDepth) +1;
}
if(root === null) return true;
treeDepth(root);
return mark;
};
解题思路：在计算二叉树的深度的过程中，同步计算左子树和右子树的深度的差是否大于1，如果大于1，则说明不是平衡二叉树。如果遍历一遍之后不存在左子树和右子树的深度的差大于1的情况，则说明此二叉树是平衡二叉树。
leetcode原题地址：https://leetcode-cn.com/problems/balanced-binary-tree/description/
N皇后
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
var res = [];
// 垂直方向的占用情况
var vertical = {};
// 水平方向的占用情况
var horitonal = {};
// 右倾斜对角线的占用情况
var diagonalRight ={};
// 做倾斜对象线的占用情况
var diagonalLeft = {};
// 尝试在n皇后的问题中，摆放第index行的皇后的位置
function putQueen(n,index,arr){
if(n===index){
res.push(genarateQueen(n,[...arr]));
}
for(var i=0;i<n;i++){
if(!vertical[i] && !horitonal[index] && !diagonalRight[i+index] && !diagonalLeft[index-i+n+1]){
arr.push(i);
vertical[i] = true;
horitonal[index] = true;
diagonalRight[i+index] = true;
diagonalLeft[index-i+n+1] = true;
putQueen(n,index+1,arr);
arr.pop();
vertical[i] = false;
horitonal[index] = false;
diagonalRight[i+index] = false;
diagonalLeft[index-i+n+1] = false;
}
}
}
function genarateQueen(n,arr){
var result = [];
for(var i=0;i<n;i++){
result.push(new Array(n).fill("."));
}
for(var p=0;p<n;p++){
result[p][arr[p]] = "Q";
result[p] = result[p].join("");
}
return result;
}
putQueen(n,0,[]);
return res;
};
解题思路：
每一行只可能存在一个皇后，所以递归地在每一行的每个位置上向后推进，递归下去的条件是水平方向和垂直方向，以及两条对角线上都还未被放置皇后。递归的终止条件就是跑到了最后一行的下一行。此时也是收集到一个满足条件的皇后的时候，再回溯进行下一个收集。
重点内容在于怎么确定两个点在某一个对角线上。我画了示意图。
leetcode原题地址：https://leetcode-cn.com/problems/n-queens/description/
组合总和 II
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
var res = [];
candidates = candidates.sort((a,b)=>a-b);
function dfs(candidates,target,arr,i){
if(target<0) return;
if(target===0){
res.push([...arr]);
}
for(var j=i;j<candidates.length;j++){
arr.push(candidates[j]);
dfs(candidates,target-candidates[j],arr,j+1);
arr.pop();
while(candidates[j]===candidates[j+1]){
j++
}
}
}
dfs(candidates,target,[],0);
return res;
};
解题思路
LeetCode：https://leetcode-cn.com/problems/combination-sum-ii/description/
有效的括号
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var arr = [];
s = s.split('');
for(var i=0;i<s.length;i++){
if(s[i] == "(" || s[i] == "[" || s[i] == "{"){
arr.push(s[i])
}
if(s[i] == ")"){
if(arr[arr.length-1] == "("){
arr.pop();
}else{
return false
}
}
if(s[i] == "]"){
if(arr[arr.length-1] == "["){
arr.pop();
}else{
return false
}
}
if(s[i] == "}"){
if(arr[arr.length-1] == "{"){
arr.pop();
}else{
return false
}
}
}
if(arr.length>0){
return false;
}
return true;
};
LeetCode原题链接：https://leetcode-cn.com/problems/valid-parentheses/description/
将阿拉伯数字转换成汉语
/**
* 将一个数字转换成汉语
*/
function toChinese(num){
num = num+"";
var arr = num.split(".");
if(arr.length>1){
return zhengshu(arr[0])+xiaoshu(arr[1]);
}else{
return zhengshu(arr[0]);
}
}
/**
* 处理整数，并返回整数的汉语
*/
function zhengshu(zs){
var zsStr = "";
for(var i=zs.length-1;i>0;i--){
var temp = "";
var char = zs[i];
switch(char){
case "0" : temp = "零" + temp; break;
case "1" : temp = "一" + temp; break;
case "2" : temp = "二" + temp; break;
case "3" : temp = "三" + temp; break;
case "4" : temp = "四" + temp; break;
case "5" : temp = "五" + temp; break;
case "6" : temp = "六" + temp; break;
case "7" : temp = "七" + temp; break;
case "8" : temp = "八" + temp; break;
case "9" : temp = "九" + temp; break;
}
switch (zs.length-1 - i){
case 0 : temp = temp; break;
case 1 : if (char != "0") temp = temp+"十"; break;
case 2 : if (char != "0") temp = temp+"百"; break;
case 3 : if (char != "0") temp = temp+"千"; break;
case 4 : temp = temp+"万"; break;
case 5 : if (char != "0") temp = temp+"十"; break;
case 6 : if (char != "0") temp = temp+"百"; break;
case 7 : if (char != "0") temp = temp+"千"; break;
case 8 : temp = temp+"亿"; break;
case 9 : if (char != "0") temp = temp+"十"; break;
case 10 : if (char != "0") temp = temp+"百"; break;
case 11 : if (char != "0") temp = temp+"千"; break;
case 12 : temp = temp+"兆"; break;
case 13 : if (char != "0") temp = temp+"十"; break;
case 14 : if (char != "0") temp = temp+"百"; break;
case 15 : if (char != "0") temp = temp+"千"; break;
}
zsStr = temp+zsStr;
}
// 替换由连续的零引起的无用汉子
while (zsStr.indexOf("零零") !== -1 ||
zsStr.indexOf("零万") !== -1 ||
zsStr.indexOf("零亿") !== -1 ||
zsStr.indexOf("零兆") !== -1 ||
zsStr.indexOf("亿万") !== -1 ||
zsStr.indexOf("兆万") !== -1 ||
zsStr.indexOf("兆亿") !== -1 ) {
zsStr = zsStr.replace("零零", "零");
zsStr = zsStr.replace("零万", "万");
zsStr = zsStr.replace("零亿", "亿");
zsStr = zsStr.replace("零兆", "兆");
zsStr = zsStr.replace("亿万", "亿");
zsStr = zsStr.replace("兆万", "兆");
zsStr = zsStr.replace("兆亿", "兆");
}
//将以“一十”开头的替换为“十”
if (zsStr.startsWith("一十")) {
zsStr = zsStr.substr(1);
}
//将以“零”结尾的替换为“”
if (zsStr.lastIndexOf("零") === zsStr.length - 1) {
zsStr = zsStr.substr(0, zsStr.length - 2);
}
return zsStr;
}
/**
* 处理小数，并返回小数的汉语
*/
function xiaoshu(xs){
var numMap = {
0:'零',
1:'一',
2:'二',
3:'三',
4:'四',
5:'五',
6:'六',
7:'七',
8:'八',
9:'九'
}
var xsChinese ="";
for(var i=0;i<xs.length;i++){
xsChinese = xsChinese + numMap[xs[i]];
}
return "点"+xsChinese;
}
console.log(toChinese(880000000045.7117));
排序算法大总结
制作GIF动图的时间成本太高。制作了半张我就放弃了。于是偷懒从网上搜了一些动图。如有侵权，请联系我删除
1. 冒泡排序
时间复杂度O(n^2)，空间复杂度O(1)
冒泡排序，就是从前往后寻找，如果碰到一个更大的。就交换位置往后放。这样一遍下来，就找到了一个最大的值。并且正好这个最大值处于末尾。然后我们第二轮就从开头到倒数第二个值之间进行再次遍历，得到一个次最大值。这样一遍遍的跑。最终整个数组将是从小到大排列
动图如下：
代码如下：
var arr = [1,3,20,5,2,9,6,4,80,9,4];
var arrLength = arr.length;
for(var i=0;i<arrLength;i++){
for(j=0;j<arrLength-i-1;j++){
if(arr[j]>arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
console.log(arr);
2. 选择排序
时间复杂度O(n^2)，空间复杂度O(1)
在每一遍比较中，在剩余的待比较的数中选择一个最小的数与这个剩余序列的第一个数交换位置。
动图如下：
代码如下：
var arr = [1,3,20,5,2,9,6,4,80,9,4];
var n = arr.length;
for(var i=0;i<n;i++){
var minIndex = i;
for(var j=i;j<n;j++){
if(arr[j]<arr[minIndex]){
var temp = arr[minIndex];
arr[minIndex]=arr[j];
arr[j] = temp;
}
}
}
console.log(arr);
3. 插入排序
时间复杂度O(n^2)，空间复杂度O(1)
动画演示：
代码如下：
var arr = [1,3,20,5,2,9,6,4,80,9,4];
var n = arr.length;
for(var i=1;i<n;i++){
for(var j=i;j>0;j--){
if(arr[j]<arr[j-1]){
var temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
console.log(arr);
4.改进型的插入排序
时间复杂度略小于O(n^2)，空间复杂度O(1)
改进型的插入排序，比第三种插入排序要快很多。因为没有数据交换。我们用一个变量记录下当前要插入的值。判断这个值应该插到那个蹲。 这种改进型的插入排序的动态图在网上没找到相应的图片。之后抽空我自己做一个补充上。
代码如下：
var arr = [1,3,20,5,2,9,6,4,80,9,4];
var n = arr.length;
for(var i=1;i<n;i++){
var temp = arr[i];
var j;
for(j=i;j>0 && arr[j-1]>temp;j--){
arr[j] = arr[j-1]
}
arr[j] = temp;
}
console.log(arr);
5. 希尔排序（优化的插入排序）
// 修改于 2019-03-06
function shellSort(arr) {
var len = arr.length;
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = gap; i < len; i++) {
var j = i;
var current = arr[i];
while (j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}
6.归并排序
利用递归
var arr = [1,3,20,5,2,9,6,4,80,9,4,6];
function mergeSort(arr){
function _merge(arr,start,middle,end){
// 开辟临时空间，将start到end的子数组复制到此空间
const tempArr = arr.slice(start,end+1)
let index1 = start
let index2 = middle+1
for(let k=start;k<=end;k++){
if(index1>middle){
arr[k] = tempArr[index2-start]
index2++
}else if(index2>end){
arr[k] = tempArr[index1-start]
index1++
}else if(tempArr[index1-start]<tempArr[index2-start]){
arr[k] = tempArr[index1-start]
index1++
}else{
arr[k] = tempArr[index2-start]
index2++
}
}
}
// 前闭后闭
function _mergeSort(arr,start,end){
if(start>=end){
return;
}
let middle = Math.floor((start+end)/2)
_mergeSort(arr,start,middle)
_mergeSort(arr,middle+1,end)
_merge(arr,start,middle,end)
}
_mergeSort(arr,0,arr.length-1)
}
mergeSort(arr)
console.log(arr)
利用迭代
var arr = [1,3,20,5,2,9,6,4,80,9,4,6];
function mergeSort(arr){
function _merge(arr,start,middle,end){
// 开辟临时空间，将start到end的子数组复制到此空间
const tempArr = arr.slice(start,end+1)
let index1 = start
let index2 = middle+1
for(let k=start;k<=end;k++){
if(index1>middle){
arr[k] = tempArr[index2-start]
index2++
}else if(index2>end){
arr[k] = tempArr[index1-start]
index1++
}else if(tempArr[index1-start]<tempArr[index2-start]){
arr[k] = tempArr[index1-start]
index1++
}else{
arr[k] = tempArr[index2-start]
index2++
}
}
}
function _mergeSort(arr,n){
for(var sz=1;sz<n;sz+=sz){
for(var i=0;i+sz<n;i=i+2*sz){
_merge(arr,i,i+sz-1,Math.min(i+sz+sz-1,n-1))
}
}
}
_mergeSort(arr, arr.length)
}
mergeSort(arr)
console.log(arr)
7.快速排序
非原地排序
var arr = [1,3,20,5,2,9,6,4,80,9,4,6];
function quickSort(arr){
if(arr.length<=1){
return arr;
}
let mid = Math.floor(arr.length/2)
let left = [];
let right = [];
let middle = arr.splice(mid,1)[0];
for(var i=0;i<arr.length;i++){
if(arr[i]<middle){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quickSort(left).concat(middle,quickSort(right))
}
console.log(quickSort(arr))
原地排序
var arr = [1,3,20,5,2,9,6,4,80,9,4,6];
function quickSort(arr){
// 找到位置p，使得l到p-1之间的数小于arr[p],p+1到r之间的数大于arr[p]
function partition(arr,l,r){
let v = arr[l];
let p =l;
for(let i=l+1;i<=r;i++){
if(arr[i]<v){
let temp = arr[p+1]
arr[p+1] = arr[i]
arr[i] = temp
p++
}
}
let temp = arr[p]
arr[p] = arr[l]
arr[l] = temp
return p
}
function _quickSort(arr,l,r){
if(l>=r){
return;
}
let p = partition(arr,l,r);
_quickSort(arr,l,p-1)
_quickSort(arr,p+1,r)
}
_quickSort(arr,0,arr.length-1)
}
quickSort(arr)
console.log(arr)
三路快排
var arr = [1,3,20,5,2,9,6,4,80,9,4,6];
function quickSort(arr){
function _quickSort(arr,l,r){
if(l>=r){
return;
}
// 随机选择一个值v，然后对数组进行整理，整理的目标是
// 把这个数组整理成三段。l到lt之间的值要小于v，lt到rt之间的值等于v，rt到r之间的值大于v
// 因此我们分三步走
// 1. 在l到r之间随机选择一个值v
let index = l+Math.floor(Math.random()*(r-l))
let v = arr[index]
// 2. 先把v放置在l处
let temp = arr[index];
arr[index] = arr[l];
arr[l] = temp;
// 3. 开始整理
let i = l+1;
let lt = l;
let rt = r;
while(i<=rt){
// 当arr[i]等于v的时候，i前移一步。把arr[i]纳入相等区
if(arr[i]===v){
i++;
}
// 当arr[i]小于v的时候，将arr[lt]和v的位置交换
if(arr[i]<v){
temp = arr[lt];
arr[lt] = arr[i];
arr[i] = temp;
i++;
lt++;
}
// 当arr[i]大于v的时候，将arr[i]和arr[rt]的位置交换，rt往左移一步
if(arr[i]>v){
temp = arr[rt];
arr[rt]= arr[i];
arr[i] = temp;
rt--
}
}
_quickSort(arr,l,lt-1)
_quickSort(arr,rt+1,r)
}
_quickSort(arr,0,arr.length-1)
}
quickSort(arr)
console.log(arr)
8. 堆排序
方法1：普通的堆排序
const data = Symbol('data');
const count = Symbol('count');
const _shiftUp = Symbol('shiftUp');
const _shiftDown = Symbol('shiftDown');
class MaxHeap {
constructor(){
this[data] = [0];
this[count] = 0;
}
// 公共方法：获取堆的大小
size(){
return this[count];
}
// 公共方法： 判断最大堆是否是空堆
isEmpty(){
return this[count] === 0
}
// 公共方法： 向堆中添加一个数
insert(item){
this[data].push(item);
this[count]++;
this._shiftUp(this[count]);
}
// 公共方法： 从堆中取出一个最大值
extractMax(){
if(this[count]<=0) return;
let res = this[data][1];
this[data][1] = this[data][this[count]];
this[count]--;
this._shiftDown(1)
return res;
}
// 私有方法： shiftUp过程
_shiftUp(k){
while(k>1){
let index = Math.floor(k/2)
if(this[data][index]<this[data][k]){
let temp = this[data][index];
this[data][index] = this[data][k];
this[data][k] = temp;
}else{
break;
}
k = Math.floor(k/2);
}
}
// 私有方法： shiftDown过程
_shiftDown(k){
while(k*2<= this[count]){
let j = k*2
if(j+1<=this[count] && this[data][j+1] > this[data][j]){
j++
}
if(this[data][k]>=this[data][j]) break;
let temp = this[data][k];
this[data][k] = this[data][j];
this[data][j] = temp;
k=j;
}
}
}
// 堆排序
let arr = [1,3,20,5,2,9,6,4,80,9,4,6];
let heap = new MaxHeap();
for(let i=0;i<arr.length;i++){
heap.insert(arr[i])
}
for(let j=arr.length-1;j>0;j--){
arr[j] = heap.extractMax();
}
console.log(arr);
方法2： 经过优化的堆排序
const data = Symbol('data');
const count = Symbol('count');
const _shiftUp = Symbol('shiftUp');
const _shiftDown = Symbol('shiftDown');
class MaxHeap {
constructor(arr){
if(arguments.length>0 && Array.isArray(arguments[0])){
this[data] = [0].concat(arr);
this[count] = arr.length;
for(let i=Math.floor(this[count]/2); i>1 ;i--){
this._shiftDown(i);
}
}else{
this[data] = [0];
this[count] = 0;
}
}
// 公共方法：获取堆的大小
size(){
return this[count];
}
// 公共方法： 判断最大堆是否是空堆
isEmpty(){
return this[count] === 0
}
// 公共方法： 向堆中添加一个数
insert(item){
this[data].push(item);
this[count]++;
this._shiftUp(this[count]);
}
// 公共方法： 从堆中取出一个最大值
extractMax(){
if(this[count]<=0) return;
let res = this[data][1];
this[data][1] = this[data][this[count]];
this[count]--;
this._shiftDown(1)
return res;
}
// 私有方法： shiftUp过程
_shiftUp(k){
while(k>1){
let index = Math.floor(k/2)
if(this[data][index]<this[data][k]){
let temp = this[data][index];
this[data][index] = this[data][k];
this[data][k] = temp;
}else{
break;
}
k = Math.floor(k/2);
}
}
// 私有方法： shiftDown过程
_shiftDown(k){
while(k*2<= this[count]){
let j = k*2
if(j+1<=this[count] && this[data][j+1] > this[data][j]){
j++
}
if(this[data][k]>=this[data][j]) break;
let temp = this[data][k];
this[data][k] = this[data][j];
this[data][j] = temp;
k=j;
}
}
}
// 经过优化的堆排序
let arr = [1,3,20,5,2,9,6,4,80,9,4,6];
let heap = new MaxHeap(arr);
for(let j=arr.length-1;j>0;j--){
arr[j] = heap.extractMax();
}
console.log(arr);
方法3： 原地的堆排序
function heapSort(arr){
function _heapSort(arr,n){
// heapify
for(let i=Math.floor((n-1)/2);i>=0;i--){
_shiftDown(arr,n,i);
}
//
for(let j = n-1;j>0; ){
var temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
j--
_shiftDown(arr,j,0)
}
}
function _shiftDown(arr,n,k){
while(2*k+1 <n){
let j = 2*k+1
if(j+1<n && arr[j]< arr[j+1]){
j++
}
if(arr[k]>arr[j]){
break;
}
let temp = arr[k];
arr[k] = arr[j];
arr[j] = temp;
k=j
}
}
_heapSort(arr,arr.length);
}
let arr = [1,3,20,5,2,9,6,4,80,9,4,6];
heapSort(arr);
console.log(arr);
9.利用二分搜索树进行排序
买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
由于可以无数次随时买卖，所以，只要有利润就吃掉。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
var max = 0
for(var i =1; i<=prices.length; i++){
if(prices[i]>prices[i-1]){
max = max + prices[i]-prices[i-1];
}
}
return max;
};
旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。
算法
方法1
var rotate = function(nums, k) {
for(var i= 1; i<=k; i++){
nums.unshift(nums.pop())
}
};
方法2
var rotate = function(nums, k) {
var a = nums.splice(-k,k);
nums.unshift(...a);
};
方法3
var rotate = function(nums, k) {
nums.splice(0,0,...nums.splice(-k,k))
};
整数拆分
方法一
利用递归
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
var memo = new Array(n+1).fill(-1);
function breakInteger(n){
if(n===1) return 1;
if(memo[n] != -1 ) return memo[n];
var res = -1;
for(var i=1;i<=n-1;i++){
res = Math.max(res, i * (n-i), i * breakInteger(n-i))
}
memo[n] = res;
return res;
}
return breakInteger(n);
};
方法二
利用动态规划
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
var memo = new Array(n+1).fill(-1);
memo[1] =1;
memo[2] =1;
for(var i=2;i<=n;i++){
for(var j=1;j<i;j++){
memo[i] = Math.max(memo[i],j*(i-j),j*memo[i-j])
}
}
return memo[n]
};
leetcode原题地址：https://leetcode-cn.com/problems/integer-break/description/
最长子串拓展的问题
一个只有0和1的数组，如果将此数组中的某一个0换成1，得到连续1的最大值是多少。
比如 [0,1,1,0,1,1],将第二个0换成1能出现五个连续的1. 所以值是5，
解题思路： 双指针滑动窗口+记录滑动块内的零的数量
function find(arr){
var max = 0;
var p1 =0;
var p2 =1;
var zeroNum = 0;
var length = arr.length;
if(length === 1) return 1;
if(arr[p1]=== 0) zeroNum ++;
if(arr[p2]===0) zeroNum ++;
while(p2<length){
if(p1===p2){
p2++;
if(arr[p2]=== 0) zeroNum ++;
}
if(arr[p2] === 1){
p2++;
if(arr[p2]=== 0) zeroNum ++;
if(p2 == length) max = Math.max(max,p2-p1);
}else{
if(zeroNum<2){
p2++;
if(arr[p2]=== 0) zeroNum ++;
}else{
max = Math.max(max,p2-p1);
if(arr[p1]===0){
zeroNum --;
}
p1++;
}
}
}
return max;
}
var arr1 = [0,1,1,0,0,0,1,1,1,0,1,1,1,0,0,1,1,1,1,0,1,1,1,1,0,0]
var arr2 = [0,1,1,0]
var arr3 = [0,1]
var arr4 = [0]
var arr5 = [1]
console.log(find(arr1))
console.log(find(arr2))
console.log(find(arr3))
console.log(find(arr4))
console.log(find(arr5))
爬楼梯
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
var temp = {
1:1,
2:2,
};
for(var i=3;i<=n;i++){
temp[i] = temp[i-1] + temp[i-2];
}
return temp[n]
};
leetcode原题地址：https://leetcode-cn.com/problems/climbing-stairs/description/
二叉搜索树的最近公共祖先
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(root === null) return null;
// 如果两个节点的值全部在节点的右侧，则说明不是最近的节点，需要进一步向右搜索
if(p.val > root.val && q.val >root.val){
return lowestCommonAncestor(root.right,p,q);
}
// 如果两个节点的值全部在节点的左侧，则说明不是最近的节点，需要进一步向左搜索
if(p.val < root.val && q.val < root.val){
return lowestCommonAncestor(root.left,p,q);
}
// 如果不满足上边的两个条件，说明p和q分布在节点的两侧，此时找到最近的节点
return root;
};
解题思路：
如果p和q分布在某个节点的两侧，说明此节点是最近的公共祖先
leetcode原题地址：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
组合
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
res = [];
var arr = [];
generateCombine(n,k,1,arr);
return res;
};
var res = [];
function generateCombine(n,k,start,arr){
if(arr.length===k){
res.push([...arr]);
}
for(var i=start;i<=n;i++){
arr.push(i);
generateCombine(n,k,i+1,arr);
arr.pop();
}
return;
}
解题思路：
利用递归和回溯法，往arr中添加item。当item的长度等于k的时候，把这个结果放到res中。
leetcode原题地址：https://leetcode-cn.com/problems/combinations/description/
子集 II
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
nums = nums.sort((a,b)=>a-b);
var res = [];
function dfs(nums,arr,i){
res.push([...arr])
for(var j=i;j<nums.length;j++){
arr.push(nums[j]);
dfs(nums,arr,j+1);
arr.pop();
while(nums[j]===nums[j+1]) j++;
}
}
dfs(nums,[],0);
return res;
};
解题思路
这个题和之前一个题子集非常相似，唯一的不同在于nums可能包含重复元素。
思路和求子集的那个题的思路差不多，唯一的变化是先对nums进行排序，这样剪枝的时候更加方便。只需要关注相邻的两个数是否相等即可。
看下图，除了红色的剪枝，绿色部分的剪枝，就是过滤相邻的相等元素。
LeetCode原题地址：https://leetcode-cn.com/problems/subsets-ii/description/
验证二叉搜索树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
// 方法1： 先中序遍历得到一个数组。再判断这个数组是否是从小到大的顺序排列
// var isValidBST = function(root) {
// var res = [];
// leftTraverse(root,res);
// var mark = true;
// for(var i=0;i<res.length;i++){
// if(res[i+1]<=res[i]){
// mark = false;
// }
// }
// console.log(res);
// return mark;
// };
// function leftTraverse(root,res=[]){
// if(root === null) return null;
// leftTraverse(root.left,res);
// res.push(root.val);
// leftTraverse(root.right,res);
// }
// 方法2：递归进行，从根开始递归，如果node节点的值大于最大值或者小于最小值，那返回false。否则同时向左和向右递归，向左的最大值是node节点的值，向右的最小值是node节点的值。递归下去。
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
return loop(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
};
function loop(node,min,max){
if(!node) return true;
if(node.val<=min || node.val>= max) return false;
return loop(node.left, min, node.val) && loop(node.right, node.val,max);
}
LeetCode原题地址：https://leetcode-cn.com/problems/validate-binary-search-tree/description/
组合总和 III
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
var candidates = [1,2,3,4,5,6,7,8,9];
var res = [];
function dfs(candidates,k,n,arr,i){
if(arr.length>k || n<0){
return;
}
if(arr.length===k && n===0){
res.push([...arr]);
return;
}
for(var j=i;j<candidates.length;j++){
arr.push(candidates[j]);
dfs(candidates,k,n-candidates[j],arr,j+1);
arr.pop();
}
}
dfs(candidates,k,n,[],0);
return res;
};
// console.log(combinationSum3(3,7));
解题思路
利用递归、回溯、剪枝。递归的终止条件是收集的数组的长度大于k或者n小于0，或者是数组的长度等于k并且n正好等于0. 因为不能有重复元素，所以我们的下一层迭代要后移一位。
LeetCode原题地址：https://leetcode-cn.com/problems/combination-sum-iii/description/
完全平方数
/**
* @param {number} n
* @return {number}
*/
function node(val,step){
this.val = val;
this.step = step;
}
var numSquares = function(n) {
var queue = [];
var visited = {};
queue.push(new node(n,0));
visited[n] = true;
while(queue.length>0){
var front = queue[0].val;
var step = queue[0].step;
queue.shift();
if(front===0) return step;
for(var i=0;front-i*i>=0;i++){
if(visited[front-i*i]!== true){
queue.push(new node(front-i*i,step+1));
visited[front-i*i]= true;
}
}
}
};
思路：建模，整个问题转化为图论问题
从N到0的所有节点，如果某两个节点之间相差一个完全平方数，则连接一条边。此时我们得到了一个无权图，成功将问题转化为求这个无权图中从N到0的最短路径问题。
leetcode原题地址：https://leetcode-cn.com/problems/perfect-squares/description/
二叉树的后序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
var res = []
function traversal(node,res){
if(!node) return;
traversal(node.left,res);
traversal(node.right,res);
res.push(node.val);
}
traversal(root,res);
return res;
};
leetcode原题地址：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
对称二叉树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if(root == null){
return true;
}
return symmetric(root.left,root.right);
};
function symmetric(node1,node2){
if(node1 === null || node2 === null){
return node1 === node2
}
return (node1.val === node2.val) && symmetric(node1.left,node2.right) && symmetric(node1.right,node2.left);
}
解题思路，对于每两个相比较的节点node1和node2。node1的左节点和node2的右节点比较，node1的右节点和node2的左节点比较。如果满足三个条件，则两个节点是对称的。三个条件为为node1和node2 的值相等，node1.left 和node2.right同样相等，node1.right和node2.left同样相等。以此递归下去。
题中的二叉树画的层次有点浅，我画了一个层次稍微深一点的。可以在脑子里过一遍，对于下图是怎么递归比较的。
leetcode 原题地址： https://leetcode-cn.com/problems/symmetric-tree/description/
解码方法
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
if(s==="0") return 0;
var memo = {};
var length = s.length;
var arr = s.split("");
memo[1] = 1;
if(length===1){
return 1;
}
if(arr[0]==="0"){
return 0;
}else if(arr[0]==="1"){
if(arr[1]==="0"){
memo[2] =1
}else{
memo[2] = 2
}
}else if(arr[0]==="2"){
if(arr[1]==="0"){
memo[2]=1;
}else if(arr[1]<="6"){
memo[2]=2;
}else{
memo[2]=1;
}
}else {
if(arr[1] ==="0"){
return 0;
}else{
memo[2] =1;
}
}
for(var i=3;i<=length;i++){
if(arr[i-2]==="0"){
if(arr[i-1] ==="0"){
return 0;
}else{
memo[i] = memo[i-1]
}
}else if(arr[i-2]==="1"){
if(arr[i-1]==="0"){
memo[i] = memo[i-2];
}else{
memo[i] = memo[i-1] + memo[i-2];
}
}else if(arr[i-2]==="2"){
if(arr[i-1]==="0"){
memo[i] = memo[i-2]
}else if(arr[i-1]<="6"){
memo[i] = memo[i-1]+ memo[i-2];
}else{
console.log(memo[i-1]);
memo[i] = memo[i-1];
}
}else{
if(arr[i-1]==="0"){
return 0;
}else{
memo[i] = memo[i-1];
}
}
}
return memo[length];
};
leetcode原题地址：https://leetcode-cn.com/problems/decode-ways/description/
路径总和
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
if(root === null){
return false;
}
if(root.left === null && root.right === null){
return sum -root.val === 0;
}
return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
};
解题思路：在递归遍历的过程中，对于每个节点来说。sum减去本节点的val值之后的值作为子节点的sum，如果sum为零时正好到达叶子节点。那说明存在这样的一条路径。
leetcode原题地址：https://leetcode-cn.com/problems/path-sum/description/
翻转二叉树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if(root === null ) return null;
root.left = invertTree(root.left);
root.right = invertTree(root.right);
var temp = root.left;
root.left = root.right;
root.right = temp;
return root;
};
LeetCode原题地址：https://leetcode-cn.com/problems/invert-binary-tree/description/
二叉树的中序遍历
方法一：利用递归
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
function loop(node,arr){
if(node === null) return;
if(node.left){
loop(node.left,arr)
}
arr.push(node.val)
if(node.right){
loop(node.right,arr)
}
}
var res = [];
loop(root,res);
return res;
};
方法二： 利用栈
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
var res = [];
var stack = [];
while(true){
while(root){
stack.push(root)
root = root.left;
}
if(stack.length===0) break;
let node = stack.pop();
if(node !== null){
res.push(node.val);
root = node.right;
}
}
return res;
};
LeetCode原题地址：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/
路径总和 II
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function(root, sum) {
function loop(root,sum){
var res = [];
if(root === null) return res;
if(root.left === null && root.right === null){
res.push({currentSum:root.val,arr:[root.val]})
return res;
}
var leftRes = loop(root.left,sum);
for(var i=0;i<leftRes.length;i++){
var currentSum = leftRes[i].currentSum+root.val;
leftRes[i].arr.splice(0,0,root.val)
res.push({currentSum:currentSum,arr:leftRes[i].arr})
}
var rightRes = loop(root.right,sum);
for(var i=0;i<rightRes.length;i++){
var currentSum = rightRes[i].currentSum + root.val;
rightRes[i].arr.splice(0,0,root.val);
res.push({currentSum:currentSum,arr:rightRes[i].arr})
}
return res;
}
return loop(root,sum)
.filter(item=>{
return item.currentSum === sum
})
.map(item=>item.arr);
};
解题思路：递归调用。计算一个节点左子树的字符串数组，和右子树的字符串数组，并和本节点的值串联起来，记录累加的值。
leetcode 原题地址：https://leetcode-cn.com/problems/path-sum-ii/description/
相同的树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if(p===null || q===null){
return p === q;
}
if(p.val == q.val){
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}else{
return false;
}
};
leetcode原题地址：https://leetcode-cn.com/problems/same-tree/description/
长度最小的子数组
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
var l = 0;
var r = -1;
var sum = 0;
var length = nums.length;
var res = length+1;
while(l<length){
if(r+1<length && sum<s){
sum = sum + nums[++r];
}else{
sum = sum - nums[l++];
}
if(sum>=s){
res = Math.min(r-l+1,res);
}
}
if(res == length+1) return 0; // 遍历一遍之后发现无解的时候返回0
return res
};
leetcode原题地址：https://leetcode-cn.com/problems/minimum-size-subarray-sum/description/
js快排
var quickSort = function(arr) {
if(arr.length<=1) {return arr};
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex,1)[0];
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 getMaxOfArray(arr){
return Math.max,apply(null, arr)
}
方法二
Math.max(...arr);
方法三
自定义一个函数，把数组里的每个数遍历一遍。
路径总和 III
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number}
*/
var pathSum = function(root, sum) {
if(root === null) return 0;
var res = findPath(root,sum);
res += pathSum(root.left,sum);
res += pathSum(root.right,sum);
return res;
};
function findPath(node,sum){
if(node === null) return 0;
var res = 0;
if(sum - node.val === 0) res += 1;
res += findPath(node.left,sum-node.val);
res += findPath(node.right,sum-node.val)
return res;
}
解题思路
我们遍历整个树的过程中，对于每个节点来说，我们可以这样思考
在从这个节点往下走的路径中，有可能是包含此节点的值的和满足sum，
也有可能是不包含此节点的值的和满足sum
因此，我们的代码可以这样设计
var pathSum = function(root, sum) {
if(root === null) return 0;
// 包含本节点的值的和为sum的情况
var res = findPath(root,sum);
// 不包含本节点的值的和为sum的情况
res += pathSum(root.left,sum);
res += pathSum(root.right,sum);
// 返回的是上边两种情况的和
return res;
};
findPath的作用是找到包含此节点的值的情况。问题成功缩小到了寻找包含根节点的路径的和等于给定数值的路径数目，这样就简单了许多。我们在往下找的过程中。走一步减一下本节点的值，直到某一个节点的时候减去本节点的值之后正好等于零，说明我们找到了一条。
因此findPath应该这样设计。
function findPath(node,sum){
if(node === null) return 0;
var res = 0;
if(sum - node.val === 0) res += 1;
res += findPath(node.left,sum-node.val);
res += findPath(node.right,sum-node.val)
return res;
}
leetcode原题地址：https://leetcode-cn.com/problems/path-sum-iii/description/
子集
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
var res = [];
function dfs(nums,arr,j){
res.push([...arr]);
for(var i=j;i<nums.length;i++){
arr.push(nums[i]);
dfs(nums,arr,i+1);
arr.pop();
}
}
dfs(nums,[],0);
return res;
};
// var nums = [1,2,3]
// console.log(subsets(nums))
解题思路：
LeetCode原题地址：https://leetcode-cn.com/problems/subsets/description/
二叉树的层次遍历（广度优先遍历）
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
function nodeWithLevel(TreeNode,level){
this.treeNode = TreeNode;
this.level = level;
}
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
var res = [];
var queue = [];
if(root === null) return res;
queue.push(new nodeWithLevel(root,0))
while(queue.length>0){
var frond = queue[0];
var level = frond.level;
if(level===res.length){
res[level] = []
}
res[level].push(frond.treeNode.val);
if(frond.treeNode.left){
queue.push(new nodeWithLevel(frond.treeNode.left,level+1))
}
if(frond.treeNode.right){
queue.push(new nodeWithLevel(frond.treeNode.right,level+1))
}
queue.shift();
}
return res;
};
leetcode原题地址：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/description/
岛屿的个数
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
var res =0;
var visited =[];
var m = grid.length;
if(grid.length===0) return res;
var n = grid[0].length;
var d = [[0,1],[1,0],[0,-1],[-1,0]];
// 初始化visited
for(var i=0;i<grid.length;i++){
visited.push(new Array(grid[0].length).fill(false));
}
for(var i=0;i<m;i++){
for(var j=0;j<n;j++){
if(inArea(i,j) && !visited[i][j] && grid[i][j] !== "0"){
res++;
dfs(grid,i,j);
}
}
}
return res;
// 判断是否在网格中
function inArea(i,j){
return i>=0 && j>=0 && i<m && j<n;
}
// 深度优先遍历，递归去标记是否已经被访问过
function dfs(grid,i,j){
visited[i][j] = true;
for(var k=0;k<4;k++){
var newI = i+d[k][0];
var newJ = j+d[k][1];
if(inArea(newI,newJ) && grid[newI][newJ] !=="0" && !visited[newI][newJ]){
dfs(grid,newI,newJ);
}
}
}
};
// var grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]];
// console.log(numIslands(grid));
解题思路：
遍历二维数组，在每个点再进行深度优先遍历，标记是否已经访问过。
leetcode原题地址：https://leetcode-cn.com/problems/number-of-islands/description/
三角形最小路径和
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
for(var j= triangle.length;j>1;j--){
for(var i=0;i<j-1;i++){
var rootValue = triangle[j-2][i];
var leftValue = triangle[j-1][i];
var rightValue = triangle[j-1][i+1];
var minValue = getMin(rootValue+leftValue,rootValue+rightValue);
triangle[j-2][i] = minValue;
}
}
return triangle[0][0]
};
function getMin(left,right){
return left<=right? left:right;
}
方法二：
递归的写法,此种方法效率不高，有重复的计算。
function minimumTotal(triangle){
function loop(triangle,n,index){
if(n==triangle.length-1){
return triangle[n][index];
}
var left = loop(triangle,n+1,index)+triangle[n][index];
var right = loop(triangle,n+1,index+1)+triangle[n][index];
return Math.min(left,right);
}
return loop(triangle,0,0)
}
var triangle = [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
];
console.log(minimumTotal(triangle))
leetcode原题地址：https://leetcode-cn.com/problems/triangle/description/
最小路径和
function minPathSum(grid){
if(!grid || grid.length===0) return 0;
var m = grid.length;
var n = grid[0].length;
var dp = new Array(n);
dp[0] = grid[0][0];
for(var j=1;j<n;j++){
dp[j] = dp[j-1] + grid[0][j];
}
for(var i=1;i<m;i++){
dp[0] = dp[0] + grid[i][0];
for(var j=1;j<n;j++){
dp[j] = grid[i][j] +Math.min(dp[j-1],dp[j]);
}
}
return dp[n-1];
}
解题思路：
由于到达某个点的路径只能是从左侧或者是上侧因此，到达第一个点0,0的最小路径，就是grid[0,0],
我们记为dd[0,0]。到达01的最小路径为到达0,0的最小路径加上grid[0,1],我们记为dd[0,1]。
以此类推，我们可以算出到达第一行的任意一个点的最小路径，我们再来看第二行，第二行的第一个点1,0
到达此点的最小路径为从头部过来，也就是dd[0,0]+grid[1,0]，我们记为dd[1,0]。然后我们再看第二行的第二个点，1,1 。这个点为最小路径为min(dd[1,0],dd[0,1])+grid[1,1]，我们记为dd[1,1]。
以此类推，一行行的算出来到达每个点的小路径。一直算到最后一行的最后一个，此时得出结论
上边的代码是这种思路的精简版。没有采用二维数组记忆。而是采用了一位数组记忆。更节约空间。
LeetCode原题地址：https://leetcode-cn.com/problems/minimum-path-sum/description/
左叶子之和
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumOfLeftLeaves = function(root) {
if(root === null) return 0;
if(root.left !== null){
if(root.left.left === null && root.left.right ===null){
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + root.left.val;
}
};
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
};
解题思路：递归遍历每个节点，当节点的右子树是叶子节点时，捡起此节点的值
leetcode 原题地址：https://leetcode-cn.com/problems/sum-of-left-leaves/description/
多维数组的展开
多维数组的展开可以有很多种写法。下面总结一下
写法1
function flatten1(arr){
var result=[];
for(var i=0;i<arr.length;i++){
if(Array.isArray(arr[i])){
result.push(...flatten1(arr[i]));
}else{
result.push(arr[i])
}
}
return result;
}
// 测试用例
var test1 = [1,2,[3,4,[5,6,[7,8],9],10]];
console.log(flatten1(test1))
function flatten(arr){
let result = []
if(Array.isArray(arr)){
arr.map(item=>{
result = result.concat(flatten(item))
})
}else{
result.push(arr);
}
return result;
}
var test1 = [1,2,[3,4,[5,6,[7,8],9],10]];
console.log(flatten(test1))
写法2
function flatten2(arr){
return [].concat(...arr.map(a=> Array.isArray(a)? flatten2(a):a))
}
// 测试用例
var test2 = [1,2,[3,4,[5,6,[7,8],9],10]];
console.log(flatten2(test2));
写法3
function flatten3(arr){
return arr.reduce(function(total,currentValue){
return total.concat(Array.isArray(currentValue) ? flatten3(currentValue) : currentValue);
},[])
}
// 测试用例
var test3 = [1,2,[3,4,[5,6,[7,8],9],10]];
console.log(flatten3(test3));
如果能自定义展开的深度呢？
function flatten4(arr,deep=1){
let result = [];
arr.forEach(a => {
let d = deep
if(Array.isArray(a) && d>0){
result.push(...(flatten4(a,--d)))
}else{
result.push(a)
}
})
return result;
}
// 测试用例
var test4 = [1,2,[2,2],[3,4,[3,3],[5,6,[7,8],9],10]];
console.log(flatten4(test4));
在线演示地址：https://codepen.io/zhaojianxin/pen/RJJGrB?editors=0012
全排列 II
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
if(nums.length===0) return [];
var res = [];
var used = {};
function combile(nums,index,s){
if(index === nums.length){
var str = s.join(',');
if(!res.includes(str)){
res.push(str);
}
return;
}
for(var i=0;i<nums.length;i++){
if(!used[i]){
s.push(nums[i]);
used[i] = true;
combile(nums, index+1,s);
s.pop();
used[i] = false;
}
}
return;
}
combile(nums,0,[]);
return res.map(item=>item.split(',').map(i=>Number(i)));
};
leetcode原题地址：https://leetcode-cn.com/problems/permutations-ii/description/
二叉树的最小深度
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
if(root === null) return 0;
var leftMin = minDepth(root.left);
var rightMin = minDepth(root.right);
if(leftMin === 0 || rightMin ===0) return leftMin+rightMin+1; // 排除只有左节点或者右节点的节点的影响
return Math.min(leftMin,rightMin)+1;
};
leetcode 原题地址：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/
二叉树的所有路径
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function(root) {
var res = [];
if(root === null) return res;
if(root.left === null && root.right === null){
res.push(String(root.val));
return res;
}
var leftS = binaryTreePaths(root.left);
for(var i=0;i<leftS.length;i++){
res.push(`${root.val}->${leftS[i]}`);
}
var rightS = binaryTreePaths(root.right);
for(var i=0;i<rightS.length;i++){
res.push(`${root.val}->${rightS[i]}`)
}
return res;
};
解题思路：递归调用。计算一个节点左子树的字符串数组，和右子树的字符串数组，并和本几点的值串联起来返回。
leetcode原题地址：https://leetcode-cn.com/problems/binary-tree-paths/description/
数组去重
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
nums = nums.sort();
function loop(nums){
for(var i=1;i<=nums.length;i++){
if(nums[i] === nums[i-1]){
nums.splice(i,1);
loop(nums);
return;
}
}
}
loop(nums);
return nums;
};
console.log(removeDuplicates([1,1,2]));
//console.log(removeDuplicates([0,0,1,1,1,2,2,3,3,4]));
/* 方法二 */
var removeDuplicates1 = function(nums) {
var set = new Set();
for(var i =0;i<nums.length;i++){
set.add(nums[i]);
}
return [...set];
}
console.log(removeDuplicates1([1,1,2]));
console.log(removeDuplicates1([0,0,1,1,1,2,2,3,3,4]));
电话号码的字母组合
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
var digitsArray = digits.split('');
if(digitsArray.length===0) return [];
var map ={
"2":"abc",
"3":"def",
"4":"ghi",
"5":"jkl",
"6":"mno",
"7":"pqrs",
"8":"tuv",
"9":"wxyz"
}
// 存储收集的结果
var res = [];
// 其实这些字母所代表的字母组成了一个树，我们顺着每条路径往下加，加到叶子之后，此时就得到了一个符合条件的字符串。放入res中。
function combineLetters(digitsArray,index,str){
if(index === digitsArray.length){
res.push(str);
return;
}
var letters = map[digitsArray[index]].split('');
for(var i=0;i<letters.length;i++){
combineLetters(digitsArray,index+1,str+letters[i]);
}
return;
}
combineLetters(digitsArray,0,"");
return res;
};
解题思路：
我们可以从根开始，进行字符串的相加，一直加到叶子节点停止，此时得到一个符合条件的组合字符串
如红线所标注的一样。如果整个过程是递归进行的。那跑一遍之后，我们将得到所有可能的组合
leetcode原题地址：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/
单词搜索
// 表示某一个点的上右下左的偏移量
var d = [[-1,0],[0,1],[1,0],[0,-1]];
// 标记是否已经被占用
var visited = [];
// 判断是否越界
function inArea(board,x,y){
return x>=0 && y>=0 && x<board[0].length && y<board.length;
}
function searchWord(board,wordArray,index,x,y){
if(wordArray.length === index+1){
return board[y][x] === wordArray[index];
}
if(board[y][x] === wordArray[index]){
visited[y][x] = true;
for(var i=0;i<4;i++){
var newY = y + d[i][0];
var newX = x + d[i][1];
if(inArea(board,newX,newY) && !visited[newY][newX] && searchWord(board,wordArray,index+1,newX,newY)){
return true;
}
}
visited[y][x] = false;
}
return false;
}
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
visited = [];
for(var m=0;m<board.length;m++){
visited.push(new Array(board[0].length).fill(false))
}
for(var i=0;i<board.length;i++){
for(var j=0;j<board[i].length;j++){
if(searchWord(board,word.split(''),0,j,i)){
return true
}
}
}
return false;
};
解题思路
遍历二维数组，以每个点为起点开始往四周搜索。搜索的过程是一个递归和回溯的过程。
leetcode原题地址：https://leetcode-cn.com/problems/word-search/description/
实现最大堆
const data = Symbol('data');
const count = Symbol('count');
const _shiftUp = Symbol('shiftUp');
const _shiftDown = Symbol('shiftDown');
class MaxHeap {
constructor(){
this[data] = [0];
this[count] = 0;
}
// 公共方法：获取堆的大小
size(){
return this[count];
}
// 公共方法： 判断最大堆是否是空堆
isEmpty(){
return this[count] === 0
}
// 公共方法： 向堆中添加一个数
insert(item){
this[data].push(item);
this[count]++;
this._shiftUp(this[count]);
}
// 公共方法： 从堆中取出一个最大值
extractMax(){
if(this[count]<=0) return;
let res = this[data][1];
this[data][1] = this[data][this[count]];
this[count]--;
this._shiftDown(1)
return res;
}
// 私有方法： shiftUp过程
_shiftUp(k){
while(k>1){
let index = Math.floor(k/2)
if(this[data][index]<this[data][k]){
let temp = this[data][index];
this[data][index] = this[data][k];
this[data][k] = temp;
}else{
break;
}
k = Math.floor(k/2);
}
}
// 私有方法： shiftDown过程
_shiftDown(k){
while(k*2<= this[count]){
let j = k*2
if(j+1<=this[count] && this[data][j+1] > this[data][j]){
j++
}
if(this[data][k]>=this[data][j]) break;
let temp = this[data][k];
this[data][k] = this[data][j];
this[data][j] = temp;
k=j;
}
}
}
二叉树的最大深度
答案1
可以利用深度优先遍历和递归的思路
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if(root === null) return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
};
答案2
也可以利用广度优先遍历和栈的思路
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if(root ===null ) return 0;
var depth = 1
var stack = [];
root.depth=1;
stack.push(root);
while(stack.length>0){
var node = stack.shift();
if(node.left){
depth = node.left.depth = node.depth+1;
stack.push(node.left)
}
if(node.right){
depth = node.right.depth = node.depth+1;
stack.push(node.right);
}
}
return depth;
};
leetcode原题地址：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/
二分查找法查找一个数在数组中的位置
function binarySearch(arr,l,r,target){
if(l>r) return -1;
var mid = l+ Math.floor((r-l)/2);
if(arr[mid]===target){
return mid;
}else if(arr[mid]>target){
return binarySearch(arr,l,mid-1,target);
}else{
return binarySearch(arr,mid+1,r,target);
}
}
如何快速找出两个数之和等于某一个值的两个数？
如何从一个数组中快速找出两个数之和等于某一个值的两个数？
穷举法
用for循环的嵌套，穷举，这种方法的时间复杂度为O（n^2），是最差的方法
快排+双指针
function pickNumOfSum(arr,sum){
var i,j;
var n = arr.length;
for(i=0,j=n-1;i<j;){
if(arr[i]+arr[j]===sum){
return [i,j]
}else if(arr[i]+arr[j]<sum){
i++;
}else{
j--;
}
}
return [-1,-1];
}
var a = [10,8,98,3,5,9,8,20];
a = a.sort(function(x,y){
return x-y;
})
pickNumOfSum(a,108)
如果换成是找出三个数之和满足某一条件的值呢？
组合总和
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
var res = [];
function dfs(candidates,target,arr,j){
if(target<0){
return;
}
if(target===0){
res.push([...arr]);
return;
}
for(var i=j;i<candidates.length;i++){
arr.push(candidates[i]);
dfs(candidates,target-candidates[i],arr,i);
arr.pop();
}
}
dfs(candidates,target,[],0);
return res;
};
解题思路
递归终止的条件就是target等于零，还有一个问题是如何确保收集的结果不重复，这里需要进行剪枝操作
LeetCode原题地址：https://leetcode-cn.com/problems/combination-sum/description/
删除链表的倒数第N个节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
var virtulNode = new ListNode('virtul');
virtulNode.next = head;
var p = virtulNode;
var q = virtulNode;
for(var i=0;i<n+1;i++){
q=q.next;
}
while(q!= null){
p=p.next;
q=q.next;
}
var delNode = p.next;
p.next = delNode.next;
return virtulNode.next;
};
leetcode原题链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
积雨水的问题
方法一：两头往中间挤
var trap = function(arr) {
var leftPoint = 0, // 左侧指针
rightPoint = arr.length -1, // 右侧指针
leftMax = arr[leftPoint], // 左侧最大值
rightMax = arr[rightPoint], // 右侧最大值
res = 0 // 雨水量
while (leftPoint < rightPoint) {
// 在左侧指针和右侧指针相碰之前，一直进行下面的步骤
if (leftMax < rightMax) { // 如果左侧最大值小于右侧最大值
leftPoint++ // 左指针向右移一步
if(leftMax < arr[leftPoint]) { // 此时，如果左侧最大值小于左指针所在的值，说明指针所在的值为左侧最大值，所以更新最大值，
leftMax = arr[leftPoint]
} else { // 如果左侧最大值大于左指针所在的值，那就把左指针所在的柱和左侧最大值的差值算作雨水量加入到res中
res += leftMax - arr[leftPoint];
}
} else { // 右侧同理
rightPoint --
if (rightMax < arr[rightPoint]) {
rightMax = arr[rightPoint]
} else {
res += rightMax - arr[rightPoint];
}
}
}
return res;
};
方法二：某一个节点能积累的水量 = (Min( Max(它前面的节点) , Max(它后面的节点)) - 它自身的高度)
var trap = function(arr){
if(arr.length<3){return 0};
var res = 0
for(var i=1; i<arr.length-1; i++){
var leftMax = Math.max(...arr.slice(0,i));
var rightMax = Math.max(...arr.slice(i+1,arr.length));
var min = Math.min(leftMax,rightMax);
if(arr[i]<min){
res += min-arr[i]
}
}
return res;
}
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]))
全排列
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
if(nums.length===0) return [];
var used = {};
var res = [];
function combine(nums,index,s){
if(index === nums.length){
res.push([...s]);
return;
}
for(var i=0;i<nums.length;i++){
if(!used[i]){
s.push(nums[i]);
used[i]= true;
combine(nums,index+1,s);
s.pop(); // 恢复现场
used[i]=false; // 恢复现场
}
}
return;
}
combine(nums,0,[]);
return res;
};
解题思路
用res记录收集的结果。用s记录深度遍历时捡到的值。一旦达到叶子节点的时候，就把捡到的值放到res中。然后回溯。 这里需要注意的是，在深度遍历的过程中，已遍历的数字，不要再参与遍历了。所以需要有一个字段来记录一下在之前的路径中是否已经使用过某个数字。而且在回溯的过程中。s数组需要恢复原状。
LeetCode原题地址：https://leetcode-cn.com/problems/permutations/description/
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.