LeetCode 176, 289, 437

176. 第二高的薪水

题目链接

176. 第二高的薪水

表

• 表Employee的字段为id和salary。

要求

查询并返回 Employee 表中第二高的薪水 。如果不存在第二高的薪水，查询应该返回 null(Pandas 则返回 None) 。

知识点

1. order by：根据某些字段排序。
2. distinct：根据某个字段去重。
3. limit：限制查询结果的数量。
4. offset：跳过指定数量的记录，经常与limit搭配实现分页查询结果，公式为OFFSET = (页码 - 1) * 每页的记录数。例如limit 15 offset 15表示返回第2页数据，共有15条。

思路

查询第二高的薪水时，可以先将数据按薪水降序排列（由于薪水可能重复，所以需要对薪水进行去重操作），然后限制每页只有一条数据，返回第二页的数据。

注意：直接这样查询是不会在没有第二高的薪水返回null，这里需要将查询结果作为子表，然后就能在没有查询结果时返回null了。

代码

select(selectdistinct salaryfromEmployeeorder bysalary desclimit 1offset 1) SecondHighestSalary

289. 生命游戏

题目链接

289. 生命游戏

标签

数组 矩阵 模拟

简单版

思路

注意题目中的“面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。”这是因为本轮细胞的状态不能由本轮细胞的状态（更新后的值）决定，只能由上一轮细胞的状态决定。这就意味着需要将原先的矩阵拷贝一份，拷贝矩阵便是上一轮的状态，用拷贝矩阵更新原矩阵。

更新的方法很简单，在拷贝矩阵中统计各细胞周围的活细胞数，然后根据题中的四条规则更新这个细胞的值。

代码

class Solution {private int[][] dir = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}; // 方向数组，分别为 左上 正上 右上 正左 正右 左下 正下 右下public void gameOfLife(int[][] board) {int row = board.length;int col = board[0].length;// 将原矩阵拷贝到新矩阵中int[][] copy = new int[row][col];for (int r = 0; r < row; r++) {for (int c = 0; c < col; c++) {copy[r][c] = board[r][c];}}// 统计拷贝矩阵中每个细胞周围的活细胞数，并根据规则修改原矩阵for (int r = 0; r < row; r++) {for (int c = 0; c < col; c++) {// 统计当前细胞周围的活细胞数int cnt = 0; // 当前细胞周围的活细胞数for (int k = 0; k < 8; k++) {int kr = r + dir[k][0], kc = c + dir[k][1];if (kr >= 0 && kr < row && kc >= 0 && kc < col && copy[kr][kc] == 1) {cnt++;}}// 如果 活细胞 周围八个位置的活细胞数 少于两个 或 超过三个，则该位置活细胞 死亡if (copy[r][c] == 1 && (cnt < 2 || cnt > 3)) {board[r][c] = 0;}// 如果 活细胞 周围八个位置有 两个 或 三个 活细胞，则该位置活细胞仍然存活// 也就是说不需要对其进行操作// 如果 死细胞 周围正好有 三个 活细胞，则该位置死细胞 复活if (copy[r][c] == 0 && cnt == 3) {board[r][c] = 1;}}}}
}

进阶版

思路

既然不使用拷贝矩阵，那就得想一种方法，这种方法使得本轮更新完细胞后还能辨认出这个细胞上一轮的状态，其实很简单，就像制作生命游戏的人一样，再多自定义几种状态，这几种状态表示上一轮是某个状态，而这一轮是另一个状态。

观察更新的四条规则，发现只有两种变化：死亡（上一轮活着，本轮死亡）、复活（上一轮死亡，本轮活着）。所以可以自定义这两种状态分别为2, 3，然后细胞的状态就有四种了：0（死细胞）、1（活细胞）、2（死亡的细胞）、3（复活的细胞）。

更新整个矩阵的策略是：先扫描一遍矩阵，获取每个细胞的状态，然后再扫描一遍，把两种自定义状态还原回0或1。

