什么是分治算法
将手头的问题分成较小的子问题，而后别离解决每个子问题。如果子问题没方法解决，将子问题划分为更小的子问题时，达到无奈划分的阶段时得出后果。最初合并所有子问题的解决方案，以取得原始问题的解决方案。
- 宰割，将问题宰割为较小的子问题，通常采纳递归的模式，直到没有子问题能够进一步宰割为止。
- 解决，当问题无奈宰割，此时应该曾经失去了子问题的答案。
- 合并，解决了较小的子问题后，此阶段将它们递归组合，失去原始问题的答案。
分治算法能够解决什么问题？
- 归并排序
- 疾速排序
- 二分查找
等等
满足应用分治算法的条件
应用分治算法满足的条件：
- 原问题能够合成为若干个规模较小的子问题
- 子问题相互独立
- 子问题的解合并解决后可失去原问题的解
???????? 53.最大子序和
这道题目更简略不便的解答应该是应用动静布局
思路
将原问题合成为3个子问题，最大子序和要么在数组的右边，要么在数组的左边，要么横跨数组两头。，咱们通过递归拆解子问题。
当咱们把问题拆解成，数组的长度只有1时，咱们就能够失去子问题的解。因为此时最大的子序和就是数组中元素的值。咱们只须要返回，数组的右边，数组的左边，或者横跨数组两头的最大值即可，这些子问题的解答，最终会组合成原问题的解。
举一个例子????, 求[4, -3, 5, -2]的最大子序和。下图是合成的过程
把思路变为代码时，会有一个问题，左右两边能够通过递归获取最大值，如何获取两头的最大值呢？上面是办法的介绍
先计算右边序列外面的蕴含最左边元素的子序列的最大值，也就是从右边序列的最左边元素向左一个一个累加起来，找出累加过程中每次累加的最大值，就是右边序列的最大值，依照同样的办法，找出左边序列的最大值，左右两边的最大值相加，就是蕴含这两个元素的子序列的最大值。
解答
/** * @param {number[]} nums * @return {number} */var maxSubArray = function(nums) { /** * 求逾越两头的最大值 */ 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) { // 失去了最小子问题的解答 return arr.length === 1 ? arr[0] : Number.MIN_SAFE_INTEGER; } // 持续拆解子问题 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)};其余题解
这些应用分治办法的解答很多不是最优解，代码还有很多能够优化的中央，能力无限还请见谅
???????? 215.数组中的第K个最大元素
这道题目，之前我应用的是利用小顶堆，在不排序数组的状况下，获取第K个最大元素
思路
本题的解答的思路有很多种。最简略的是应用语言内置的排序，将数组排序后返回第K个最大元素（然而这样刷题也没有任何意义）。
其余的思路是能够利用堆这种数据结构，最小堆，最大堆都能够。因为堆的顶部，永远是最大值或者最小值。
咱们重点说一下分治的思路，有点相似快排，然而咱们不会像快排一样对整个数组进行排序。只对局部内容进行排序。
取数组的第一个值为基准值，大于它的放在右边，小于它的放在左边。咱们的指标是获取数组中的第K个最大元素，如果右边的数组的长度大于K，阐明K必定在右边的数组。如果K的长度大于右边的数组，阐明K必定在左边的数组。
在下一次迭代中，咱们能够只解决K所存在的那半边的数组。当数组的长度等于1时就是K了。过程合成如下
解答
/** * @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存在在max数组中 divideAndConquer(max, base) } else if (maxLen < k && min.length) { // 阐明k存在在min数组中 divideAndConquer(min, maxLen) } } divideAndConquer(nums, 0) return result};???????? 169.少数元素
思路
对半拆分数组。如果少数元素的长度大于数组的1/2。那么少数的元素，必定是拆分进去的两个数组，中的至多其中一个数组中的众数（如果少数元素次要集中在数组的两头局部，则拆分进去的两个数组的众数都是少数元素）。
应用对半拆分的思路，合成子问题：
- 当子问题（数组）被合成为长度为1时，那么子问题的解（子数组的众数）就是数组中的惟一值
- 当子问题（数组）被合成为长度为2时，如果数组中两个元素相等那么众数就是该元素。如果数组中两个元素不相等，能够看作子问题没有解。
- 当右边数组的没有解，左边数组有解时，数组的少数元素就是左边数组的众数
- 当右边数组的有解，左边数组没有解时，数组的少数元素就是右边数组的众数
- 当右边数组的有解，左边数组有解，并且解雷同时，数组的少数元素就是两边数组雷同的解
- 当右边数组的有解，左边数组有解，并且解不雷同时，此时咱们须要遍历数组计数，失去那一个解才是真正的众数。
上面是一个例子，展现了拆解子问题的过程：
解答
/** * @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 { // 须要判断下记数 let counterLeft = counter(arr, leftMode) let counterRight = counter(arr, rightMode) return counterLeft > counterRight ? leftMode : rightMode; } } return divideAndConquer(nums)};???? 241.为运算表达式设计优先级
思路
本题在最初的合并子问题的解时。不像其余分治算法的题目，把子问题的解简略的累加，或者取最大值。本题须要对子问题进行排列组合，获得原始问题的解。
遍历字符串，遇到运算符就将字符串宰割成两局部，而后为宰割进去的两局部增加小括号。合成子问题，直到被格调进去的局部不蕴含运算符为止。而后把子问题进行排列组合，失去最终的解答。
上面是合成的过程:
解答
/** * @param {string} input * @return {number[]} */var diffWaysToCompute = function(input) { const result = [] const operatorHash = { '+': true, '-': true, '*': true, } // 获取排列组合 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) // 如果是纯数字的状况 if (result.length === 0) { return [Number(input)] } return result.map(item => eval(item));};???? 395.至多有K个反复字符的最长子串
思路
本题思路，先找到不可能的字符（在字符串中，少于K次的字符串），用它们宰割数组（因为如果蕴含它们子串就不可能符合要求）。
将合成出的字符串代入下一次迭代。如果在迭代时发现，不存在不可能的字符的字符，这个字符串就是咱们的解。后果取解中长度最大的即可。
上面是合成过程：
解答
/** * @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() 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) => { // 切割的点 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;};???? 973.最靠近原点的K个点
欧几里得间隔的公式
思路
和215题相似，相似快排然而咱们不会对全副的内容进行排序。取数组的第一个值为基准值，求出该点的欧几里得间隔，以该店的欧几里得间隔为基准值，大于基准值放到左边的数组。小于基准值的放到右边的数组。
- 如果K等于右边数组的长度，阐明右边的数组就是咱们的答案。
- 如果K大于右边数组的长度，阐明右边的数组都是咱们的答案，然而还有一部分的答案在左边的数组中。在下一次迭代时，咱们只须要迭代左边的数组。
- 如果K小于右边数组的长度，阐明右边数组中蕴含了咱们的答案，然而还有局部的点，不是咱们的答案。左边的数组中，不会蕴含咱们的答案。在下一次迭代时，咱们须要迭代右边的数组。
上面以[[3,3],[5,-1],[-2,4]]为例子做一个简略的图解：
[3,3]的欧几里得间隔，4.24[5,-1]的欧几里得间隔，5.09[-2,4]的欧几里得间隔，4.47
解答
/** * @param {number[][]} points * @param {number} K * @return {number[][]} */var kClosest = function(points, K) { let reuslt = [] // 欧几里得间隔 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 // K个点都在left中，完结递归 reuslt = [...reuslt, ...left]; } else if (K < len) { // k个点都在left中，然而left中还有多余的点，须要排查 divideAndConquer(left) } else { // left中都是最近的点，还有一部分在right中，须要查找right K -= len reuslt = [...reuslt, ...left] divideAndConquer(right) } } } divideAndConquer(points) return reuslt;};???????? 43.字符串相乘
本题最简略的办法，就是用程序模仿小学乘法的步骤进行计算。
分治乘法
Karatsuba乘法是一种疾速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出，并于1962年得以发表。此算法次要用于两个大数相乘。一般乘法的复杂度是n2，而Karatsuba算法的复杂度仅为3n^log3≈3n^1.585（log3是以2为底的）
上面应用Karatsuba乘法合成下 5678 * 1234 的过程
思路
合并子问题的解时，请应用字符串加法，因为测试用例数字可能过大，会超过计算机的下限
解答
// 字符串加法，这里间接拷贝了网上现成的解答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};后续
leetcode上一些分治题目的剖析和解答，如有谬误还请斧正。应该能够对分治的思维有点肤浅的认知。共勉吧。