LeetCode67--跳水板、汉诺塔问题

1.跳水板

//你正在使用一堆木板建造跳水板。有两种类型的木板,其中长度较短的木板长度为shorter,长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方
//法,生成跳水板所有可能的长度。 
//
// 返回的长度需要从小到大排列。 
//
// 示例 1 
//
// 输入:
//shorter = 1
//longer = 2
//k = 3
//输出: [3,4,5,6]
//解释:
//可以使用 3 次 shorter,得到结果 3;使用 2 次 shorter 和 1 次 longer,得到结果 4 。以此类推,得到最终结果。 
//
// 提示: 
//
// 
// 0 < shorter <= longer 
// 0 <= k <= 100000 
// 
// Related Topics 递归 记忆化

 这个问题很容易让人想到原先做过的爬楼梯的问题,但是爬楼梯是固定了楼梯的阶数,而这个没有,只是要求遍历所有跳水板的长度。所以我们可以不采用递归的思想,将所有可能出现的长度组合进行遍历即可。

public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        if (shorter == longer) {
            return new int[]{shorter * k};
        }
        int[] lengths = new int[k + 1];
        for (int i = 0; i <= k; i++) {
            lengths[i] = shorter * (k - i) + longer * i;
        }
        return lengths;
    }

2.汉诺塔问题

//在经典汉诺塔问题中,有 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]
// 
//
// 提示: 
//
// 
// A中盘子的数目不大于14个。 
// 
// Related Topics 递归

汉诺塔问题是一个比较经典的递归问题,想要将A上的n个圆盘都移动到C上,那么我们可以先将A上的n-1个圆盘都移动到B上,然后将第n块圆盘移动到C上,再将B上的n-1个圆盘移动到C上。那么如何将A上的n-1个圆盘移动到B上,我们可以先将n-2块圆盘移动到C上,然后再将第n-1个圆盘移动到 B上。再将C上的圆盘移动到B上。依次类推,最后问题就被简化为一个圆盘的问题,所以我们只需要写好递归,剩下的就交给计算机了。

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }
    //先将A上面的n-1个盘子移动到B
    //然后再将A上面第n个盘子移动到C
    //然后再将B上的n-1个盘子移动到C
    private void move(int n, List<Integer> A, List<Integer> B, List<Integer> C){
        if(n == 1){
            C.add(A.remove(A.size()-1));
            return;
        }
        move(n-1, A, C, B);
        C.add(A.remove(A.size()-1));
        move(n-1, B, A, C);
    }
}

 

上一篇:linux – 超级线程cpu的/ proc / cpuinfo中“cpu MHz”字段是什么意思?


下一篇:1029-