本文主要是介绍LeetCode 1731, 151, 148,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 1731. 每位经理的下属员工数量
- 题目链接
- 表
- 要求
- 知识点
- 思路
- 代码
- 151. 反转字符串中的单词
- 题目链接
- 标签
- 思路
- 代码
- 148. 排序链表
- 题目链接
- 标签
- Collections.sort()
- 思路
- 代码
- 归并排序
- 思路
- 代码
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
进行排序即可。
代码
selectemployee_id,name,reports_count,average_age
fromEmployees m,(selectreports_to manager_id,count(*) reports_count,round(avg(age), 0) average_agefromEmployeesgroup bymanager_id) sub
whereemployee_id = manager_id
order byemployee_id
151. 反转字符串中的单词
题目链接
151. 反转字符串中的单词
标签
双指针 字符串
思路
本题可以使用 J a v a Java Java字符串的 s p l i t ( ) split() split()方法,这个方法可以按模式字符串分割原字符串,并且会保留空字符串,比如" main".split(" ")
的结果是[, main]
而不是[main]
。
针对空串,需要遍历 s p l i t ( ) split() split()返回的数组,将长度不为0的字符串(即不是空串)加入到一个链表中(为什么使用链表?因为不知道最终非空字符串的个数),再使用 C o l l e c t i o n s . r e v e r s e ( ) Collections.reverse() Collections.reverse()方法将链表反转,最后将这个链表转为 O b j e c t [ ] Object[] Object[],这就得到了一个字符串数组,然后将这些字符串通过 S t r i n g B u i l d e r StringBuilder StringBuilder拼接得到结果。
注意, S t r i n g B u i l d e r StringBuilder StringBuilder的 . a p p e n d ( ) .append() .append()方法的返回值仍然是 S t r i n g B u i l d e r StringBuilder StringBuilder,也就是说 . a p p e n d ( ) .append() .append()支持链式编程,即可以将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()
思路
相信看到这道题后,想到的第一个方法就是先将链表转为节点数组,然后对节点数组进行排序,最后再将节点数组转换为链表,这样做完全可以。
在 J a v a Java Java中,可以使用 C o l l e c t i o n s . s o r t ( ) Collections.sort() Collections.sort()方法对 L i s t List List的实现类(比如 A r r a y L i s t , L i n k e d L i s t ArrayList, LinkedList ArrayList,LinkedList)进行排序,传入 一个 L i s t List List集合 和 匿名内部类或Lambda表达式 就可以排序了。所以第一步是将链表转化为 L i s t List List集合,第二步是对 L i s t List List集合进行排序,第三步是将有序的 L i s t List List集合转化为链表返回。
代码
class Solution {public ListNode sortList(ListNode head) {// 先将链表转为java中的ListList<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,那就意味着第二个短链表的长度为subNnext = 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); // 定义一个哨兵节点,返回它的nextListNode 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;}
}
这篇关于LeetCode 1731, 151, 148的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!