【LeetCode】挑战100天 Day14（热题+面试经典150题）
【LeetCode】挑战100天 Day14（热题+面试经典150题）
- 一、LeetCode介绍
- 二、LeetCode 热题 HOT 100-16
- 2.1 题目
- 2.2 题解
- 三、面试经典 150 题-16
- 3.1 题目
- 3.2 题解
一、LeetCode介绍
LeetCode是一个在线编程网站，提供各种算法和数据结构的题目，面向程序员、计算机科学专业学生和技术爱好者等人群，旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目，因此它也是程序员面试准备的重要资源之一。
LeetCode上的问题涵盖了各种难度级别，从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案，LeetCode能够对结果进行评估并返回测试结果。
除了题目外，LeetCode还提供了讨论区、排行榜等社区功能，用户可以在这里交流学习心得、解决疑难问题，并与其他用户比较自己的做题成绩。
挑战100天 AI In LeetCode是基于LeetCode题库，借助AI的能力进行解题、并学习其解题过程。
二、LeetCode 热题 HOT 100-16
2.1 题目
最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 10^4
2.2 题解
本题可以使用双指针法解决最接近的三数之和问题的代码。时间复杂度为 O(n^2)，其中 n 是数组的长度。
解题思路：
- 对数组进行排序，以便于使用双指针法遍历数组。
- 初始化一个变量 diff，用于记录当前最接近的和与目标值的差距，初始值为无穷大。
- 遍历排序后的数组，固定一个数（假设为 nums[i]），并使用双指针法在剩余的元素中查找另外两个数，使它们的和最接近 target。
- 在双指针法中，设置左指针指向 i+1，右指针指向数组末尾。计算当前三个数的和 sum = nums[i] + nums[left] + nums[right]。
- 如果 sum == target，直接返回 target 作为最接近的和。
- 如果 sum 与 target 的差距小于 diff，更新 diff 和结果值 result。
- 如果 sum > target，将右指针左移一位。
- 如果 sum < target，将左指针右移一位。
- 遍历完所有可能的组合后，返回结果值 result。
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int diff = Integer.MAX_VALUE; // 初始差距设为最大值
int result = 0;
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return target;
}
if (Math.abs(sum - target) < diff) {
diff = Math.abs(sum - target);
result = sum;
}
if (sum > target) {
right--;
} else {
left++;
}
}
}
return result;
}
}
三、面试经典 150 题-16
数组 / 字符串
3.1 题目
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 10^5
3.2 题解
本题可以使用双指针法解决接雨水问题的代码。时间复杂度为 O(n)，其中 n 是数组的长度。
解题思路：
- 使用两个指针 left 和 right 分别指向数组的首尾。
- 初始化变量 leftMax 和 rightMax 为 0，用于记录左边和右边的最大高度。
- 初始化变量 ans 为 0，用于记录结果。
- 当 left 小于等于 right 时，进行以下操作：
- 如果 height[left] 小于等于 height[right]，表示左边的柱子较低，可以接到雨水。
- 如果 height[left] 大于等于 leftMax，更新 leftMax。
- 否则，将 ans 增加 leftMax 减去 height[left]，表示接到的雨水量。
- 将 left 右移一位。
- 如果 height[left] 大于 height[right]，表示右边的柱子较低，可以接到雨水。
- 如果 height[right] 大于等于 rightMax，更新 rightMax。
- 否则，将 ans 增加 rightMax 减去 height[right]，表示接到的雨水量。
- 将 right 左移一位。
- 如果 height[left] 小于等于 height[right]，表示左边的柱子较低，可以接到雨水。
- 最终返回 ans。
public class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int ans = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
ans += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
ans += rightMax - height[right];
}
right--;
}
}
return ans;
}
}
至此，挑战100天 AI In LeetCode Day14（热题+面试经典150题）完成，后续会持续调整；查阅过程中若遇到问题欢迎留言或私信交流。