目录
- 1667. 修复表中的名字
- 题目链接
- 表
- 要求
- 知识点
- 思路
- 代码
- 36. 有效的数独
- 题目链接
- 标签
- 思路
- 代码
- 199. 二叉树的右视图
- 题目链接
- 标签
- 思路
- 代码
1667. 修复表中的名字
题目链接
1667. 修复表中的名字
表
- 表
Users
的字段为user_id
和name
。
要求
编写解决方案,修复名字,使得只有第一个字符是大写的,其余都是小写的。
返回按 user_id
排序的结果表。
知识点
substring()
:截取字符串,接收三个(或两个)参数:源字符串、起始字符索引(索引从1开始)和长度(可选),如果不写长度,则截取源字符串从 起始字符 到 字符串末尾字符 的部分。例如select substring("abcde", 1, 2)
的结果为ab
,select substring("abcde", 2)
的结果为bcde
。upper()
:将字符串转化为大写的函数。例如select upper("aBc")
的结果为ABC
。lower()
:将字符串转化为小写的函数。例如select upper("AbC")
的结果为abc
。concat()
:拼接字符串的函数。例如select concat("us", "er")
的结果为user
。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;
}
}