【Leetcode】task1.分治

pow(x,n)

题解：
求x的n次幂，如果n是偶数，则可以拆解成(x* x)^(n/2)
如果n是奇数，则可以拆解成(x*x)^((n-1)/2)*x
此外，n为负数时，求倒数即可。但是当n=-2^31时，大于2 ^31-1，产生溢出，所以先-(n+1)，然后再乘一个x。

最大子序和

int maxSubArray(int* nums, int numsSize){
int i;
int max=nums[0],cnt=nums[0];
for(i=1;i<numsSize;i++){
    if(cnt>0){
        cnt+=nums[i];
    }
    else{cnt=nums[i];}
    max=max>cnt?max:cnt;
}
return max;
}

题解：将数组中的元素依次相加，如果和小等于0，那么相加从下一个元素开始。

多数元素

int majorityElement(int* nums, int numsSize){
    int key = nums[0];
    int count = 0;
    for (size_t i = 0; i < numsSize; i++)
    {
        if(nums[i] == key)
            count++;
        else
            count--;
        
        if(count <= 0)
        {
            key = nums[i+1];
        }
        
    }
    return key;
}

将相等元素的数量计数，如果个数小等于0了，就从下一个元素开始计个数。