function checkPalindrom(str) {
    return str == str.split('').reverse().join('');
}

console.log(checkPalindrom('mamam')); //true
console.log(checkPalindrom('banana')); //false

2.去掉数组的重复值

let unique = function(arr) {
 let hashTable = {};
 let data = [];
  for (let i = 0, l = arr.length; i < l; i++) {
        if (!hashTable[arr[i]]) {
           hashTable[arr[i]] = true;
           data.push(arr[i]);
      }
   }
   return data
}
var arr = [1, 13, 24, 11, 11, 14, 1, 2] console.log(unique(arr)) //[1, 13, 24, 11, 14, 2]

//es6
var arr = [1, 13, 24, 11, 11, 14, 1, 2];
let uniqueES6 = function(arr) {
  return Array.from(new Set(arr))
}
console.log(uniqueES6(arr)) //[1, 13, 24, 11, 14, 2]

3.统计一个字符串出现最多的字母

给出一段英文连续的英文字符窜，找出重复出现次数最多的字母

比如： 输入：afjghdfraaaasdenas 输出 ： a

前面出现过去重的算法，这里需要是统计重复次数。

function findMaxDuplicateChar(str) {
  if (str.length == 1) {
      return str
  }

   let charObj = {}
    for (let i = 0; i < str.length; i++) {
       if (!charObj[str.charAt(i)]) {
          charObj[str.charAt(i)] = 1;
     } else {
            charObj[str.charAt(i)] += 1;
        }
   }

   let maxchar = '',
   maxvalue = 1;
   for (var k in charObj) {
        if (charObj[k] >= maxvalue) {
            maxchar = k;
            maxvalue = charObj[k];
      }
   }
   return maxchar;

}
console.log(findMaxDuplicateChar('gffhghjllyesdfffnmfffssssffffjjffff')) //f

4.排序算法

如果说到算法题目的话，应该大多都是比较开放的题目，不限定算法的实现，但是一定要求掌握其中的几种。

冒泡排序

插入排序

快速排序

选择排序

let arr = [4, 6, 32, 11, 5, 667, 39, 56, 78, 2, 42, 7];

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

/*插入排序*/
function insertionSort(array) {
  console.time('插入排序耗时：');
    for (var i = 1; i < array.length; i++) {
     var key = array[i];
     var j = i - 1;
      while (array[j] > key) {
         array[j + 1] = array[j];
            j--;
        }
       array[j + 1] = key;
 }
   console.timeEnd('插入排序耗时：');
 return array;
}
console.log(insertionSort(arr));

/*快速排序*/
function quickSort(arr) {
 //如果数组<=1,则直接返回
  if (arr.length <= 1) {
       return arr;
 }
   var pivotIndex = Math.floor(arr.length / 2);
    //找基准，并把基准从原数组删除
    var pivot = arr.splice(pivotIndex, 1)[0];
   //定义左右数组
    var left = [];
  var right = [];

 //比基准小的放在left，比基准大的放在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));
}

console.log(quickSort(arr))

// 选择排序
var arr = [8, 3, 9, 12, 45, 23, 4, 89, 48, 63, 27, 53, 56, 98]

function selectSort(arr) {
    var len = arr.length
    for (var i = 0; i < len - 1; i++) {
      for (var j = i + 1; j < len; j++) {
          if (arr[i] > arr[j]) {
               var temp = arr[i] arr[i] = arr[j] arr[j] = temp
         }
       }
   }

   return arr
}

console.log(selectSort(arr))
// 选择排序的思想是：把每一个数都与第一个数比较，如果小于第一个数，就把它们交换位置；这样一轮下来，最小的数就排到了最前面；重复n-1轮，就实现了选择排序
// 选择排序和冒泡排序思想上有些相近

5.使用canvas 绘制一个有限度的斐波那契数列的曲线

斐波那契数列曲线

数列长度限定在10.

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。我们一般都知道定义
fibo[i] = fibo[i-1]+fibo[i-2];

