task1分治 LeetCode

多数元素 class Solution {
public:
int majorityElement(vector& nums) {
int tar = nums[0], times = 1;
for(int i = 1; i < nums.size(); i++){
if(times == 0){
tar = nums[i];
times = 1;
}
else if(nums[i] != tar)
times–;
else
times++;
}

return tar; }

};
最大子序和 class Solution {
public:
struct st{
int ls, rs, ms, is;
};

int maxSubArray(vector& nums) { return get(nums, 0, nums.size() - 1).ms; }st push(st l, st r){ int is = l.is + r.is; int ls = max(l.ls, l.is + r.ls); int rs = max(r.rs, r.is + l.rs); int ms = max(max(l.ms, r.ms), l.rs + r.ls); return st{ls, rs, ms, is}; }st get(vector ar, int l, int r){ if(l == r) return st{ar[l], ar[l], ar[l], ar[l]}; int m = (l + r) >> 1; st lsub = get(ar, l, m); st rsub = get(ar, m + 1, r); return push(lsub, rsub); }

};
Pow(x, n) class Solution {
public:
double eps = 1e-8;
bool eq(double x, double y){
return x == y;
}
double myPow(double x, int n) {
// if(eq(x, 0) || eq(x, 1))
// return x;
// if(n == 0)
// return 1;

int of = 0; if(n < 0){ if(n != INT_MIN){ n = -n; } else{ n = INT_MAX; of = 1; } x = 1 / x; }double ans = 1; if(of) ans = ans * x; while(n){ if(n & 1) ans = ans * x; x = x * x; n = n >> 1; }return ans; }

【task1分治】};