preface

Today there is no foreword, divide and conquer is very difficult, the main difficulty is how to better govern the merger after splitting, which is more difficult than splitting and ending. Therefore, here belongs to the thinking of the idea of divide and conquer, and we will try our best to exercise such practice in the future. When you do a divide-and-conquer, if you can substitute it with some other method, it’s not always optimal, at least it hurts your brain;

Drainage of the

Learn these a few and check collection, can happily brain teaser!

Brush the 18 greedy, mother no longer have to worry about me to see greedy is afraid!

Brush these 15 tracebacks, and you’re ready for a no-brainer assault interview

Brush these two pointer questions, you can tear the front end of the interview

After brushing the 12 sliding Windows, you can tear the front end of the interview

Brush these 20 dichotomy questions, may still tear the big factory interview

Brush these a few pile of questions, or may not tear the big factory interview

Brush these 30 tree questions, may still tear the big factory interview

Brush these 20 linked list questions, may still tear the big factory interview

Brush these 15 DP questions, can only chance the topic into dachang

Brush up on these bits, and wait until you consider the job interview

Text – Refer to Lucifer’s divide-and-conquer notes

concept

Divide and conquer means divide and conquer, so it’s in two

  • Divide a problem of size N into several smaller sub-problems
  • To solve the original problem according to the solution of the sub-problem

The key point

  • It must be divide and conquer
  • The rule must be made using the result of the rule, that is to say, the rule depends on the rule

Applicable scenario

  1. If the problem can be broken down into several smaller identical problems
  2. The results of these decomposed problems can be combined
  3. These decomposed problems are independent of each other and do not contain overlapping sub-problems

Bifurcation has a lot to do with DP, and it has to do with dichotomy, and essentially dichotomy is divide and conquer all the time, because the result of dichotomy is just to find the solution to the same smaller problem, you don’t have to combine it;

skills

  1. Think about the solution boundaries of subproblems and define the problem using functions
  2. Consider how to combine the solutions of subproblems – assuming the subproblems have been calculated, how to combine them
  3. Think of coding ideas – generally using recursion

Divide-and-conquer and dichotomy, similarities and differences of DP

  • Dichotomy only points on the problem, points directly abandoned; But divide and conquer not only need to decompose the problem, but also need to govern many problems
  • Both divide-and-conquer and DP deal with the problem of the problem, and both need to ensure that the sub-problem is not heavy or leaky.
    • Dp is translated by recursion and selection, from special generalization to half
    • Divide-and-conquer may also involve choice;
    • Dp solves problems that are often accompanied by overlapping subproblems, while divide-and-conquer does not

summary

  • If a problem is divided into several non-overlapping independent sub-problems by Wenjie, and the sub-problems can be pushed to the original problem, we can solve it by divide and conquer.

Topic summary

  • 53. Maximum suborder sum
  • 96. Different binary search trees
  • 169. Majority elements
  • Merge K ascending linked lists
  • 932. Beautiful array
  • 215. The KTH largest element in an array

The title

53. Maximum suborder sum

Analysis — divide and conquer

  1. First points – the use of recursive method of the array interval left and right nodes L,r constantly dichotomy out, until L === r, this time need to consider how to govern
  2. Let’s consider the combination of two values. The maximum case is three, math.max (L,R,L+R),
    • Max (LMAX,RMAX,L_Rmax+R_Lmax), where LMAX,RMAX refers to the maximum value of the combination of the two intervals,L_Rmax refers to the maximum interval of the L interval containing the right endpoint;
  3. Therefore, in the process of governance, each interval needs four variables, namely, the totalSum of totalSum interval, leftSum contains the maximum sum of consecutive subcolumns of left node, rightSum contains the maximum sum of consecutive subcolumns of right node, and the maximum value of maxSum interval
  4. At initialization, that is, at a single node, all four variables are unique values nums[l]
  5. Start merging governance,
    • TotalSum = totalSum; totalSum = totalSum;
    • LeftSum is always associated with left interval — Math. Max (left. MaxSum, left. TotalSum + right. LeftSum), or direct area left the maximum range, otherwise all left + right interval leftSum
    • Similarly rightSum is always associated with right interval — Math. Max (right. MaxSum, right. TotalSum + left. RightSum)
    • MaxSum points three conditions – Math. Max (left. MaxSum, right. MaxSum, left rightSum + right. LeftSum)
  6. So the time is O(n){O(n)}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, // The sum of values in the interval
            leftSum:Math.max(left.leftSum,left.totalSum+right.leftSum), // The maximum sum of contiguous subcolumns from the left boundary
            rightSum: Math.max(right.rightSum,right.totalSum+left.rightSum), // The maximum sum of contiguous subcolumns at the end of the interval
            maxSum:Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum)
        }
    }
    return recursion(0,nums.length-1).maxSum
}
Copy the code

