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);
}
}