var canvas = document.querySelector('canvas');

        canvas.width = 600;
        canvas.height = 480;

        var coor = {
            x: 300,
            y: 240,
        };

        var ctx = canvas.getContext('2d');

        function draw(r, n ,prevR) {
            if(n>2) {
                switch(n%4) {
                    case 0 :
                        coor.y = coor.y - 5 * prevR;
                        coor.y = coor.y + 5 * r;

                        break;
                    case 1 :
                        coor.x = coor.x + 5 * prevR;
                        coor.x = coor.x - 5 * r;
                        break;
                    case 2 :
                        coor.y = coor.y + 5 * prevR;
                        coor.y = coor.y - 5 * r;
                        break;
                    case 3 :
                        coor.x = coor.x - 5 * prevR;
                        coor.x = coor.x + 5 * r;
                        break;
                }
            }
            ctx.beginPath();
            ctx.arc(coor.x,coor.y,5*r,Math.PI*0.5*(n),Math.PI*0.5*(n-1),true);
            if(n>1) {
                switch(n%4) {
                    case 0 :
                        ctx.moveTo(coor.x - 5*r,coor.y);

                        break;
                    case 1 :
                        ctx.moveTo(coor.x,coor.y + 5*r);
                        break;
                    case 2 :
                        ctx.moveTo(coor.x + 5*r,coor.y);
                        break;
                    case 3 :
                        ctx.moveTo(coor.x,coor.y-5*r);
                        break;
                }
            }

            ctx.lineWidth = 1;
            ctx.strokeStyle = '#fff';
            ctx.stroke();
        }

        /*生成斐波那契数组的方法*/
        function getFibonacci(n) {
            var fibarr = [];
            var i = 0;
            while(i<n) {
                if(i<=1) {
                    fibarr.push(i);
                }else{
                    fibarr.push(fibarr[i-1] + fibarr[i-2])
                }
                i++;
            }

            return fibarr;
        }

        console.log(getFibonacci(10))  //[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

        var data = getFibonacci(10);

        for(var i = 0,l=data.length;i<l;i++) {
            if(data[i]!=0) {
                draw(data[i],i,data[i-1]);

            }
        }

6.找出下列正数组的最大差值

比如： 输入 [10,5,11,7,8,9] 输出 6

这是通过一道题目去测试对于基本的数组的最大值的查找，很明显我们知道，最大差值肯定是一个数组中最大值与最小值的差。

var arr = [16, 5, 111, 7, 21, 9]

function getMaxProfit(arr) {

  const item1 = Math.max.apply(null, arr);

    const item2 = Math.min.apply(null, arr);

    return item1 - item2;

}

console.log(getMaxProfit(arr)) //106

//ES6的方法
var arr = [16, 5, 111, 7, 21, 9]
//ES6
function getMaxProfitES6(arr) {
 const item1 = Math.max(...arr);
 const item2 = Math.min(...arr);
 return item1 - item2;
}
console.log(getMaxProfitES6(arr));

7.随机生成指定长度的字符串

实现一个算法，随机生成指制定长度的字符窜。

比如：给定 长度 8 输出 4ldkfg9j

function randomString(n) {
  let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
   let tmp = '',
   l = str.length;
 for (let i = 0; i < n; i++) {
        tmp += str.charAt(Math.floor(Math.random() * l));
   }
   return tmp;
}

console.log(randomString(8))

7.计算一个整数的阶乘

function factorialize(num) {
    if (num < 1) {
       return 1;
   } else {
        return num * factorialize(num - 1);
 }
}
console.log(factorialize(5)); //120

8.找到提供的句子中最长的单词，并计算它的长度

function findLongestWord(str) {
  //转化成数组
 var astr = str.split(" ");
  //对数组中每个元素的字符串长度进行比较，按照字符串长度由大至小排列数组顺序。
 var bstr = astr.sort(function(a, b) {
       return b.length - a.length;
 });
 //取出数组中第一个元素(也就是最大长度的字符串）
   console.log(bstr[0]) //jumped
   var lenMax = bstr[0].length;
    //返回长度值
 return lenMax;
}

console.log(findLongestWord("The quick brown fox jumped over the lazy dog")); //6

array.sort()方法默认是升序排序，如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：

若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
若 a 等于 b，则返回 0。
若 a 大于 b，则返回一个大于 0 的值。
简单点：比较函数两个参数a和b，返回a-b升序，返回b-a降序

9.确保字符串的每个单词首字母都大写，其余部分小写。

function titleCase(str) {
 var astr = str.toLowerCase().split(" ");
    for (var i = 0; i < astr.length; i++) {
      astr[i] = astr[i][0].toUpperCase() + astr[i].substring(1, astr[i].length);
  }
   var string = astr.join(" ");
    return string;
}

console.log(titleCase("I'm a little tea pot")); //结果：I'm A Little Tea Pot

10.找出4个小数组中最大值，组成一个新数组

function largestOfFour(arr) {
    var newArr = [];
    for (i = 0; i < arr.length; i++) {
       arr[i].sort(function(a, b) {
            return b - a;
       });

     newArr.push(arr[i][0]);
 }
   return newArr;

}
console.log(largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]])); //[5,27,39,1001]

11.比较两个数组，然后返回一个新数组，该数组的元素为两个给定数组中所有独有的数组元素。换言之，返回两个数组的差异。

function diff(arr1, arr2) {
 var newArr = [];
    //过滤数组1中与数组2相等的项
    var arr1Filtered = arr1.filter(function(num) {
      for (var i = 0; i < arr2.length; i++) {
          if (num == arr2[i]) {
               return false;
           }
       }
       return true;
    });
 //过滤数组2中与数组1相等的项
    var arr2Filtered = arr2.filter(function(num) {
      for (var i = 0; i < arr1.length; i++) {
          if (num == arr1[i]) {
               return false;
           }
       }
       return true;
    });
 //连接两个数组
    newArr = arr1Filtered.concat(arr2Filtered);
 return newArr;
}

