LeetCode 1667, 36, 199

1667. 修复表中的名字

题目链接

1667. 修复表中的名字

表

• 表Users的字段为user_id和name。

要求

编写解决方案，修复名字，使得只有第一个字符是大写的，其余都是小写的。

返回按 user_id 排序的结果表。

知识点

1. substring()：截取字符串，接收三个（或两个）参数：源字符串、起始字符索引（索引从1开始）和长度（可选），如果不写长度，则截取源字符串从 起始字符 到 字符串末尾字符 的部分。例如select substring("abcde", 1, 2)的结果为ab，select substring("abcde", 2)的结果为bcde。
2. upper()：将字符串转化为大写的函数。例如select upper("aBc")的结果为ABC。
3. lower()：将字符串转化为小写的函数。例如select upper("AbC")的结果为abc。
4. concat()：拼接字符串的函数。例如select concat("us", "er")的结果为user。
5. order by：根据某些字段排序。

思路

想必大家看完知识点之后已经想出如何解决本题了：截取名字的第一个字符，转化为大写；截取名字从第二个字符到末尾字符的部分，转化为小写。然后再将这两部分拼接起来，最后根据user_id进行排序即可。

代码

select
    user_id,
    concat(upper(substring(name, 1, 1)), lower(substring(name, 2))) name
from
    Users
order by
    user_id

36. 有效的数独

题目链接

36. 有效的数独

标签

数组 哈希表 矩阵

思路

可以使用二维数组保存各行、各列、各3x3宫内数字1-9是否出现过，在遍历到某个数字时，先检查它所在行、列、3x3宫是否有这个数字，如果有，则返回false；如果没有，就标记它所在行、列、3x3宫有这个数字。如果能遍历完整个9x9宫，说明这个数独有效，返回true。

二维数组如何保存数字1-9？对于行数组row来说，每行表示九宫格的每行，每列表示数字1-9；对于列数组col来说，每行表示九宫格的每列，每列表示数字1-9；对于3x3宫数组sub来说，每行表示九宫格的编号从0到9，每列表示数字1-9。

行数组row和列数组col实现起来比较简单，但3x3宫数组sub的实现就不是这么简单了，需要计算每个3x3宫的编号，先给每个3x3宫编号，如下图所示：

观察可得：

0行0列是第0个3x3宫，…，2行2列是第0个3x3宫
0行3列是第1个3x3宫，…，2行5列是第1个3x3宫
0行6列是第2个3x3宫，…，2行8列是第2个3x3宫
3行0列是第3个3x3宫，…，5行2列是第3个3x3宫
3行3列是第4个3x3宫，…，5行5列是第4个3x3宫
3行6列是第5个3x3宫，…，5行8列是第5个3x3宫
6行0列是第6个3x3宫，…，8行2列是第6个3x3宫
6行3列是第7个3x3宫，…，8行5列是第7个3x3宫
6行6列是第8个3x3宫，…，8行8列是第8个3x3宫

不难看出，每当列数增加3，编号增加1；每当行数增加3，编号增加3。所以可以得出一个结论：第i行第j列的格子属于编号为i / 3 * 3 + j / 3的3x3宫。

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][] sub = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char ch = board[i][j];
                if (ch == '.') { // 当ch不是数字时
                    continue; // 跳过ch
                }
                int num = ch - '1';
                int subIndex = i / 3 * 3 + j / 3;
                // 判断这个数字是否重复
                if (row[i][num] || col[j][num] || sub[subIndex][num]) {
                    return false;
                }
                // 进行标记
                row[i][num] = true;
                col[j][num] = true;
                sub[subIndex][num] = true;
            }
        }
        return true;
    }
}

199. 二叉树的右视图

题目链接

199. 二叉树的右视图

标签

树 深度优先搜索 广度优先搜索 二叉树

思路

由右视图的定义可知右视图是二叉树每层最右边节点组成的链表，所以本题的思路为：层序遍历二叉树，将每层的最后一个节点的值加入结果链表。如果对层序遍历不熟悉，可以看这篇文章：102. 二叉树的层序遍历。

对层序遍历做个总结：使用队列存放每层节点，预先放入根节点，在遍历每层节点时将下一层的节点（即当前层节点的左、右子节点）加入队尾，直到队列为空。

代码

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) { // 如果根节点为null
            return new ArrayList<>(); // 则返回空链表
        }

        List<Integer> res = new ArrayList<>(); // 结果链表
        LinkedList<TreeNode> queue = new LinkedList<>(); // 存放每层节点的队列
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(); // 获取本层节点的数量
            for (int i = 0; i < size; i++) { // 遍历本层的所有节点
                TreeNode curr = queue.poll();
                if (i == size - 1) { // 如果是本层最后一个节点
                    res.add(curr.val); // 将该节点的值放入结果链表
                }
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }
        return res;
    }
}