【LeetCode】挑战100天 Day13（热题+面试经典150题）
【LeetCode】挑战100天 Day13（热题+面试经典150题）
- 一、LeetCode介绍
- 二、LeetCode 热题 HOT 100-15
- 2.1 题目
- 2.2 题解
- 三、面试经典 150 题-15
- 3.1 题目
- 3.2 题解
一、LeetCode介绍
LeetCode是一个在线编程网站，提供各种算法和数据结构的题目，面向程序员、计算机科学专业学生和技术爱好者等人群，旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目，因此它也是程序员面试准备的重要资源之一。
LeetCode上的问题涵盖了各种难度级别，从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案，LeetCode能够对结果进行评估并返回测试结果。
除了题目外，LeetCode还提供了讨论区、排行榜等社区功能，用户可以在这里交流学习心得、解决疑难问题，并与其他用户比较自己的做题成绩。
挑战100天 AI In LeetCode是基于LeetCode题库，借助AI的能力进行解题、并学习其解题过程。
二、LeetCode 热题 HOT 100-15
2.1 题目
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 10^5
2.2 题解
解题思路：
可以使用双指针的方法来解决。首先对数组进行排序，然后固定一个数，再使用双指针在剩余的区间内查找满足条件的两个数。
具体步骤如下：
- 对数组 nums 进行排序。
- 遍历排序后的数组 nums，固定第一个数 nums[i]，将问题转化为在剩余的区间 [i+1, nums.length-1] 中寻找两个数，使得它们的和等于 -nums[i]。
- 使用双指针 left 和 right 分别指向区间的两端，计算当前的和 sum = nums[i] + nums[left] + nums[right]。
- 如果 sum 等于 0，则将 [nums[i], nums[left], nums[right]] 添加到结果列表中，并同时将 left 和 right 分别向右和向左移动，跳过重复的元素。
- 如果 sum 小于 0，则将 left 向右移动一位，增大 sum。
- 如果 sum 大于 0，则将 right 向左移动一位，减小 sum。
- 重复步骤 2 和步骤 3，直到 left 和 right 相遇或者超出边界。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
if (n < 3) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
}
三、面试经典 150 题-15
数组 / 字符串
3.1 题目
分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 10^4
3.2 题解
解题思路：
可以使用贪心算法来解决，分别从左往右和从右往左遍历一遍，计算每个孩子能够获得的最小糖果数量。
具体做法如下：
- 初始化一个长度为 n 的糖果数组 candy，每个元素初始化为 1。
- 第一遍遍历：从左往右遍历一遍，如果右边的孩子评分比左边的高，那么右边的孩子应该比左边的孩子获得更多的糖果，因此将右边孩子的糖果数量更新为左边孩子的糖果数量加 1。
- 第二遍遍历：从右往左遍历一遍，如果左边的孩子评分比右边的高，并且左边孩子当前的糖果数量不大于右边孩子的糖果数量，那么左边的孩子应该比右边的孩子获得更多的糖果，因此将左边孩子的糖果数量更新为右边孩子的糖果数量加 1。
- 计算糖果总数：将每个孩子获得的糖果数量累加即可。
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candy = new int[n];
Arrays.fill(candy, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candy[i] = candy[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
candy[i] = candy[i + 1] + 1;
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += candy[i];
}
return sum;
}
}
至此，挑战100天 AI In LeetCode Day13（热题+面试经典150题）完成，后续会持续调整；查阅过程中若遇到问题欢迎留言或私信交流。