What is a divide-and-conquer algorithm
Break the problem at hand into smaller sub-problems and tackle each sub-problem individually. If the subproblem cannot be solved, the subproblem is divided into smaller subproblems and the result is obtained when the stage cannot be divided. Finally, the solution of all subproblems is merged to obtain the solution of the original problem.
- Partition, the division of a problem into smaller subproblems, usually recursively, until no further subproblems can be divided.
- Solution, when the problem cannot be divided, the answer to the subproblem should already be obtained.
- Merge, after solving the smaller sub-problems, they are recursively combined at this stage to get the answer to the original problem.
What problem can a divide-and-conquer algorithm solve?
- Merge sort
- Quick sort
- Binary search
, etc.
The conditions for using the divide-and-conquer algorithm are met
The conditions met by the divide-and-conquer algorithm are as follows:
- The original problem can be decomposed into several smaller sub-problems
- The subproblems are independent of each other
- The solution of the original problem can be obtained by combining the solutions of the sub-problems
🎉😄 53. Maximum suborder sum
A simpler and more convenient solution to this problem would be to use dynamic programming
Train of thought
The original problem is decomposed into three subproblems, with the largest suborder sum either on the left side of the array, on the right side of the array, or across the middle of the array. We break down the subproblem recursively.
When we break down the problem into an array of only one length, we can get a solution to the subproblem. Because the largest sum is the value of the element in the array. We just return the left side of the array, the right side of the array, or the maximum across the middle of the array, and the solutions to these subproblems will eventually combine into solutions to the original problem.
For example 🌰, find the sum of the largest suborders of [4, -3, 5, -2]. Below is the decomposition process
One of the problems with thinking in code is that if you can maximize the left and right recursively, how do you maximize the middle? Here is an introduction to the method
First on the left side of the inside of the sequence contains the maximum of the right sequence of elements, namely the sequence is the most the right side of elements on the left side to the left a a sum up, find out the maximum of every time accumulation during the process of accumulation, the left is a maximum of sequence, according to the same method, find out the right sequence of maximum, a maximum of left and right sides together, It’s the maximum number of subsequences that contain these two elements.
answer
/ * * *@param {number[]} nums
* @return {number}* /
var maxSubArray = function(nums) {
/** * find the maximum span between */
const getMiddMax = (left, right) = > {
let leftMax = Number.MIN_SAFE_INTEGER
let rightMax = Number.MIN_SAFE_INTEGER
let leftSum = 0
let rightSum = 0
for (let i = left.length - 1; i >= 0; i--) {
leftSum += left[i]
leftMax = Math.max(leftSum, leftMax)
}
for (let i = 0; i < right.length; i++) {
rightSum += right[i]
rightMax = Math.max(rightSum, rightMax)
}
return rightMax + leftMax
}
const divideAndConquer = (arr) = > {
if (arr.length <= 1) {
// Get the answer to the smallest question
return arr.length === 1 ? arr[0] : Number.MIN_SAFE_INTEGER;
}
// Continue dismantling the subproblem
const middIndex = Math.floor(arr.length / 2)
const left = arr.slice(0, middIndex)
const right = arr.slice(middIndex)
const middMax = getMiddMax(left, right)
const leftMax = divideAndConquer(left)
const rightMax = divideAndConquer(right)
return Math.max(middMax, leftMax, rightMax)
}
return divideAndConquer(nums)
};
Copy the codeOther answer key
Many of these divide-and-conquer solutions are not optimal, the code can be optimized in many places, limited ability please forgive me
🎉😄 215. The KTH largest element in the array
So this problem, what I used before was to take the small top heap, get the KTH largest element without sorting the array
Train of thought
There are many ways to answer this question. The simplest is to use the built-in sort, which returns the KTH largest element after sorting the array (but that doesn’t make any sense). Another idea is that you can use a heap as a data structure, the smallest heap, the largest heap. Because the top of the heap is always a maximum or a minimum.
Let’s focus on the idea of divide-and-conquer, which is kind of like quicksort, but we’re not going to sort the entire array like quicksort. Sort only parts of the content.
Take the first value of the array as the reference value, and put whatever is greater on the left and less on the right. Our goal is to get the KTH largest element in the array. If the length of the left array is greater than K, K must be in the left array. If K is larger than the array on the left, K must be in the array on the right.
In the next iteration, we can only deal with the half of the array where K exists. It’s K when the length of the array is equal to 1. The process is decomposed as follows
answer
/ * * *@param {number[]} nums
* @param {number} k
* @return {number}* /
var findKthLargest = function(nums, k) {
let result = null
const divideAndConquer = (arr, base) = > {
if (arr.length === 1) {
result = arr[0]
return
}
const referenceValue = arr[0]
const min = []
const max = []
for (let i = 1; i < arr.length; i++) {
if (arr[i] > referenceValue) {
max.push(arr[i])
} else {
min.push(arr[i])
}
}
max.push(referenceValue)
const maxLen = max.length + base;
if (maxLen >= k && max.length) {
K exists in the Max array
divideAndConquer(max, base)
} else if (maxLen < k && min.length) {
// k exists in min array
divideAndConquer(min, maxLen)
}
}
divideAndConquer(nums, 0)
return result
};
Copy the code🎉😄 169. Majority elements
Train of thought
Split an array in half. If most elements are greater than half the length of the array. Most of the elements must be the mode of at least one of the two split arrays (if most elements are concentrated in the middle of the array, the mode of both split arrays is most elements).
Using the idea of split in half, decompose the sub-problem:
- When the subproblem (array) is decomposed to length 1, then the solution of the subproblem (mode of the subarray) is the unique value in the array
- When the subproblem (array) is decomposed into length 2, the mode is that element if the two elements in the array are equal. If two elements in the array are not equal, it can be considered that the subproblem has no solution.
- When the array on the left has no solution and the array on the right has a solution, most elements of the array are the mode of the array on the right
- When the left array has a solution and the right array has no solution, the majority of the elements of the array are the mode of the left array
- When the array on the left has a solution and the array on the right has a solution, and the solutions are identical, most elements of the array are identical solutions
- When the array on the left has solutions and the array on the right has solutions, and the solutions are not the same, then we need to go through the array counting, and get which solution is the real mode.
Here is an example that shows the process of unpacking subproblems:
answer
/ * * *@param {number[]} nums
* @return {number}* /
var majorityElement = function(nums) {
const counter = (arr, target) = > {
let count = 0
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
count += 1}}return count
}
const divideAndConquer = (arr) = > {
if (arr.length === 1) {
return arr[0]}if (arr.length === 2) {
if (arr[0] === arr[1]) {
return arr[0]}else {
return null}}const middIndex = Math.floor(arr.length / 2)
const left = arr.slice(0, middIndex)
const right = arr.slice(middIndex)
const leftMode = divideAndConquer(left)
const rightMode = divideAndConquer(right)
if (leftMode === null&& rightMode ! = =null) {
return rightMode
} else if(leftMode ! = =null && rightMode === null) {
return leftMode
} else if (leftMode === null && rightMode === null) {
return null
} else {
// We need to judge the number
let counterLeft = counter(arr, leftMode)
let counterRight = counter(arr, rightMode)
returncounterLeft > counterRight ? leftMode : rightMode; }}return divideAndConquer(nums)
};
Copy the code😄 241. Design priorities for operational expressions
Train of thought
In the final merging of the solutions to the subproblems. Unlike other divide-and-conquer problems, the subproblems are simply summed up, or maximized. This problem requires permutation and combination of sub-problems to obtain the solution of the original problem.
Iterating through the string, dividing the string into two parts as it encounters an operator, and then adding parentheses to the separated parts. Decompose the subproblem until the styled part does not contain the operator. Then the subproblems are permutations and combinations to get the final solution.
Here’s how it works:
answer
/ * * *@param {string} input
* @return {number[]}* /
var diffWaysToCompute = function(input) {
const result = []
const operatorHash = {
'+': true.The '-': true.The '*': true,}// Get permutations and combinations
const getPermutations = (a, b, operator) = > {
const hash = {}
const result = []
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < b.length; j++) {
const key = ` ((${a[i]})${operator}(${b[j]})) `
if(! hash[key]) { result.push(key) } } }return result
}
const divideAndConquer = (str, res) = > {
for (let i = 0; i < str.length; i++) {
const operator = str[i]
if (operatorHash[operator]) {
const left = str.slice(0, i)
const right = str.slice(i + 1)
const leftRes = []
const rightRes = []
if (isNaN(Number(left))) {
divideAndConquer(left, leftRes)
} else {
leftRes.push(left)
}
if (isNaN(Number(right))) {
divideAndConquer(right, rightRes)
} else{ rightRes.push(right) } res.push(... getPermutations(leftRes, rightRes, operator)) } } } divideAndConquer(input, result)// In the case of pure numbers
if (result.length === 0) {
return [Number(input)]
}
return result.map(item= > eval(item));
};
Copy the code😄 395. The largest string with at least K repeated characters
Train of thought
Find impossible characters (in strings, less than K times) and use them to split the array (because if you include them, the substring will not fit the requirement).
Substitute the decomposed string into the next iteration. If, during iteration, it is found that there are no impossible characters, this string is our solution. Results The solution with the greatest length is ok.
Here’s the breakdown:
answer
/ * * *@param {string} s
* @param {number} k
* @return {number}* /
var longestSubstring = function(s, k) {
if (s.length < k) {
return 0
}
let result = Number.MIN_SAFE_INTEGER;
const getSplitDots = (str) = > {
let splitDots = []
const hash = new Map(a)for (let i = 0; i < str.length; i++) {
const key = str[i]
if(! hash.has(key)) { hash.set(key, [i]) }else {
const val = hash.get(key)
hash.set(key, [...val, i])
}
}
const entries = hash.entries()
for (let [key, value] of entries) {
if (value.length < k) {
splitDots = [...splitDots, key]
}
}
return splitDots
}
const divideAndConquer = (str) = > {
// Cut the point
let splitDots = getSplitDots(str)
if (splitDots.length === 0) {
result = Math.max(result, str.length);
} else {
const arr = str.split(splitDots[0])
for (let i = 0; i < arr.length; i++) {
divideAndConquer(arr[i])
}
}
}
divideAndConquer(s)
return result;
};
Copy the code😄 973. K points closest to the origin
Euclidean distance formula
Train of thought
Just like problem 215, just like quicksort but we’re not going to sort everything. Take the first value of the array as the reference value, calculate the Euclidean distance of the point, take the store’s Euclidean distance as the reference value, greater than the reference value to the right of the array. Anything less than the reference value goes into the left array.
- If K is equal to the length of the array on the left, that means the array on the left is our answer.
- If K is greater than the length of the left array, it means that all of the left array is our answer, but some of the answers are in the right array. In the next iteration, we just iterate over the array on the right.
- If K is less than the length of the array on the left, that means that the array on the left contains our answer, but there are some points that are not our answer. The array on the right is not going to contain our answer. In the next iteration, we need to iterate over the array on the left.
Here is a simple diagram using [[3,3],[5,-1],[-2,4]] as an example:
[3, 3]The Euclidean distance of 4.24[5,-1]Euclidean distance of 5.09[-2,4]The Euclidean distance of 4.47
answer
/ * * *@param {number[][]} points
* @param {number} K
* @return {number[][]}* /
var kClosest = function(points, K) {
let reuslt = []
// Euclidean distance
const getEuclideanDistance = (o1) = > {
const [x1, y1] = o1;
const x2 = 0;
const y2 = 0
return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
}
const divideAndConquer = (arr) = > {
if(!!!!! arr.length && K) {const benchmark = getEuclideanDistance(arr[0])
const left = []
const right = []
for (let i = 1; i < arr.length; i += 1) {
if (getEuclideanDistance(arr[i]) < benchmark) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
if (left.length) {
right.push(arr[0])}else {
left.push(arr[0])}const len = left.length;
if (K === len) {
K -= len
// all K points are in left, end recursion
reuslt = [...reuslt, ...left];
} else if (K < len) {
// All k points are in left, but there are extra points in left, which need to be checked
divideAndConquer(left)
} else {
// Left is the nearest point, and part of it is in right
K -= len
reuslt = [...reuslt, ...left]
divideAndConquer(right)
}
}
}
divideAndConquer(points)
return reuslt;
};
Copy the code🎉😄 43. String multiplication
The simplest method in this case is to use a program to simulate the steps of primary school multiplication.
Divide and conquer method
Karatsuba multiplication is a fast multiplication. This algorithm was proposed by Anatolii Alexeevitch Karatsuba in 1960 and published in 1962. This algorithm is mainly used to multiply two large numbers. The complexity of ordinary multiplication is N2, while the complexity of Karatsuba algorithm is only 3n^log3≈3n^1.585 (log3 is base 2).
The process of 5678 * 1234 decomposition under Karatsuba multiplication is used below
Train of thought
When combining solutions to subproblems, use string addition because test case numbers may be too large to exceed the computer’s upper limit
answer
// string addition, here is a direct copy of the online solution
var addition = function(num1, num2) {
let i = num1.length - 1, j = num2.length - 1, add = 0;
const ans = [];
while (i >= 0 || j >= 0|| add ! =0) {
const x = i >= 0 ? num1.charAt(i) - '0' : 0;
const y = j >= 0 ? num2.charAt(j) - '0' : 0;
const result = x + y + add;
ans.push(result % 10);
add = Math.floor(result / 10);
i -= 1;
j -= 1;
}
return ans.reverse().join(' ');
}
var padZero = function (num) {
let zero = ' '
while (num) {
zero += '0'
num -= 1
}
return zero
}
/ * * *@param {string} num1
* @param {string} num2
* @return {string}* /
var multiply = function(num1, num2) {
const divideAndConquer = (str1, str2) = > {
let str1High, str1Low, str2High, str2Low, str1Carry, str2Carry, r1, r2, r3, r4
if (str1.length > 1) {
const str1MiddIndex = Math.floor(str1.length / 2)
str1High = str1.slice(0, str1MiddIndex)
str1Low = str1.slice(str1MiddIndex)
str1Carry = str1Low.length
} else {
str1High = str1
str1Low = '0'
str1Carry = 0
}
if (str2.length > 1) {
const str2MiddIndex = Math.floor(str2.length / 2)
str2High = str2.slice(0, str2MiddIndex)
str2Low = str2.slice(str2MiddIndex)
str2Carry = str2Low.length
} else {
str2High = str2
str2Low = '0'
str2Carry = 0
}
if (str1High.length <= 1 && str2High.length <= 1) {
r1 = String(Number(str1High) * Number(str2High)) + padZero(str1Carry + str2Carry)
} else {
r1 = divideAndConquer(str1High, str2High) + padZero(str1Carry + str2Carry)
}
if (str1High.length <= 1 && str2Low.length <= 1) {
r2 = String(Number(str1High) * Number(str2Low)) + padZero(str1Carry)
} else {
r2 = divideAndConquer(str1High, str2Low) + padZero(str1Carry)
}
if (str1Low.length <= 1 && str2High.length <= 1) {
r3 = String(Number(str1Low) * Number(str2High)) + padZero(str2Carry)
} else {
r3 = divideAndConquer(str1Low, str2High) + padZero(str2Carry)
}
if (str1Low.length <= 1 && str2Low.length <= 1) {
r4 = String(Number(str1Low) * Number(str2Low)) + ' '
} else {
r4 = divideAndConquer(str1Low, str2Low)
}
return addition(addition(r1, r2), addition(r3, r4))
}
const result = divideAndConquer(num1, num2)
if (result[0= = ='0') {
return '0'
}
return result
};
Copy the codesubsequent
Analysis and solution of some divide-and-conquer problems in Leetcode, please correct any mistakes. It should be possible to be a little superficial about the idea of divide and conquer. ‘.