前言今天没有前言。分而治之是非常困难的。主要难点在于如何更好地管理拆分后的合并。这是比二分法更难的一个层次。后续我会尽量练习这个方法；做分治的时候，如果可以换成其他的方法，一般分治不是最优解，至少很麻烦；divideandconquering这个词概念，所以一定要分成两部分Divide：把一个规模为N的问题分解成几个更小的子问题。治理：根据子问题的求解，对原问题的关键点进行先划分后求解。划分的结果一定要用，也就是说Governance要看应用场景。如果问题可以分解成几个规模较小的相同问题，则可以合并这些分解问题的结果。这些分解后的问题相互独立，不包含重叠的子问题。branches和dp有很深的联系，也和二分法有关。二分法本质上是一种永远只有分而无治的分治法，因为二分法的结果只需要找到较小的相同问题的解，不需要合并；问题的解边界，用函数定义问题，思考如何组合子问题的解——假设子问题已经计算好了，如何组合来思考编码思路——一般使用递归的分治法和二分法，dp的异同只是对二分法的问题进行划分，划分完直接丢弃；而分而治之不仅需要分解问题，还需要管理多个问题。分治和dp都是和题有关的，要保证子题不重复。.dp通过递归和选择进行翻译，选择也可能涉及到从特提升到对半；dp解决的问题往往伴随着重叠的子问题，而分而治之不是总结。如果一个问题被分成几个不重叠的问题，并且子问题可以推导到原问题，我们可以使用分治法来解决；题目53.最大子序列分析——先分而治之——用递归的方法对数组区间左右两边节点l和r继续一分为二，直到l===r。这个时候就要考虑怎么管理了。这里最终需要的是最大的连续子序列。我们首先考虑两个值的组合。最大的情况是三种，Math.max(L,R,L+R)，但是当取值比较多的时候，我们需要改变Math.max(LMAX,RMAX,L_Rmax+R_Lmax)其中LMAX,RMAX指的是combination两个区间的最大值，L_Rmax表示L区间包括右端点作为最大区间；因此在治理的过程中，每个区间需要有4个变量，分别是totalSum区间之和，leftSum包含左节点最大的连续子节点列sum，rightSum包含右节点的最大连续子列和，初始化maxSum区间的最大值，即当使用单节点时，四个变量都是唯一值nums[l]开始合并管理，totalSum直接将两个节点的totalSum合并即可；leftSum总是和左区间有关——Math.max(left.maxSum,left.totalSum+right.leftSum)，或者直接计算左区间的最大值，或者取左区间+右区间的leftSum同理rightSum总是与右区间相关--Math.max(right.maxSum,right.totalSum+left.rightSum)maxSum分为三种情况--Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum)所以先递归再递归，时间复杂度为O(n)varmaxSubArray=function(nums){constrecursion=(l,r)=>{if(l===r){return{totalSum:nums[l],leftSum:nums[l],rightSum:nums[l],maxSum:nums[l]}}constmid=((r-l)>>2)+lconstleft=递归(l,mid)constright=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)}}returnrecursion(0,nums.length-1).maxSum}分析——贪婪求连续子数组的最大和。使用sum缓存前面的sum大于0的子数组的sum，一旦小于0，就不再累加，重置为0，每次迭代前保持sum的值>=0，所以即对于每一个局部子数组，其累加值都大于等于0，这样每次累加一个新的值时，都在比较最大值，保证整体是最大子数组的和时复杂度O(n)varmaxSubArray=function(nums){letmax=-Infinity;letsum=0for(leti=0;i{如果(n<=1)返回1;//没有节点也是一个分配lettemp=0;for(leti=1;i<=n;i++){letl,r;如果(map.has(i-1)){l=map.get(i-1);}else{l=递归(i-1);map.set(i-1,l);}if(map.has(n-i)){r=map.get(n-i);}else{r=递归(n-i);map.set(n-i,r);}temp+=l*r;}返回温度；};returnrecursion(n);};分析--dp+divideandconquer根据分治解法，我们可以知道每次只根据节点子树的个数来管理对应的节点，所以可以利用dp来cachedp[i]的意思是当有i个节点时，不同子树的最大个数basecasedp[0]=1，这其实就是划分结束时的初始治理状态转移等式：dp[i]=accumulateddp[k-1]*dp[i-k]这里是分而治之的治理合并过程，dp中是状态转移方程；时间复杂度为O(nlog(n))，空间复杂度为O(n)varnumTrees=function(n){constdp=newArray(n+1)dp[0]=1for(leti=1;i<=n;i++){dp[i]=0for(letj=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j]}}返回dp[n]}169.众数分析--分而治之先：将nums拆分成单个值数组后，再开始治理和再治理：合并时，先找出合并后的两个模式的值和数量，再考虑合并后哪个才是真正的模式；然后治理2：通过比较合并后的两个数组来选择众数，合并后必须得到两个数组的众数值，所以每次处理都要重新得到目标对应的数量治理分析：为什么可以直接比较两个数组的众数得到合并数组的众数，那么这两个值就是当前数组最有可能的众数，只需要比较这两个值就可以得到真正的众数当前的合并数组。二元递归的时间复杂度是logn，每次治理合并的复杂度也是logn，所以时间复杂度是O(n)，空间复杂度是O(1)varmajorityElement=function(nums){constrecursion=(l,r)=>{if(l===r)returnnums[l]constmid=((r-l)>>1)+lconstlMax=recursion(l,mid)constrMax=recursion(mid+1,r)if(lMax===rMax)returnlMax//如果相等则为模式letlMaxtCount=0letrMaxtCount=0for(leti=l;i<=r;i++){if(nums[i]===lMax)lMaxtCount++if(nums[i]===rMax)rMaxtCount++}returnlMaxtCount>rMaxtCount?lMax:rMax}returnrecursion(0,nums.length-1)}分析——摩尔投票法如果有一个值目标，得票数是nums的一半以上，那么对于任意初始值，我们可以假设是目标，然后维护选票计数。如果计数已经为0，则替换目标值，直到目标上剩下最后一个值，即这里考虑最极端的情况，即一开始就得到真正的目标值，不断与其他值进行偏移。由于靶子数量多了一半，所以最后还是能守在靶子上。时间复杂度O(n)，空间复杂度O(1)varmajorityElement=function(nums){lettarget;letcount=0for(letnumofnums){if(count===0&&target!==num){//如果count为0，则证明最后一个target无效target=num}if(target===num){count++}else{count--}}returntarget};23.MergeK升序链表分析--直接迭代合并链表，合并k个链表不好合并。合并2个链表比较简单；这里每次合并两个链表就是将两个链表合并为一个，然后不断迭代，最后得到一个最终的超时时间，时间复杂度为NM其中N是链??表数组的长度，M是链表的平均长度varmergeKLists=function(lists){if(!lists.length)returnnewListNode().next;returnlists.reduce((prev,cur)=>mergeTwoList(prev,cur));};//合并两个排序列表constmergeTwoList=(l1,l2)=>{lettemp1=l1,temp2=l2;让emptyNode=(current=newListNode());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;当前=当前.下一个；temp1=temp1.next;}while(temp2){current.next=temp2;当前=当前.下一个；temp2=temp2.??next;}returnemptyNode.next;2个链表比较简单；先分：按照长度分成两份，只要有2个以上的链表，就继续分，直到有1个，然后管理再处理：进行二分分割后，再Combining，迭代得到两个最后排序数组，然后得到一个完整的链表使用分治法代替迭代合并可以将合并次数从n次减少到logn，时间复杂度为MlogN其中M是合并两个链表的长度,n是链表数组的长度varmergeKLists=function(lists){constlen=lists.length;如果(!len)返回null如果(len===1)返回列表[0];如果(len===2)returnmergeTwoList(lists[0],lists[1])constmid=len>>1;返回mergeTwoList(mergeKLists(lists.slice(0,mid)),mergeKLists(lists.slice(mid)));};932。美丽的数组分析——分而治之这道题主要有两个公式，奇数+偶数！==奇数，所以如果值为如果左边是奇数，右边是偶数，那么一定满足要求。第二个公式是：如果2i!==l+r，则2(i2+b)!==l2+b+r2+b；这个等式是当我们取的3个值都是相同的parity(2(i2+b),l2+b,r2+b)时，我们需要考虑在它的下一层，他们(i,l,r)符合漂亮的数组；所以每次都需要自下而上组合漂亮的数组，然后先在线合并管理：由于给定的数组长度都给定了，所以填入对应的[1,2...n]值为fine，直到只有一个值，则为1，然后规则：合并的时候，必须保证合并的两边已经是美数组，这样合并之后，一定是美数组。这里我们保证合并后左边是奇数，右边是偶数。由于漂亮数组的排列只与长度n有关，为了减少重复计算，使用map缓存数据的时间复杂度为O(n)。这里最需要考虑的是当fetch的三个值是同一个奇偶校验时，如何保证美观；我们知道，对于同校验的值，是从下一层的漂亮数组递归返回的，再经过2k+b转换，也就是说同校验的值符合第二个公式，然后可以确定它们也很漂亮。这里其实隐藏了一个等式，即对于[1,2,...,2n]，由[[1,2,...n].map(i=>i2-1)决定，[1,2,...n].map(i=>i2-1)]，这样奇数也放在左边，偶数放在右边，这是规则的一部分；varbeautifulArray=function(n){constmap=newMap();map.set(1,[1]);//初始化，也是截止条件constrecursion=(n)=>{if(map.has(n))returnmap.get(n);//递归的终止条件//奇数放在左边——根据数组的长度把数组排得很漂亮之后，然后再通过2N-1转换为当前层的奇数constleft=递归((n+1)>>1).map((item)=>item*2-1);constright=recursion(n>>1).map((item)=>item*2);constret=[...左，...右];map.set(n,ret);返还；};返回递归（n）；}；215。数组中第K大元素分而治之——快速搜索第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)。varfindKthLargest=function(nums,k){constselect=(left,right)=>{if(left===right)returnnums[left];}让mid=((right-left)>>1)+left;//pivotIndex表示mid排序数组的索引constpivotIndex=dfs(left,right,mid);如果(pivotIndex===nums.length-k)返回nums[pivotIndex];如果(pivotIndex>nums.length-k){returnselect(left,pivotIndex-1);}else{returnselect(pivotIndex+1,right);}};constdfs=(left,right,pivot)=>{让l=左，r=右；nsttarget=nums[pivot];//先放在最左边，然后在[l+1,r]的位置处理，最后在l,r的交界处把target交换回来//这里先把target放在了left，所以需要找到的是交界处比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--;}如果(l>r)中断；[nums[l],nums[r]]=[nums[r],nums[l]];}[nums[left],nums[r]]=[nums[r],nums[left]];返回r；};返回选择（0，nums.length-1）；};
