n日一道题

1.字符串反转 abc -> cba

方法一：

var str = 'abc';

var newStr = str.split('').reverse().join('');
console.log(newStr);

方法二：

var str = 'abc';
var newStr1 = str.split('').reduce(function (total, value) {
    return value + total;
})
console.log(newStr1);

方法三：

var str = 'abc';
var newStr2 = ''
for (var i of str) {
    newStr2 = i + newStr2;
}
console.log(newStr2);

方法四：

var str = 'abc';
var newStr2 = Array.from(str).reverse().join();
console.log(newStr2);

方法五：

var str = 'abc';
var newStr2 = [...str].reverse().join();
console.log(newStr2);

2.Int类型反转

方法：

function reverseInt(number){
    var newNumber = 0;
    while(number%10 != 0 || number/10 != 0){ 
        newNumber = number%10 + newNumber*10;
        number = parseInt(number/10);
    }
    return newNumber;
}
reverseInt(-51230);//-3215

3.多维数组扁平化

[1,[2,3],[4,[5,6]]] => [1,2,3,4,5,6];

方法一：

var arr = [1, [[2, 3], 4]];
var str = arr.toString().split("");
var newArr = [];
for(key of str){
  key != "," && (newArr.push(key));
}
console.log(newArr);

方法二：

var arr = [1, [2, 3], [4, [5, 6]]];
var newArr = [];
function flat(arr) {
    if (arr instanceof Array) {
        arr.forEach(function (value) {
            return flat(value);
        });
    } else {
        return newArr.push(arr);
    }
}
flat(arr);
console.log(newArr);

方法三：

var arr = [1,8,[2, 3], [4, [5, 6]]];
function flat(arr){
   return arr.reduce(function(prev, cur){
        console.log(cur);
        return prev.concat(Array.isArray(cur)?flat(cur):cur);
    },[])
}

console.log(flat(arr));

方法四：

var arr = [1, 8, [2, 3], [4, [5, 6]]];
var newArr = [];
function* flat(arr) {
    if (Array.isArray(arr)) {
        for (let i = 0; i <  arr.length; i++){
            yield* flat(arr[i]);
        }
    } else {
        yield arr;
    }
}
var g = flat(arr);
for(key of g){
    newArr.push(key);
}
console.log(newArr);

4.breakCamelCase(‘camelCasing’) => ‘camel Casing’

function breakCamelCase(str){
  return str.replace(/\d*[A-Z]/g,function(c){
    return " " + c;
  })
}

5.camelCase(‘test case’) => TestCase

function camelCase(str) {
  return str.replace(/[ ]?\b\w/g,function(c){
    console.log(c);
    return c.trim().toUpperCase();
  })
}

6.toUnderscore(‘TestController’) => ‘test_controller’

function toUnderscore(str)  {
  return str.replace(/\B(?=[A-Z])/g,function(c){
      console.log(c);
    return c+"_"
  })
}

7.toCamelCase(‘the-stealth-warrior’) => ‘theStealthWarrior’

function toCamelCase(str)  {
  return str.replace(/-\w/g,function(c){
    return c.slice(1).toUpperCase();
  })
}

8.判断两个对象是否相等

var obj1 = {name:'qinhanwen',age:{name:'qinhanwen',age:{a:1}}};
var obj2 = {name:'qinhanwen',age:{name:'qinhanwen',age:{a:1}}};

function equal(obj1,obj2){
 var same = true;
 if(Object.keys(obj1).length === Object.keys(obj2).length){
     Object.keys(obj1).forEach(function(value){
        if(!same)return; 
        if(obj1[value] instanceof Object){
             same = equal(obj1[value],obj2[value]); 
        }else{
             same = (obj1[value] === obj2[value]);
        }    
     })
 }else{
     same = false;    
 }
 return same;
}
console.log(equal(obj1,obj2));

9.判断两个数组是否相等

var arr1 = [1, [1, 2]];
var arr2 = [1, [1, 2]];
equal(arr1,arr2);//true

