分治法

ryluo 2020-08-17 13:06:47

实现pow(x,n)(50)

题目链接:https://leetcode-cn.com/problems/powx-n/

image-20200817130810394


题目分析:

该题是求解一个数x的n次幂,其中x可以是整数也可以是小数,n可以是整数也可以是负数,对于负数求幂,$x^{-n}= \frac{1}{x^n}$,本质上还是求n为正数的幂,但是需要注意,int类型是$2^{31}-1$,当直接将$-2^{31}$转换成int会报错,这里需要将n转换成long long类型。

最简单暴力的做法就是遍历n,一个个相乘,复杂度是O(n)的,由于这里的n的取值是$2^{31}$,所以即使是O(n)的也非常的慢,而对于优化O(n)的算法,一般思路就是看能否将其优化成O(logn),所以这题应该是分治法的思路。

解法一:

使用递归,每次将求n次幂转换成两个n/2次幂结果的乘积(指数乘法,底数相同,指数相加),但是需要注意当指数为单数的时候,需要多乘一次,具体的例子如下。注意这里的边界条件是n=0的时候。

$a^{10}=a^5\cdot a^5$

$a^5=a\cdot (a^2\cdot a^2)$

$a^3=a\cdot (a\cdot a)$

$a^2=a\cdot a$

class Solution {
public:
    double qmi(double x, int n){
        if (n == 0) return 1.0;
        double half = qmi(x, n / 2);
        if (n & 1) return half * half * x;
        else return half * half;
    }

    double myPow(double x, int n) {
        double ans = 1.0;
        long long t = (long long)abs(n);
        return n > 0 ? qmi(x, n) : 1 / qmi(x, n);
    }
};


解法二:

将求$a^{n}$转化成求$a^{2^{x_1}} \cdot a^{2^{x_2}} … a^{2^{x_k}}$,其中$2^{x_1}+2^{x_2}+..2^{x_k}=n$ 这样就把原来要遍历n次的问题变成了遍历k次,这里的$k=log(n)$,那么如何将n拆分成多个2的指数幂的和呢?其实就是将n转化成2进制的形式,然后二进制中1的位置就是其中$x_{k}$的取值,举个例子,求$4^{10}$,在这里n=10,那么10的二级制表示为:10=(1010),即$10=2^1+2^3$,所以这题的代码实现就是遍历n的二进制表示的每一位,$4^{10}=4^{2^1} \cdot 4^{2^3}$,而在计算$4^{2^3}$的时候,只需要$4^{2^1}$连续乘三次就行了,也就是说需要不断的更新下面的x的值(注意二进制中0的部分,乘积是1直接忽略就行了)。

class Solution {
public:
    double myPow(double x, int n) {
        double ans = 1.0;
        long long t = (long long)abs(n);
        while(t){
            if(t & 1) ans *= x;
            x *= x;
            t >>= 1;
        }
        return n > 0 ? ans : 1 / ans;
    }
};


最大子序和(53)

题目链接:https://leetcode-cn.com/problems/maximum-subarray/

image-20200819112938605


题目分析:

这道题上来很容易想到使用动态规划的做法,但是使用分治的思路也是非常清晰的。

解法一:

动态规划:

  1. 状态表示:dp[i]表示的是以第i个位置为结尾的最大子序和(这里需要注意,状态表示的是以某个位置为结尾的最大子序和,但是最终结果返回的是数组中所有可能位置结尾的最大子序和,并不是最后一个位置的最大子序和,即dp[n])

  2. 状态初始化:dp[0]=nums[0]表示的是第一个数的最大子序和,那就是数组中的第一个数

  3. 状态转移方程:dp[i],由状态表示的定义可知,其表示的是第i个位置为结尾的最大值,那么可以分为两种情况,(1)包括dp[i-1](当前值加上前面的子序和), 那么dp[i] = dp[i-1] + nums[i](2)舍去前面的子序和,dp[i] = nums[i],这两者取最大值(因为加上前面的部分会使得总和小于当前值)。

