刷题汇总（一）leetcode 精选50题 JavaScript答案总结

题目来源

腾讯精选练习（50 题）

GitHub地址：https://github.com/zj19941113/LeetCode-50-JavaScript-Answers

相关：
刷题汇总（二）剑指Offer 66题 C++答案总结
刷题汇总（三）leetcode 精选50题 C++答案总结
刷题汇总（四）技术类编程题汇总 C++
刷题汇总（五）leetcode 热题 HOT 100 C++ 答案总结
刷题汇总（六）leetcode 多线程 / Shell

2两数相加-33.0%-中等

https://leetcode-cn.com/problems/add-two-numbers/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var re = new ListNode(0); //0随便取，不会用到，只为了初始化
    var r=re;  //浅拷贝
    var carry=0;
    while(l1!=null || l2!=null){
        var x = l1==null? 0:l1.val;
        var y = l2==null? 0:l2.val;
        r.next=new ListNode((carry+x+y)%10);
        r=r.next;
        if(carry+x+y>9){
            carry=1;
        }else{
            carry=0;
        }
        if(l1!=null){
            l1=l1.next;
        }
        if(l2!=null){
            l2=l2.next;
        }
    }
    if(carry>0){
        r.next=new ListNode(1); //最高位进1
    } 
    return re.next;
};

4寻找两个有序数组的中位数-33.8%-困难

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(a, b) {
    // 谁小谁移，移动k次，k中间
    var n = a.length;
    var m = b.length;
    var nm = n + m;
    var ni = 0,mi = 0,x,y; 

    while(ni + mi < nm ){  
        if(ni < n ){
            while(mi == m || a[ni] <= b[mi]){
                ni=ni+1;
                if(ni+mi == (nm+1)/2){ //总长奇
                    return a[ni-1];
                }
                if(ni+mi == nm/2){//总长偶
                    x = a[ni-1];
                    break;
                }
                if(ni+mi == (nm/2 + 1)){ 
                    y = a[ni-1];
                    return (x+y)/2
                }
            }
        }
        if(mi < m){
            while(ni == n || b[mi] <= a[ni]){
                mi = mi + 1;
                if(ni+mi == (nm+1)/2){
                    return b[mi-1];
                }
                if(ni+mi == nm/2){
                    x = b[mi-1];
                }
                if(ni+mi == (nm/2 + 1)){ 
                    y = b[mi-1];
                    return (x+y)/2
                }
            }
        }
    }
    return -1;
};

5最长回文子串-24.7%-中等

https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s==null&&s.length<1){
        return "";
    }
    var fir = 0;
    var las = 0;
    for(var i=0;i<s.length;i++){
        var lenl = getsub(s,i,i);
        var lenr = getsub(s,i,i+1);
        var len = Math.max(lenl,lenr);
        if(len>las-fir){
            fir = i - Math.floor((len-1)/2);
            las = i + Math.floor(len/2);
        }     
    }
    return s.slice(fir,las+1);
};

function getsub(s,l,r){
    while(l>=0&&r<=s.length-1&&s.charAt(l)==s.charAt(r)){
        l--;
        r++;
    }
    return r-l-1;
}

7整数反转-31.8%-简单

https://leetcode-cn.com/problems/reverse-integer/

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    var result = 0;
    var strx;
    var mayAns;
    if(x>0){
        strx = String(x);
        mayAns = Number(strx.split("").reverse().join(""));
        return mayAns<=Math.pow(2,31)-1?mayAns:0;
    }
    else{
        strx = String(-x);
        mayAns = -Number(strx.split("").reverse().join(""));
        return mayAns>=-Math.pow(2,31) ?mayAns:0;
    }
    return result;
};

8字符串转换整数 (atoi)-16.6%-中等

https://leetcode-cn.com/problems/median-of-two-sorted-arrays

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
    str = str.trim();
    var word = str.split(" ")[0];
    if(parseInt(word)){
        if(parseInt(word)>Math.pow(2,31)-1){
            return Math.pow(2,31)-1;
        };
        if(parseInt(word)<-Math.pow(2,31)){
            return -Math.pow(2,31);
        };
        return parseInt(word);
    }
    return 0;
};

