LeetCode 1729, 12, 19
目录
- 1729. 求关注者的数量
- 题目链接
- 表
- 要求
- 知识点
- 思路
- 代码
- 12. 整数转罗马数字
- 题目链接
- 标签
- 思路
- 代码
- 19. 删除链表的倒数第 N 个结点
- 题目链接
- 标签
- 基础
- 思路
- 代码
- 进阶
- 思路
- 代码
1729. 求关注者的数量
题目链接
1729. 求关注者的数量
表
- 表
Followers的字段为user_id和follower_id。
要求
- 编写解决方案，对于每一个用户，返回该用户的关注者数量。
- 按
user_id的顺序返回结果表。
知识点
count()：统计个数的函数。group by：根据某些字段进行分组。order by：按照某些字段进行排序。
思路
由于该表的字段是 用户id 和 关注他的用户id，所以 一个人的粉丝数 可以看作 他在这张表中的记录数，从而只需要统计每个人的记录数，然后在按照user_id升序返回即可。
代码
select
user_id,
count(*) followers_count
from
Followers
group by
user_id
order by
user_id
12. 整数转罗马数字
题目链接
12. 整数转罗马数字
标签
哈希表 数学 字符串
思路
如果将罗马数字看作是
M
(
1000
)
,
D
(
500
)
,
C
(
100
)
,
L
(
50
)
,
X
(
10
)
,
V
(
5
)
,
I
(
1
)
M(1000), D(500), C(100), L(50), X(10), V(5), I(1)
M(1000),D(500),C(100),L(50),X(10),V(5),I(1)的组合，那么还有六种特殊情况需要注意，即
C
M
(
900
)
,
C
D
(
400
)
,
X
C
(
90
)
,
X
L
(
40
)
,
I
X
(
9
)
,
I
V
(
4
)
CM(900), CD(400), XC(90), XL(40), IX(9), IV(4)
CM(900),CD(400),XC(90),XL(40),IX(9),IV(4)，但 如果将这六种特殊情况也当作组合中的元素，那不就没有特殊情况了。
所以将罗马数字看作是
M
(
1000
)
,
C
M
(
900
)
,
D
(
500
)
,
C
D
(
400
)
,
C
(
100
)
,
X
C
(
90
)
,
L
(
50
)
,
X
L
(
40
)
,
X
(
10
)
,
I
X
(
9
)
,
V
(
5
)
,
I
V
(
4
)
,
I
(
1
)
M(1000), CM(900), D(500), CD(400), C(100), XC(90), L(50), XL(40), X(10), IX(9), V(5), IV(4), I(1)
M(1000),CM(900),D(500),CD(400),C(100),XC(90),L(50),XL(40),X(10),IX(9),V(5),IV(4),I(1) 的组合，这样只需要 从大到小找出合适的值拼接得到最终的罗马数字。
说到拼接，在
J
a
v
a
Java中有
S
t
r
i
n
g
B
u
i
l
d
e
r
StringBuilder
StringBuilder和
S
t
r
i
n
g
B
u
f
f
e
r
StringBuffer
StringBuffer类，它们都可以使用
a
p
p
e
n
d
(
)
append()
append() 方法做字符串的拼接，然后通过
t
o
S
t
r
i
n
g
(
)
toString()
toString() 方法返回拼接的字符串，它们的主要区别如下：
| 类 | 线程安全 | 速度 |
|---|---|---|
| StringBuilder | 线程不安全 | 快 |
| StringBuffer | 线程安全 | 慢 |
由于本题所写的方法不需要在多线程情况下使用，所以不存在线程安全问题，从而使用
S
t
r
i
n
g
B
u
i
l
d
e
r
StringBuilder
StringBuilder比较好，但是 如果在生产环境下，就得考虑所写的方法是否存在 多个线程对同一个共享资源进行读和写操作 的情况，如果是，则需要使用线程安全的类
S
t
r
i
n
g
B
u
f
f
e
r
StringBuffer
StringBuffer。
代码
class Solution {
private class Mapper { // 罗马数字与阿拉伯数字的映射
String roman; // 罗马数字的符号
int num; // 对应的阿拉伯数字
public Mapper(String roman, int num) {
this.roman = roman;
this.num = num;
}
}
private final Mapper[] mappers = {
new Mapper("M", 1000),
new Mapper("CM", 900),
new Mapper("D", 500),
new Mapper("CD", 400),
new Mapper("C", 100),
new Mapper("XC", 90),
new Mapper("L", 50),
new Mapper("XL", 40),
new Mapper("X", 10),
new Mapper("IX", 9),
new Mapper("V", 5),
new Mapper("IV", 4),
new Mapper("I", 1)
}; // 构建 从大到小的 罗马数字与阿拉伯数字的映射
public String intToRoman(int num) {
StringBuilder builder = new StringBuilder();
for (Mapper mapper : mappers) {
while (num >= mapper.num) { // 如果剩余的数比当前数大
num -= mapper.num; // 给剩余的数减去当前数
builder.append(mapper.roman); // 给结果字符串拼接当前数对应的罗马数字
}
if (num == 0) { // 如果剩余的数等于0
break; // 则退出循环，返回结果
}
}
return builder.toString();
}
}
19. 删除链表的倒数第 N 个结点
题目链接
19. 删除链表的倒数第 N 个结点
标签
链表 双指针
基础
思路
要删除倒数第
N
N
N 个节点，就得找到倒数第
N
+
1
N+1
N+1 个节点，然后让它指向它下一个节点指向的节点。
如何找倒数第
N
+
1
N+1
N+1 个节点？这是个问题，不过标签中的 双指针 作了提醒：可以使用左指针
l
e
f
t
left
left和右指针
r
i
g
h
t
right
right，倒数第
N
+
1
N+1
N+1 个节点与倒数第
0
0
0 个节点（也就是空节点）的距离刚好是
N
N
N，所以可以让右指针
r
i
g
h
t
right
right先走
N
+
1
N+1
N+1步（此时左右指针的距离也刚好是
N
N
N），然后再让左右指针同速前进，直到右指针
r
i
g
h
t
right
right为空，这时左指针恰好就指向倒数第
N
+
1
N+1
N+1 个节点。
由于可能删除链表的倒数最后一个节点（也就是链表的头节点），所以使用哨兵节点指向链表的头节点，这样可以简化对头节点的判断。
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(-1, head); // 哨兵节点，指向链表头部
ListNode left = sentinel, right = sentinel;
// 先让右指针走 N + 1 步，与左指针保持 N 的距离
for (int i = 0; i < n + 1; i++) {
right = right.next;
}
// 循环结束后，right == null，left就是倒数第 N + 1 个节点
while (right != null) {
left = left.next;
right = right.next;
}
left.next = left.next.next; // 删除倒数第 N 个节点
return sentinel.next; // 返回哨兵节点指向的节点
}
}
进阶
- 进阶：你能尝试使用一趟扫描实现吗？
思路
既然只扫描一次链表，就需要从每个节点的扫描中获取“信息”，这个信息就是 当前节点是倒数第几个节点。有了这个信息后，就可以根据它删除倒数第
N
N
N 个节点了。
这里定义一个概念——倒序：对于一个节点，它的倒序 就是 它是倒数第几个节点。比如说最后一个节点的倒序为1，因为它是倒数第一个节点；倒数第
N
N
N 个节点的倒序为
N
N
N。
和基础版一样，要删除倒序为
N
N
N 的节点，还是得先找倒序为
N
+
1
N+1
N+1 的节点。
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(-1, head);
getNodeRevSeq(sentinel, n);
return sentinel.next;
}
private int getNodeRevSeq(ListNode curr, int n) {
if (curr == null) { // 倒数第 0 个节点的倒序是0
return 0;
}
int revSeq = getNodeRevSeq(curr.next, n); // 先查这个节点的下一个节点的倒序
if (revSeq == n) { // 如果这个节点的下一个节点的倒序为n，则删除下一个节点
curr.next = curr.next.next;
}
return revSeq + 1; // 再返回这个节点的倒序，这个节点的倒序 = 下一个节点的倒序 + 1
}
}
