实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1: 输入: 2.00000, 10 输出: 1024.00000
示例 2: 输入: 2.10000, 3 输出: 9.26100
示例 3: 输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
说明: -100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。
Pow（x,n)
暴力（超时）
double myPow(double x, int n){ long long N = n; if(N < 0) { N = -N; x = 1/x; } double result = 1; for(int i = 0; i < N; i++) { result = result*x; } return result; }递归分治
double myPow(double x, int n){ long long N = n; if(N < 0) { N = -N; x = 1/x; } double subproblem = pow(x, N/2); if(N % 2 == 1) { return subproblem*subproblem*x; } else { return subproblem*subproblem; } }Line 5: Char 11: runtime error: negation of -2147483648 cannot be represented in type ‘int’; cast to an unsigned type to negate this value to itself (solution.c) 用int型将负整数转换为正整数时会溢出，改为long long型。
递归分治
double newpow(double x, long n) { if(n == 0) { return 1; } if(n == 1) { return x; } double subproblem = newpow(x, n/2); if(n % 2 == 1) { return subproblem*subproblem*x; } else { return subproblem*subproblem; } } double myPow(double x, int n){ long long N = n; if(N < 0) { N = -N; x = 1/x; } return newpow(x, N); }给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 多数元素 法一：利用众数的性质，排序后最中间那个即为众数。超时了
void Quicksort(int *a, int low, int high) { if(low < high) { int i = low; int j = high; int tmp = a[low]; while(i < j) { while(i < j && a[j] >= tmp) {j--;} if(i < j) {a[i] = a[j];} while(i < j && a[i] <= tmp) {i++;} if(i < j) {a[j] = a[i];} } a[i] = tmp; Quicksort(a, low, i-1); Quicksort(a, i+1, high); } } int majorityElement(int* nums, int numsSize){ Quicksort(nums, 0, numsSize-1); return nums[numsSize/2]; }法二：摩尔投票法思路 候选人(cand_num)初始化为nums[0]，票数count初始化为1。 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。 当票数count为0时，更换候选人，并将票数count重置为1。 遍历完数组后，cand_num即为最终答案。 成立原因 投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。 且“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。 因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。 这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。 参考链接
int majorityElement(int* nums, int numsSize){ int key = nums[0]; int count = 0; for(int i = 0; i < numsSize; i++) { if(nums[i] == key) { count++; } else { count--; } if(count <= 0) { key = nums[i+1]; } } return key; }