辽宁智能网站建设推荐,WordPress到底好不好用,微网站建设合同,html制作网站的步骤挑战100天 AI In LeetCode Day02#xff08;2#xff09; 一、LeetCode介绍二、LeetCode 热题 HOT 100-42.1 题目2.2 题解 三、面试经典 150 题-43.1 题目3.2 题解 一、LeetCode介绍 LeetCode是一个在线编程网站#xff0c;提供各种算法和数据结构的题目#xff0c;面向程序… 挑战100天 AI In LeetCode Day022 一、LeetCode介绍二、LeetCode 热题 HOT 100-42.1 题目2.2 题解 三、面试经典 150 题-43.1 题目3.2 题解 一、LeetCode介绍 LeetCode是一个在线编程网站提供各种算法和数据结构的题目面向程序员、计算机科学专业学生和技术爱好者等人群旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目因此它也是程序员面试准备的重要资源之一。
LeetCode上的问题涵盖了各种难度级别从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案LeetCode能够对结果进行评估并返回测试结果。
除了题目外LeetCode还提供了讨论区、排行榜等社区功能用户可以在这里交流学习心得、解决疑难问题并与其他用户比较自己的做题成绩。
挑战100天 AI In LeetCode是基于LeetCode题库借助AI的能力进行解题、并学习其解题过程。
二、LeetCode 热题 HOT 100-4
2.1 题目
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (mn)) 。示例 1输入nums1 [1,3], nums2 [2]
输出2.00000
解释合并数组 [1,2,3] 中位数 2
示例 2输入nums1 [1,2], nums2 [3,4]
输出2.50000
解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5提示nums1.length m
nums2.length n
0 m 1000
0 n 1000
1 m n 2000
-106 nums1[i], nums2[i] 1062.2 题解
该算法的时间复杂度为 O(m n)其中 m 和 n 分别为两个数组的长度。合并两个数组的过程需要遍历所有元素。由于题目要求算法的时间复杂度为 O(log (mn))所以还可以使用更高级的算法如二分查找来解决这个问题。但在本例中是给出了一个时间复杂度为 O(m n) 的简单解法。
解题思路
首先我们可以将两个数组合并成一个有序数组。由于两个数组本身就是有序的合并过程可以使用双指针法进行。创建一个新的数组 merged用于存储合并后的结果。初始化两个指针 p1 和 p2 分别指向两个数组的起始位置。比较 nums1[p1] 和 nums2[p2] 的大小 如果 nums1[p1] nums2[p2]将 nums1[p1] 加入到 merged 中并将 p1 向后移动一位。如果 nums1[p1] nums2[p2]将 nums2[p2] 加入到 merged 中并将 p2 向后移动一位。 重复步骤 4直到其中一个数组遍历完毕。将剩余未遍历完的数组的元素添加到 merged 中。计算 merged 的长度 len。 如果 len 是奇数则中位数为 merged[len / 2]。如果 len 是偶数则中位数为 (merged[len / 2 - 1] merged[len / 2]) / 2.0。 返回计算得到的中位数。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m nums1.length;int n nums2.length;int[] merged new int[m n];int p1 0; // 指针指向 nums1int p2 0; // 指针指向 nums2int idx 0; // 合并数组的索引while (p1 m p2 n) {if (nums1[p1] nums2[p2]) {merged[idx] nums1[p1];} else {merged[idx] nums2[p2];}}while (p1 m) {merged[idx] nums1[p1];}while (p2 n) {merged[idx] nums2[p2];}int len merged.length;if (len % 2 0) {return (merged[len / 2 - 1] merged[len / 2]) / 2.0;} else {return merged[len / 2];}
}三、面试经典 150 题-4 数组 / 字符串 3.1 题目
删除有序数组中的重复项 II
给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。说明为什么返回数值是整数但输出的答案是数组呢请注意输入数组是以「引用」方式传递的这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下:// nums 是以“引用”方式传递的。也就是说不对实参做任何拷贝
int len removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i 0; i len; i) {print(nums[i]);
}示例 1输入nums [1,1,1,2,2,3]
输出5, nums [1,1,2,2,3]
解释函数应返回新长度 length 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2输入nums [0,0,1,1,1,1,2,3,3]
输出7, nums [0,0,1,1,2,3,3]
解释函数应返回新长度 length 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。提示1 nums.length 3 * 104
-104 nums[i] 104
nums 已按升序排列3.2 题解
时间复杂度为 O(n)其中 n 为数组长度遍历整个数组一次即可完成操作而算法的空间复杂度为 O(1)不需要额外的存储空间。
解题思路
由于题目要求我们在原地修改数组所以不能使用额外的空间来存储新的数组。我们可以使用两个指针来完成这个操作其中一个指针 i 指向原数组的当前元素另一个指针 j 指向最后一个不重复的元素。我们遍历整个数组对于每个元素我们检查它是否与前面的元素相同
如果不相同则将其添加到新的数组中并将 j 指针向后移动一位。如果相同则判断该元素是不是已经出现了两次 如果是则跳过该元素不将其添加到新的数组中。如果不是则将其添加到新的数组中并将 j 指针向后移动一位。 最后返回 j 1即为新数组的长度。
public int removeDuplicates(int[] nums) {if (nums null || nums.length 0) {return 0;}int j 1;int count 1; // 记录当前数字出现的次数for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1]) {count;} else {count 1;}if (count 2) {nums[j] nums[i];}}return j;
}至此挑战100天 AI In LeetCode Day022完成后续会持续调整查阅过程中若遇到问题欢迎留言或私信交流。
