【LeetCode】挑战100天 Day13（热题+面试经典150题）

一、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 题解

解题思路：

可以使用双指针的方法来解决。首先对数组进行排序，然后固定一个数，再使用双指针在剩余的区间内查找满足条件的两个数。

具体步骤如下：

1. 对数组 nums 进行排序。
2. 遍历排序后的数组 nums，固定第一个数 nums[i]，将问题转化为在剩余的区间 [i+1, nums.length-1] 中寻找两个数，使得它们的和等于 -nums[i]。
3. 使用双指针 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。
4. 重复步骤 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 题解

解题思路：

可以使用贪心算法来解决，分别从左往右和从右往左遍历一遍，计算每个孩子能够获得的最小糖果数量。

具体做法如下：

1. 初始化一个长度为 n 的糖果数组 candy，每个元素初始化为 1。
2. 第一遍遍历：从左往右遍历一遍，如果右边的孩子评分比左边的高，那么右边的孩子应该比左边的孩子获得更多的糖果，因此将右边孩子的糖果数量更新为左边孩子的糖果数量加 1。
3. 第二遍遍历：从右往左遍历一遍，如果左边的孩子评分比右边的高，并且左边孩子当前的糖果数量不大于右边孩子的糖果数量，那么左边的孩子应该比右边的孩子获得更多的糖果，因此将左边孩子的糖果数量更新为右边孩子的糖果数量加 1。
4. 计算糖果总数：将每个孩子获得的糖果数量累加即可。

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题）完成，后续会持续调整；查阅过程中若遇到问题欢迎留言或私信交流。