9回文数-56.0%-简单

https://leetcode-cn.com/problems/palindrome-number/

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if(x >= 0){
       var strx = String(x); 
       return strx == strx.split("").reverse().join("");
    }
    return false;
};

11盛最多水的容器-53.5%-中等

https://leetcode-cn.com/problems/container-with-most-water/

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var maxs = 0;
    for (var i=0;i<height.length;i++){
        for (var j=i+1;j<height.length;j++){
            var tmp = Math.min(height[i],height[j])*(j-i);
            if(tmp>maxs){
                maxs = tmp;
            }
        }
    }
    return maxs;
};

14最长公共前缀-32.2%-简单

https://leetcode-cn.com/problems/longest-common-prefix/

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length == 0){
        return "";
    }
    var mini = 0;
    for(var i=1;i<strs.length;i++){
        if (strs[i].length<strs[mini].length){
            mini = i;
        }
    }
    var result = "";
    for(let j=0;j<strs[mini].length;j++){
        for( i=0;i<strs.length;i++){
            if(strs[mini].slice(0,j+1) != strs[i].slice(0,j+1)){
                return result;
            }
        }
        result =  strs[mini].slice(0,j+1); 
    }
    return result;
};

15三数之和-21.2%-中等

https://leetcode-cn.com/problems/3sum

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort(function(a,b){return a-b});
    var ls = [];
    for (var i=0;i<nums.length-2;i++) {
        if(nums[i]==nums[i-1]){ //i和前面一样，跳过
            continue;
        }
        for (var j=i+1;j<nums.length-1;j++) {
            if(nums[j]==nums[j-1]&&j!=i+1){ //j和前面一样，且前面不是i，跳过
                continue;
            }
            for (var k=j+1;k<nums.length;k++) {
                if(nums[k]+nums[j]+nums[i] == 0){
                    ls.push([nums[i],nums[j],nums[k]]); //找到k跳出，不再往后
                    break;
                }
            }
        }
    }
    return ls;
};

16最接近的三数之和-39.0%-中等

https://leetcode-cn.com/problems/3sum-closest/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    var len = nums.length;
    var minl = nums[0]+nums[1]+nums[2];
    for(var i=0;i<len-2;i++){
        for(var j=i+1;j<len-1;j++){
            for(var k=j+1;k<len;k++){
                var tmp = nums[i]+nums[j]+nums[k];
                if(Math.abs(tmp-target)<Math.abs(minl-target)){
                    minl = tmp;
                }
            }
        }
    }
    return minl;
};

20有效的括号-36.7%-简单

https://leetcode-cn.com/problems/valid-parentheses/

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s == null||s.length <1){
        return true;
    }
    var stack = [];
    for(var i=0;i<s.length;i++){
        if(s[i] == ""){
            continue;
        }
        if(stack.leng<1){
            stack.push(s[i]);
        }else if(stack[stack.length-1]=="("&&s[i]==")" ||stack[stack.length-1]=="{"&&s[i]=="}" ||stack[stack.length-1]=="["&&s[i]=="]"){
            stack.pop();
        }else{
            stack.push(s[i]);
        }
    }
    return stack.length<1;
};

21合并两个有序链表-52.9%-简单

https://leetcode-cn.com/problems/merge-two-sorted-lists/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    var l3 = new ListNode(0);
    var l4 = l3;
    while(l1!=null && l2!=null){
        if(l1.val<l2.val){
            l4.next = l1;
            l1 = l1.next;
        }else{
            l4.next = l2;
            l2 = l2.next;
        }
        l4 = l4.next;
    }
    l4.next = l1==null?l2:l1;
    return l3.next;
};

23合并K个排序链表-43.8%-困难

https://leetcode-cn.com/problems/merge-k-sorted-lists/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    var rl = null;
    for(var i=0;i<lists.length;i++){
        rl = mergeTwoLists(lists[i],rl);
    }
    return rl;
};

var mergeTwoLists = function(l1, l2) {
    var l3 = new ListNode(0);
    var l4 = l3;
    while(l1!=null && l2!=null){
        if(l1.val<l2.val){
            l4.next = l1;
            l1 = l1.next;
        }else{
            l4.next = l2;
            l2 = l2.next;
        }
        l4 = l4.next;
    }
    l4.next = l1==null?l2:l1;
    return l3.next;
};