var arr1 = [1, "calf", 3, "piglet"],
arr2 = [1, "calf", 3, 4]

console.log(diff(arr1, arr2)); // ["piglet", 4]

//方法2
var arr1 = [1, "calf", 3, "piglet"],
arr2 = [1, "calf", 3, 4]

function fn(arr1, arr2) {
    var newArr = []
 var arr1Filtered = arr1.filter(function(num) {
      if (arr2.indexOf(num) != -1) {
          return false
        }
       return true
 })

  var arr2Filtered = arr2.filter(function(num) {
      if (arr1.indexOf(num) != -1) {
          return false
        }
       return true
 })

  return arr1Filtered.concat(arr2Filtered)
}

console.log(fn(arr1, arr2))

12.写一个 function，传入两个或两个以上的数组，返回一个以给定的原始数组排序的不包含重复值的新数组。

说明：所有数组中的所有值都应该以原始顺序被包含在内，但是在最终的数组中不包含重复值。

如：unite([1, 3, 2], [5, 2, 1, 4], [2, 1]) 应该返回 [1, 3, 2, 5, 4]。

unite([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8]) 应该返回 [1, 2, 3, 5, 4, 6, 7, 8]。

方法一：

function unite(arr1, arr2, arr3) {
    for (var j = 1; j < arguments.length; j++) {
     //过滤掉第j个数组中已经在前面出现过的值
       var filteredArr = arguments[j].filter(function(num) {
           for (var i = 0; i < arr1.length; i++) {
              if (arr1[i] == num) {
                   return false;
               }
           }
           return true;
        });
     arr1 = arr1.concat(filteredArr);
    }
   return arr1;
}

console.log(unite([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8])); //[1,2,3,5,4,6,7,8]

方法二：

function unite() {
   var arr = arguments[0]
  for (let i = 0; i < arguments.length; i++) {
     var filterArr = arguments[i].filter(function(num) {
         if (arr.indexOf(num) != -1) {
               return false
            }
           return true
     }) arr = arr.concat(filterArr)
  }

   return arr
}

console.log(unite([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8]));

13.求小于等于给定数值的质数（素数）之和。

说明：只有 1 和它本身两个约数的数叫质数。例如，2 是质数，因为它只能被 1 和 2 整除。1 不是质数，因为它只能被自身整除。给定的数不一定是质数。

如：sumPrimes(10) 应该返回 17。

function sumPrimes(num) {
   //将所有小于等于num的质数放进一个数组
   var arr = [];
   //1不是质数，从2开始循环，需算上num
   for (var i = 2; i <= num; i++) {
     var j = 2;
      //判断i能否被从2开始的数整除
        while (i % j !== 0) {
           j++;
        }
       //判断这个数是不是自身，是则加进数组
     if (i == j) {
           arr.push(i);
        }
   }
   //对数组求和
 var result = arr.reduce(function(a, b) {
        return a + b;
   });

 return result;
}

console.log(sumPrimes(10)) ///17

reduce() 方法接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终计算为一个值。

reduce() 可以作为一个高阶函数，用于函数的 compose。

注意: reduce() 对于空数组是不会执行回调函数的。

另外一种写法
function sumFun(num) {

  let sum = 0
 for (let i = 2; i <= num; i++) {
     var j = 2

       while (i % j !== 0) {
           j++
     }

       if (j == i) {
           sum += j
        }
   }

   return sum
}

console.log(sumFun(11)) //18

//方法三
function getPrimes(n) {
 var arr = []
    for (var i = 2; i <= n; i++) {
       var flag = true
     for (var j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) {
               flag = false
                break
           }
       }
       if (flag) {
         arr.push(i)
     }
   }
   //对数组求和
 var result = arr.reduce(function(a, b) {
        return a + b;
   });
 return result
}
//方法四
function getPrimes(n) {
 var prime = []
  var arr = []
    for (var i = 2; i <= n; i++) {
       if (!prime[i]) {
            arr.push(i) for (var j = i; j * i <= n; j++) {
               prime[j * i] = true;
            }
       }
   }

   //对数组求和
 var result = arr.reduce(function(a, b) {
        return a + b;
   });
 return result
}

14.对嵌套的数组进行扁平化处理。你必须考虑到不同层级的嵌套。

如：steamroller([1, [2], [3, [[4]]]]) 应该返回 [1, 2, 3, 4]。

steamroller([1, [], [3, [[4]]]]) 应该返回 [1, 3, 4]。

steamroller([1, {}, [3, [[4]]]]) 应该返回 [1, {}, 3, 4]。

function steamroller(arr) {
 var newArr = [];
    for (var i = 0; i < arr.length; i++) {
       if (!Array.isArray(arr[i])) {
           newArr.push(arr[i]);
        } else {
            newArr = newArr.concat(steamroller(arr[i]));
        }
   }
   return newArr;
}
console.log(steamroller([1, {},
[3, [[4]]]])) //[1, {}, 3, 4]

此题的解法是在一个for循环中使用了递归，在for循环中使用递归时，不会影响for循环的进程。