function equal(obj1,obj2){
 var same = true;
 if(Object.keys(obj1).length === Object.keys(obj2).length){
     Object.keys(obj1).forEach(function(value){
        if(!same)return; 
        if(obj1[value] instanceof Object){
             same = equal(obj1[value],obj2[value]); 
        }else{
             same = (obj1[value] === obj2[value]);
        }    
     })
 }else{
     same = false;    
 }
 return same;
}
console.log(equal(arr1,arr2));//true

10.看题吧。。

var obj1 = {a:1,b:2};
var obj2 = {b:2,a:1};

var arr1 = [1,2,{a:1,b:2},3];
var arr2 = [1,2,{b:2,a:1},3];
equal(obj1,obj2);//true
equal(arr1,arr2);//true
equal(obj1,arr1);//false

function equal(obj1,obj2){
 var same = true;
 if(Object.keys(obj1).length === Object.keys(obj2).length){
     Object.keys(obj1).forEach(function(value){
        if(!same)return; 
        if(obj1[value] instanceof Object){
             same = equal(obj1[value],obj2[value]); 
        }else{
             same = (obj1[value] === obj2[value]);
        }    
     })
 }else{
     same = false;    
 }
 return same;
}

11.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

//给定 nums = [2, 7, 11, 15], target = 9

//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]

var twoSum = function(nums, target) {
    var arr = [];
    var sameNumber = [];
    nums.forEach(function(item,i){
        nums.forEach(function(value,index){
            if(item + value == target && sameNumber.indexOf(value)  == -1 && i != index){
               arr.push(i,index);
               sameNumber.push(item);
            }
        })
    })
    return arr;
};

12.实现一个merge方法

merge([1,2,2,3,4,5,5,6]);//[1,2,3,4,5,6];
//方法一
function merge(arr){
   var ret = [];
   for(var i = 0;i<arr.length;i++){
       if(arr[i] !== ret[ret.length - 1]){
           ret.push(arr[i]);
       }
   }
   return ret;
}

//方法二
function merge(arr){
    var ret = arr.filter(function(value,i){
        return value != arr[i-1];
    })
   return ret;
}

13.实现如下方法

composeFunction(fn1,fn2,fn3)等于fn3(fn2(fn1()));
//例如:
const add = x => x+1;
const multiply = x * y;
const multiplyAdd = composeFunction(multiply,add);
multiplyAdd(3,4);//13

//方法一：
function composeFunction() {
    var arr = Array.from(arguments);
    function test() {
        var fn = arr.splice(0, 1)[0];
        if (arr.length > 0) {
            test(fn.apply(null, arguments));
        } else {
            console.log(fn.apply(null, arguments));
        }
    }
    return test;
}
//非严格模式下
function composeFunction() {
    var arr = Array.from(arguments);
    return function() {
        var fn = arr.splice(0, 1)[0];
        if (arr.length > 0) {
            arguments.callee(fn.apply(null, arguments));
        } else {
            console.log(fn.apply(null, arguments));
        }
    };
}

//方法二
function composeFunction(){
  let args = Array.from(arguments);
  return function(){
    let fn, result = arguments;
    while(fn = args.shift()){
      result = [fn.apply(null,result)]
    }
      return result[0];
  }
}

14.排序

在下面

15.

class Squence {
    static index = 1;
    next(){
        console.log(Squence.index++);
    }
}


var squence1 = new Squence();
squence1.next();
squence1.next();

var squence2 = new Squence();
squence2.next();
squence2.next();

16.

function capitalize(str){
   return str.split(" ").map((item)=>{
        return item[0].toUpperCase()+item.substr(1);
    }).join(" ");
}

17.

function maxChar(str){
    var obj={},maxChar = 0,key;
    for(let i = 0;i<str.length;i++){
        obj[str[i]]?(obj[str[i]]++):(obj[str[i]] = 1);
    }
    Object.keys(obj).forEach(item=>{
        if(obj[item]>maxChar){
            maxChar = obj[item];
            key=item;
        }else{
            maxChar = maxChar;
        }
    })
    return key;
}