26删除排序数组中的重复项-42.9%-简单

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    for(var i=0;i<nums.length;i++){
        var j=1;
        while(nums[i] == nums[i+j]){
            ++j;
        }
        if(j!=1){
            nums.splice(i,j-1);
        }
    }
    return nums.length;
};

33搜索旋转排序数组-35.8%-中等

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    return searchs(nums, 0, nums.length-1, target);
};

function searchs(nums,l,h,target){
    //搜不到返回-1，搜到了返回target
    if (l > h){
        return -1;
    } 
    var mid = Math.floor((l + h)/2);//[0,1,2,4,5,6,7]
    if(nums[mid] == target){
        return mid;
    }
    if(nums[mid] < nums[h]){ //旋转在左 [6,7,0,1,2,4,5]
        if(nums[mid]<target&&target<=nums[h]){ 
            return searchs(nums,mid+1,h,target);//在右，右顺序
        }else{
            return searchs(nums,l,mid-1,target);//不在右
        }
    }else{ //旋转在右 [2,4,5,6,7,0,1]
        if(nums[l]<=target&&target<nums[mid]){ 
            return searchs(nums,l,mid-1,target);//在左，左顺序
        }else{
            return searchs(nums,mid+1,h,target);//不在右
        }
    }
}

43字符串相乘-37.9%-中等

https://leetcode-cn.com/problems/multiply-strings/

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    var res = "";
    var len1 = num1.length;
    var len2 = num2.length;
    for(var i=0;i<len1;i++){
        for(var j=0;j<len2;j++){
            var base = Array(i+j+1).join(0);//i+j个0  eg:"00"  //逐位相乘
            var tmp = String(Number(num1[len1-1-i])*Number(num2[len2-1-j])) + base;
            res = addstr(res,tmp);
        }
    }
    while(res[0] == 0 && res.length > 1){//"002" -> "2"
        res = res.slice(1);
    }
    return res;
};

function addstr(s1, s2) { //字符串相加
    var re = "";
    if(s1.length>=s2.length){
        s2 =  Array(s1.length-s2.length+1).join(0) + s2;
    }else{
        s1 = Array(s2.length-s1.length+1).join(0) + s1;
    }
    var flag = 0;
    for(let i=0;i<s1.length;i++){
        var t = Number(s1[s1.length - 1 - i]) + Number(s2[s1.length - 1 - i]) + flag;
        if(t < 10){
            re = String(t).concat(re);
            flag = 0;
        }else{
            re = String(t-10).concat(re);
            flag = 1;
        }
    }
    return flag == 0? re:"1"+re;
};

46全排列-66.7%-中等

https://leetcode-cn.com/problems/permutations/

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    if(nums.length == 0){
        return [[]];
    }
    if(nums.length == 1){
        var re = [];
        re.push(nums);
        return re;
    }
    var nums1 = permute(nums.slice(1));
    var num0 = nums[0];
    var result = [];
    for(var i=0;i<nums1.length;i++){
        for(var j=0;j<nums1[i].length+1;j++){
            var tmp = nums1[i].concat();
            tmp.splice(j,0,num0);
            result.push(tmp);
        }
    }
    return result;
};

53最大子序和-42.9%-简单

https://leetcode-cn.com/problems/maximum-subarray/

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    var sum = 0;
    var maxsum = nums[0];
    for(var i=0;i<nums.length;i++){
        sum +=nums[i];
        if(sum > maxsum){
            maxsum = sum;
        } 
        if(sum < 0){
            sum = 0;
        }
    }
    return maxsum;
};

54螺旋矩阵-34.0%-中等

