关于leetcode:JavaScript刷LeetCode拿offer分治

明天没啥前言，分治很难，次要难在如何拆分后比拟好治理合并，这比二分这些只有拆了就完结要难上一个 level，所以这里属于出入 分治 这种想法的思维，后续会尽可能的锤炼这样的做法；做一道分治，如果能用其余办法代替的时候，个别分治不算是最优解，起码很伤脑子；

分治即 分而治之，所以要分成两局部

分：将一个规模为 N 的问题合成为若干个规模较小的子问题
治：依据子问题的解求原问题

肯定是先分再治
治肯定是利用分的后果进行的，也就是说治依赖于分

如果问题能够被合成为若干个规模较小的雷同问题
这些被合成的问题的后果能够进行合并
这些被合成的问题是互相独立的，不蕴含重叠的子问题

分支和 dp 有很深分割，且与二分法也有关联，实质上，二分就是始终只有分没有治的分治，因为二分的后果只须要找到那个较小的雷同问题的解，不须要再合并起来；

思考子问题的求解边界，应用函数来定义问题
思考如何将子问题的解进行合并 — 假如子问题曾经计算好了，如何合并起来
思考编码思路 — 个别应用递归

二分只对问题进行分，分完间接舍弃；而分治不仅须要对问题进行合成，还须要对多个问题进行治理
分治和 dp 都波及到问题的问题，并且都须要保障子问题的不重不漏。
- dp 是通过递推和抉择进行转译，从非凡推广到一半
- 分治也可能波及到抉择；
- dp 解决的问题往往随同重叠子问题，而分治则不是

如果一个问题被文杰为若干个不重叠的独立子问题，并且子问题能够推到出原问题，咱们就能够用分治来解决；

剖析 — 分治法

先分 — 使用递归的办法将数组区间的左右节点 l,r 一直二分进来，直到 l === r 为止，这个时候须要思考怎么治理了
再治 — 这里最终要求的是最大的间断子序列，咱们先思考两个值合并，最大的状况是三种, Math.max(L,R,L+R),
- 然而当再多一点值的时候，咱们就须要扭转一下 Math.max(LMAX,RMAX,L_Rmax+R_Lmax) 这里的 LMAX, RMAX 是指合并两个区间的最大值，L_Rmax 是指在 L 区间蕴含 right 起点为最大区间；
所以治的过程中，每个区间须要有 4 个变量，别离是 totalSum 区间总和，leftSum 蕴含 left 节点的最大间断子列和, rightSum 蕴含 right 节点的最大间断子列和, maxSum 区间的最大值
初始化的时候，也就是单个节点的时候，4 个变量都是惟一值 nums[l]
开始合并治理，
- totalSum 间接将两个节点的 totalSum 合并即可；
- leftSum 总是和 left 区间相干 — Math.max(left.maxSum,left.totalSum+right.leftSum), 要不间接区左区间的最大值，要不全取左区间 + 右区间的 leftSum
- 同理 rightSum 也总是和 right 区间相干 — Math.max(right.maxSum,right.totalSum+left.rightSum)
- maxSum 分三种状况 — Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum)
所以先递后归，工夫复杂度为 O(n)

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
}

剖析 — 贪婪

求的是最大和的 间断子数组
用 sum 缓存后面和大于 0 的子数组之和，一旦小于 0，就不再累加，从新置 0, 放弃每一次迭代前 sum 的值都是 >=0
这样对于每一个部分子数组，它的累加值都是大于等于 0 的，这样每次累加一个新值，就进行最大值比拟，保障整体是一个最大子数组之和
工夫复杂度 O(n)

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
};

参考视频：传送门

剖析 — 分治

题目都是给定 n 个节点，求最多能有多少种 BST，也就是求在 [1,n] 这些节点能形成多少中 BST，能够细分到按程序的 [k,k+n] 的小区间，能形成多少个 BST
先分: 因为 BST 左树小于右树，所以能够一直将节点区间拆分左右两份，交给子树本人解决
再治: 拆分到只有一个节点的时候，天然只有一种了；当左右树别离都有 l,r 种不同的解法，合并之后就是 l*r 种了
当然这种方法会做很多反复的工作，毕竟咱们在执行回调的时候，入参的指数一个节点树 x, 所以咱们能够用空间换工夫的概念，缓存一些值
这样解决之后，工夫复杂度为 O(nlog(n)), 空间复杂度为 O(n)

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);
};

剖析 — dp + 分治

依据分治解法可知，每一次都只是依照节点数来治理相应的子树，所以能够用 dp 来缓存
dp[i] 示意有 i 个节点时，不同子树的最大数量
base case dp[0] =1, 这个其实就是分治中分到最初的首次治理
状态转移方程: dp[i] = 累加的 dp[k-1]*dp[i-k] 这里就是分治中治理合并的过程，在 dp 中是状态转移方程；
工夫复杂度为 O(nlog(n)), 空间复杂度为 O(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]
}

