367. 有效的完全平方数
题目链接
标签
数学 二分查找
暴力
思路
暴力的思路就是 穷举可能为 num 的平方根的数：从 1 1 1 到 n u m \sqrt{num} num ，如果没有一个数是 num 的平方根，则说明 num 不是有效的完全平方数。
由于本题不让使用 sqrt()，所以每次枚举一个正整数 x，如果它的平方 square 小于 num，则继续枚举，直到它的平方 square 大于或等于 num 才退出枚举，如果最终的 square 等于 num，则说明 num 是有效的完全平方数。
代码
class Solution {
public boolean isPerfectSquare(int num) {
long x = 1, square = 1;
while (square < num) {
x++;
square = x * x;
}
return square == num;
}
}
二分查找
思路
既然可以 枚举 (枚举可能是 num 的平方根的数)，并且是在 有限的枚举区间 (区间为 [1, num]) 内枚举，则可以使用 二分枚举答案 的思路来解决本题，枚举的值就是 mid：
- 如果 枚举值
mid的平方 大于num，则 缩小 枚举的值。 - 如果 枚举值
mid的平方 小于num，则 扩大 枚举的值。 - 如果 枚举值
mid的平方 等于num，则返回true；
代码
class Solution {
public boolean isPerfectSquare(int num) {
long left = 1, right = num;
while (left <= right) {
long mid = left + (right - left >> 1); // 枚举 可能是 num平方根 的值
long square = mid * mid; // 计算 mid 的平方
if (num < square) { // 如果 num 小于 mid 的平方
right = mid - 1; // 则 缩小 枚举的值
} else if (num > square) { // 如果 num 大于 mid 的平方
left = mid + 1; // 则 扩大 枚举的值
} else { // 如果 num 等于 mid 的平方
return true; // 返回 true
}
}
return false;
}
}
56. 合并区间
题目链接
标签
数组 排序
思路
先对每个区间进行 排序，左端点值小的放在前面。然后对这些区间进行合并，对于一个区间，有如下的条件分支：
- 如果该区间与前一个区间 不重叠，则将该区间加入到结果集合中。
- 否则该区间与前一个区间 重叠，将该区间合并到前一个区间中，合并后前一个区间的左、右端点分别如下：
- 右端点：将 前一个区间的右端点 更新为 这两个区间右端点的较大值。
- 左端点：由于当前区间的左端点一定大于前一个区间的左端点(因为经过排序)，所以 前一个区间的左端点 保持不变 。
在 Java 中，可以使用 Arrays.sort() 方法进行排序，即有 Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);（此处使用了 l a m b d a lambda lambda 表达式简化内部类的编写）。但是这样的性能不是很高（因为调用 Arrays.sort() 这个操作花费了一部分时间），执行时间大约为 7 m s 7ms 7ms，可以自己实现一个排序的方法，如果对快速排序不了解，可以先看看这篇文章快速排序。
简要描述一下快速排序的思想：取基准元素，将小于基准元素的元素放到区间左边，大于基准元素的元素放到区间右边，然后交换基准元素和最后一个小于基准元素的元素。至此，基准元素左边都是小于基准元素的元素，基准元素右边都是大于基准元素的元素，对基准元素左边的区间和右边的区间分别再进行这样的操作，直到区间长度为负数。
代码
class Solution {
public int[][] merge(int[][] intervals) {
// 如果intervals为空，则返回空数组
if (intervals.length == 0) {
return new int[0][2];
}
// 按区间左端点的大小进行排序
quickSort(intervals, 0, intervals.length - 1);
// 对区间进行合并
List<int[]> res = new ArrayList<>();
res.add(new int[]{intervals[0][0], intervals[0][1]}); // 先把第一个区间添加到res中
for (int i = 1; i < intervals.length; i++) { // 从第二个区间开始循环
int left = intervals[i][0]; // 该区间的左端点
int right = intervals[i][1]; // 该区间的右端点
int[] prev = res.get(res.size() - 1); // 获取前一个区间
if (prev[1] < left) { // 若 前一个区间的右端点 小于 该区间的左端点，即两个区间不重叠
res.add(new int[]{left, right}); // 则将该区间加入到结果集合中
} else { // 否则 两个区间重叠，将该区间合并到前一个区间中
// 区间的左端点保持不变
prev[1] = Math.max(prev[1], right); // 右端点取 原右端点 和 现右端点 的最大值
}
}
// 返回一个二维数组
return res.toArray(new int[res.size()][]);
}
// 针对二维数组intervals的快速排序
private void quickSort(int[][] intervals, int left, int right) {
if (left > right) { // 如果没有待排序的区间
return; // 则退出排序
}
int p = intervals[left][0]; // 取 第一个区间的左端点 作为 基准元素
int i = left;
int j = right;
// 分区
while (i < j) {
// 获取左端点大于 p 的区间的索引
while (p <= intervals[j][0] && i < j) {
j--;
}
// 获取左端点小于 p 的区间的索引
while (p >= intervals[i][0] && i < j) {
i++;
}
// 将 左端点小于 p 的区间 放在左边，将 左端点大于 p 的区间 放在右边
int[] temp = intervals[j];
intervals[j] = intervals[i];
intervals[i] = temp;
}
// i 最终指向 最后一个左端点小于 p 的区间，将 基准元素所在区间 与 i指向的区间 交换位置
int[] arr = intervals[left];
intervals[left] = intervals[i];
intervals[i] = arr;
// 对 p 左边的区间们 进行分区
quickSort(intervals, left, j - 1);
// 对 p 右边的区间们 进行分区
quickSort(intervals, j + 1, right);
}
}
22. 括号生成
题目链接
标签
字符串 动态规划 回溯
思路
本题可以使用 深度优先搜索 的思想，不过，本题搜索的规则有些复杂：
- 当 左括号数 等于 右括号数 时，由于 左右括号需要闭合，即右括号左边一定得有和它配对的左括号，所以该情况下 只能添加左括号。
- 当 左括号数 大于 右括号数 时 (不可能存在左括号数小于右括号数的情况，因为当左括号数和右括号数相等时，永远先添加左括号)，添加左括号还是添加右括号都可以，根据左括号的数量又分成两种情况：
- 当 左括号数 不够
n个时，先添加左括号，然后再添加右括号。 - 当 左括号数 够
n个时，直接添加右括号。
- 当 左括号数 不够
搜索步骤如下：
- 判断左括号和右括号是否都够
n个，如果都够，则代表左、右括号都拼接够了，将拼接的字符串加入结果集合中，然后返回；否则就进行拼接下列操作。 - 按照拼接的规则拼接括号。
- 搜索下一个括号。
- 将本次拼接的括号移除。
代码
class Solution {
public List<String> generateParenthesis(int n) {
dfs(n, 0, 0);
return res;
}
private List<String> res = new ArrayList<>(); // 存储结果的集合
private StringBuilder builder = new StringBuilder(); // 拼接括号的字符串
// 搜索下一个括号，left是左括号数，right是右括号数
private void dfs(int n, int left, int right) {
if (left == n && right == n) { // 如果左、右括号都拼接够了
res.add(builder.toString()); // 则将拼接的字符串加入到结果集合中
return; // 并直接返回
}
if (left == right) { // 如果左、右括号数相同
builder.append('('); // 则添加左括号
dfs(n, left + 1, right); // 搜索下一个括号
builder.deleteCharAt(builder.length() - 1); // 移除当前添加的括号
} else { // 否则 左括号数 大于 右括号数
if (left < n) { // 如果左括号还没够n个
builder.append('('); // 则先添加左括号
dfs(n, left + 1, right); // 搜索下一个括号
builder.deleteCharAt(builder.length() - 1); // 移除当前添加的括号
}
builder.append(')'); // 接下来再添加右括号
dfs(n, left, right + 1); // 搜索下一个括号
builder.deleteCharAt(builder.length() - 1); // 移除当前添加的括号
}
}
}