代码

class Solution {private int[][] dir = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}; // 方向数组，分别为 左上 正上 右上 正左 正右 左下 正下 右下public void gameOfLife(int[][] board) {int row = board.length;int col = board[0].length;// 统计拷贝矩阵中每个格子周围的活细胞数，并根据规则修改原矩阵for (int r = 0; r < row; r++) {for (int c = 0; c < col; c++) {// 统计当前格子周围的活细胞数int cnt = 0;for (int k = 0; k < 8; k++) {int kr = r + dir[k][0], kc = c + dir[k][1];if (kr >= 0 && kr < row && kc >= 0 && kc < col&& (board[kr][kc] == 1 || board[kr][kc] == 2)) {cnt++;}}// 如果 活细胞 周围八个位置的活细胞数 少于两个 或 超过三个，则该位置活细胞 死亡// 死亡的细胞(board[r][c] == 2)上一轮是活的if ((board[r][c] == 1 || board[r][c] == 2) && (cnt < 2 || cnt > 3)) {board[r][c] = 2; // 死亡}// 如果 活细胞 周围八个位置有 两个 或 三个 活细胞，则该位置活细胞仍然存活// 也就是说不需要对其进行操作// 如果 死细胞 周围正好有 三个 活细胞，则该位置死细胞 复活// 复活的细胞(board[r][c] == 3)上一轮是死的if ((board[r][c] == 0 || board[r][c] == 3) && cnt == 3) {board[r][c] = 3; // 复活}}}// 将自定义状态还原回0和1for (int r = 0; r < row; r++) {for (int c = 0; c < col; c++) {if (board[r][c] == 2) {board[r][c] = 0;} else if (board[r][c] == 3) {board[r][c] = 1;}}}}
}

437. 路径总和 III

题目链接

437. 路径总和 III

标签

树 深度优先搜索 二叉树

思路

本题可以这样做：以二叉树中每个节点为路径的起始节点，探索有没有路径之和恰好为targetSum的路径。

以二叉树中每个节点为路径的起始节点，这个很容易做到，使用递归即可，可以使用前序遍历、中序遍历、后序遍历中的任意一种。

处理当前节点就是探索以本节点curr为路径起点，curr已经在路径中了，让targetSum减去当前节点值curr.val，计算出剩余值rest，在子树中寻找和为剩余值rest的路径。

注意：由于本题的测试用例中有一个节点的val比较大，下一个剩余值rest就超出int的下限了，所以在寻找路径时需要将rest设置为long类型。

代码

class Solution {// 从二叉树根节点开始遍历每个节点，统计 当前节点curr及其子树中 和为targetSum 的路径个数public int pathSum(TreeNode curr, int targetSum) {if (curr == null) { // 如果当前节点为nullreturn 0; // 则没有路径}// 使用了前序遍历：先处理当前节点，再遍历左子树，最后遍历右子树int res = sum(curr, targetSum); // 统计 以curr作为路径起点 和为targetSum 的路径个数res += pathSum(curr.left, targetSum); // 统计 curr的左子树中 和为targetSum 的路径个数res += pathSum(curr.right, targetSum); // 统计 curr的右子树中 和为targetSum 的路径个数return res;}// 统计 以从pathSum中传入的节点curr作为路径起点 和为rest 的路径个数private int sum(TreeNode curr, long rest) {if (curr == null) { // 如果当前节点为nullreturn 0; // 则没有路径}int res = 0; // 路径数int val = curr.val; // 获取当前节点的值if (val == rest) { // 如果当前节点的值 等于 restres++; // 则路径个数 + 1}res += sum(curr.left, rest - val); // 让路径向左子节点走，下一个rest为rest - valres += sum(curr.right, rest - val); // 让路径向右子节点走，下一个rest为rest - valreturn res; // 返回路径个数}
}