分治算法

1. 分治算法介绍

  1. 分治法是一种很重要的算法。在计算机科学中，分治法是构建基于多项分支递归的一种很重要的算法范式。
  2. 字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
  3. 这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
  4. image-20201009205519913
  5. 但在这广义之下，所有使用递归或循环的算法均被视作“分治算法”。

1.1 分治算法可以求解的一些经典问题

  1. 二分搜索
  2. 大整数乘法
  3. 棋盘覆盖
  4. 合并排序
  5. 快速排序
  6. 线性时间选择
  7. 最接近点对问题
  8. 循环赛日程表
  9. 汉诺塔

1.2 分治法在每一层递归上都有三个步骤

  1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
  2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
  3. 合并：将各个子问题的解合并为原问题的解。。

2. 分治算法最佳实践-汉诺塔

2.1 汉诺塔的传说

汉诺塔：

  • 汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。
  • 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
  • 假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

2.2 汉诺塔游戏的演示和思路分析

  1. 如果是有一个盘， A->C
    • 如果我们有 n >= 2 情况，我们总是可以看做是两个盘
      1. 最下边的盘
      2. 上面的盘
  2. 先把 最上面的盘 A->B
  3. 把最下边的盘 A->C
  4. 把 B 塔的所有盘 从 B->C

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Hanoitower {

    /**
    * 用来计数
    */
	public static int count = 1;
    
	public static void main(String[] args) {
		hanoitower(25,'A','B','C');
		System.out.println("执行了"+count+"次");
		
	}

	/*
	 * 	汉诺塔的移动方法--分治算法
	 * @param num
	 * @param a
	 * @param b
	 * @param c
	 */
	public static void hanoitower(int num,char a,char b,char c) {
        
		// 如果只有一个盘，直接从A柱移动到C柱
		if(num == 1) {
            
			System.out.println("第1个盘从 "+ a +" --> " + c);
			
			// 如果我们有 n >= 2 情况，我们总是可以看做是两个盘
			//	1.最下边的一个盘 
			//	2.上面的所有盘
		}else {
			
			// 先把最上面的所有盘 A->B， 移动过程会使用到 c
			hanoitower(num-1, a, c, b);
			
			count++;
			
			//	把最下边的盘A->C
			System.out.println("第"+num+"个盘从"+ a + " --> "+c);
			
			//	把B塔的所有盘从 B->C,移动过程使用到 a 塔
			hanoitower(num-1, b, a, c);
		}
        
	}
	
}

3. leetCode–面试题 08.06. 汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:

  1. 每次只能移动一个盘子;
  2. 盘子只能从柱子顶端滑出移到下一根柱子;
  3. 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。你需要原地修改栈。

  • 示例1:

    1
    2
    输入：A = [2, 1, 0], B = [], C = []
    输出：C = [2, 1, 0]

  • 示例2:

    1
    2
    输入：A = [1, 0], B = [], C = []
    输出：C = [1, 0]

  • 提示：A中盘子的数目不大于14个。

3.1 代码实现

List接口的remove方法：

E remove(int index) 删除该列表中指定位置的元素（可选操作）。
boolean remove(Object o) 从列表中删除指定元素的第一个出现（如果存在）（可选操作）。
boolean removeAll(Collection<?> c) 从此列表中删除包含在指定集合中的所有元素（可选操作）。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        moveHanota(A.size(),A,B,C);
    }

    void moveHanota(int num,List<Integer> A, List<Integer> B, List<Integer> C){
        if(num == 1){
            // 将A柱中最上面的盘子移动到C柱上
            C.add(A.remove(A.size()-1));
            return;
        }
        
        // 先把上面的部分移动到 B
        moveHanota(num-1,A,C,B);
        
        // 再把最下面的一个移动到 C
        C.add(A.remove(A.size()-1));
        
        // 最后把B那一坨移动到 C,再经历以上步骤
        moveHanota(num-1,B,A,C);
    }
}

3.2 结果分析

  1. 执行用时：1 ms, 在所有 Java 提交中击败了84.48%的用户
  2. 内存消耗：37.6 MB, 在所有 Java 提交中击败了23.21%的用户

☆