剖析 — 分治

先分：将 nums 拆分到单个值的数组之后，而后开始治理
再治：合并的时候，先找出两个合并的众数值和数量，而后再思考合并之后哪一个才是真正的众数；
再治 2：抉择众数是通过比拟两个合并数组失去的，合并之后众数值是两个数组都要获取的，所以每一次治的时候都要再次获取对应 target 的数量
治理解析: 为什么间接比对两个数组的众数就能失去合并后数组的众数，那么这两个值就以后数组最有可能的众数了，只有比对这两个值就能失去以后合并数组的真正众数了
二分递归的工夫复杂度是 logn, 每一次治理合并的时候的复杂度也是 logn，所以工夫复杂度是 O(n), 空间复杂度 O(1)

 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)
}

剖析 — 摩尔投票法

如果有一个值 target 失去票数是 nums 的一半以上，那么对于任意一个最开始的取值，咱们都能够假如为 target，而后保护一个票数 count
如果 count 曾经为 0 了，那么就替换 target 值，直到最初留在 target 上的值，就是所求的值
这里思考最极其的状况，就是一开始就取到了实在的 target 值，它一直和其余值进行对消，因为 target 的数量是大于一半的，所以最初还是能保留在 target 上
工夫复杂度 O(n), 空间复杂度 O(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
};

剖析 — 间接迭代合并链表

合并 k 个链表不好合并，合并 2 个链表就比较简单了；
这里每一次合并两个链表
合并两个链表为 1 个，而后一直的迭代，最初失去一个
最初超时了，工夫复杂度是 NM 其中 N 是链表数组的长度，M 是链表的均匀长度

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;
  };

剖析 — 分治

合并 k 个链表不好合并，合并 2 个链表就比较简单了；
先分: 依照长度进行二分拆分, 只有超过 2 个链表就持续往下拆分，直到为 1 个的时候，再治理
再治: 当进行二分拆分后，再组合起来，迭代到最初失去两个有序的数组，而后失去了一个残缺的链表
应用分治而不是迭代合并，能够使得合并的次数从 n 次升高到了 logn，工夫复杂度为 MlogN 其中 M 为合并两个链表的长度，n 是链表数组的长度

 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))
    );
  };

剖析 — 分治

解答这道题最次要是有两个公式，奇数 + 偶数 !== 奇数, 所以如果取值的时候左侧都是奇数，右侧都是偶数，那么必定符合要求
第二个公式是: 如果 2i !== l+r, 那么 2(i2+b) !== l2+b+ r2+b; 这个等式是当咱们取的 3 个值同奇偶的时候 (2(i2+b),l2+b, r2+b)，咱们须要思考，在它的下一层，他们(i,l,r) 是合乎丑陋数组的；
所以这就须要自底向上，每一次都组合好丑陋数组，而后再网上去合并治理
先分: 因为给定的都是数组长度，所以本人按需填入对应的 [1,2…n] 值就好，始终分到只有一个值了，那么就是 1 了
再治: 合并的时候必须保障合并单方都曾经是丑陋数组，这样合并之后才必然是丑陋数组，这里保障合并之后，左侧都是奇数，右侧都是偶数
因为丑陋数组的排列只和长度 n 无关，为了升高反复计算，应用 map 缓存数据
工夫复杂度 O(n)

这里最须要思考的就是当取到三个值是同奇偶的时候，如何保障丑陋；
咱们晓得对于同奇偶的值而言，它是由下一层的丑陋数组递归回来，而后通过 2k+b 的形式转换而来的，也就是说同奇偶的值是合乎第二个公式的，进而能够确定他们也是丑陋的
这里其实还暗藏了一个等式，那就是对于 [1,2,…,2n] 而言，它是由[[1,2,…n].map(i=>i2-1) , [1,2,…n].map(i=>i2-1)] 组成的，这样也同时将奇数放在右边，偶数放在了左边，这是治的一部分;

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);
};

分治 — 疾速搜寻

求第 k 大，也就是求排好序之后的第 len(nums)-k+1 个值，对应于下标就是 targetIndex =len(nums)-k
这里用到快排的形式，找出随机下标 mid，而后进行快搜，将大于 nums[mid] 的放在右侧，小于 mid 的放在左侧，最初返回 nums[mid] 在整顿后的下标 pivotIndex
如果失去的 pivotIndex 大于咱们的 targetIndex，则再次快搜左侧 [left,pivotIndex-1] 数组
工夫复杂度，最快是 O(n) 一次找到，最慢是 O(n2)

 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);
  };

关于leetcode:JavaScript刷LeetCode拿offer分治

前言

注释

概念

关键点

实用场景

技巧

分治和二分，dp 的异同

小结

题目

53. 最大子序和

96. 不同的二叉搜寻树

169. 少数元素

23. 合并 K 个升序链表

932. 丑陋数组

215. 数组中的第 K 个最大元素