//少一轮循环
function maxChar(str){
    let max = 0, maxStr = "",map={},len = str.length;
    for(let i = 0;i<len;i++){
        if(map[str[i]]){
            map[str[i]]++;
        }else{
            map[str[i]] = 1;
        }
        if(map[str[i]]>max){
            max = map[str[i]];
            maxStr = str[i];
        }
    }
    return maxStr;
}
maxChar('aabbbcccc');

18.

function vowels(str){
    var reg = /(a|e|i|o|u)/g;
    return str.toString().match(reg) && str.toString().match(reg).length || 0;
}

19.

function pyraid(num){
    var col = 2*num-1;
    var src = '';
    var arr = [];
    var spaceNum = 0;
    for(let j = num;j > 0;j--){
        src = '';
        for(let i = 0;i < col; i++){   
            if(i<spaceNum/2 || (i >= col - spaceNum/2)){
              src+=' ';
            }else{
              src+='#';
            }
        }
        spaceNum+=2;
        arr.push(src);
    }
   return arr.reverse().join('\n');
}

20.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

var twoSum = function(nums, target) {
    const len = nums.length;
    for(let i=0;i<len;i++){
        for(let j=0;j<len;j++){
            if(nums[i]+nums[j] == target && i != j){
                return [i,j];
            }
        }
    }
};

var twoSum = function(nums, target) {
    const len = nums.length;
    for(let i=0;i<len;i++){
        let result = target - nums[i];
        let index = nums.indexOf(result);
        if(index>-1 && index != i)return [i,index]
    }
};

var twoSum = function(nums, target) {
    let res = {}
    
    for(let i = 0; i < nums.length; i++) {
        if(res[nums[i]] !== undefined) 
            return [res[nums[i]], i]
        else
            res[target - nums[i]] = i
    }
}

21.. 无重复字符的最长子串

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

示例：

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

var lengthOfLongestSubstring = function (s) {
    let max=0,left=0,len = s.length,map={};
    for(let i=0;i<len;i++){
        let v = s[i];
        if(map[v] !== undefined){
            left = left<=map[v]? map[v] + 1:left;
        }
        map[v] = i;
        max = Math.max(max,i-left+1);
    }
    return max;
};

22.回文数

示例：

输入: 121
输出: true

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

var isPalindrome = function(x) {
    var str = x.toString().split('').reverse().join('');
    return str == x;
};

var isPalindrome = function(x) {
    var str = x.toString(),strLen = str.length,len = Math.floor(strLen/2),equal = true;
    for(let i=0;i<len;i++){
        if(str[i] != str[strLen-i-1]){
            equal = false;
            break;
        }
    }
    return equal;
};

23.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例：

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

var longestCommonPrefix = function(strs) {
    var len = strs.length;
    if(len == 0)return '';
    if(len == 1){
        return strs[0];
    }else{
        strs = strs.sort();
        console.log(strs);
        let first = strs[0],last = strs[len-1],result='';
        for(let i = 0; i < last.length; i++){
                if(last[i] == first[i]){
                    result+=first[i];
                }else{
                    break;
                }
        }
        return result;
    }
};

24.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例：

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

var isValid = function(s) {
    if(!s)return true;
    if(!s.startsWith('(') && !s.startsWith('[') && !s.startsWith('{'))return false;
    let map = {
        "(":")",
        "[":"]",
        "{":"}"
    };
    let arr = [];
    const len = s.length;
    for(let i=0;i<len;i++){
        if(map.hasOwnProperty(s[i])){
            arr.push(s[i]);
        }else{
          if(map[arr.pop()] != s[i]){
              return false;
            }
        }
    }
    return !arr.length;
};

25.删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例：

给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

var removeDuplicates = function (nums) {
  if(nums.length === 0)return 0;
  for(let i=0;i<nums.length;i++){
      if(nums[i] === nums[i+1]){
          while(nums[i] === nums[i+1]){
             nums.splice(i,1);   
          }
      }
  }
  return nums.length;
};

var removeDuplicates = function (nums) {
  if(nums.length === 0)return 0;
  var j = 0;
  for(let i=0;i<nums.length;i++){
    if(nums[i] !== nums[j]){
      j++;
      nums[j] = nums[i];
    }
  }
  return j+1;
};

26.移除元素

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。