2、另外一种方法：

function flatten(arr) {
    while (arr.some(item = >Array.isArray(item))) {
      arr = [].concat(...arr)
 }
   return arr;
}
console.log(flatten([1, {},
[3, [[4]]]])); //[1, 2, 3]

some() 方法用于检测数组中的元素是否满足指定条件（函数提供）。

some() 方法会依次执行数组的每个元素：

• 如果有一个元素满足条件，则表达式返回true , 剩余的元素不会再执行检测。
• 如果没有满足条件的元素，则返回false。

注意： some() 不会对空数组进行检测。
注意： some() 不会改变原始数组。

3、es6新增的数组实例方法flat()

[1, 2, [3, 4]].flat()
// [1, 2, 3, 4]

flat()默认只会“拉平”一层，如果想要“拉平”多层的嵌套数组，可以将flat()方法的参数写成一个整数，表示想要拉平的层数，默认为1。

[1, 2, [3, [4, 5]]].flat()
// [1, 2, 3, [4, 5]]

[1, 2, [3, [4, 5]]].flat(2)
// [1, 2, 3, 4, 5]

如果不管有多少层嵌套，都要转成一维数组，可以用Infinity关键字作为参数。

[1, [2, [3]]].flat(Infinity)
// [1, 2, 3]

如果原数组有空位，flat()方法会跳过空位。

[1, 2, , 4, 5].flat()
// [1, 2, 4, 5]

4、如果数组中元素都是字符串，可以利用数组toString()方法
例如：['a',[b],c,[[d],e,[f,[g,h]]]]

var arr= ['a',[`b`],`c`,[[`d`],`e`,[`f`,[`g`,`h`]]]]
   console.log(arr.toString().split(','))

15.二分查找

function binary_search(arr, key) {
    var low = 0,
    high = arr.length - 1;
  while (low <= high) {
        var mid = parseInt((high + low) / 2);
       if (key == arr[mid]) {
          return mid;
     } else if (key > arr[mid]) {
         low = mid + 1;
      } else if (key < arr[mid]) {
         high = mid - 1;
     }
   }
   return - 1;
};

var arr = [2, 4, 6, 9, 11, 25, 28, 36, 44, 47, 67, 76, 79],
key = 36;
console.log(binary_search(arr, key)) //7

因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：

一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
……
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为
n/(2^m)=1;
2^m=n;
所以时间复杂度为：log2(n)

16.回文解码

现在有一个字符串，你要对这个字符串进行 n 次操作，每次操作给出两个数字：(p, l) 表示当前字符串中从下标为 p 的字符开始的长度为 l 的一个子串。你要将这个子串左右翻转后插在这个子串原来位置的正后方，求最后得到的字符串是什么。字符串的下标是从 0 开始的，你可以从样例中得到更多信息。输入描述:

每组测试用例仅包含一组数据，每组数据第一行为原字符串，长度不超过 10 ，仅包含大小写字符与数字。接下来会有一个数字 n 表示有 n 个操作，再接下来有 n 行，每行两个整数，表示每次操作的(p , l)。保证输入的操作一定合法，最后得到的字符串长度不超过 1000。

输出描述:

输出一个字符串代表最后得到的字符串。

输入例子:

ab

2

0 2

1 3

输出例子:

abbaabb

function reversecion(input) {
    var arr = input.split('\n') var str = arr[0],
   num = arr[1]

    for (var i = 0; i < num; i++) {
      var arrtemp = arr[i + 2]
        var start = arrtemp.split(' ') var startnum = +start[0]
     var endnum = +start[1]
      var temp = str.substr(startnum, endnum) str = str.substr(0, startnum + endnum) + temp.split("").reverse().join("") + str.substr(startnum + endnum)
  }

   return str;
}

var input = "ab\n2\n0 2\n1 3"console.log(reversecion(input)) //abbaabb
var input1 = "abc\n2\n0 2\n1 2"

console.log(reversecion(input1)) //abbbbac

substring()

substr()

slice()

slice()
第一个参数代表开始位置,第二个参数代表结束位置的下一个位置,截取出来的字符串的长度为第二个参数与第一个参数之间的差;若参数值为负数,则将该值加上字符串长度后转为正值;若第一个参数等于大于第二个参数,则返回空字符串.

substring()
第一个参数代表开始位置,第二个参数代表结束位置的下一个位置;若参数值为负数,则将该值转为0;两个参数中,取较小值作为开始位置,截取出来的字符串的长度为较大值与较小值之间的差.

substr()
第一个参数代表开始位置,第二个参数代表截取的长度

17.你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ?

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。 保证 n ≤ 100 , s ≤ L ≤ 10000

输出描述:

输出一个整数代表你至少需要的 CD 数量。

输入例子:

7 2 6

输出例子:

4

