建电影网站赚钱挣钱吗,怎么用wordpress模板,网页打不开但是qq能上是怎么回事,帮人做分销网站违法么第18节
题目1#xff1a;汉诺塔问题#xff08;变体#xff09; 体系学习班18节有讲暴力递归的汉诺塔原题。 给定一个数组arr#xff0c;长度为N#xff0c;arr中的值只有1#xff0c;2#xff0c;3三种
arr[i] 1#xff0c;代表汉诺塔问题中#xff0c;从上往下第…第18节
题目1汉诺塔问题变体 体系学习班18节有讲暴力递归的汉诺塔原题。 给定一个数组arr长度为Narr中的值只有123三种
arr[i] 1代表汉诺塔问题中从上往下第i个圆盘目前在左
arr[i] 2代表汉诺塔问题中从上往下第i个圆盘目前在中
arr[i] 3代表汉诺塔问题中从上往下第i个圆盘目前在右
那么arr整体就代表汉诺塔游戏过程中的一个状况
如果这个状况不是汉诺塔最优解运动过程中的状况返回-1
如果这个状况是汉诺塔最优解运动过程中的状况返回它是第几个状况而不是还剩几个状况
思路
对于传统的汉诺塔问题如果我要将 123456 从最左边的柱子上移动到最右边的柱子上需要分成三大步
【第一大步】将 12345 从左边的柱子移动到中间的位置【第二大步】将 6 从左边的柱子移动到右边的位置【第三大步】将 12345 从中间的位置移动到右边的位置
上述传统问题的解法是定义递归函数 f(i, from, to, other)表示将 [0~i] 的圆盘从 from 柱子移动到 to 柱子上另外那个柱子叫 other。
对于本题需要明确一下题意有几个已知条件
汉诺塔问题最优解是唯一的路径。题目中给的过程状态如果不在唯一路径上就返回-1。举个极端的例子1层汉诺塔问题把1从最左边的柱子上移动到最右边的柱子上只要一步就可以了。而”1在中间这个柱子上“这个状态就是一个不在最优解路径上的例子。
本题的解法是定义递归函数int step(int[] arr, int i, int from, int to, int other)表示当前来到 arr 状态下将 [0~i] 的圆盘从 from 柱子移动到 to 柱子上另外那个柱子叫 other返回至少需要几步。
public static int kth(int[] arr) {int N arr.length;return step(arr, N - 1, 1, 3, 2);
}// 我的疑问arr为什么全程不更新
// 自问自答因为返回它当前走到了第几个状况而不是还剩几个状况。
public static int step(int[] arr, int index, int from, int to, int other) {if (index -1) {return 0;}if (arr[index] other) { // 最大的数字只可能在from或者to的底部不可能在other上return -1;}// arr[index]的值剩下两种情况// 情况1arr[index] from// 情况2arr[index] toif (arr[index] from) { // 情况1如果index号圆盘还在from上说明上述连【第一大步】都没走完// 因为我只想知道当前已经走过多少步了所以只要统计在【第一大步】中走了多少步就可以了后面的【第二大步】【第三大步】肯定根本没走// 怎么统计呢我们知道【第一大步】的目标是将[0~i-1]从from挪到other上而且当前已经走到arr状态了所以就这样继续递归return step(arr, index - 1, from, other, to);} else { // 情况2如果index号圆盘已经在to上了说明已经完成[0~index-1]的汉诺塔问题了// 【第一大步】已经完成的从[0~index-1]范围上的index层汉诺塔问题需要的步骤数n层汉诺塔最优解2^n-1步int p1 (1 index) - 1; // 【第二大步】已经将index号圆盘从from挪到to了因为我们从arr中看到index号圆盘已经在to上了int p2 1; // 【第三大步】当前正在经历的将[0~i-1]号圆盘从other挪到to上在arr状态下统计已经走过多少步了int p3 step(arr, index - 1, other, to, from); // 如果发现它的子问题根本就不是最优解的某一步直接返回-1if (p3 -1) { return -1;}return p1 p2 p3;}
}题目2两个岛屿的距离“感染”问题
Leetcode 原题
https://leetcode.com/problems/shortest-bridge/
我在力扣上的自己写的答案
class Solution {int m, n;public static final int offset 100;public int shortestBridge(int[][] grid) {m grid.length;n grid[0].length;// 将其中一个岛A加offset用来区分两个岛label:for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {incr(grid, i, j);break label; // 中断所有循环回到label处但并不重新进入循环}}}// 左上角主动感染右下角原地不动int term offset;while (true) {boolean[][] seen new boolean[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] term !seen[i][j]) {int result process(grid, i, j, term, seen);if (result ! Integer.MAX_VALUE) return result - offset;}}}term;}}// 当前岛屿向外感染public int process(int[][] grid, int i, int j, int term, boolean[][] seen) {int result Integer.MAX_VALUE;if (i 0 || i m || j 0 || j n || seen[i][j]) return result; // 越界或重复路线seen[i][j] true;if (grid[i][j] 0) { // 当前位置未感染则感染grid[i][j] term 1;} else if (grid[i][j] term) { // 当前位置是感染源则去感染周围result Math.min(result, process(grid, i 1, j, term, seen));result Math.min(result, process(grid, i - 1, j, term, seen));result Math.min(result, process(grid, i, j 1, term, seen));result Math.min(result, process(grid, i, j - 1, term, seen));} else if (grid[i][j] 1) { // 两岛接壤则快速返回return term;}return result;}// 给其中一个岛加offsetpublic void incr(int[][] grid, int i, int j) {if (i 0 || i m || j 0 || j n) return;if (grid[i][j] 1) {grid[i][j] offset;incr(grid, i 1, j);incr(grid, i - 1, j);incr(grid, i, j 1);incr(grid, i, j - 1);}}
}题目3最大路径和
牛客网原题
https://www.nowcoder.com/questionTerminal/8ecfe02124674e908b2aae65aad4efdf
给定一个矩阵matrix先从左上角开始每一步只能往右或者往下走走到右下角。然后从右下角出发每一步只能往上或者往左走再回到左上角。任何一个位置的数字只能获得一遍。返回最大路径和。
输入描述
第一行输入两个整数M和NM,N200
接下来M行每行N个整数表示矩阵中元素5 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1输出描述
输出一个整数表示最大路径和16思路 第一次见到这题是在体系学习班第14节。当时只讲了不能贪心应该用dp但没有细说。 黄色部分表示我想要拿到的位置 错误的贪心路径
少拿一个灰色的格子。
正确的路径
最好情况下能够拿到所有的格子。 虽然题目要求是一来一回但我们可以想象成有两个人 a、b都从左上角走到右下角求整个过程中最多能拿到多少值。
内存超限版本如下。其实可以省掉一个维度就不会超了因为(i1, j1), (i2, j2) 两个坐标中存在关系i1j1i2j2。可变参数数量能省则省
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static int[][] arr;public static void main(String[] args) {Scanner in new Scanner(System.in);int m in.nextInt();int n in.nextInt();arr new int[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {arr[i][j] in.nextInt();}}int[][][][] dp new int[m][n][m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {for (int k 0; k m; k) {for (int l 0; l n; l) {dp[i][j][k][l] -1;}}}}int res process(0, 0, 0, 0, dp);System.out.println(res);}// 当前a在i1,j1位置b在i2,j2位置// 两个人都只能向右走或者向下走求能拿到的最多点数public static int process(int i1, int j1, int i2, int j2, int[][][][] dp) {if (i1 arr.length || j1 arr[0].length) return 0;if (i2 arr.length || j2 arr[0].length) return 0;if (dp[i1][j1][i2][j2] 0) return dp[i1][j1][i2][j2];// a,b如果走到了同一个位置点数只能累加一次int res arr[i1][j1];if (i1 ! i2 j1 ! j2) res arr[i2][j2];// a向右b向右int p1 process(i1 1, j1, i2 1, j2, dp);// a向下b向下int p2 process(i1, j1 1, i2, j2 1, dp);// a向右b向下int p3 process(i1, j1 1, i2 1, j2, dp);// a向下b向右int p4 process(i1 1, j1, i2, j2 1, dp);res Math.max(Math.max(p1, p2), Math.max(p3, p4));dp[i1][j1][i2][j2] res;return res;}
}
/*5 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 12 2
1 1
1 1*/题目4
牛客网原题
https://www.nowcoder.com/practice/7201cacf73e7495aa5f88b223bbbf6d1
给定两个有序数组arr1和arr2再给定一个整数k你可以从来自arr1和arr2的两个数各选一个数返回相加和最大的前k个。
思路
不能用双指针从最右边开始往左滑动因为这样会丢失本来可以重复使用的数字。
正确的方法是用大根堆。
当从大根堆拿走一个元素之后将表格中在它左边和上边的元素加入大根堆。
