LeetCode 学习记录——分治

分治

一、主要思想：

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

二、分治算法的步骤

分：递归地将问题分解为各个的子问题(性质相同的、相互独立的子问题)；
治：将这些规模更小的子问题逐个击破；
合：将已解决的子问题逐层合并，最终得出原问题的解；

三、 分治法适用的情况

原问题的计算复杂度随着问题的规模的增加而增加。
原问题能够被分解成更小的子问题。
子问题的结构和性质与原问题一样，并且相互独立，子问题之间不包含公共的子子问题。
原问题分解出的子问题的解可以合并为该问题的解。

四、题目

169. 多数元素.
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

三种思路：
（1）哈希表
（2）摩尔投票
（3）排序后

（1）哈希

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map <int,int> mp;
        for(int n:nums)   
            if(++ mp[n] > nums.size()/2)   return n;         
        return -1;
    }
};

（2）摩尔投票

class Solution {
public:
    int majorityElement(vector<int>& nums) {    //摩尔投票法，投我++，不投--，超过一半以上的人投我，那我稳赢哇
        int count=0,candidate;
        for(int n:nums)
        {
            if(count==0)        candidate=n;

            if(n==candidate)    count++;
            else                count--;
        }
        return candidate;
    }
};

（3）排序

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

53.最大自序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

一看就知道是动态规划问题，题目已经提示了使用更为精妙的分治法，那就是两种思路：

(1)动态规划
（2）分治法

（1）动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

（2）分治法
以下代码是直接使用官方解答，我自己并没有写出来。

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) return (Status) {a[l], a[l], a[l], a[l]};
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

50.Pow(x,n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。

二分思想递归：

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) { return 1; }
        if (n == 1) { return x; }
        if (n == -1) { return 1 / x; }
        double half = myPow(x, n / 2);
        double rest = myPow(x, n % 2);
        return rest * half * half;
    }
};

参考