【LeetCode】挑战100天 Day09(热题+面试经典150题)
- 一、LeetCode介绍
- 二、LeetCode 热题 HOT 100-11
- 2.1 题目
- 2.2 题解
- 三、面试经典 150 题-11
- 3.1 题目
- 3.2 题解
一、LeetCode介绍
LeetCode是一个在线编程网站,提供各种算法和数据结构的题目,面向程序员、计算机科学专业学生和技术爱好者等人群,旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目,因此它也是程序员面试准备的重要资源之一。
LeetCode上的问题涵盖了各种难度级别,从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案,LeetCode能够对结果进行评估并返回测试结果。
除了题目外,LeetCode还提供了讨论区、排行榜等社区功能,用户可以在这里交流学习心得、解决疑难问题,并与其他用户比较自己的做题成绩。
挑战100天 AI In LeetCode是基于LeetCode题库,借助AI的能力进行解题、并学习其解题过程。
二、LeetCode 热题 HOT 100-11
2.1 题目
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明:你不能倾斜容器。示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。示例 2:输入:height = [1,1]
输出:1提示:n == height.length
2 <= n <= 105
0 <= height[i] <= 104
2.2 题解
解题思路:
- 使用双指针法,将左指针指向数组开头,右指针指向数组末尾。
- 计算当前两条线之间的高度,并计算当前容器的水量,更新最大水量值。
- 移动左右指针:若左指针对应的高度小于右指针对应的高度,则将左指针右移;否则将右指针左移。
- 重复步骤2和3,直到左右指针相遇。
这种方法的关键在于每次移动指针时,都选择移动较短边,因为如果移动较长边,容器的宽度一定会减小,而容器的高度又不能增加,因此容器的面积一定会减小。而移动较短边,由于容器的宽度减小,所以只有在高度增加的情况下才可能得到更大的面积。
public int maxArea(int[] height) {int maxArea = 0;int left = 0; // 左指针int right = height.length - 1; // 右指针while (left < right) {int h = Math.min(height[left], height[right]); // 计算当前两条线之间的高度maxArea = Math.max(maxArea, h * (right - left)); // 计算当前容器的水量并更新最大值if (height[left] < height[right]) {left++; // 移动左指针} else {right--; // 移动右指针}}return maxArea;}
三、面试经典 150 题-11
数组 / 字符串
3.1 题目
H 指数
给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值,h 指数 是其中最大的那个。示例 1:输入:citations = [3,0,6,1,5]
输出:3
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3, 0, 6, 1, 5 次。由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3。
示例 2:输入:citations = [1,3,1]
输出:1提示:n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
3.2 题解
这道题可以通过对研究者的论文引用次数进行排序,并找到满足条件的最大 h 值来解决。
解题思路:
我们首先对研究者的引用次数数组进行排序。然后,我们从数组末尾开始遍历,对于每个位置 i,我们计算出当前引用次数大于或等于剩余论文篇数的数量,如果满足这个条件,就更新 h 的值为当前的 count 值。最终得到的 h 就是研究者的 h 指数。
- 对研究者的引用次数数组进行排序,这样可以更方便地找出满足条件的 h 值。
- 从数组末尾开始遍历,用一个变量 count 记录当前引用次数大于或等于剩余论文篇数的数量。
- 如果当前引用次数大于或等于 count,就更新 h 值为当前的 count 值。
- 最终得到的 h 就是研究者的 h 指数。
public int hIndex(int[] citations) {Arrays.sort(citations);int h = 0;for (int i = citations.length - 1; i >= 0; i--) {int count = citations.length - i;if (citations[i] >= count) {h = count;} else {break;}}return h;}
至此,挑战100天 AI In LeetCode Day09(热题+面试经典150题)完成,后续会持续调整;查阅过程中若遇到问题欢迎留言或私信交流。