var removeElement = function(nums, val) {
    let len = nums.length,j=0;
    for(let i=0;i<len;i++){
        if(nums[i] != val){
           nums[j] = nums[i];
           j++;
       }
    }
    return j;
};

27.实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例：

输入: haystack = "hello", needle = "ll"
输出: 2

输入: haystack = "aaaaa", needle = "bba"
输出: -1

var strStr = function(haystack, needle) {
    if(!haystack && !needle)return 0;
    if(needle.length > haystack.length) return -1;
    var arr = haystack.split('');
    const needleLen = needle.length;
    const len = arr.length - needleLen + 1;
    for(let i = 0; i < len; i++){
        if(arr.slice(i,i+needleLen).join('') == needle){
           return i;
        }
    }
    return -1
};

28.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例：

输入: [1,3,5,6], 5
输出: 2

输入: [1,3,5,6], 2
输出: 1

输入: [1,3,5,6], 7
输出: 4

var searchInsert = function(nums, target) {
  var index = 0;
  const len = nums.length;
  for(let i=0;i<len;i++){
      if(nums[i] == target){
         return i;
      }else if(nums[i]<target){
           index = i + 1;    
      }
  }  
  return index;
};

29.最后一个单词的长度

给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

示例：

输入: "Hello World"
输出: 5

var lengthOfLastWord = function(s) {
    var arr = s.split(" ");
    var len = arr.length - 1;
    for(let i = len;i >= 0; i--){
        if(arr[i] != ""){
           return arr[i].length;
        }
    }
    return 0
};

30.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

var climbStairs = function(n) {
    if(n == 1)return 1;
    if(n == 2)return 2;
    var arr = [];
    arr.push(1,2);
    for(let i=2;i<n;i++){
      arr.push(arr[i-1]+arr[i-2]);
    }
    return arr[arr.length-1];
};

31.杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

 var generate = function(numRows) {
    var arr = [];
    for(let i=1;i<=numRows;i++){
        let item = [];
        for(let j=0;j<i;j++){
            if(j == 0 || i - 1 == j){
                item.push(1);
            }else{
                item.push(arr[i-2][j-1] + arr[i-2][j]);
            }
        }
        arr.push(item);
    }
    return arr;
};

32.买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。


输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let max = 0,min = prices[0];
    for(let i=0;i<prices.length;i++){
        if(prices[i] - min >max){
           max = prices[i] - min;
       }
       if(min>prices[i]){
            min = prices[i];
       }
    }
    return max;
};

33.买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let total = 0, min = prices[0];
    for(let i=0;i<prices.length;i++){
      if(min>prices[i] || prices[i]<prices[i-1]){
         min = prices[i];
        }
        if(prices[i]-min>0){
           total += prices[i]-min;
           min = prices[i];
       }
    }
    return total;
};

34.验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例:

输入: "A man, a plan, a canal: Panama"
输出: true

输入: "race a car"
输出: false

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    if(!s)return true;
    var reg = /([a-zA-Z0-9])/;
    var arr = s.split('');
    var newArr = arr.filter(item=>{
        return reg.test(item);
    }).map(item=>item.toLowerCase());
    return newArr.join('') == newArr.reverse().join('');
};

//没有大小写并且不忽略字符和数字字符的情况
function palindrong(str){
    if(typeof str !== 'string')throw new TypeError('');
    const LEN = str.length;
    for(let i = 0; i < Math.floor(LEN/2); i++){
        if(str[i] !== str[LEN-i-1])return false;
    }
    return true;
}

35.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例:

输入: [2,2,1]
输出: 1

输入: [4,1,2,1,2]
输出: 4

var singleNumber = function(nums) {
    return nums.reduce((v1, v2) => {
        return v1 ^ v2
    })
};

36.三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件的三元组。

会重复的三元组

var threeSum = function(nums) {
  let map = {},target = 0,len = nums.length,arr = [];
  for (let i = 0;i < len-1; i++){
    for(let j = i + 1;j < len;j++){
      if(map[nums[j]]){
        arr.push(map[nums[j]].concat(nums[j]));
        map[nums[j]] = undefined;
      }else{
        const key = target - nums[i] - nums[j];
        map[key] = [nums[i],nums[j]];
      }
    }
  }  
  return arr;
};

