# 算法：递归和分治-实战

## leetcode:50实现 pow(x, n) ，即计算 x 的 n 次幂函数。

### 方法一、直接调用库函数

```public double myPow(double x, int n) {
return Math.pow(x, n);
}```

### 方法二、暴力

```public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
for (long i = 0; i < N; i++)
ans = ans * x;
return ans;
}```

### 方法三、递归分治的做法

```class Solution {
private double fastPow(double x, long n) {
if (n == 0) {
return 1.0;
}
double half = fastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}

return fastPow(x, N);
}
};```

## leetcode:169求众数。

### 方法一：暴力

```    public int majorityElement1(int[] nums) {
int n = nums.length;
for (int x : nums) {
int count = 0;
for (int j : nums) {
if (x == j) count++;
}
if (count > n / 2) return x;
}
return 0;
}```

### 方法二：哈希表 ，元素出现次数存入map中

```public int majorityElement2(int[] nums) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap();
for (int x : nums) {
Integer num = map.get(x);
if (num == null) num = 0;
map.put(x, num + 1);
if (num + 1 > n / 2) return x;
}
return 0;
}```

### 方法三：分治

```class Solution11 {
private int countInRange(int[] nums, int num, int lo, int hi) {
//计算两边次数
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}

private int majority(int[] nums, int lo, int hi) {
if (lo == hi) {         //递归出口
return nums[lo];
}
//数据准备
int mid = (hi-lo)/2 + lo;
//对子问题进行递归处理
int left = majority(nums, lo, mid);
int right = majority(nums, mid+1, hi);

//子结果数据合并判断
if (left == right) {
return left;
}

//left!=right时，根据次数判断
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);

return leftCount > rightCount ? left : right;
}

public int majorityElement(int[] nums) {
return majority(nums, 0, nums.length-1);
}
}```

### 方法四：扩展 Boyer-Moore 投票算法

```   public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;

for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}

return candidate;
}```

0 条评论

• ### Java的基础程序设计结构（Java学习-1）

注释就是方便自己或者别人阅读代码，绝大多数的程序语言都有注释这个功能，大部分的注释命令都是相同的或者想通的，

• ### 复习：GoF的23种设计模式之iterator模式（行为型）

就如java集合中的iterator类似，是一种最简单也是最常用的设计模式。它可以让用户通过的特定接口轮询容器中的每一个元素，而不需要了解底层实现。

• ### 算法：HashTable、List、Map、Set-实战

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### top100习题

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

• ### 【Leet Code】1. Two Sum

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### 查找算法

查找，作为应用最为广泛和最基础的算法思想之一，几乎在所有应用程序之中都有它的思想身影。往细一点说：查找可以有 顺序查找、二分查找、散列表查找，下面依次来看一下这...

• ### 适合数据分析面试笔试入门的编程题

1.在输入ai1的时候，因为是每颗果树的第一个输入，代表刚开始果树的苹果含量，所以可以写在第二个循环的前面和第一个循环的里面，所以第二个循环就要从1开始。

• ### codeforces415D. Glad to see you!

交互库会返回\$|x - a| <= |y - b| ? "TAK" : "NIE"\$

• ### cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案