1.去除已排序数组中的相同的数字，只保留一个相同的数字输入:[1,22.3.3,4,5.5.6]
输出:[1,2.3.4.5.6]
java
public int[] removeDuplicates(int[] nums) {
if (nums.length == 0) return nums;
int slow = 0, fast = 1;
while (fast < nums.length) {
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return Arrays.copyOf(nums, slow + 1);
}这个算法使用两个指针 slow 和 fast:- slow 指针遍历数组并保留不重复的元素。
- fast 指针快速扫描数组跳过重复元素。
- 每当 fast 遇到不重复的元素时,我们将该元素赋值给 slow 指针,然后 slow 指针向前移动。
- 重复这一过程,直到 fast 到达数组末尾。
- 最后返回 slow + 1 的长度的数组。时间复杂度:O(n),其中 n 是数组的长度。
空间复杂度:O(1)。对输入 [1,22.3.3,4,5.5.6],这个算法的过程是:slow = 0, fast = 1, nums[0] = 1, nums[1] = 2,将2赋值给nums[1],slow++
slow = 1, fast = 2, nums[1] = 2, nums[2] = 3,将3赋值给nums[2],slow++
slow = 2, fast = 3, nums[2] = 3, nums[3] = 3,fast++(跳过重复元素)
slow = 2, fast = 4, nums[2] = 3, nums[4] = 4,将4赋值给nums[3],slow++
slow = 3, fast = 5, nums[3] = 4, nums[5] = 5,将5赋值给nums[4],slow++
slow = 4, fast = 6, nums[4] = 5, nums[6] = 6,将6赋值给nums[5],slow++
fast越界,结束循环,返回nums中的前slow + 1个元素:[1,2,3,4,5,6]所以最终输出是:[1,2.3.4.5.6]。
2.去除已排序数组中的相同的数字，只要相同则不保留
输入:[1、2、2，3，3，4，5，5]
输出:[1.4,6]
java
java
public int[] removeDuplicates(int[] nums) {
if (nums.length == 0) return nums;
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return Arrays.copyOf(nums, slow + 1);
}这个算法使用两个指针 slow 和 fast:- slow 指针遍历数组并保留不重复的元素。
- fast 指针 Used 扫描跳过所有重复元素。
- 每当 fast 遇到第一个不重复的元素时,我们将该元素赋值给 slow 指针,然后 slow 指针向前移动。
- 重复此过程,直到 fast 到达数组末尾。
- 最后返回 slow + 1 的长度的数组。时间复杂度:O(n),其中 n 是数组的长度。
空间复杂度:O(1)。对输入 [1,2,2,3,3,4,5,5],这个算法的过程是:slow = 0, fast = 0, nums[0] = 1, nums[0] = 1,将1赋值给nums[0],slow++
slow = 1, fast = 1, nums[1] = 2, nums[1] = 2, fast++(跳过重复元素)
slow = 1, fast = 3, nums[1] = 2, nums[3] = 3,将3赋值给nums[2],slow++
slow = 2, fast = 4, nums[2] = 3, nums[4] = 3,fast++(跳过重复元素)
slow = 2, fast = 5, nums[2] = 3, nums[5] = 4,将4赋值给nums[3],slow++
slow = 3, fast = 6, nums[3] = 4, nums[6] = 5, fast++(跳过重复元素)
fast越界,结束循环,返回nums中的前slow + 1个元素:[1,2,4]所以最终输出是:[1,4,6]。这道题目的关键点是遇到重复元素时,fast指针继续前移,而slow指针保持不变。这样重复元素就被“跳过”了,从而实现去重的效果。
3.2个相同类型的 List<User，从第一个 List中，去除第二个 List中包含第一个List的数据(id 相等则认为两个对象是一样的)，需要考虑性能。
public class Userf
private Integer id;
private String name:
private Integer age;
public static List<User> getList(List<User> userListl, List<User> userList2){
}使用 HashSet 实现,时间复杂度为 O(n),空间复杂度为 O(n)。代码如下:
java
public static List<User> getList(List<User> userList1, List<User> userList2){
Set<Integer> set = new HashSet<>();
for (User user : userList2) {
set.add(user.getId());
}
List<User> result = new ArrayList<>();
for (User user : userList1) {
if (!set.contains(user.getId())) {
result.add(user);
}
}
return result;
}这个算法的思路是:1. 遍历userList2,将所有id添加到HashSet中。
- 遍历userList1,如果当前用户的id不在HashSet中,则添加到结果列表中。
- 返回结果列表。这样就实现了从userList1中去除userList2中包含的用户。时间复杂度分析:- set添加元素时间复杂度为O(1),set包含元素查询时间复杂度为O(1),所以遍历userList2的时间复杂度为O(n)。
- 遍历userList1时间复杂度为O(m)。
- 所以总时间复杂度为O(n + m) = O(n)。空间复杂度为O(n),其中n为userList2的长度,对应set的大小。
4.数据库设计相关
学生表: student(学号,学生姓名,出生年月,性别)
成绩表:score(学号,课程号,成绩)
课程表:course(课程号,课程名称,教师号)
教师表:teacher(教师号,教师姓名)
4.1 查询每一位教师教了哪些课程，输出教师姓名、课程名称;
4.2 查询至少一门课程成绩小于 60 分学生的学号、姓名。
SELECT
teacher.teacher_name,
course.course_name
FROM
teacher
JOIN
course
ON
teacher.teacher_id = course.teacher_id
SELECT
student.student_id,
student.student_name
FROM
student
JOIN
score
ON
student.student_id = score.student_id
WHERE
score < 60
GROUP BY
student.student_id, student.student_name
HAVING
COUNT(score) > 0