一、算法思想介绍
常用的算法包含但不限于以下几种:
- 分治: 分而治之,将问题拆解为形式相同子问题处理,然后合并为原问题解。
- 穷举: 无差别例举每一种可能解。
- 迭代: 不断用变量的旧值推出新值。
- 回溯: 按条件走,走不通就退回重新再走,回溯的核心在递归。
- 递归: 函数调用自身来处理相同逻辑。
- 贪心: 将问题拆解为子问题来处理,每一步都先考虑当前最优(贪心)选择。
- 动态规划:将问题拆解为子问题来处理,整体问题的最优解依赖各个子问题的最优解,自下而上求解,需要记录之前的所有局部最优解。
二、经典案例分析
1)二分查找 (分治)
题干:在一个有序数组中,在不增加空间复杂度的前提下,高效查找目标数。
public static int binarySearch(int[] arr, int target, int low, int high) {
if (target < arr[low] || target > arr[high] || low > high) {
return -1;
}
int middle = (low + high) / 2;
if (target < arr[middle]) {
return binarySearch(arr, target, low, middle);
} else if (target > arr[middle]) {
return binarySearch(arr, target, middle, high);
} else {
return middle;
}
}
注:这里用了递归来简化逻辑。
2)鸡兔共笼 (穷举)
题干:一个笼子里关有鸡兔共35头,一共94只脚,笼中鸡兔各有多少只?
public static void exhaustion(int head, int foot) {
int chicken ;
int rabbit ;
for (int i = 0; i <= head; i++) {
chicken = i;
rabbit = head - i;
if (2 * chicken + 4 * rabbit == foot) {
System.out.println("chicken:" + chicken + "; rabbit:" + rabbit);
}
}
}
3)Fibonacci数列 (迭代)
题干:求Fibonacci数列:1、1、2、3、5、8、13、21、34、…… 第N位元素值
public static int iteration(int n) {
if (n == 0) {
return 0;
} else if (n == 1 || n == 2) {
return 1;
} else if (n > 2) {
return fibonacci(n - 1) + fibonacci(n - 2);
}
return -1;
}
4)八皇后问题 (回溯)
题干:将八个皇后放在棋盘上,没有任何两个皇后在同一行、同一列或者同一对角线上
static int count = 0;
static int size = 4;
public static void main(String[] args) {
LinkedList<Location> arr = new LinkedList<>();
traceBack(arr, 0, 0);
printResult(arr);
System.out.println("八皇后共有: " + count + "种摆放方式");
}
static class Location {
int x;
int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
}
public static void printResult(LinkedList<Location> arr) {
if (arr.size() == 0) {
return;
}
System.out.println("第" + (count + 1) + "种:");
for (int i = 0; i < arr.size(); i++) {
System.out.print(arr.get(i).toString() + "\t");
}
System.out.println();
count++;
}
public static void traceBack(LinkedList<Location> arr, int x, int y) {
if (arr.size() == size) {
printResult(arr);
}
for (int i = x; i < size; i++) {
Location location = new Location(i, y);
if (isOk(arr, location)) {//判断是否满足排列要求,不满足回溯到上一层 判断同行的下一列位置
arr.offer(location);//保存摆好的皇后
System.out.println("offer:" + "(" + location.x + ", " + location.y + ")");
traceBack(arr, 0, y + 1);//开始排下一行的皇后
arr.pollLast();//当前不满足条件则取消上一次摆放方案,重新摆放
System.out.println("polllast:" + "(" + location.x + ", " + location.y + ")");
}
}
}
public static boolean isOk(LinkedList<Location> arr, Location oriLocation) {
for (Location loc : arr) {
if (loc.x == oriLocation.x || loc.y == oriLocation.y) { //同行同列判断
return false;
} else if (Math.abs(loc.x - oriLocation.x) == Math.abs(loc.y - oriLocation.y)) {//斜对角线判断
return false;
}
}
return true;
}
5)剪绳子问题 (贪心与动态规划)
题干:一根长度为n的绳子,请把绳子剪成m段,最终每段绳子长度的乘积最大值是多少?例如,当绳子的长度为8时,我们剪成3,3,2三段,最大乘积是18。
动态规划解:
public static int dp(int len) {
if (len < 2)
return 0;
if (len == 2)
return 1;
if (len == 3)
return 2;
//子问题的最优解存储在arr数组中,第i个元素表示把长度为i的绳子剪成若干段后各段长度乘积的最大值
int[] arr = new int[len + 1];
//这些情况下,不剪的时候长度比剪的时候长,所以作为初始条件
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
for (int i = 4; i <= len; i++) {
int max = 0;
for (int j = 1; j <= i / 2; j++) {
//动态规划:以上一个子问题的最优解为依据来求下一个子问题的最优解
int num = arr[j] * arr[i - j];
System.out.println("i:" + i + " arr[" + j + "] * " + "arr[" + (i - j) + "]" + " " + "num:" + num);
if (max < num)
max = num;
}
arr[i] = max;
}
return arr[len];
}
贪心解:
public static int greedy(int len) {
/**
* 先找规律
* len = 1 1
*
* len = 2 1
* len = 3 2
*
* len = 4 2*2 4
* len = 5 2*3 6
* len = 6 3*3 9
* len = 7 3*2*2 12
* len = 8 3*3*2 18
* len = 9 3*3*3 27
* len = 10 3*3*2*2 36
* ...
* 从5开始,就由3和2组成,有3尽量满足3,如何最后剩余3和1则转为2*2
* 贪心:有最优解3,尽量凑成3,最后3*1 的情况特殊考虑转为2*2
*/
if (len == 1) {
return 1;
}
if (len > 1 && len < 4) {
return len - 1;
}
if (len == 4) {
return len;
}
if (len % 3 == 1) {
return (int) Math.pow(3, len / 3 - 1) * (int) Math.pow(2, 2);
} else {
return (int) Math.pow(3, len / 3) * 2;
}
}
网友评论