地下城游戏(数组、动态规划)
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为_负整数_，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为_正整数_，则表示骑士将增加健康点数）。 为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
| -2 (K) | -3 | 3 |
|---|---|---|
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
说明:
- 骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
解答：
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length;
int col = dungeon[0].length;
int[][] dp = new int[row][col];
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i == row - 1 && j == col - 1) {
dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
} else if (i == row - 1) {
dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
} else if (j == col - 1) {
dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
} else {
dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
}
}
}
return dp[0][0];
}
}
复制题目
恢复二叉搜索树(树、深度优先搜索)
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。 **进阶：**使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示：
- 树上节点的数目在范围 [2, 1000] 内
- -231 <= Node.val <= 231 - 1
解答：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
TreeNode t1, t2, pre;
public void recoverTree(TreeNode root) {
inorder(root);
int temp = t1.val;
t1.val = t2.val;
t2.val = temp;
}
public void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
if (pre != null && pre.val > root.val) {
if (t1 == null)
t1 = pre;
t2 = root;
}
pre = root;
inorder(root.right);
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????