算法（一）-算法思想
2019-12-30 本文已影响0人
Stan_Z
一、算法思想介绍
常用的算法包含但不限于以下几种：
- 分治： 分而治之，将问题拆解为形式相同子问题处理，然后合并为原问题解。
- 穷举： 无差别例举每一种可能解。
- 迭代： 不断用变量的旧值推出新值。
- 回溯： 按条件走，走不通就退回重新再走，回溯的核心在递归。
- 递归： 函数调用自身来处理相同逻辑。
- 贪心： 将问题拆解为子问题来处理，每一步都先考虑当前最优(贪心)选择。
- 动态规划：将问题拆解为子问题来处理，整体问题的最优解依赖各个子问题的最优解，自下而上求解，需要记录之前的所有局部最优解。
二、经典案例分析
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;
}
}
