LeetCode 1731, 151, 148-个人在线分享

1731. 每位经理的下属员工数量

题目链接

1731. 每位经理的下属员工数量

表

表Employees的字段为employee_id、name、reports_to和age。

要求

编写一个解决方案来返回需要听取汇报的所有经理的 ID、名称、直接向该经理汇报的员工人数，以及这些员工的平均年龄，其中该平均年龄需要四舍五入到最接近的整数。
返回的结果集需要按照 employee_id 进行排序。

知识点

round()：四舍五入的函数。
count()：统计个数的函数。
avg()：求平均值的函数。
group by：根据某些字段进行分组。
order by：根据某些字段进行排序。

思路

可以先按经理的id report_to AS manager_id 统计(将查询结果作为一张表)出直接向该经理汇报的员工人数、平均年龄(需要四舍五入到整数位)，然后再将 Employees 作为经理的表 m，与这张子表 sub 进行多表查询，限制条件为 m.employee_id == sub.manager_id，最后再根据 employee_id 进行排序即可。

代码

select
    employee_id,
    name,
    reports_count,
    average_age
from
    Employees m,
    (
        select
            reports_to manager_id,
            count(*) reports_count,
            round(avg(age), 0) average_age
        from
            Employees
        group by
            manager_id
    ) sub
where
    employee_id = manager_id
order by
    employee_id

151. 反转字符串中的单词

题目链接

151. 反转字符串中的单词

思路

本题可以使用

Java

$J a v a$ 字符串的

(

)

split()

$s p l i t ()$ 方法，这个方法可以按模式字符串分割原字符串，并且会保留空字符串，比如" main".split(" ")的结果是[, main]而不是[main]。

针对空串，需要遍历

(

)

split()

$s p l i t ()$ 返回的数组，将长度不为0的字符串(即不是空串)加入到一个链表中(为什么使用链表？因为不知道最终非空字符串的个数)，再使用

(

)

Collections.reverse()

$C o l l e c t i o n s . r e v e r s e ()$ 方法将链表反转，最后将这个链表转为

[

]

Object[]

$O b j e c t []$ ，这就得到了一个字符串数组，然后将这些字符串通过

StringBuilder

$S t r i n g B u i l d e r$ 拼接得到结果。

注意，

StringBuilder

$S t r i n g B u i l d e r$ 的

(

)

.append()

$. a p p e n d ()$ 方法的返回值仍然是

StringBuilder

$S t r i n g B u i l d e r$ ，也就是说

(

)

.append()

$. a p p e n d ()$ 支持链式编程，即可以将builder.append(" " + str)写作builder.append(" ").append(str)。

代码

class Solution {
    public String reverseWords(String s) {
        Object[] split = split(s);
        int n = split.length;

        // 如果字符串的个数为0，则返回空串
        if (n == 0) {
            return "";
        }

        // 拼接单词和空格
        StringBuilder builder = new StringBuilder();
        builder.append(split[0]); // 上面的判断已经保证至少有一个单词，所以可以先拼接第1个单词
        for (int i = 1; i < split.length; i++) {
            builder.append(" ").append(split[i]);
        }
        return builder.toString();
    }
    // 将字符串分成单词的数组并反转
    private Object[] split(String s) {
        List<String> list = new ArrayList<>();
        for (String str : s.split(" ")) {
            if (str.length() != 0) {
            	list.add(str);
            }
        }
        Collections.reverse(list);
        return list.toArray();
    }
}

148. 排序链表

题目链接

148. 排序链表

Collections.sort()

思路

相信看到这道题后，想到的第一个方法就是先将链表转为节点数组，然后对节点数组进行排序，最后再将节点数组转换为链表，这样做完全可以。

在

Java

$J a v a$ 中，可以使用

(

)

Collections.sort()

$C o l l e c t i o n s . s o r t ()$ 方法对

List

$L i s t$ 的实现类(比如

ArrayList, LinkedList

$A r r a y L i s t, L i n k e d L i s t$ )进行排序，传入一个

List

$L i s t$ 集合和匿名内部类或Lambda表达式就可以排序了。所以第一步是将链表转化为

List

$L i s t$ 集合，第二步是对

List

$L i s t$ 集合进行排序，第三步是将有序的

List

$L i s t$ 集合转化为链表返回。

代码

class Solution {
    public ListNode sortList(ListNode head) {
        // 先将链表转为java中的List
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }

        // 对List进行排序
        Collections.sort(list, (n1, n2) -> n1.val - n2.val);

        // 将有序List转化为链表
        ListNode sentinel = new ListNode();
        ListNode curr = sentinel;
        for (ListNode node : list) {
            curr.next = node;
            curr = curr.next;
        }
        curr.next = null; // 防止成为循环链表，这一步很关键
        return sentinel.next;
    }
}

