174. 地下城游戏
恶魔们抓住了公主并将她关在了地下城
dungeon的 右下角 。地下城是由m * n个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出：7 解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。示例 2：
输入：dungeon = [[0]] 输出：1
解题思路
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出：7 解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2：
输入：dungeon = [[0]] 输出：1
完整代码
Python
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
dp[m][n - 1] = dp[m - 1][n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
min_health = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
dp[i][j] = max(1, min_health)
return dp[0][0]Java
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[m][n - 1] = dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
int minHealth = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = Math.max(1, minHealth);
}
}
return dp[0][0];
}
}189. 轮转数组
给定一个整数数组
nums，将数组中的元素向右轮转k个位置，其中k是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出:[5,6,7,1,2,3,4]解释: 向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]示例 2:
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
解题思路
解决这个问题的关键在于找到一种高效的方法来旋转数组，而不仅仅是简单地执行 k 次单步旋转。一种有效的方法是通过反转数组的部分来实现旋转效果。具体步骤如下：
-
反转整个数组：首先，将整个数组反转。这一步会将原本应该被移动到数组前面的元素移动到数组的后面。
-
反转数组的前
k个元素：接着，反转数组中前k个元素。由于数组已经被整体反转过，这一步实际上是将那些应该位于数组前面的元素放到了正确的位置。 -
反转数组剩余部分：最后，反转数组中剩余的部分，即从索引
k到数组结束的部分。这一步是将剩余的元素放到它们应该在的位置。
注意 由于 k 可能大于数组的长度，所以在进行操作之前需要将 k 对数组长度取模，以确保 k 在数组长度范围内。
完整代码
Python
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
def reverse(start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start, end = start + 1, end - 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)Java
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解题思路
这个问题可以通过动态规划（Dynamic Programming, DP）来解决。我们可以定义一个一维数组 dp，其中 dp[i] 表示到达第 i 个房屋时能偷窃到的最高金额，注意这里的 i 是从 0 开始的索引。
解题步骤如下：
-
基本情况：当只有一间房屋时（即数组长度为 1），那么偷窃到的最高金额就是这间房屋中的金额。所以
dp[0] = nums[0]（如果数组不为空）。 -
第二间房屋：当有两间房屋时，由于不能同时偷窃相邻的房屋，因此偷窃到的最高金额是这两间房屋中金额较大的那一个。所以
dp[1] = max(nums[0], nums[1])。 -
状态转移方程：对于第
i间房屋（i > 1），有两种选择：- 不偷窃第
i间房屋，那么最高金额为到达前一间房屋时的最高金额，即dp[i-1]； - 偷窃第
i间房屋，那么由于不能偷窃相邻的房屋，最高金额为第i-2间房屋的最高金额加上第i间房屋中的金额，即dp[i-2] + nums[i]。
因此，状态转移方程为
dp[i] = max(dp[i-1], dp[i-2] + nums[i])。 - 不偷窃第
-
结果：数组
nums中最后一个房屋的索引为nums.length - 1，所以dp[nums.length - 1]就是不触动警报装置情况下能偷窃到的最高金额。
完整代码
Python
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]Java
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[nums.length - 1];
}
}