不重复的三元组

解题思路：先排序，记录最左边（最小值）和右边的值（最大值），然后从左边第二个开始匹配（匹配的值），三个数相加，如果结果大于0说明最大值太大，则最大值左移一位，如果小于0说明匹配的值太小，右移一位。

var threeSum = function (nums) {
  nums.sort((a, b) => a - b);//先排序
  const len = nums.length;
  let arr = [];
  for (let i = 0; i < len; i++) {
    let second = i + 1, last = len - 1;
    if (nums[i] > 0 || nums[last] < 0) break;//如果第一项大于0了，相加不可能为0，或者最后一项小于0
    if (nums[i] == nums[i - 1]) continue;//如果当前这一项和前面一项一样，就忽略
    while (second < last) {
      const result = nums[i] + nums[second] + nums[last];
      if (result == 0) {
        arr.push([nums[i], nums[second], nums[last]]);
        while(nums[second] == nums[++second]){}
      } else if (result < 0) {//小于0，说明太小了，左边负值的右移一位
        while(nums[second] == nums[++second]){}
      } else {//大于0说明 大的值太大，左移一位
        while(nums[last] == nums[--last]){}
      }
    }
  }
  return arr;
};

37.最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路：与上一题类似

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
  nums.sort((a, b) => a - b);//先排序
  const len = nums.length;
  let arr = [], min, total;//记录一下最接近的值和3个值加起来的数
  for (let i = 0; i < len; i++) {
    let second = i + 1, last = len - 1;
    if (nums[i] == nums[i - 1]) continue;//如果当前这一项和前面一项一样，就忽略
    while (second < last) {
      const result = nums[i] + nums[second] + nums[last];
      if(min == undefined){//如果没有最接近的值，就给初始值
          min = Math.abs(target - result);
          total = result;
      }
      if(min > Math.abs(result - target)){//如果值更小就更新
          min = Math.abs(result - target);
          total = result;
      }  
      if (result == target) {
        return result;
        while(nums[second] == nums[++second]){}
      } else if (result < target) {//小于0，说明太小了，左边负值的右移一位
        while(nums[second] == nums[++second]){}
      } else {//大于0说明 大的值太大，左移一位
        while(nums[last] == nums[--last]){}
      }
    }
  }
  return total;
};

38. 括号生成

示例:

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题思路，总共有2n个括号，一半左括号一半右括号，递归，每次都可以添加左括号或者右括号，根据左括号的数量是否小于总数来决定，而右括号必须小于左括号数量。

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    var arr = [];
    function add(str,l,r){
        if(l < n){
            add(str+"(",l+1,r);
        }
        if(r < l){
            add(str + ")",l,r+1);
        }
        if(l == n && r == n){
            arr.push(str);
        }
    }
    add('',0,0);
    return arr;
};

39.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

//暴力破解
 var longestPalindrome = function(s) {
    var max = '';
    var len = s.length
    if(len < 2) return s;
    for (var i = 0; i <= len; i++) {
        for (var j = 0; j <= len; j++) {
            var child = s.slice(i,j);
            var child_len = child.length;
            var max_len = max.length;
            var arr = child.split('');
            var str1 = arr.join();
            var str2 = arr.reverse().join();
            if(str1 === str2 && max_len < child_len) max = child;
            child = child_len = max_len = arr = str1 = str2 = null
        }
    }
    return max;
};

40.冒泡排序

遍历n次，每次循环相邻元素两两比较，把其中大的元素往后放

var array = [5, 4, 3, 2, 1, 8, 7];

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

bubbleSort(array)

41.选择排序

找到最小的，然后替换前面的位置

var arr = [3, 5, 4, 2, 1];
function selectionSort(arr){
  let minIndex;
 	for(let i = 0;i < arr.length; i++){
    minIndex = i;
    for(let j = i; j< arr.length; j++){
      if(arr[j]<arr[minIndex]){
         minIndex = j;
      }
    }
    if(minIndex !== i){
      swap(arr,i,minIndex);
    }
  }
  return arr;
}
function swap(arr,i,j){
  [arr[i],arr[j]] = [arr[j],arr[i]];
}
selectionSort(arr);

