626. 换座位
题目链接
表
- 表
Seat的字段为id和student。
要求
- 编写解决方案来交换每两个连续的学生的座位号。如果学生的数量是奇数，则最后一个学生的id不交换。
- 按
id升序 返回结果表。
知识点
max()：求最大值的函数。order by：根据某些字段排序。case when then else end：多路分支语句，如果将其与 J a v a Java Java中的if - else-if - else做比较，则when相当于if或else-if、else相当于else，而case和end表示这个语句的起始和结束。
思路
本题可以只修改学生姓名student对应的id，然后通过order by id将学生的数据重新排序，这样就可以达到交换两个连续学生的座位号的效果。
对于修改id，有些复杂，按理来说这应该属于在程序中写的代码，但却被限制只能写在sql语句中。可以想一想在 J a v a Java Java中如何实现：对于id为偶数的学生，直接将他的id减一即可；对于id为奇数的学生，还需要考虑他是不是最后一个学生（即id最大的学生），如果不是，则将他的id加一，如果是，则直接返回他的id。
所以需要先找到最大id（使用子查询），并且需要一个case语句来判断这些情况。
代码
select
(
case
when
id % 2 = 0
then
id - 1
when
id % 2 = 1
and
id != max_id
then
id + 1
else
id
end
) id,
student
from
Seat,
(
select
max(id) max_id
from
Seat
) sub
order by
id
11. 盛最多水的容器
题目链接
标签
贪心 数组 双指针
思路
可以使用双指针来解决本题，左指针left从头到尾遍历，右指针right从尾到头遍历，如果两指针相遇，则退出循环。
外层的架子搭好了，现在要决定的是移动指针的策略：如果 左指针left指向的线的高度 小于 右指针right指向的线的高度，则将左指针left往右移动一位；否则就将右指针right往左移动一位。
为什么要这样移动指针？拿 左指针left指向的线的高度 小于 右指针right指向的线的高度 举一个例子：对于height = [2, 4, 6, 8, 10]，如果不是 将左指针left往右移动一位，而是 将右指针right往左移动一位，则最终的最大容量为(4 - 0) * 2 = 8(初始left = 0, right = 4时容量最大)，但要是 将左指针left往右移动一位，则最终的最大容量为(4 - 1) * 4 = 12(当left = 1, right = 4时容量最大)，所以策略是这样的。
这种策略可以这样理解：找到矮线后无论如何向中心移动高线都比当前容量小，还不如试试移动矮线，寻找一个比当前容量大的容量。
代码
class Solution {
public int maxArea(int[] height) {
int res = 0;
int left = 0, right = height.length - 1;
while (left < right) {
if (height[left] < height[right]) {
res = Math.max(res, (right - left) * height[left]);
left++;
} else {
res = Math.max(res, (right - left) * height[right]);
right--;
}
}
return res;
}
101. 对称二叉树
题目链接
标签
树 深度优先搜索 广度优先搜索 二叉树
递归
思路
本题可以看作是根节点的左子树和右子树之间是否轴对称，所以可以写一个递归的方法，这个方法传入左节点和右节点。
先对节点做null校验：如果两个节点都是null，则这两个节点轴对称；如果两个节点只有一个是null，则这两个节点不轴对称。
然后再对节点做值校验：如果两个节点的值不同，则这两个节点不轴对称。
最后对节点的子节点做校验：发现两个节点轴对称其实就是 左节点的左子节点left.left 与 右节点的右子节点right.right 轴对称、并且 左子点的右子节点left.right 与 右节点的左子节点right.left 轴对称，所以在最后进行递归。
代码
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
// 检查左节点和右节点是否轴对称
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) { // 如果左节点和右节点都是null
return true; // 则它们两个轴对称
}
if (left == null || right == null) { // 如果左节点和右节点只有一个是null
return false; // 则它们两个不轴对称
}
if (left.val != right.val) { // 如果左节点和右节点的值不同
return false; // 则它们两个不轴对称
}
return check(left.left, right.right) && check(left.right, right.left);
}
}
迭代
思路
其实迭代的思路和递归一模一样，由于要横向比较（在二叉树的同一层进行比较，即层序遍历），所以迭代需要使用一个 队列 来存储这些节点。
开始先往队列中存入两个节点（即根节点的左子节点和右子节点），这对节点等待被比较。
每次比较时，先从队列中取出前两个节点left, right，然后进行比较（做null校验和值校验），最后将 左节点的左子节点left.left 与 右节点的右子节点right.right 作为待比较的一对节点加入队列、再将 左子点的右子节点left.right 与 右节点的左子节点right.left 作为待比较的一对节点加入队列。
代码
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
// 第一对待比较节点为根节点的左子节点和右子节点
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) {
continue;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
// 将待比较的一对节点加入队列
queue.offer(left.left);
queue.offer(right.right);
// 将待比较的另一对节点加入队列
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}