目录
852. 山脉数组的峰顶索引
题目链接
标签
数组 二分查找
二分
思路
本题的 arr 是 先递增，后递减 的，共有如下两种情况：
对于第一种情况：中间值的前一个值 大于 中间值，可以发现：最大值在左子区间上。
对于第二种情况：中间值的前一个值 小于 中间值，可以发现：最大值在右子区间上。
代码
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left + 1 >> 1); // 中间值的索引
if (arr[mid - 1] < arr[mid]) { // 中间值的前一个值 小于 中间值
left = mid; // 最大值在右子区间上
} else { // 中间值的前一个值 大于 中间值
right = mid - 1; // 最大值在左子区间上
}
}
return left;
}
}
三分
思路
寻找峰值是 三分 的经典用法，三分 与 二分 类似，都是将区间平均分，不过 三分 把区间分成 三份，比较 左三等分点 和 右三等分点 指向的值 的大小，从而决定选择查找哪个区间。
当 左三等分点指向的值 小于 右三等分指向的值 时，说明 最大值点在右边的 2 3 \frac{2}{3} 32 区间。
当 左三等分点指向的值 大于 右三等分指向的值 时，说明 最大值点在左边的 2 3 \frac{2}{3} 32 区间。
代码
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int midL = left + (right - left) / 3, midR = right - (right - left) / 3;
if (arr[midL] < arr[midR]) { // 左三等分点指向的值 小于 右三等分指向的值
left = midL + 1; // 最大值点在右边的 2/3 区间
} else { // 左三等分点指向的值 大于 右三等分指向的值
right = midR - 1; // 最大值点在左边的 2/3 区间
}
}
return left;
}
}
20. 有效的括号
题目链接
标签
栈 字符串
思路
有效字符串需满足：
- 左括号必须用 相同类型 的右括号闭合。
- 左括号必须以 正确的顺序 闭合。这就说明
"[(])"不是有效字符串，而"([])"是有效字符串。 - 每个 右括号都有一个对应的相同类型的左括号。
注意有效字符串的以上三个条件，尤其是第二个条件。由 "[(])" 不是有效字符串可知：对于一个右括号，它要匹配它前面的最后一个左括号。由 "([])" 是有效字符串可知：被右括号成功匹配之后的左括号可以视而不见。
这样的判断驱使着我们使用 栈 这种数据结构来存储左括号，对于字符串 s 中的每一个字符 ch (顺序遍历)，有以下的操作：
- 如果
ch是左括号，直接将其放入栈中。 - 如果
ch是右括号，判断栈顶元素 (这里的栈顶元素就是ch前面的最后一个左括号) 是否能与ch匹配，如果不能，则返回false；否则将匹配成功的左括号 (即栈顶元素) 弹出栈，并继续遍历下一个字符。 - 此外，可能会遇到 当
ch是右括号时，栈为空 的情况，例如"]", "()}"，对于第一个字符串，当ch == ']'时，栈为空；对于第二个字符串，当ch == '}'时，栈为空。此时直接返回false即可。
遍历完所有字符后，不能直接返回 true，因为此时栈可能不为空，例如对于 "[({"，栈最后还存储着三个左括号，此时应该返回 false；如果最后的栈为空，则可以放心地返回 true。
代码
class Solution {
public boolean isValid(String s) {
LinkedList<Character> stack = new LinkedList<>(); // 储存 左括号 的栈
for (char ch : s.toCharArray()) { // 从字符串 s 中拿出字符 ch 进行操作
if (ch == '(' || ch == '{' || ch == '[') { // 如果是左括号之一
stack.push(ch); // 则将其放入栈中
continue; // 不进行接下来的操作
}
// 否则 ch 是右括号，需要给它匹配相应的左括号
if (stack.isEmpty()) { // 如果栈中没有元素
return false; // 则无法匹配，返回 false
}
// 否则栈中有元素，这时开始匹配
if ((ch == ')' && stack.peek() != '(') // 如果 ')' 匹配不到 '('
|| (ch == '}' && stack.peek() != '{') // 或者 '}' 匹配不到 '{'
|| (ch == ']' && stack.peek() != '[')) { // 或者 ']' 匹配不到 '['
return false; // 则 ch 没有 正确顺序的左括号 与之匹配，返回 false
}
// 否则 ch 有 正确顺序的左括号 与之匹配
stack.pop(); // 将 匹配过的左括号 从栈中删除
}
return stack.isEmpty(); // 如果栈中还有元素，说明没有匹配成功，返回 false；否则返回 true
}
}
51. N 皇后
题目链接
标签
数组 回溯
思路
回溯
本题的 困难 标签有些夸张了，使用基本的 回溯 就可以解决。
题目要求把皇后放到无法攻击的位置上，皇后能攻击到的对象为 同一行、同一列、同一左斜线 (左斜线指的是从 左上 到 右下 的斜线↘️)、同一右斜线 (右斜线指的是从 右上 到 左下 的斜线↙️) 的对象。既然要求在 n×n 的棋盘上要放置 n 个皇后，那么 每一行和每一列都必须有皇后，并且在一条 左斜线 和 右斜线 上不能同时存在多个皇后。
可以想到，使用 回溯 对 每一行 进行操作：在 每一行 中枚举 每一列 来放置皇后，前提是 在 这一列、这一左斜线、这一右斜线 上不存在皇后，如果能放置，就按照 回溯 的常规做法：
- 将皇后放到棋盘的当前位置上。
- 标记皇后在这一列、这一左斜线、这一右斜线上。
- 放置下一个皇后。
- 取消标记。
- 将当前皇后从棋盘上移除。
完全可以改变回溯的策略，即 对 每一列 进行操作：在 每一列 中枚举 每一行 来放置皇后。
如何保证皇后之间无法互相攻击
本题除 回溯 思想比较难想到之外，还有一个难点：如何保证皇后之间无法互相攻击？上面其实已经提到过了，就是防止皇后被放到相同的 行、列、左斜线 或 右斜线 上，行和列都很直观，但左、右斜线就不是那么直观了，得使用行和列进行简单的计算。
下图是一个 4×4 的棋盘，标记了每个元素所对应的左、右斜线的编号，从 0 开始，到 2 * 4 - 1 - 1 = 6 结束，可以得到：在 n×n 的棋盘上，对于第 i 行、第 j 列的元素，它的左斜线的编号为 n - (i - j) - 1，右斜线的编号为 i + j。
代码
class Solution {
public List<List<String>> solveNQueens(int n) {
// 初始化本对象的属性
this.n = n;
this.col = new boolean[n];
this.lSlash = new boolean[2 * n - 1];
this.rSlash = new boolean[2 * n - 1];
this.table = new char[n][n];
for (char[] row : table) { // 将棋盘的每行都填充为 '.'
Arrays.fill(row, '.');
}
dfs(0);
return res;
}
private List<List<String>> res = new ArrayList<>(); // 存储结果的集合
private char[][] table; // 棋盘
private int n; // 棋盘的 行数 和 列数
private boolean[] col; // 判断 某一列 是否有皇后
private boolean[] lSlash; // 判断 某一左斜线(左上 到 右下) 是否有皇后
private boolean[] rSlash; // 判断 某一右斜线(右上 到 左下) 是否有皇后
// 在索引为 i 的行上，放置第 i+1 个皇后
private void dfs(int i) {
if (i == n) { // 如果已经放置够了 n 个皇后
// 将 放置皇后的棋盘 加入到结果集合中
List<String> ans = new ArrayList<>();
for (char[] row : table) {
ans.add(new String(row));
}
res.add(ans);
return; // 并直接返回
}
for (int j = 0; j < n; j++) { // 枚举所有的 列
int ls = n - (i - j) - 1; // 当前行列对应的 左斜线的编号
int rs = i + j; // 当前行列对应的 右斜线的编号
// 如果 这列、左斜线、右斜线 之一被占，则取消本次放置
if (col[j] || lSlash[ls] || rSlash[rs]) {
continue;
}
table[i][j] = 'Q'; // 将皇后放到棋盘的当前位置上
col[j] = lSlash[ls] = rSlash[rs] = true; // 标记皇后在这一列、这一左斜线、这一右斜线上
dfs(i + 1); // 放置下一个皇后
col[j] = lSlash[ls] = rSlash[rs] = false; // 取消标记
table[i][j] = '.'; // 将当前皇后从棋盘上移除
}
}
}