Analysis — greed

  1. I want the largest sumContinuous subarray
  2. Cache the sum of the preceding and subarrays greater than 0 with sum. Once the sum is less than 0, the sum is no longer added. Reset the sum to 0 and keep sum >=0 before each iteration
  3. In this way, for each local subarray, its summation value is greater than or equal to 0, so that each new summation value, the maximum comparison, to ensure that the whole is the sum of the largest subarray
  4. Time complexity O(n){O(n)}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
};

Copy the code

96. Different binary search trees

Analyze — divide and conquer

  1. Given n nodes, find the maximum number of types of BST, that is, find the number of BST in [1,n] these nodes can form, can be subdivided into sequential [k,k+n] cell, how many BST can form
  2. First division: since the left tree of BST is smaller than the right tree, the node interval can be continuously divided into the left and right parts and handed over to the sub-tree for processing
  3. Rule again: split to only a node of the time, only a natural; When you have l, R different ways of doing it, you have L times R
  4. Of course, this method does a lot of repetitive work, after all, when we perform the callback, the index is a node tree x, so we can use the concept of space for time, cache some values
  5. After this process, the time complexity is O (nlog (n)) {O (nlog (n))} O (nlog (n)), space complexity is O (n) (n)} {O O (n)
var numTrees = function (n) {
  const map = new Map(a);const recursion = (n) = > {
    if (n <= 1) return 1; // No node counts as an assignment
    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);
};
Copy the code

Analysis — DP + divide-and-conquer

  1. According to the divide-and-conquer method, the corresponding subtree is treated only by the number of nodes each time, so dp can be used for caching
  2. Dp [I] represents the maximum number of different subtrees with I nodes
  3. Base case DP [0] =1, which is actually the initial governance of the final division in the partition and rule
  4. State transition equation: dp[I] = cumulative DP [k-1]* DP [i-k] here is the process of governance merger in divide and conquer, in DP is the state transition equation;
  5. Time complexity is O (nlog (n)) {O (nlog (n))} O (nlog (n)), space complexity is O (n) (n)} {O 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]
}
Copy the code

169. Majority elements

Analyze — divide and conquer

  1. First split: After splitting NUMS into an array of single values, governance begins
  2. Rerule: when merging, first find out the mode value and number of two merging, and then consider which one is the real mode after merging;
  3. Reconquer 2: The mode is selected by comparing two merged arrays. After the merge, the mode value is obtained by both arrays. Therefore, the number of the corresponding target should be obtained again each time the reconquer is performed
  4. If you compare the mode of two arrays, you can get the mode of the array. If you compare the mode of two arrays, you can get the mode of the array
  5. The time complexity of binary recursion is logn, and the complexity of each governance merge is logn, so the time complexity is O(n){O(n)}O(n), and the space complexity is O(1){O(1)}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 // If it is equal, then it is mode
        let lMaxtCount = 0
        let rMaxtCount = 0
        for(leti=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)}Copy the code

Analysis — Moore voting method

  1. If there is a value target that gets more than half as many votes as NUMs, then we can assume target for any initial value and maintain a vote count
  2. If count is already 0, then the target value is replaced until the last value left on target is the desired value
  3. Consider the extreme case, where you start with the real target value, which is constantly canceling out with the other values, and because the number of targets is greater than half, you still end up with the target value
  4. Time complexity O(n){O(n)}O(n), space complexity O(1){O(1)}O(1)
var majorityElement = function(nums) {
    let target;
    let count = 0
    for(let num of nums){
        if(count === 0&& target ! == num) {// If count is 0, the last target is invalid
            target = num 
        }
        if(target === num){
            count++
        }else{
            count--
        }
    }
    return target
};

