【多路递归】汉诺塔&杨辉三角
2024-07-28 本文已影响0人
我可能是个假开发
一、汉诺塔
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]
提示:A中盘子的数目不大于14个。
4片圆盘的移动方法：
Tower_of_Hanoi_4.gif
2.解题过程：
找规律：
一片圆盘：
- A->C
两片圆盘：
- A->B
- A->C
- B->C
三片圆盘：
- A->C
- A->B
- C->B 这一步结束之后，前两个圆盘已经从A移动到了B：A->B
- A->C 第三个从A移动到了C
- B->A
- B->C
- A->C 这一步结束之后，前两个从B移动到了C：B->C
即三片圆盘的移动方法可以简化成2片的移动方法：把前两片圆盘看做是一片圆盘：
- A->B
- A->C
- B->C
此移动方法就是2片的移动方法。
总结：两片圆盘的移动方法就是最终的移动方法，大于2片的都能拆解成2片的移动方法。
3.代码
/**
* a b c：
* 1个圆盘：
* 第1根移动到c：a->c
*
* 2个圆盘：
* 前1根移动到b：a->b 相当于1个的移法
* 第2根移动到c：a->c
* 前1根移动到c：b->c 相当于1个的移法
*
* 3个圆盘：
* 前2根移动到b：a->c a->b c->b 相当于2个的移法
* 第3根移动到c：a->c
* 前2根移动到c：b->a b->c a->c 相当于2个的移法
*
*
* 4个圆盘:
* 前3根移动到b：a->b a->c b->c a->b c->a c->b a->b 相当于3个的移法
* 第4根移动到c：a->c
* 前3根移动到c：b->c b->a c->a b->c a->b a->c b->c 相当于3个的移法
*
*/
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
remove(A.size(),A,B,C);
}
public void remove(int count,List<Integer> A, List<Integer> B, List<Integer> C){
if (count == 0) {
return;
}
remove(count - 1, A, C, B);
C.add(A.remove(A.size() - 1));
remove(count - 1, B, A, C);
}
}
递归过程：
汉诺塔递归流程.png
public void hanota(3, a, b, c){
// 开始第一行的递归流程，即左侧的树
hanota(3-1=2, a, c, b){
hanota(2-1=1, a, b, c) {
hanota(1 - 1 = 0, a, c, b) {
if (n == 0) {
return;
}
}
c.addLast(a.removeFirst()); // 1.a->c
hanota(1 - 1 = 0, b, a, c){
if (n == 0) {
return;
}
}
}
b.addLast(a.removeFirst()); // 2.a->b
hanota(2 - 1 = 1, c, a, b) {
hanota(1 - 1 = 0, c, b, a){
if (count == 0) {
return;
}
}
b.addLast(c.removeFirst()); // 3.c->b
hanota(1 - 1 = 0, a, c, b){
if (count == 0) {
return;
}
}
}
// 左侧的树执行完毕 即第一行的递归执行完毕
//======================================
c.addLast(a.removeFirst()); // 4.a->c
// 开始第三行的递归流程 即右侧的树
//======================================
hanota(3-1=2, b, a, c){
hanota(2-1=1, b, c, a){
hanota(1-1=0, b, a, c){
if (n == 0) {
return;
}
}
a.addLast(b.removeFirst()); // 5.b->a
hanota(1-1=0, c, b, a){
if (n == 0) {
return;
}
}
}
c.addLast(b.removeFirst()); // 6.b->c
hanota(2-1=1, a, b, c){
hanota(1-1=0, a, c, b){
if (n == 0) {
return;
}
}
c.addLast(a.removeFirst()); // 7.a->c
hanota(1-1=0, b, a, c){
if (n == 0) {
return;
}
}
}
}
}
二、杨辉三角
1.题目
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
PascalTriangleAnimated2.gif
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
2.题解
把杨辉三角左边对齐来看：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
从图中可以看出，已知的元素是每一行的第一个元素和最后一个元素都是1；
其余元素的结果是上一行的前两个的和：
行为i，列为j，那么任一一个元素 [i][j] = [i-1,j-1]+[i-1,j]，
其中，当j==0||i==j时，[i][j] = 1
所以，所有元素最终都可以简化为1相加的和。
3.递归解法：
/**
* 求第i行第j列元素
* @param i
* @param j
* @return
*/
public static int element(int i,int j) {
//每一行的第一个(第0列)和最后一个都是1
if (j == 0 || i == j) {
return 1;
}
return element(i - 1, j - 1) + element(i - 1, j);
}
/**
* 递归
* @param numRows
* @return
*/
public static List<List<Integer>> generateRecursion(int numRows) {
List<List<Integer>> lists = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> list = new ArrayList<>();
for (int j = 0; j <= i; j++) {
//第i行第j列元素
int element = element(i, j);
list.add(element);
}
lists.add(list);
}
return lists;
}
以上解法超出时间限制
4.递归优化：使用记忆法缓存
每次求出的元素缓存到数组中，判断当前要求的数组里是不是有了，如果有了，就直接从数组中拿出来，不用再递归计算了。
/**
* 递归优化
* @param numRows
* @return
*/
public static List<List<Integer>> generateRecursionCache(int numRows) {
List<List<Integer>> lists = new ArrayList<>();
//行初始化为numRows
int[][] arr = new int[numRows][];
for (int i = 0; i < numRows; i++) {
//i行的列初始化为i+1
arr[i] = new int[i + 1];
List<Integer> list = new ArrayList<>();
for (int j = 0; j <= i; j++) {
//第i行第j列元素
int element = elementCache(i, j, arr);
list.add(element);
}
lists.add(list);
}
return lists;
}
/**
* 求第i行第j列元素 使用记忆法优化
* @param i
* @param j
* @return
*/
public static int elementCache(int i,int j,int[][] arr) {
if (arr[i][j] != 0) {
return arr[i][j];
}
//每一行的第一个(第0列)和最后一个都是1
if (j == 0 || i == j) {
arr[i][j] = 1;
return 1;
}
arr[i][j] = elementCache(i - 1, j - 1, arr) + elementCache(i - 1, j, arr);
return arr[i][j];
}
5.使用动态规划
/**
* 递归优化 使用动态规划
* @param numRows
* @return
*/
public static List<List<Integer>> generateDynamic(int numRows) {
List<List<Integer>> lists = new ArrayList<>();
//行初始化为numRows
//List<Integer> rowList = new ArrayList<>();
int[] rowArr = new int[numRows];
for (int i = 0; i < numRows; i++) {
List<Integer> list = new ArrayList<>();
//求第i行元素
dynamicElement(rowArr, i);
//这里有瑕疵 又要把数组转成List
for (int k : rowArr) {
if (k != 0) {
list.add(k);
}
}
lists.add(list);
}
return lists;
}
/**
* 计算rowNum行元素 动态规划
* @param arr 上一行的元素
* @param rowNum
* @return
*/
public static void dynamicElement(int[] arr,int rowNum) {
if (rowNum == 0) {
arr[0] = 1;
return;
}
/**
* 1 rowNum=0
* 1 1 rowNum=1
* 1 2 1 rowNum=2
* 1 3 3 1 rowNum=3 arr=4
* 1 4 6 4 1 rowNum=4
*/
//求出第n行的所有元素 原本arr[0]都是1 所以不用管
for (int i = rowNum; i > 0; i--) {
arr[i] = arr[i] + arr[i - 1];
}
}
动态规划是一种解决问题的算法思想，通常用于解决具有重叠子问题和最优子结构性质的问题。
杨辉三角的过程可以描述为动态规划的一个应用：
- 定义状态：
int[] rowArr 数组用于存储当前行的元素，它们构成了杨辉三角的一行。
lists 是一个 List<List<Integer>>，用于存储所有行的元素。 - 状态转移：
dynamicElement 方法实现了状态转移的逻辑。它从第一行开始计算，依次更新每一行的元素值，直到第 numRows 行。
在动态规划的思想中，每一行的元素可以通过上一行的元素计算得到。具体来说，每个元素的值等于它上方两个元素之和（例如第 i 行的第 j 列元素等于第 i-1 行的第 j-1 列和第 j 列元素之和）。 - 填充列表：
在 generate 方法中，通过调用 dynamicElement 方法来更新 rowArr 数组，然后将非零元素添加到 list 中，最后将 list 添加到 lists 中，完成了对杨辉三角每一行的构建。
6.迭代解法
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> lists = new ArrayList<>();
List<Integer> listFirst = new ArrayList<>();
listFirst.add(1);
lists.add(listFirst);
if (numRows == 1) {
return lists;
}
for (int i = 0; i < numRows-1; i++) { //行
List<Integer> list = new ArrayList<>();
//每一行的第一个和最后一个元素都是1
list.add(1);
if (i > 0) {
//当前下标1元素来源于上一行的下标0和下标1的和 这里的循环是循环中间一共有多少个元素
for (int j = 0; j < i; j++) { //列
//上一行的元素 [1,2,1]
List<Integer> list1 = lists.get(lists.size() - 1);
//依次求和，0+1 1+2 2+3
list.add(list1.get(j) + list1.get(j + 1));
}
}
//当前下标2元素来源于上一行的下标1和小标2的和。
list.add(1);
lists.add(list);
}
return lists;
}