下面的代码中稍微优化了一下,将一维数组给优化掉了。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); i++){
            dp = max(nums[i], dp + nums[i]);  // 括号里面的dp表示的是上一次的状态
            ans = max(ans, dp);
        }
        return ans;
    }
};


解法二:

分治(递归):

  1. 将nums分成两部分[l, mid], [mid + 1, r]
  2. 求区间[l, mid]的最大子序和(最终返回的结果可能在这半边)
  3. 求区间[mid + 1, r]的最大子序和(最终返回的结果也可能在这半边)
  4. 最终返回的结果可能横跨两边,也就是说包括了中点。那么可以计算以mid为中点的最大子序和(也就是从mid位置从后往前不断遍历相加前面的值,得到一个最大值),在计算以mid+1为起点的最大子序和(也就是从mid+1位置开始从前往后遍历相加,得到最大的子序和),横跨两边的最大子序和就是上述两段的最大子序和的和。
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return subsum(nums, 0, nums.size() - 1);
    }
    int subsum(vector<int>& nums, int l, int r){
        if(l == r) return nums[l];
        int mid = (l + r) >> 1;
        int left = subsum(nums, l, mid);
        int right = subsum(nums, mid + 1, r);

        int tmp = 0; // 以中点为结尾的最大子序和
        int lsum = INT_MIN;
        for(int i = mid; i >= l; i --){
            tmp += nums[i];
            lsum = max(tmp, lsum);
        }

        tmp = 0;
        int rsum = 0; // 以中点的下一个数位起始的最大子序和
        for(int i = mid + 1; i <= r; i++){
            tmp += nums[i];
            rsum = max(tmp, rsum);
        }

        return max(max(left, right), lsum + rsum);
    }
};


多数元素(169)

题目链接:https://leetcode-cn.com/problems/majority-element/

image-20200819134456127

题目分析:

这道题上来的第一个思路就是使用分治的思路:

解法一(分治法):

  1. 先将数组分成两部分[l, mid], [mid + 1, r]
  2. 计算区间[l,mid]中出现次数最多的数
  3. 计算区间[mid+1, r]中出现次数最多的数
  4. 如果两边出现次数比较多的数相同直接返回随便一个数即可,若不同进行下一步
  5. 分别统计区间[l,mid]和[mid+1, r]中出现最多次数数出现的次数,返回出现次数更多的那个数

该算法的复杂度为O(nlogn)

class Solution {
public:
    int devide(vector<int>& nums, int l, int r){
        if(l == r) return nums[l];
        int mid = (l + r) >> 1;
        int left = devide(nums, l, mid);
        int right = devide(nums, mid + 1, r);
        if(left == right) return left;

        int lsum = 0, rsum = 0;
        for(int i = l; i <= mid; i++)
            if (nums[i] == left) lsum ++;

        for(int i = mid + 1; i <= r; i++)
            if(nums[i] == right) rsum ++;

        return lsum > rsum ? left : right; 
    }
    int majorityElement(vector<int>& nums) {
        return devide(nums, 0, nums.size() - 1);
    }
};


解法二:

投票法(复杂度为O(n)):

该题中是要找出出现次数超过一半的数,那么可以将整个数组分成两大类,第一类就是出现次数最多的数,将其权重记为+1, 其他的数都记为-1,那么遍历一遍数组,将所有数的权重相加,其和必定大于等于1。

我们可以使用一个变量作为候选众数,也就是所有的数都可能是众数,但是我们在遍历数组的时候去判断该数遍历到当前位置是否还满足众数的要求。

  1. 将第一个数作为候选众数,依次遍历数组中的其他数
  2. 若下一个数是众数,那么当前总的权重值+1,否则当前的总权重值-1,当权重值为0的时候,跟新众数为下一个值,也就是前面的那两类数的权重正负抵消了,但是结果一定从后面可以找到
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = nums[0], w = 1;
        for(int i = 1; i < nums.size(); i++){
            if(w == 0) ans = nums[i];
            if(nums[i] == ans) w ++;
            else w--;
        }
        return ans;
    }
};