LeeCode常见算法系列(持续更新！2-26)

215. 数组中的第K个最大元素 https://leetcode-cn.com/problems/kth-largest-element-in-an-array

选择最大数排序，选到下标为k-1的元素时，就可以返回了

var findKthLargest = function(nums, k) {
    let maxInd, tmp;
    let len = nums.length;
    for (let i = 0 ; i < len; i++) {
        maxInd = i;
        for (let j = i+1; j < len; j++) {
            if (nums[j] > nums[maxInd]) {
                maxInd = j;
            }
        }
        tmp = nums[i];
        nums[i] = nums[maxInd];
        nums[maxInd] = tmp;
        if (i === k -1) return nums[i];
    }
};

209. 长度最小的子数组 https://leetcode-cn.com/problems/minimum-size-subarray-sum

滑动窗口，维护俩个下标值start，end，通过Math.min记录窗口的最小长度

var minSubArrayLen = function(target, nums) {
    if (nums.length === 0) return 0;
    let min = 999999999999;
    let start = 0;
    let end = 0;
    let sum = 0;
    while(end < nums.length) {
        sum += nums[end];
        while(sum >= target) {
            min = Math.min(min, end - start + 1)
            sum -= nums[start];
            start++;
        }
        end++
    }
    return min === 999999999999 ? 0 : min;
};

88. 合并两个有序数组 https://leetcode-cn.com/problems/merge-sorted-array

最直接调用api的方法（不推荐）

var merge = function(nums1, m, nums2, n) {
    nums1.splice(m);
    nums2.splice(n);
    nums1.push(...nums2);
    return nums1.sort((a,b)=> a-b);
};

112. 路径总和 https://leetcode-cn.com/problems/path-sum

先收集所有从根到叶子节点的路径，然后判断路径有没有相加为targetSum的

var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    let result = [];
    function fn(node, pathArr) {
        if (!node.left && !node.right) {
            result.push(pathArr);
        }
        if (node.left) {
            fn(node.left, [...pathArr, node.left.val])
        }
        if (node.right) {
            fn(node.right, [...pathArr, node.right.val])
        }
    }
    fn(root, [root.val]);
    return result.some(item => item.reduce((pre, next)=>pre+next, 0) === targetSum);
};

递归，到最后的叶子节点，判断当前的数字是不是0

var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    targetSum -= root.val;
    if (!root.left && !root.right) {
        if (targetSum === 0) return true;
        else return false;
    }
    let val = root.val;
    return hasPathSum(root.left || {}, targetSum) || hasPathSum(root.right || {}, targetSum)
};

415. 字符串相加 https://leetcode-cn.com/problems/add-strings

简单的加法运算

var addStrings = function(num1, num2) {
    let p1 = num1.length - 1;
    let p2 = num2.length - 1;
    let tmp = 0;
    let arr = [];
    while(p1 >= 0 || p2 >= 0 || tmp !== 0) {
        let count1 = num1.charAt(p1) ? num1.charAt(p1) - 0 : 0;
        let count2 = num2.charAt(p2) ? num2.charAt(p2) - 0 : 0;
        let sum = count1 + count2 + tmp;
        if (sum < 10) {
            arr.unshift(sum);
            tmp=0;
        } else {
            tmp = Math.floor(sum / 10);
            arr.unshift(sum % 10);
        }
        p1--;
        p2--;
    }
    return arr.join('');
};

165. 比较版本号 https://leetcode-cn.com/problems/compare-version-numbers

自个的想法，挨个数比较

var compareVersion = function(version1, version2) {
    let arr1 = version1.split('.');
    let arr2 = version2.split('.');
    let p1 = 0;
    let p2 = 0;
    while(p1 < arr1.length || p2 < arr2.length) {
        if (arr1[p1] === undefined && arr2[p2] - 0 !== 0) {
            return -1;
        }
        if (arr2[p2] === undefined  && arr1[p1] - 0 !== 0) {
            return 1;
        }
        let n1 = arr1[p1] - 0;
        let n2 = arr2[p2] - 0;
        if (n1 > n2) {
            return 1;
        }
        if (n1 < n2) {
            return -1;
        }
        p1++;
        p2++;
    }
    return 0;
};

226. 翻转二叉树 https://leetcode-cn.com/problems/invert-binary-tree