https://leetcode-cn.com/problems/spiral-matrix/

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    var arr = [];
    while(!(matrix.length == 0||matrix[0].length == 0)){
        var tmp = matrix.shift(); //剪第一行
        arr = arr.concat(tmp);
        if(matrix.length == 0||matrix[0].length == 0){ //[]   [[],[]]
            return arr;
        }
        for(var i=0;i<matrix.length;i++){//剪最后一列
            var tmp = matrix[i].pop();
            arr.push(tmp);
        }
        if(matrix.length == 0||matrix[0].length == 0){
            return arr;
        }
        var tmp = matrix.pop().reverse();//剪最后一行
        arr = arr.concat(tmp);
        if(matrix.length == 0||matrix[0].length == 0){
            return arr;
        }
        for(var i=0;i<matrix.length;i++){//剪第一列
            var tmp = matrix[matrix.length-1-i].shift();
            arr.push(tmp);
        }
    }
    return arr;
};

59螺旋矩阵II-71.1%-中等

https://leetcode-cn.com/problems/spiral-matrix-ii/

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    var arr = [];
    for(var i = 0; i < n; i++) {
        arr.push(new Array(n).fill(0));//创建n*n零矩阵
    }
    var c = 1;
    var i = 0;
    while(c <= n*n){
        for(var j=i;j<n-i;j++){//第一行
            arr[i][j] = c++;
        }
        for(var j=i+1;j<n-i;j++){//最后一列
            arr[j][n-i-1] = c++;
        }
        for(var j=i+1;j<n-i;j++){//最后一行
            arr[n-i-1][n-j-1] = c++;
        }
        for(var j=i+1;j<n-i-1;j++){//第一列
            arr[n-j-1][i] = c++;
        }
        i++;
    }
    return arr;
};

61旋转链表-37.5%-中等

https://leetcode-cn.com/problems/rotate-list/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if(head == null||k==0){
        return head;
    }
    var h = head;
    var len = 1;//总长
    while(h.next !=null ){
        ++len;
        h = h.next;
    }
    if(k % len == 0){//不用旋转 head本身
        return head;
    }
    if(k > len){//需旋转
        k = k % len;
    }
    len = len - k;
    var ln = new ListNode(0);//0->1->2->3->NULL
    var n = ln; 
    while(len != 0){
        n.next = head;
        n = n.next;
        head = head.next;
        --len;
    }
    n.next = null;
    var r = head;
    var lr = r;
    while(head.next != null){
        lr = head;
        head = head.next;
        lr = lr.next;
    }
    lr.next = ln.next
    return r;
};

62不同路径-52.6%-中等

https://leetcode-cn.com/problems/unique-paths/

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    var dp = [];
    for(var i=0;i<m;i++){ //创建m*n零矩阵
        dp.push(new Array(n).fill(0));
    }
    for(var i=0;i<m;i++){
        for(var j=0;j<n;j++){
            if(i==0||j==0){
                dp[i][j] = 1;
            }
            else{
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1];
};

70爬楼梯-44.5%-简单

https://leetcode-cn.com/problems/climbing-stairs/

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    var i = 1;
    var j = 2;
    for(var k=0;k<n-2;k++){
        var tmp = i + j;
        i = j;
        j = tmp;
    }
    return j;
};

78子集-71.6%-中等

https://leetcode-cn.com/problems/subsets/

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    var arr = [];
    arr.push([]);
    for(var i=0;i<nums.length;i++){
        var tmp = []; //tmp深拷贝arr
        for(var k=0;k<arr.length;k++){
            tmp[k] = arr[k].slice(0);
        }
        for(var j=0;j<tmp.length;j++){
            tmp[j].push(nums[i]);
            arr.push(tmp[j]);
        }
    }
    return arr;
};

88合并两个有序数组-43.0%-简单

https://leetcode-cn.com/problems/merge-two-sorted-lists/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    var l3 = new ListNode(0);
    var l4 = l3;
    while(l1!=null && l2!=null){
        if(l1.val<l2.val){
            l4.next = l1;
            l1 = l1.next;
        }else{
            l4.next = l2;
            l2 = l2.next;
        }
        l4 = l4.next;
    }
    l4.next = l1==null?l2:l1;
    return l3.next;
};

89格雷编码-62.7%-中等

https://leetcode-cn.com/problems/gray-code/

/**
 * @param {number} n
 * @return {number[]}
 */
// 000 001 011 010  ——
//                    |
// 100 101 111 110 <——
var grayCode = function(n) {
    if(n == 0){
        return [0];
    }
    var tmp = grayCode(n-1).concat();//深拷贝
    for(var i=0;i<tmp.length;i++){
        tmp[i] += Math.pow(2,n-1);
    }
    tmp.reverse();
    return grayCode(n-1).concat(tmp);
};