42.插入排序

这个确实比较复杂，需要理解很久

1.外层遍历这个不用说，取到当前的 i 项是target

2.内层遍历，从j开始做减1操作，target跟上一个位置

的值比较，如果小于，就做偏移，直到最后不小于，就终止循环，

并且把target赋值给当前位置的值。

var arr = [5, 3, 4, 2, 1];

function insertionSort(array) {
    for (var i = 0; i < array.length; i++) {
        var target = array[i];
        let j = i;
        while (array[j - 1] > target && j > 0) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = target;
    }
    return array
}
insertionSort(arr);

43.归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

function mergeSortRec(array) {
  if (array.length == 1) return array;
  const mid = Math.floor(array.length / 2);
  let left = array.slice(0, mid);
  let right = array.slice(mid);
  return merge(mergeSortRec(left), mergeSortRec(right));
}

function merge(arr1, arr2) {
  var leftIndex = 0;
  var rightIndex = 0;
  var result = [];
  while (leftIndex < arr1.length && rightIndex < arr2.length) {
    if (arr1[leftIndex] > arr2[rightIndex]) {
      result.push(arr2[rightIndex++]);
    }else{
      result.push(arr1[leftIndex++]);
    }
  }
  while (leftIndex < arr1.length) {
    result.push(arr1[leftIndex++]);
  }
  while (rightIndex < arr2.length) {
    result.push(arr2[rightIndex++]);
  }
  return result;
}
console.log(mergeSortRec([8,7,6,5,4,3,2,1]));

快速排序

它的复杂度为 O(nlog^n)，它的性能比其他复杂度一样的排序算法好。也是用分治的方法。

function quick(array, left, right) {
  if(array.length == 1)return;
  const leftIndex = partition(array, left, right);
  if(left < leftIndex - 1){
    quick(array, left, leftIndex - 1);
  }
  if(right > leftIndex){
    quick(array, leftIndex, right);
  }
}
function partition(array, left, right) {
  let leftIndex = left;
  let rightIndex = right;
  const mid = array[Math.floor((right + left) / 2)];
  while (leftIndex < rightIndex) {
    while (array[leftIndex] < mid) {
      leftIndex++;
    }
    while (array[rightIndex] > mid) {
      rightIndex--;
    }
    if (leftIndex < rightIndex) {
      swap(array, leftIndex, rightIndex);
      leftIndex++;
      rightIndex--;
    }
  }
  return leftIndex;
}
function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]];
}
var arr = [7, 1, 2];
quick(arr, 0, arr.length - 1);

45.取出数组最大值

es5、es6

var arr = [1,2,3,4,5];
Math.max.apply(null,arr);

Math.max(...arr);

arr.reduce((a,b)=>{
  return a>b?a:b;
})

46.实现下面

add(1); 	// 1
add(1)(2);  	// 3
add(1)(2)(3)；  // 6
add(1)(2, 3);   // 6
add(1, 2)(3);   // 6
add(1, 2, 3);   // 6

//方法1这个需要传入参数长度
function curry(fn,length){
    const LEN = length || fn.length;
    let args = [];
    return function(){
        args = args.concat([...arguments]);
        return LEN>args.length?arguments.callee:fn.apply(null,args);
    }
}

function addFn(){
    return [...arguments].reduce((total,next)=>{
        return total + next;
    })
}
var add = curry(addFn,3);

//方法2 调用console或者alert会对fn做隐式转换
function curry(fn){
    let result = [];
    return function(){
        result = [fn.apply(null,result.concat([...arguments]))];
        arguments.callee.toString = arguments.callee.valueOf = function(){
            return result[0];
        }
        return arguments.callee;
    }
}

function addFn(){
    return [...arguments].reduce((total,next)=>{
        return total + next;
    })
}
var add = curry(addFn);

//修改一下上面的
function curry(fn){
    let result = [];
    function _add(){
        result = [fn.apply(null,result.concat([...arguments]))];
        return _add;
    }
    _add.toString = _add.valueOf = function(){
        return result[0];
    }
    return _add;
}