递归，用一个暂时的中间变量

var invertTree = function(root) {
    function fn(node) {
        if (!node) return;
        let tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        if (node.left) {
            fn(node.left)
        }
        if (node.right) {
            fn(node.right)
        }
    }
    fn(root)
    return root;
};

1. 两数之和 https://leetcode-cn.com/problems/two-sum

哈希表，用空间换时间

var twoSum = function(nums, target) {
    let map = new Map();
    let tmp;
    map.set(nums[0], 0);
    for (let i = 1; i < nums.length; i++) {
        tmp = target - nums[i];
        if (map.get(tmp) !== undefined) {
            return [map.get(tmp), i]
        } else {
            map.set(nums[i], i)
        }
    }
};

路径总和 II https://leetcode-cn.com/problems/path-sum-ii/

递归，得到每一条路径，然后最后判断这条路径的数相加是不是目标数

var pathSum = function(root, targetSum) {
    if (!root) return [];
    let result = [];
    function fn(node, arr) {
        if (!node.left && !node.right) {
            if (arr.reduce((a,b) => a+b, 0) === targetSum) {
                result.push(arr);
            }
            return;
        }
        if (node.left) {
            fn(node.left, [...arr, node.left.val])
        }
        if (node.right) {
            fn(node.right, [...arr, node.right.val])
        }
    }
    fn(root, [root.val])
    return result;
};

141 判断环形链表 https://leetcode-cn.com/problems/linked-list-cycle

1. 使用一个set数据记录每一步的数据

var hasCycle = function(head) {
    let set = new Set();
    let pre = head;
    while(pre) {
        if (set.has(pre)) return true;
        set.add(pre)
        pre = pre.next;
    }
    return false;
};

2. 快慢指针，快指针走俩步，慢指针走一步，相等了就是环形

var hasCycle = function(head) {
    let d = new ListNode();
    d.next = head;
    let fast = slow = d;
    if (!fast.next || !fast.next.next) return false;
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
};

53 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/submissions/

动态规划

var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};

121. 买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

维护一个最大值

var maxProfit = function(prices) {
    let len = prices.length;
    let min = prices[0];
    let result = -1;
    let start = 1;
    while(start < len) {
        if (prices[start] < min) {
            min = prices[start];
        } else if (min < prices[start]) {
            result = Math.max(result, prices[start] - min);
        }
        start++;
    }
    return result === -1 ? 0 : result;
};

94. 二叉树的中序遍历 https://leetcode-cn.com/problems/binary-tree-inorder-traversal

中序遍历： 按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

var inorderTraversal = function(root) {
    let result = [];
    function fn(node) {
        if (!node) return;
        if (node.left) {
            fn(node.left)
        }
        result.push(node.val);
        if (node.right) {
            fn(node.right)
        }
    }
    fn(root)
    return result;
};

15. 三数只和 https://leetcode-cn.com/problems/3sum/

先对数组进行从小到大的排序，再对排序数组进行循环，如果当前数大与0，已经不可能有三数相加为0了，跳出循环，维护左右俩个指针，相加三个数，和为0的时候，加入结果，并且为了避免没有重复数据，要对俩个指针进行while循环，去除重复数据，小于0 的时候，左边++，大于0 的时候右边减减。

var threeSum = function(nums) {
    let len = nums.length;
    if (len < 3) return [];
    if (len === 3) {
        return nums[0] + nums[1] + nums[2] === 0 ? [nums] : [];
    }
    let result = [];
    let sortNums = nums.sort((a,b)=>a-b);
    for (let p = 0; p < len; p++) {
        if (sortNums[p] > 0) break;
       if (p > 0 && sortNums[p] === sortNums[p-1]) continue;
       let left = p + 1;
       let right = len - 1;
       while(left < right) {
           let sum = sortNums[p] + sortNums[left] + sortNums[right];
           if (sum === 0) {
               result.push([sortNums[p],sortNums[left],sortNums[right]])
               while(left < right && sortNums[left] === sortNums[left+1]) left++;
               while(left < right && sortNums[right] === sortNums[right-1]) right--;
               left++;
               right--; 
           } else if (sum > 0) {
               right--;
           } else {
               left++;
           }
       }
    }
    return result;
};