104二叉树的最大深度-67.4%-简单

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

/**
 * 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 l_height = maxDepth(root.left);
    var r_height = maxDepth(root.right);
    return Math.max(l_height,r_height) + 1;
};

121买卖股票的最佳时机-48.5%-简单

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

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

122买卖股票的最佳时机II-51.6%-简单

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

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

124二叉树中的最大路径和-33.8%-困难

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
    var len = -Number.MAX_VALUE;
    submax(root);
    function submax(t){
        if(t == null){
            return 0;
        }
        var l = Math.max(submax(t.left),0);
        var r = Math.max(submax(t.right),0);
        if(t.val + l + r > len){
            len = t.val + l + r;
        }
        return Math.max(l,r) + t.val;
    }
    return len;
};

136只出现一次的数字-59.1%-简单

https://leetcode-cn.com/problems/single-number/

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 交换律：a ^ b ^ c  <=> a ^ c ^ b,俩两相同的移到一起
    // 相同的数异或为0: n ^ n => 0,只剩下单个的了
    // 任何数于0异或为任何数 0 ^ n => n
    var s = 0;
    for(var i=0;i<nums.length;i++){
        s = s^nums[i];
    }
    return s;
};

141环形链表-35.5%-简单

https://leetcode-cn.com/problems/linked-list-cycle

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
 
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    var slow = head, fast = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
};

142环形链表II-34.8%-中等

https://leetcode-cn.com/problems/linked-list-cycle-ii/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    var slow = head,fast = head;
    var isloop = false;
    while(fast && fast.next){
        slow  = slow.next;
        fast = fast.next.next;
        if(slow == fast){//相遇
            isloop = true;
            break;
        }
    }
    if(isloop){
        var l  = head;
        while(l != slow){
            l = l.next;
            slow = slow.next;
        }
        return slow;
    }
    return null;
};

146LRU缓存机制-39.0%-困难

https://leetcode-cn.com/problems/lru-cache/

/**
 * @param {number} capacity
 */

/**
1.新加入的数据
            ————> ___ 头 <—————
                  ___          |
                  ___          |2.被访问的数据
                  ___     —————
                  ___
                  ___
            <———— ___ 尾
3.淘汰的数据
*/

var LRUCache = function(capacity) {
    this.size = capacity;
    this.map = {};
    this.list = []; 
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map[key] != null){
        this.list.splice(this.list.indexOf(key),1);//更新list
        this.list.unshift(key);
        return this.map[key];
    }
    return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    var tmp = this.list.indexOf(key);
    if(tmp != -1){ //key已存在，更新list
        this.list.splice(tmp,1);
    }
    else{ //key不存在
        if(this.list.length == this.size){ //栈满
            var d = this.list.pop();
            this.map[d] = null;
        }   
    }
    this.list.unshift(key);
    this.map[key] = value;
};

/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = Object.create(LRUCache).createNew(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

148排序链表-58.6%-中等

https://leetcode-cn.com/problems/sort-list/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (!head || !head.next){
        return head;
    } 
    var slow = head,bk = head,fast = head;
    while(fast && fast.next ){
        bk = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    bk.next = null;
    var l1 = sortList(head);//中分，归并
    var l2 = sortList(slow);
    return merge(l1,l2);
};

function merge(l1,l2){//合并有序链表
    var l = new ListNode(0);
    var rl = l;
    while(l1 && l2){
        if(l1.val < l2.val){
            rl.next = l1;
            l1 = l1.next;
        }else{
            rl.next = l2;
            l2 = l2.next;
        }
        rl = rl.next;
    }
    rl.next = l1==null?l2:l1;
    return l.next;
}

155最小栈-47.7%-简单

https://leetcode-cn.com/problems/min-stack/

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.arr = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.arr.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.arr.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.arr[this.arr.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return Math.min.apply( {}, this.arr );
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

160相交链表-37.2%-简单

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if(headA == null || headB == null){
        return null;
    }
    var pA = headA;
    var pB = headB;
    while(pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
};

169求众数-58.0%-简单

https://leetcode-cn.com/problems/majority-element/

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length/2)];
};