function addFn(){
    return [...arguments].reduce((total,next)=>{
        return total + next;
    })
}
var add = curry(addFn);

47.删除排序链表中的重复元素

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
//排序链表



//未排序链表
var deleteDuplicates = function(head) {
    const linkedList = head;
    let map = new Map(),pre=head;
    while(head){
        if(map.has(head.val)){
            while(head.next && head.val == head.next.val){
               head = head.next;
            }
            pre.next = head.next || null;
        }else{
            map.set(head.val);
        }
        pre = head;
        head = head.next;
    }
    return linkedList
};

48.最大子序和

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

示例：

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

思路：

// 假设你是一个选择性遗忘的赌徒，数组表示你这几天来赢钱或者输钱，
// 你用sum来表示这几天来的输赢，
// 用ans来存储你手里赢到的最多的钱，
// 如果昨天你手上还是输钱（sum < 0），你忘记它，明天继续赌钱；
// 如果你手上是赢钱(sum > 0), 你记得，你继续赌钱；
// 你记得你手气最好的时候

var maxSubArray = function(nums) {
  if(!Array.isArray(nums) && !nums.length)return undefined;
	let sum = nums[0];
  let ans = nums[0];
  const len = nums.length
  for(let i = 1; i < len; i++){
    if(sum < 0){
        sum = nums[i];
    }else{
        sum = sum + nums[i];
    } 
    ans = Math.max(ans, sum);
  }
  return ans;
};

49.跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路：

//从最后一位开始遍历，如果找到左边有合适它的，就从当前这个位置开始

//这个遍历2次，希望能找到每次能到达当前值的最大值
var canJump = function (nums) {
  //设置默认条件，不满足直接退出
    if (!Array.isArray(nums) || Array.isArray(nums) && nums[0] == 0 && nums.length != 1) return false;
    if (nums.length == 1) return true;
  
    let bigestIndex = nums.length - 1; //需要到达的最后一个位置
    let max = 0;//设置最大能到达的值
    for (let j = 0; j < bigestIndex; j = 0) {
        out = true;
        for (let i = bigestIndex - 1; i >= 0; i--) {//遍历寻找能到达当前位置的最大值
            if (max < nums[i] && nums[i] + i >= bigestIndex) {
                max = nums[i];
                bigestIndex = i;
                out = false;
            }

        }
        if(max == 0)return false;
        max = 0;
    }
    return true;
};

//优化上面，一次循环就够，从最后一个开始往前找，有没有能到达当前位置的值
var canJump = function (nums) {
    if (!Array.isArray(nums)) return false;
    let leftIndex = nums.length - 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] >= leftIndex - i) {
            leftIndex = i;
        }
    }
    return leftIndex == 0;
};

50.取两个集合中相同的

function fn(arr1,arr2){
    let shortArr = arr1.length>arr2.length?arr2:arr1;
    let longArr = arr1.length>arr2.length?arr1:arr2;
    let map = new Map();
    return shortArr.filter((value)=>{
        const index = longArr.findIndex(item=>value === item);
        return ~index && !map.has(index) && map.set(index);
    })
}
fn([1,2],[1,1,2])

51.周一算法题之「移动零」

var arr = [0,1,0,3,12];
fn(arr);

function fn(arr){
    const LEN = arr.length;
    let i = 0;
    for(let j = 0;j<LEN - i;j++){
        if(arr[j] === 0){
            arr.splice(j,1);
            arr.push(0);
            i++;
            j--;
        }
    }
    return arr;
}

//
function fn(arr){
    const LEN = arr.length;
    let i = 0;
    for(let j = 0;j<LEN - i;j++){
        if(arr[j] === 0){
            arr.splice(j,1);
            i++;
            j--;
        }
    }
    arr.push(...new Array(i).fill(0));
    return arr;
}

52 汉明重量

// 暴力解法
function fn(num){
  return [...(num).toString(2)].reduce((total,next)=> {return total+=+next},0)
}

// 
function hammingWeight(n) {
    let bits = 0;
    let mask = 1;
    for(let i = 0;i < 32;i++){
        if((n & mask) != 0){
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}