归并排序

思路

上面的办法虽然好，但出这道题的人可能不希望这样解，他希望使用 归并排序 的思想对本题进行求解。

归并排序的思想是分治，对一个长链表进行排序，可以先把其分为很多段(直到不可再分，即只剩一个节点)，然后对每段都排序，最后再合成这些有序的短链表为长链表。

对于合并两个有序链表，可以看我写的这篇文章 21. 合并两个有序链表。

可以先求出链表的长度，代码如下，其中 n 是链表的长度：

int n = 0;
for (ListNode curr = head; curr != null; curr = curr.next) {
    n++;
}

然后再进行归并排序，先从短链表的长度为0开始，每次合并完所有短链表后，将短链表的长度扩大1倍，然后再进行合并，直到短链表的长度比长链表大。

每次合并得先得到两个短链表，然后才能合成，当合并到最后两个短链表时，这两个短链表的长度可能不够这轮归并所要求的短链表长度，但无所谓，依然可以将其合并一次，除了消耗一点点时间外没有任何影响。

注意：合并完短链表后，短链表和长链表是分开的，所以需要重建它们之间的关系。

只说这些思路是远远不够的，本题的难点在于对边界值的判断，这就需要大家极其仔细了，具体看代码的注释吧。

代码

class Solution {
public ListNode sortList(ListNode head) {
// 如果链表为空，则返回空；如果链表只有一个节点，则不需要排序
if (head == null || head.next == null) {
return head;
}
// 先统计链表的长度
int n = 0;
for (ListNode curr = head; curr != null; curr = curr.next) {
n++;
}
// 再进行归并排序
ListNode sentinel = new ListNode(-1, head);
for (int subN = 1; subN < n; subN <<= 1) { // subN是短链表的长度
// prev指向待合成的两个短链表的第一个短链表的头节点
ListNode prev = sentinel, curr = sentinel.next;
while (curr != null) {
// 找第一个长度为subN的短链表
ListNode list1 = curr; // list1为短链表的头节点
// i从1开始是因为list1也算一个节点，所以只需要走subN-1步就能得到长度为subN的短链表
for (int i = 1; i < subN && curr.next != null; i++) {
curr = curr.next;
}
// 找第二个长度为subN的短链表
// 把curr.next赋值给list2 是因为 curr是第一个短链表的最后一个节点
ListNode list2 = curr.next; // list2为短链表的头节点
curr.next = null; // 将第一个短链表和第二个短链表分开
curr = list2; // curr从第二个短链表的头节点开始
// i从1开始是因为list1也算一个节点，所以只需要走subN-1步就能得到长度为subN的短链表
// 由于curr从原先的curr.next开始，不知道原先的curr.next是否为null，所以需要加上curr != null的判断条件
for (int i = 1; i < subN && curr != null && curr.next != null; i++) {
curr = curr.next;
}
// 处理下一个短链表
ListNode next = null; // next是下一个长度为subN的短链表的头节点
if (curr != null) { // 如果curr不为null，那就意味着第二个短链表的长度为subN
next = curr.next; // 此时把curr.next 赋值给 下一个短链表的头节点
curr.next = null; // 将第二个短链表和下一个短链表分开
}
// 合并两个有序短链表，merged是合并后链表的头节点
ListNode merged = mergeTwoLists(list1, list2);
// 将短链表接入长链表
prev.next = merged;
while (prev.next != null) { // 让prev到短链表的最后一个节点
prev = prev.next;
}
// 更新curr到下一个短链表的头节点处
curr = next;
}
}
return sentinel.next;
}
// 合并两个有序链表
private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode sentinel = new ListNode(-1); // 定义一个哨兵节点，返回它的next
ListNode curr = sentinel;
// 1. 先把小的节点加到哨兵节点上，直到两个链表任意一个为空
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
// 2. 如果链表1不为空，则加上它剩余的部分
if (list1 != null) {
curr.next = list1;
} else { // 否则链表2不为空，加上它剩余的部分(就算链表2为空，也是加上一个null，对结果不影响)
curr.next = list2;
}
// 3. 返回哨兵节点的next，因为它指向结果链表
return sentinel.next;
}
}

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

LeetCode 1731, 151, 148

目录

1731. 每位经理的下属员工数量

题目链接

表

要求

知识点

思路

代码

151. 反转字符串中的单词

题目链接

标签

思路

代码

148. 排序链表

题目链接

标签

Collections.sort()

思路

代码

归并排序

思路

代码

admin 钻石

目录

1731. 每位经理的下属员工数量

题目链接

表

要求

知识点

思路

代码

151. 反转字符串中的单词

题目链接

标签

思路

代码

148. 排序链表

题目链接

标签

Collections.sort()

思路

代码

归并排序

思路

代码

admin 钻石

相关推荐