LeetCode 153, 452, 131
153. 寻找旋转排序数组中的最小值
题目链接
标签
数组 二分查找
思路
题目中描述的“旋转”在大气层，我选择这样理解“旋转”(平移)：将原数组向右移动了不知多少个单位，把移除数组的元素按照原先的升序放置到数组的头部。例如对于原数组 [0,1,2,4,5,6,7]，它“旋转”4次 (右移4个单位) 得到的结果为 [4,5,6,7,0,1,2]。
对于“旋转”后的数组，将数组平均分成两部分，如果发现 nums[mid] < nums[right]，则说明 右子区间是有序的，从而左子区间是无序的，也就是说，左子区间的前半段和后半段都是升序的，只不过出现了断层，数组的最小值就在断层处，所以这种情况 在左子区间查找 最小值。例如下图的情况：
否则 右子区间是无序的，也就是说，右子区间的前半段和后半段都是升序的，只不过出现了断层，数组的最小值就在断层处，所以这种情况 在右子区间查找 最小值。例如下图的情况：
代码
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left >> 1);
if (nums[mid] < nums[right]) { // 右子区间有序，最小值在左子区间中
right = mid; // 在左子区间查找
} else { // 左子区间有序，最小值在右子区间中
left = mid + 1; // 在右子区间查找
}
}
return nums[left];
}
}
452. 用最少数量的箭引爆气球
题目链接
标签
贪心 数组 排序
思路
本题的目标是 用最少数量的箭引爆气球 (全局最优)，可以使用 贪心 的思想，对于 一支箭，它能引爆的气球数 越多越好，所以应该 在重叠气球最多的坐标射箭 (局部最优)。
让气球尽量重叠，就需要对气球排序，此处按 气球右端点大小升序排序，然后开始射箭：
- 第一支箭射到第一个气球的 右端点 处。
- 对于之后的气球，先看上一支箭是否能将这个气球引爆，如果能引爆，则不需要再射箭；否则在这个气球的 右端点 处射一支箭。直到将全部气球都引爆。
为什么要在气球的右端点处射箭？这是因为 按右端点升序排序后，越靠右，重叠的气球数量越多，从而使用更少的箭。
代码
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) { // 如果 points 中没有元素
return 0; // 则不需要射箭，返回 0
}
Arrays.sort(points, (p1, p2) -> Integer.compare(p1[1], p2[1])); // 将 气球 按照 右端点 升序排列
int pos = points[0][1]; // 射箭的位置，一开始在 第一个气球的右端点 处射箭
int res = 1; // 射箭数
for (int[] balloon : points) { // 取出每个气球
if (balloon[0] <= pos) { // 如果这个气球能被上一支箭引爆
continue; // 则不需要再射一支箭
}
// 这个气球不能被上一支箭引爆，需要再射一支箭
pos = balloon[1]; // 这次的箭在 这个气球的右端点 处射
res++; // 射箭数 + 1
}
return res;
}
}
131. 分割回文串
题目链接
标签
字符串 动态规划 回溯
思路
本题可以采用 回溯 的思路来解决，以字符串 s 的某一个字符作为 起始字符，操作的步骤如下：
- 如果 起始字符 的索引超出了
s的长度，则说明已经把s分割为一个个回文串了，此时将已分割的回文串作为一个集合放到结果集合中；否则就继续寻找 以 起始字符开头的 回文串。 - 在 起始字符 到 字符串
s的最后一个字符中，枚举 终止字符，如果 从起始字符到终止字符 组成的字符串 不是回文串，跳过它；直到找到 回文串。 - 将找到的回文串加入到已分割回文串集合中。
- 寻找下一个回文串，递归调用。
- 将这个回文串从已分割回文串集合中移除。
回溯 的思路并不复杂，可以发现其中的 判断一个字符串是否是回文串 的操作非常多，这时就不能用简单的判断回文串思路了（简单思路指的是：使用双指针，左指针从头开始顺序遍历，右指针从尾开始逆序遍历，如果左右指针指向的字符不相同，则不是回文串。当左右指针相遇后，字符串就是回文串）。
实际上，这里判断的字符串大多都是 有联系 的，可以采用 记忆化搜索 的方式来简化判断：
- 记忆 就是记录 是否是回文串 的结果，因为 字符串 由 起始字符 和 终止字符 的索引来决定，所以得使用二维数组。例如
status[left][right]就代表 以left作为起始字符索引、以right作为终止字符索引 的字符串是否是回文串。 - 一般来说，记忆有三种状态：是、不确定、否。只有当记忆的状态为不确定时，才需要进行 递归地 判断，其他状态都可以直接返回。
代码
class Solution {
public List<List<String>> partition(String s) {
n = s.length();
status = new int[n][n];
dfs(s, 0);
return res;
}
private List<List<String>> res = new ArrayList<>(); // 存储结果的集合
private List<String> split = new ArrayList<>(); // 已分割回文串集合
private int n; // 字符串 s 的长度
/**
* 该二维数组存放了 以行数作为起始字符索引、以列数作为终止字符索引 的字符串的三种状态
* 状态：-1(不是回文串) 0(不确定) 1(是回文串)
*/
private int[][] status;
private void dfs(String s, int left) {
if (left == n) { // 如果 起始字符 取完了 s 的全部字符，则本次分割的字符串都是回文串
res.add(new ArrayList<>(split)); // 将本次分割的字符串作为一个集合加入结果集合中
return; // 直接返回
}
for (int right = left; right < n; right++) { // 枚举 终止字符的索引
if (isPalindrome(s, left, right) != 1) { // 如果 分割的字符串 不是 回文串
continue; // 则跳过这个终止字符
}
// 否则 分割的字符串 是 回文串
split.add(s.substring(left, right + 1)); // 将 分割的字符串 加入到 答案集合 中
dfs(s, right + 1); // 搜索下一个回文串
split.remove(split.size() - 1); // 将 分割的字符串 从 答案集合 中移除
}
}
// 返回 以left为起始字符索引、以right为终止字符索引 的字符串 的状态，如果是 1，则代表它是回文串
private int isPalindrome(String s, int left, int right) {
if (status[left][right] != 0) { // 如果它的状态已确定
return status[left][right]; // 则直接返回它的状态
}
// 否则需要判断它的状态
if (left >= right) { // 如果 起始字符索引 大于或等于 终止字符索引
status[left][right] = 1; // 则 是回文串
} else if (s.charAt(left) == s.charAt(right)) { // 如果 起始字符 与 终止字符 相等
// 则 继续判断 起始字符的下一个字符 和 终止字符的上一个字符 是否相等，并将结果赋值给 二维数组中的当前元素
status[left][right] = isPalindrome(s, left + 1, right - 1);
} else { // 否则 起始字符 与 终止字符 不相等
status[left][right] = -1; // 不是回文串
}
return status[left][right]; // 返回 状态的值
}
}
原文地址：https://blog.csdn.net/qq_61350148/article/details/140429500
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！