Copy the code

Merge K ascending linked lists

Analysis – Directly iteratively merge linked lists

  1. Merge k lists is not good merge, merge 2 lists is easier;
  2. Here we merge two lists at a time
  3. Merge the two lists into one and iterate until you get one
  4. And finally, I’m running out of time, and the time complexity is NM{NM}NM where N is the length of the list array, and M is the average length of the list

var mergeKLists = function (lists) {
  if(! lists.length)return new ListNode().next;
  return lists.reduce((prev, cur) = > mergeTwoList(prev, cur));
};
  // Merge two ordered lists
  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;
  };
Copy the code

Analyze — divide and conquer

  1. Merge k lists is not good merge, merge 2 lists is easier;
  2. Split first: split according to the length, as long as more than 2 linked lists continue to split, until 1, and then governance
  3. Re-governance: when the binary split, and then combined, iteration to the end of the two ordered array, and then get a complete list
  4. By using divide-and-conquer instead of iterative merge, the number of merges can be reduced from N to logn, and the time complexity is MlogN{MlogN}MlogN, where M is the length of the merge of two lists and n is the length of the list array
 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))
    );
  };
  
  
Copy the code

932. Beautiful array

Analyze — divide and conquer

  1. The main thing about this problem is that there are two formulas,Odd plus even! = = oddSo if I have an odd number on the left-hand side and an even number on the right-hand side, then I’m sure it works
  2. The second formula is: if 2i! Is equal to l plus r, so 2 times I2+b) ! == l2+b+ r2+b; This equation is when we take 3 values equal and even (2(I2+b),l2+b, r2+b), we need to consider, at the next level, that they (I, L,r) conform to beautiful arrays;
  3. So you need to do a bottom-up, beautiful array composition every time, and then merge governance online
  4. N = 1; n = 1; n = 1; n = 1; n = 1; n = 1
  5. We must make sure that both sides of the merge are already beautiful arrays. In this case, we must make sure that the left side of the merge is odd and the right side is even
  6. Since the arrangement of beautiful arrays depends only on length N, map caching is used to reduce double-counting
  7. Time complexity O(n){O(n)}O(n)

The most important thing to think about here is how to make sure that the three values are the same even and odd; We know that the values of parity and parity are recursively derived from the beautiful array at the next level, and then converted by 2k+b, which means that the values of parity and parity conform to the second formula, and we know that they are also beautiful. There is a hidden equation here, which is that for [1,2… 2n], It is made of [[1, 2,… n]. The map (I = > i2-1), [1, 2,… n]. The map (I = > i2-1)], at the same time also will be an odd number on the left, even on the right, this is part of the cure;

var beautifulArray = function (n) {
  const map = new Map(a); map.set(1[1]); // initialization, also a cut-off condition
  const recursion = (n) = > {
    if (map.has(n)) return map.get(n); // End condition of recursion
    // The odd numbers are placed on the left side -- after arranging the beautiful array by length, then converting it to the odd number of the current layer by 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);
};

Copy the code

215. The KTH largest element in an array

Divide and conquer – Quick search

  1. Len (nums)-k+1, targetIndex =len(nums)-k
  2. The method of quick sorting is used to find the random subscript mid, and then the quick search is carried out. Those greater than NUMs [mid] are placed on the right and those less than mid are placed on the left. Finally, nums[mid] is returned to pivotIndex after sorting
  3. If the resulting pivotIndex is greater than our targetIndex, we will quickly search the left [left, PivotIndex-1] array again
  4. Time complexity, the fastest is O (n) (n)} {O O (n) once found, the slowest is O (n2) {O (n ^ 2)} O (n2)
 var findKthLargest = function (nums, k) {
    const select = (left, right) = > {
      if (left === right) return nums[left];
      let mid = ((right - left) >> 1) + left;
    // pivotIndex represents the index of the array mid after collation
      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];
      // Put the target at the left of the target, then put the target at the left of the target, then put the target at the left of the target
    // The target is placed on the left, so we need to find the point where the border is smaller than target (r), and then swap r with the original left value
      [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);
  };
  
Copy the code