1. 地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
说明:
- 骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
出处：
https://edu.csdn.net/practice/24744062
代码：
import java.util.Scanner; public class calculateMinimumHP { public static 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]; } } public static void main(String[] args) { Solution s = new Solution(); int[][] nums = {{-2,-3,3},{-5,-10,1},{10,30,-5}}; System.out.println(s.calculateMinimumHP(nums)); } }
输出：
7
2. 汇总区间
给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b" ，如果 a != b
"a" ，如果 a == b
示例 1：
输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2：
输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
示例 3：
输入：nums = []
输出：[]
示例 4：
输入：nums = [-1]
输出：["-1"]
示例 5：
输入：nums = [0]
输出：["0"]
提示：
0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列
出处：
https://edu.csdn.net/practice/24744063
代码1： 原题代码（双指针）
import java.util.*; public class summaryRanges { public static class Solution { public List<String> summaryRanges(int[] nums) { List<String> list = new ArrayList<>(); int pre = 0; int next = 0; for (int i = 0; i < nums.length; i++) { if (i + 1 < nums.length && nums[i + 1] - nums[i] == 1) { next = i + 1; } else { if (next < i) next = i; if (pre != next) { list.add(nums[pre] + "->" + nums[next]); pre = i + 1; } if (pre == next) { list.add(nums[pre] + ""); pre = i + 1; } } } return list; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {0,1,2,4,5,7}; System.out.println(s.summaryRanges(nums)); int[] nums2 = {0,2,3,4,6,8,9}; System.out.println(s.summaryRanges(nums2)); } }
代码2： 双指针
import java.util.*; public class summaryRanges { public static class Solution { public List<String> summaryRanges(int[] nums) { List<String> res = new ArrayList<>(); if (nums == null || nums.length == 0) { return res; } int start = nums[0]; // 记录区间起点 int end = nums[0]; // 记录区间终点 for (int i = 1; i < nums.length; i++) { if (nums[i] != end + 1) { // 区间中断 if (start == end) { // 区间只有一个数字 res.add(String.valueOf(start)); } else { // 区间有多个数字 res.add(start + "->" + end); } start = nums[i]; // 更新区间起点 } end = nums[i]; // 更新区间终点 } // 循环完毕，最后一个区间还没有加入 if (start == end) { res.add(String.valueOf(start)); } else { res.add(start + "->" + end); } return res; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {0,1,2,4,5,7}; System.out.println(s.summaryRanges(nums)); int[] nums2 = {0,2,3,4,6,8,9}; System.out.println(s.summaryRanges(nums2)); } }
代码3： 暴力枚举
import java.util.*; public class summaryRanges { public static class Solution { public List<String> summaryRanges(int[] nums) { List<String> res = new ArrayList<>(); if (nums == null || nums.length == 0) { return res; } int start = nums[0]; // 记录区间起点 for (int i = 1; i <= nums.length; i++) { if (i == nums.length || nums[i] != nums[i - 1] + 1) { // 区间中断 if (start == nums[i - 1]) { // 区间只有一个数字 res.add(String.valueOf(start)); } else { // 区间有多个数字 res.add(start + "->" + nums[i - 1]); } if (i < nums.length) { // 更新区间起点 start = nums[i]; } } } return res; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {0,1,2,4,5,7}; System.out.println(s.summaryRanges(nums)); int[] nums2 = {0,2,3,4,6,8,9}; System.out.println(s.summaryRanges(nums2)); } }
输出：
[0->2, 4->5, 7]
[0, 2->4, 6, 8->9]
3. 寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
进阶：
这道题是 寻找旋转排序数组中的最小值的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
出处：
https://edu.csdn.net/practice/24744064
代码：
import java.util.*; public class findMin { public static class Solution { public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else if (nums[mid] < nums[right]) right = mid; else right--; } return nums[left]; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {1,3,5}; System.out.println(s.findMin(nums)); int[] nums2 = {2,2,2,0,1}; System.out.println(s.findMin(nums2)); } }
输出：
1
0
二分法中：
mid = (left + right) / 2; 存在相加后溢出可能，尽量要写成：
mid = left + (right - left) / 2;