function getNum(n, s, l) {
 var maxPerCD = parseInt((l + 1) / (s + 1));
 var num = 0;
    if (maxPerCD > n) {
      if (n % 13 == 0) {
          return 2
        } else {
            return 1
        }
   }

   if (maxPerCD % 13 == 0) {
       maxPerCD--;
 }

   if (n % maxPerCD == 0) {
        return n / maxPerCD
 } else {
        if (n % maxPerCD % 13 == 0 && (n % maxPerCD == maxPerCD - 1)) { //如果余数可被13整除，并且余数等于每张CD最多歌数-1，
          // 这时候余数不能单独一张CD，也不能再从其他CD挪一张，只能再加一张CD
          return parseInt(n / maxPerCD) + 2

       } else {
            return parseInt(n / maxPerCD) + 1
       }
   }
}

console.log(getNum(7, 2, 6)) //4
console.log(getNum(28, 30, 400)) //3

18.从一个数组中找出与给定数字最接近的元素。例如，数组[1,23,24,14,31,45,11,18,54,47,75,99,65]，给定值70，输出75.

var arr = [1, 23, 24, 14, 31, 45, 11, 18, 54, 47, 75, 99, 65];
var n = 70;

function findNear(arr, n) {
 var returnNum, cha, temp;
   for (var i = 0; i < arr.length; i++) {
       temp = Math.abs(arr[i] - n) if (!cha || cha > temp) {
            cha = temp returnNum = arr[i]
       }
   }

   return returnNum
}

console.log(findNear(arr, n))

19.倒序打印链表的值，列如

node = {
            val:1,
            next:{
                val:2,
                next:{
                    val:3,
                    next:{
                        val:4
                    }
                }
            }
        }

输出 4 3 2 1

并且不能用web存储，比如不能使用临时变量 var temp = XXX

面试今日头条被问到了这个问题，当时没想上来。

var node = {
   val: 1,
 next: {
     val: 2,
     next: {
         val: 3,
         next: {
             val: 4
          }
       }
   }
}

function reverseFun(node) {
   if (!node) {
        return
  } else {
        reverseFun(node.next) console.log(node.val)
 }
}

reverseFun(node);

20.从一个有序数组中找出两个元素之和等于给定值得元素角标的集合，只能使用单次遍历，例如，从数组 [1,2,5,7,9,12,15,18]中找出两个和为19的元素的集合，输出[0,7] [3,5]。

var arr = [1,2,5,7,9,12,15,18]
        var s= 19

        function fun(arr,s){
            var len = arr.length
            var i=0,j=len-1
            while(i<j){
                if((arr[i]+arr[j])<s){
                    i++
                }else if((arr[i]+arr[j])>s){
                    j--
                }else{
                    var res = [i,j]
                    console.log(res)
                    i++
                    j--
                }
            }
        }

        fun(arr,s)
//[0, 7]  [3, 5]

21.求二叉树中和值为n的路径

题目描述:
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路

1. 前序遍历二叉树，每次更新当前路径的和curtSum；
2. 判断当前结点是否是叶子结点，以及curtSum是否等于expectNumber。如果是，把当前路径保存在res结果中；
3. 若不符合条件，则弹出此结点。
   实现代码

4. var tree = {
      "val": 0,
      "left": {
          "val": 1,
          "left": {
              "val": 3,
              "left": {
                  "val": 7,
                  "left": {
                      "val": 11,
                 }
              },
             "right": {
                 "val": 8,
                  "left": {
                      "val": 12,
                 }
              }
          },
         "right": {
             "val": 4,
              "left": {
                  "val": 9,
              }
          }
      },
     "right": {
         "val": 2,
          "left": {
              "val": 5,
          },
         "right": {
             "val": 6,
              "right": {
                 "val": 10,
             }
          }
      }
   }
   
   function FindPath(root, expectNumber) {
      var result = [];
       if (root === null) {
           return result;
     }
      dfsFind(root, expectNumber, [], 0, result);
    return result;
   
   }
   function dfsFind(root, expectNumber, path, currentSum, result) {
    currentSum += root.val;
   
    path.push(root.val);
   
       if (currentSum == expectNumber && root.left == null && root.right == null) {
           result.push(path.slice(0));
    }
      if (root.left != null) {
           dfsFind(root.left, expectNumber, path, currentSum, result);
    }
   
      if (root.right != null) {
          dfsFind(root.right, expectNumber, path, currentSum, result);
       }
   
      path.pop();
   }
   
   console.log(FindPath(tree, 18)) // [0, 2, 6, 10]

22.有一个数组和一个给定的值，从数组中选择任意数，可以重复选择，使其和为给定的值，求所需数最少的一组数。例如：数组[2,3,6,7] 常数7，[2,2,3] [7]两种组合的和值为7，所以需要数最少的组合是[7]。

