JavaScript 刷 LeetCode 拿 offer- 分治

var maxSubArray = function (nums) {    const recursion = (l,r) => {        if(l === r) {            return {                totalSum: nums[l],                leftSum: nums[l],                rightSum: nums[l],                maxSum: nums[l]            }        }        const mid = ((r-l)>>2)+l        const left = recursion(l,mid)        const right = recursion(mid+1,r)        return {            totalSum:left.totalSum+right.totalSum, // 区间内值的总和            leftSum:Math.max(left.leftSum,left.totalSum+right.leftSum), // 左边界开始的最大连续子列和            rightSum: Math.max(right.rightSum,right.totalSum+left.rightSum), // 区间哟偶边界结束的最大连续子列和            maxSum:Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum)        }    }    return recursion(0,nums.length-1).maxSum}

var maxSubArray = function (nums) {  let max = -Infinity;   let sum = 0   for(let i = 0 ;i<nums.length;i++){       sum+=nums[i]       max = Math.max(sum,max)       if(sum<=0){           sum=0       }   }   return max};

var numTrees = function (n) {  const map = new Map();  const recursion = (n) => {    if (n <= 1) return 1; //没有节点也算一种分配    let temp = 0;    for (let i = 1; i <= n; i++) {      let l, r;      if (map.has(i - 1)) {        l = map.get(i - 1);      } else {        l = recursion(i - 1);        map.set(i - 1, l);      }      if (map.has(n - i)) {        r = map.get(n - i);      } else {        r = recursion(n - i);        map.set(n - i, r);      }      temp += l * r;    }    return temp;  };  return recursion(n);};

var numTrees = function (n) {    const dp = new Array(n+1)    dp[0] = 1    for(let i =1;i<=n;i++){        dp[i] = 0        for(let j = 1;j<=i;j++){            dp[i] +=dp[j-1]*dp[i-j]        }    }    return dp[n]}

 var majorityElement = function(nums) {    const recursion = (l,r) => {        if(l === r) return nums[l]        const mid = ((r-l)>>1)+l         const lMax = recursion(l,mid)        const rMax = recursion(mid+1,r)        if(lMax === rMax) return lMax // 如果相等，则就是众数了        let lMaxtCount = 0        let rMaxtCount = 0        for(let i=l;i<=r;i++){            if(nums[i] === lMax) lMaxtCount++            if(nums[i] === rMax) rMaxtCount++        }
        return lMaxtCount>rMaxtCount ? lMax:rMax    }    return recursion(0,nums.length-1)}

var majorityElement = function(nums) {    let target;    let count = 0    for(let num of nums){        if(count === 0 && target !== num) {            // 如果 count 为 0， 证明上一个 target 已经无效了            target = num         }        if(target === num){            count++        }else{            count--        }    }    return target};

var mergeKLists = function (lists) {  if (!lists.length) return new ListNode().next;  return lists.reduce((prev, cur) => mergeTwoList(prev, cur));};  // 合并两个有序链表  const mergeTwoList = (l1, l2) => {    let temp1 = l1,      temp2 = l2;    let emptyNode = (current = new ListNode());    while (temp1 && temp2) {      if (temp1.val > temp2.val) {        current.next = temp2;        temp2 = temp2.next;      } else {        current.next = temp1;        temp1 = temp1.next;      }      current = current.next;    }    while (temp1) {      current.next = temp1;      current = current.next;      temp1 = temp1.next;    }    while (temp2) {      current.next = temp2;      current = current.next;      temp2 = temp2.next;    }    return emptyNode.next;  };

 var mergeKLists = function (lists) {    const len = lists.length;    if (!len) return null    if (len === 1) return lists[0];    if(len === 2) return mergeTwoList(lists[0],lists[1])    const mid = len >> 1;    return mergeTwoList(      mergeKLists(lists.slice(0, mid)),      mergeKLists(lists.slice(mid))    );  };

var beautifulArray = function (n) {  const map = new Map();  map.set(1, [1]); // 初始化，也是截止条件  const recursion = (n) => {    if (map.has(n)) return map.get(n); // 递归的终止条件    // 奇数放在左侧 -- 按照数组长度排列好漂亮数组后，然后再通过 2N-1 的方式转成当前层的奇数    const left = recursion((n + 1) >> 1).map((item) => item * 2 - 1);    const right = recursion(n >> 1).map((item) => item * 2);    const ret = [...left, ...right];    map.set(n, ret);    return ret;  };  return recursion(n);};

 var findKthLargest = function (nums, k) {    const select = (left, right) => {      if (left === right) return nums[left];      let mid = ((right - left) >> 1) + left;    //   pivotIndex 表示 mid 在整理后数组所在 index      const pivotIndex = dfs(left, right, mid);      if (pivotIndex === nums.length-k) return nums[pivotIndex];      if (pivotIndex > nums.length-k) {        return select(left, pivotIndex - 1);      } else {        return select(pivotIndex + 1, right);      }    };    const dfs = (left, right, pivot) => {      let l = left,        r = right;      const target = nums[pivot];      //先放在最左边，然后[l+1,r] 的位置进行处理，最后在 l,r 的交界处，再把 target 交换回来     //  这里是先将 target 放在了左边，所以要找到的是交界处小于 target 的那个点，也就是 r，然后让 r 和 原始的left 进行值交换即可      [nums[l], nums[pivot]] = [nums[pivot], nums[l]];       while (l <= r) {        while (nums[l] <= target && l <= r) {          l++;        }        while (nums[r] >= target && r >= l) {          r--;        }        if (l > r) break;        [nums[l], nums[r]] = [nums[r], nums[l]];      }      [nums[left], nums[r]] = [nums[r], nums[left]];      return r;    };    return select(0, nums.length - 1);  };