206反转链表-58.6%-简单

https://leetcode-cn.com/problems/reverse-linked-list/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    var l  = null;
    while(head != null){
        var newl = new ListNode(head.val);
        var tmp = l;
        l = newl;
        l.next = tmp;
        head = head.next;
    }
    return l;   
};

215数组中的第K个最大元素-56.6%-中等

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    return fastkmax(nums,0,nums.length-1,k);
};

function fastkmax(n,l,r,k){
    var mid = partiton(n,l,r);//排序 左边都是比mid小的，右边都是比mid大的
    var rk = r - mid + 1;
    if(rk == k){
        return n[mid];
    }
    if(rk > k){
        return fastkmax(n,mid + 1,r,k);
    }
    return fastkmax(n,l,mid - 1,k -rk );
}

function partiton(n,l,r){//一次快排
    var base = n[l];
    var i = l,j = r,tmp;
    while(i < j){
        while(n[j] >= base && i < j){
            j--;
        }
        while(n[i] <= base && i < j){
            i++;
        }
            tmp = n[i];
            n[i] = n[j];
            n[j] = tmp;
    }
    n[l] = n[i];
    n[i] = base;
    return i;
 }

217存在重复元素-47.0%-简单

https://leetcode-cn.com/problems/contains-duplicate/

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for(var i=0;i<nums.length-1;i++){
        if(nums[i]==nums[i+1]){
            return true;
        }
    }
    return false;
};

230二叉搜索树中第K小的元素-62.0%-中等

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    var list = [];
    order(root,list);
    return list[k-1];
};
function order(root,list){//中序遍历
    if(!root){
        return;
    }
    order(root.left,list);
    list.push(root.val);
    order(root.right,list);
}

231 2的幂-44.3%-简单

https://leetcode-cn.com/problems/power-of-two/

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    if(n == 0){
        return false;
    }
    if(n == 1){
        return true;
    }
    return n%2==0?isPowerOfTwo(n/2):false;
};

235二叉搜索树的最近公共祖先-56.9%-简单

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

/**
 * 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) {
    // 二叉搜索树(二叉排序树):若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
    var res = null;
    lca(root, p , q);
    function lca(root, p, q){
        if((root.val - p.val)*(root.val - q.val) <= 0){ //root为p、q根节点
            res = root;
        }else if(root.val < p.val && root.val < q.val){ //都在右子树
            lca(root.right, p , q);
        }else{
            lca(root.left, p , q);
        }
    }
    return res;
};

236二叉树的最近公共祖先-50.4%-中等

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

/**
 * 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){
        return null;
    }
    if(root == p || root == q){
        return root;
    }
    var l = lowestCommonAncestor(root.left,p,q)//左支存在一个的位置
    var r = lowestCommonAncestor(root.right,p,q)
    if(l && r){//左支有一个，右支有一个
        return root;
    }
    if(l){//右没有，都在左，先找到的即为根节点
        return l;
    }
    if(r){
        return r;
    }
    return null;
};

237删除链表中的节点-69.4%-简单

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

238除自身以外数组的乘积-58.8%-中等

https://leetcode-cn.com/problems/product-of-array-except-self/

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    var arr = [];
    var l = 1, r = 1;
    for(var i=0;i<nums.length;i++){//arr[i] i左边数乘积
        arr[i] = l;
        l *= nums[i];
    }
    for(var j=nums.length-1;j>=0;j--){
        arr[j] *= r;
        r *= nums[j];
    }
    return arr;
};

292Nim游戏-66.4%-简单

https://leetcode-cn.com/problems/nim-game/

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return n%4 == 0?false:true;
};

344反转字符串-65.1%-简单

https://leetcode-cn.com/problems/reverse-string/

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    for(var i=1;i<s.length;i++){
        var tmp = s.splice(i,1)[0];
        s.unshift(tmp);
    }
};

557反转字符串中的单词III-63.5%-简单

https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    var arr = s.split(" ");
    for(var i=0;i<arr.length;i++){
        arr[i] = arr[i].split("").reverse().join("");
    }
    return arr.join(" ");
};