var res = []
        function combinationSum(candidates,target){
          helper(candidates,target,[],0)
          
          var minNum = res[0].length,temp=0
          for(var i=1;i<res.length;i++){
            
            if(res[i].length<minNum){
              minNum= res[i].length
              temp = i
            }
          }

          console.log('所有符合条件的组合为：',res)
          console.log('最小个数为：', minNum)
          console.log('最小个数的组合为：', res[temp])

        }

        function helper(candidates,target,list,index){
            if(target == 0){
              res.push(list.slice())
            }

            for(var i=index;i<candidates.length;i++){
                if(candidates[i] <= target){
                  list.push(candidates[i])
                  helper(candidates,target-candidates[i], list, i)
                  list.pop()
                }
            }
        }

        combinationSum([1,3,4],6)

23.合并两个降序排列的数组，使合并之后数组仍然降序排列，要求时间复杂度低。例如：[100,97,92,89,80,76] [96,93,88,72,71,66,55] 合并后为[100,97,96,93,92,89,88,80,76,72,71,66,55]

var arr1 = [100, 97, 94, 88, 84, 80, 79, 77, 73, 68, 65, 62, 57, 55, 52, 49, 46, 44]
var arr2 = [96, 93, 90, 89, 85, 78, 74, 69, 63, 59, 57, 56, 52, 48, 46, 33]
function mergeFun(arr1, arr2) {
 var i = 0,
  j = 0;
  var res = []
    while (i < arr1.length && j < arr2.length) {
      if (arr1[i] > arr2[j]) {
         res.push(arr1[i++])
     } else if (arr1[i] == arr2[j]) {
            res.push(arr1[i++]) j++;
        } else {
            res.push(arr2[j++])
     }
   }

   while (i < arr1.length) {
        res.push(arr1[i++])
 }

   while (j < arr2.length) {
        res.push(arr2[j++])
 }

   return res
}

console.log(mergeFun(arr1, arr2))

24.输出杨辉三角第m行n列的值，m、n从0开始。

我们很容易想到用递归的方法实现，如下：

function triangle1(m,n){
            if(n==0||m==n){
                return 1
            }
            return (triangle1(m-1,n)||0) + (triangle1(m-1,n-1)||0)
        }

        console.log(triangle1(6,3))

递归的方法在计算较小的数时没问题，但是计算较大的数时就容易超时。
下面用数组的方法实现一下：

function triangle(m, n) {
 var arr = [[1]]
 for (var i = 1; i < m; i++) {
        arr[i] = []
     for (var j = 0; j <= i; j++) {
           arr[i][j] = (arr[i - 1][j - 1] || 0) + (arr[i - 1][j] || 0)
     }
   }

   return arr
}

console.log(triangle(64, 30))

25.给定一个整数数组 arr ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如，输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划法——O(N)

设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i]
= max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小

var arr = [2, 4, -3, 5, -1, 3, -2, -6, -5, 6]

function maxSubArray(arr) {
   var sum = arr[0],
   n = arr[0]; //当前循环最大和值
  for (var i = 1; i < arr.length; i++) {
       if (n > 0) {
         n += arr[i]
     } else {
            n = arr[i]
      }

       if (n > sum) {
           sum = n
     }
   }

   return sum
}

console.log(maxSubArray(arr))

26.无重复字符的最长子串的长度

无重复字符的最长子串
给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定 "abcabcbbefdxvbnmkjtgfsd" ，没有重复字符的最长子串是"fdxvbnmkjtg"，那么长度就是12。

给定 "bbbbb" ，最长的子串就是 "b"，长度是1。

给定 "pwwkew"，最长子串是"wke"，长度是3。请注意答案必须是一个子串，"pwke"是 子序列 而不是子串。

思路分析：
对字符串进行遍历，使用String.prototype.indexOf()实时获取遍历过程中的无重复子串并存放于str，并保存当前状态最长无重复子串的长度为res，当遍历结束时，res的值即为无重复字符的最长子串的长度。

function longSubString(str) {
    var res = 0,
    currentStr = '',
    len = str.length
    for (var i = 0; i < len; i++) {
      var char = str.charAt(i);
       var index = currentStr.indexOf(char) if (index == -1) {
         currentStr += char res = res < currentStr.length ? currentStr.length: res
        } else {
            currentStr = currentStr.substring(index + 1) + char
     }
   }

   return res
}

console.log(longSubString('abcabcbbefdxvbnmkjtgfsd'))

27.删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路:

这道题要用双指针来实现。先用first指针前进n，然后让second从head开始和first一起前进，直到first到了末尾，此时second的下一个节点就是要删除的节点。（另外，若first一开始前进n就已经不在链表中了，说明要删除的节点正是head节点，那么直接返回head的下一个节点接口。）

