signed

QiShunwang

“诚信为本、客户至上”

Leetcode编程实践-分而治之

2020/8/19 21:42:20   来源:

1.1 主要思想

分治算法的主要思想是将原问题 若干个子问题,直到子问题 ,停止递归。将子问题逐个 击破(一般是同种方法),将已经解决的子问题合并,最后,算法会 得到原问题的答案。

1.2 分治算法步骤

  1. 分:递归将问题分解为各个的子问题 (性质相同的、相互独立的子问题);
  2. 治:将子问题逐个击破;
  3. 合:将已解决的子问题逐层合并,最终得出原问题的解。

1.3 分治法使用的情况

  1. 原问题能被分解为子问题;
  2. 子问题的结构与性质与原问题一样,并且相互独立,子问题之间不包含公共的子子问题;
  3. 子问题可以合并为原问题的解。

1.4 练习

Leetcode169 多数元素

在这里插入图片描述
【思路】
子问题:对数组分为左数组与右数组

  1. 左数组众数=右数组众数,返回该众数;
  2. 若众数不同,返回在整个数组中出现更多的那个众数。

分解停止条件:区间长度=1

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n=len(nums)
        # 设置停止点
        if n==1:
            return nums[0]
        # 分解子问题
        left=self.majorityElement(nums[:n//2])
        right=self.majorityElement(nums[n//2:])
        # 治之
        if left==right:
            return left
        if nums.count(left)>nums.count(right):
            return left
        else:
            return right

LeetCode53 最大子序和

在这里插入图片描述
【思路】
子问题:
分为左右区间,计算左区间最大子序和 A,计算右区间最大子序和 B,
计算(左区间从右起最大子序和+从右区间从左起最大子序和)C
返回max(A,B,C)
停止条件:区间长度=1

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n=len(nums)
        # 停止条件
        if n==1:
            return nums[0]
        # 分解为子问题
        left=self.maxSubArray(nums[:n//2])
        right=self.maxSubArray(nums[n//2:])
        # 解决子问题
        # 计算左区间从右起最大子序和
        max_l,tmp=-float('inf'),0
        for i in range(n//2-1,-1,-1):
            tmp+=nums[:n//2][i]
            max_l=max(tmp,max_l)
        # 计算右区间从左起最大子序和 
        max_r,tmp=-float('inf'),0
        for i in range(n-n//2):
            tmp+=nums[n//2:][i]
            max_r=max(tmp,max_r)
       	# 合并返回结果
       	return max(max_r+max_l,right,left)

Leetcode50 Pow(x,n)

在这里插入图片描述
【思路】
子问题:xn=(x2)n/2x^n={(x^2)}^{n/2}
nn 为奇数,xn=x×xn1x^n=x\times x^{n-1}
停止条件:n=0n=0 , return 1

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n<0:
            x=1/x
            n=-n
        if n==0: # 终止条件
            return 1
		# 分解子问题
        if n%2==1:
            return x*self.myPow(x,n-1)
        x*=x
        return self.myPow(x,n/2)