Leetcode.汉诺塔问题

1.题目

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

请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

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

示例2:

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

2.解答

汉诺塔问题是递归的经典使用,刚开始接触递归就是这个问题,汉诺塔如果手动自己解开的话实在太难了,但是借助算法,就可以使用递归轻松解开。

例如将A中的五个元素全部移动到C中,那么首先将把4个元素移动到B中,在把A中最下面的元素移动到C中,也就是按照顺序最大的那个,然后再把其他B上的四个元素移动到C上,那么话说回来,怎么把A上面的四个移动到B上呢,这里就使用到了递归,一直缩减数目,直到简化为移动一个元素的时候。

class Solution {
    Stack<Integer> stackA;
    Stack<Integer> stackB;
    Stack<Integer> stackC;
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        stackA = new Stack<>();
        stackB = new Stack<>();
        stackC = new Stack<>();
        for(int i = 0;i < A.size();i++){
            stackA.push(A.get(i));
        }
        helper(A.size(),stackA,stackB,stackC);
        ArrayList<Integer> temp = new ArrayList<>();
        while(!stackC.isEmpty()){
            temp.add(stackC.pop());
        }
        for(int i = temp.size()-1;i >= 0;i--){
            C.add(temp.get(i));
        }
    }
    //n表示要移动盘子的数量,ABC的顺序表示从A移动到C
        private void helper(int n,Stack<Integer> stackA,
         Stack<Integer> stackB, Stack<Integer> stackC){
             if(n == 1){
                 stackC.push(stackA.pop());
                 return;
             }
             helper(n-1,stackA,stackC,stackB);
             stackC.push(stackA.pop());
             helper(n-1,stackB,stackA,stackC);
    }
}

在hanota函数的处理中,因为顺序的问题,增加了一个temp数组进行栈顺序的摆正,增加了空间,代码行数也变多了,但是还没有想到其他方法

在多个栈帧里面共同使用的方法直接定义在类里面,在堆里面进行分配。

读题的时候不能眼瞎

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode汉诺塔问题md