/**
 * 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) {
  let first = head, second = head;
  while (n > 0) {
    first = first.next
    n--
  }
  if (!first) return head.next;     // 删除的是头节点
  while (first.next) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return head
}

28.写一个函数获取两个日期之间所有日期，放在对象里。

例如：getAllDate('2018/09/10','2019/03/04')
输出：

{
        2018:{
            9:[12,13,14,...30],
            10:[...],
            11:[...],
            12:[...]
        },
        2019:{
            1:[...],
            2:[...],
            3:[1,2,3]
        }
    }

function getAllDate(startDate, endDate) {
  let startTime = new Date(startDate),
    endTime = new Date(endDate) let arr = [] let dateObj = {}

   while (startTime < endTime) {
        let year = startTime.getFullYear() let month = startTime.getMonth() let day = startTime.getDate()

       arr.push(year + '/' + month + '/' + day) startTime.setDate(startTime.getDate() + 1)
 }

   for (let i = 0; i < arr.length; i++) {
       let temp = arr[i].split('/') let year = parseInt(temp[0]),
      month = parseInt(temp[1]) + 1,
      day = parseInt(temp[2])

     if (!dateObj[year]) {
           dateObj[year] = {}
      }
       if (!dateObj[year][month]) {
            dateObj[year][month] = []
       }
       dateObj[year][month].push(day)
  }

   return dateObj
}

console.log(getAllDate('2018/09/10', '2019/03/04'))

29.给定一个字符串，形如：'a=12,b=23,c=k1,d=2s,k=$'，请写一个find方法，给定左侧值，找到右侧值，例如：find('a')，打印：‘12’。

var str = 'a=12,b=23,c=k1,d=2s,k=$'

function find(param) {
   var arr = str.split(',') var obj = {}
   for (var i = 0; i < arr.length; i++) {
       obj[arr[i].split('=')[0]] = arr[i].split('=')[1]
    }

   console.log(obj[param])
}

find('k')

30.给定一个字符串，找出无重复字母的最长子串。

function func(str){
        var subStr = ''
        var arr = []
        var maxLen = 0
        var maxIndex=0
        var subMaxStr = ''
        for(var i=0;i<str.length;i++){
            if(subStr.indexOf(str.charAt(i))===-1){
                subStr+=str.charAt(i)
            }else{
                arr.push(subStr)
                subStr = subStr.split(str.charAt(i))[1]+str.charAt(i)
            }
        }

        maxLen = arr[0].length
        subMaxStr = arr[0]
        for(var j=1;j<arr.length;j++){
            if(arr[j].length>maxLen){
                maxLen =  arr[j].length
                maxIndex = j
                subMaxStr = arr[j]
            }
        }

        console.log(subMaxStr)
    }

    func('zxcvbngfdvfeeewdfrgthfqwertyuiokjhofd')
    func('zxcvbngfeefd')

方法二

function getSubString(str) {
  let longSub = '',
   len = str.length,
   currentStr = '',
    max = 0

 for (let i = 0; i < len; i++) {
      let char = str.charAt(i) if (currentStr.indexOf(char) == -1) {
          currentStr += char
          if (max < currentStr.length) {
               max = currentStr.length longSub = currentStr
            }
       } else {
            currentStr = currentStr.substring(currentStr.indexOf(char) + 1) + char
      }
   }

   return longSub

}

console.log(getSubString('zxcvbngfdvfeeewdfrgthfqwertyuiokjhofd')) console.log(getSubString('zxcvbngfeefd'))

31.给一个obj，要求实现一个console.tree(obj)，在控制台以缩进的形式打印这个值的树状结构（不要打印原型链中的方法名称），例如：

var obj = {'x':1,'y':{'z':2,'b':4,'c':{'d':5}},'a':3}
打印：

console.__proto__.tree = function(json) {
 var i = 0
   var str = ''
    var fun = function(json) {
      for (var key in json) {
         if (json.hasOwnProperty(key)) {
             if (typeof json[key] === 'object') {
                    str += '\t'.repeat(i) + '|---' + key + '\n'i++fun(json[key]) i--
                } else {
                    str += '\t'.repeat(i) + '|---' + key + ':' + json[key] + '\n'
               }
           }
       }
   }

   fun(json) console.log(str)
}

var json = {
 'x': 1,
 'y': {
      'z': 2,
     'b': 4,
     'c': {
          'd': 5
      }
   },
  'a': 3
}
console.tree(json)

32.有一组不同高度的台阶，有一个整数数组表示，数组中每个数是台阶的高度，当开始下雨了（雨水足够多）台阶之间的水坑会积水多少呢？如下图，可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1]，返回积水量6。

方法一

先在这个数组中找到最大值，然后从左右两边遍历。以左边为例，只要当前的数字比下一个数字大，那么这个数字的右边就可以存水，按照这个思路去分析就可以了，右边的也是一样的道理。
代码如下：

let maxIndex=0,max = arr[0]
for(let i=1;i<arr.length;i++){

    if(arr[i]>max){
        max=arr[i]
        maxIndex = i
    }
}
let sum = 0,leftMax=arr[0],rightMax=arr[arr.length-1]

for(let i=1;i<maxIndex;i++){
    if(arr[i]<leftMax){
        sum += (leftMax-arr[i])
    }else{
        leftMax = arr[i]
    }
}

for(let j = arr.length-1;j>maxIndex;j--){
    if(arr[j]<rightMax){
        sum += (rightMax - arr[j])
    }else{
        rightMax = arr[j]
    }
}

console.log(sum)

方法二

这个原理和方法一一样，只需一次遍历，相对方法一略微难理解。

let leftM = arr[0],rightM = arr[arr.length-1],leftIndex = 0,rightIndex = arr.length-1,volumn=0
while (leftIndex < rightIndex) {
    if(leftM < rightM){
        leftIndex++
        if(arr[leftIndex]>leftM){
            leftM = arr[leftIndex]
        }else{
            volumn += (leftM-arr[leftIndex])
        }

    }else{
        rightIndex--
        if(arr[rightIndex]>rightM){
            rightM = arr[rightIndex]
        }else{
            volumn += (rightM - arr[rightIndex])
        }

    }
}

console.log(volumn)

33.替换字符串中所有指定的子字符串。

例如：替换‘asssdfgghhjsssertyu’中‘sss’

方法一：

str.replace(/需要替换的字符串/g，"新字符串")

'asssdfgghhjsssertyu'.replace(/sss/g,'123')
这种形式要替换的字符串没法用参数，可以用

var str = 'asssdfgghhjsssertyu'
function replacer(str, str1, str2) {
  return str.replace(new RegExp(str1, 'g'), str2)
}
console.log(replacer(str, 'sss', 12))

方法二

var str = 'asssdfgghhjsssertyu'
function replacer(str, str1, str2) {
 var arg = str.split(str1) return arg.join(str2)
}
console.log(replacer(str, 'sss', 12))

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

解法一：有点暴力，主要思路为抛出本身后，利用indexOf查询查找是否存在重复值，不存在则直接返回当前索引
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {

  var len = s.length;
 for (var i = 0; i < len; i++) {

      var str = s,
        test = str.split('');
       test.splice(i, 1);
      var sub = test.indexOf(s[i]);

       if (sub === -1) return i;

   }

   return - 1;
};

方法二　　方法一用到了indexOf,
所以时间复杂度也达到了O（n ^ 2）,
　　则想到了利用哈希来存储重复的次数，在循环字符串查找哈希中值为1的这个字符，第一次遇到则返回，这样循环次数相对减少时间复杂度也降到了O（n）
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {

   var len = s.length,
 haxi = {};

  for (var i = 0; i < len; i++) {

      var sub = haxi[s[i]];

       if (sub) {
          haxi[s[i]] = ++sub;
     } else {
            haxi[s[i]] = 1;
     }

   }

   for (var i = 0; i < len; i++) {

      if (haxi[s[i]] === 1) {
         return i
        }

   }
   return - 1;
};

34.实现一个函数 find(obj, str)，满足:

如：

var obj = {
  a: {
        b: {
            c: 1
        }
   }
};
var obj2 = {
 d: {
        e: {
            f: 2
        }
   }
}
find(obj, 'a.b.c') //返回1
find(obj, 'a.d.c') //返回undefined 
find(obj2, 'd') //返回{e:{f:2}}
find(obj2, 'd.e.f') //返回2

function find(obj, str) {
  var arrStr = str.split('.')

 var newObj = obj
    for (var i = 0; i < arrStr.length; i++) {
        var temp = newObj[arrStr[i]]

        if (temp) {
         newObj = temp
       } else {
            return undefined
        }

   }

   return newObj
}

var obj = {
   a: {
        b: {
            c: 1
        }
   }
};
var obj2 = {
 d: {
        e: {
            f: 2
        }
   }
}
console.log(find(obj, 'a.b.c')) //返回1
console.log(find(obj, 'a.d.c')) //返回undefined 
console.log(find(obj2, 'd')) //返回{e:{f:2}}
console.log(find(obj2, 'd.e.f')) //返回2

35.把数值转化为货币形式，并保留两位小数。

例如：输入1234567.891，输出1,234,567.89

function int2str(num) {
   let newNum = num.toFixed(2) let arr = newNum.toString().split('.') let strLeft = arr[0],
    strRight = arr[1]

   let str = strLeft.split('').reverse() for (let i = 0; i < str.length; i++) {
     if ((i + 1) % 4 === 0) {
            str.splice(i, 0, ',')
       }
   }
   str.reverse()

   let reg = str.join('') + '.' + strRight
 return reg
}

console.log(int2str(1234567.891))

36.jS写一个方法，传入一个数组，返回该数组的层深(维度)

如：var arr = [1,[2,3,[4,[5,6,7]],11],[8]]

function fo(arr, len) {
  var flag = false
    var arr1 = []

   for (var i = 0; i < arr.length; i++) {
       if ( !! arr[i].length) {
            for (var j = 0; j < arr[i].length; j++) {
                arr1.push(arr[i][j])
            }
           flag = true
     }
   }

   if (flag) {
     len++
       return fo(arr1, len)
    } else {
        return len
  }
}

var arr = [1, [2, 3, [4, [5, 6, 7]], 11], [8]] console.log(fo(arr, 1))

作者：指尖跳动
链接：https://www.jianshu.com/p/2f38ac50c63a
来源：简书
著作权归作者所有。