当前位置：首页 > news >正文

LeetCode 2356, 238, 141

news 来源：原创 2024/9/24 1:26:36

2356. 每位教师所教授的科目种类的数量

题目链接

2356. 每位教师所教授的科目种类的数量

表

表Teacher的字段为teacher_id，subject_id和dept_id。

要求

查询每位老师在大学里教授的科目种类的数量。
以 任意顺序 返回结果表。

知识点

group by：按照某个或某些字段的值进行分组。
count()：统计个数函数。
distinct：去重。

思路

这道题十分简单，想要查询每位老师在大学里教授的科目种类的数量，可以按老师的idteacher_id进行分组，然后对每位老师教授的科目idsubject_id进行去重的统计。

代码

selectteacher_id,count(distinct subject_id) cnt
fromTeacher
group byteacher_id

238. 除自身以外数组的乘积

题目链接

238. 除自身以外数组的乘积

要求

请 不要使用除法，且在 $O (n)$ 时间复杂度内完成此题。

思路

先定义两个概念：前缀积和后缀积。对于下标为i的元素，它的前缀积指的是数组中下标小于i的所有元素的乘积，它的后缀积指的是数组中下标大于i的所有元素的乘积。例如对于数组arr = [1, 2, 3, 4, 5]和下标为2的元素，它的前缀积是1 * 2 = 2，后缀积是4 * 5 = 20。

可以使用两个数组分别求每个元素的前缀积和后缀积，然后输出每个元素的前缀积与后缀积的乘积即可。

代码

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] prefix = new int[n]; // 求前缀积的数组int[] suffix = new int[n]; // 求后缀积的数组int[] res = new int[n]; // 结果数组// 1. 求前缀积prefix[0] = 1; // 第一个元素的前缀积为1for (int i = 1; i < n; i++) { // 从第二个元素开始prefix[i] = prefix[i - 1] * nums[i - 1];}// 2. 求后缀积suffix[n - 1] = 1; // 最后一个元素的后缀积为1for (int i = n - 2; i >= 0; i--) { // 从倒数第二个元素开始suffix[i] = suffix[i + 1] * nums[i + 1];}// 3. 返回结果for (int i = 0; i < n; i++) {res[i] = prefix[i] * suffix[i];}return res;}
}

进阶

你可以在 $O (1)$ 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为额外空间。）

进阶思想

大家可能已经发现了一个东西：单独求前缀积（或后缀积）不需要使用一个数组，每个元素的前缀积（或后缀积）只与它的前一个元素（或后一个元素）有关，所以只需要使用一个变量来记录前缀积（或后缀积）。

既然不让使用两个数组来辅助计算，那就用结果数组来辅助计算，不妨用结果数组来当作计算前缀积的数组，计算完前缀积后，使用一个变量来记录后缀积（后缀积的初始值为倒数第一个元素），从倒数第二个元素开始（因为倒数第一个值的后缀积为1，不需要再乘），每次都给结果数组乘后缀积，然后再更新一下后缀积。

当然也可以用结果数组当作计算后缀积的数组，这样就需要单独使用一个变量来记录前缀积（前缀积的初始值为第一个元素），从第二个元素开始（因为第一个数的前缀积为1，不需要再乘），每次都给结果数组乘前缀积，然后再更新一下前缀积。

进阶代码

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] res = new int[n]; // 结果数组// 1. 求前缀积res[0] = 1; // 第一个元素的前缀积为1for (int i = 1; i < n; i++) { // 从第二个元素开始res[i] = res[i - 1] * nums[i - 1];}// 2. 求后缀积int suffix = nums[n - 1]; // 倒数第二个元素的后缀积为倒数第一个元素for (int i = n - 2; i >= 0; i--) { // 从倒数第二个元素开始res[i] *= suffix;suffix *= nums[i];}return res;}
}

141. 环形链表

题目链接

141. 环形链表

思想

Floyd判圈算法可以完美地解决这个问题，不熟悉的话可以看我写的这篇博客——算法——Floyd判圈算法。

核心思想是：使用快慢指针fast, slow，快指针每次走两步fast = fast.next.next，慢指针每次走一步slow = slow.next，当出现fast == null || fast.next == null时，说明链表不存在环，如果存在环，则快指针永远不可能指向null。

代码

public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {return true;}}return false;}
}