LeetCode hot 100 (12-16,自用2026.04.06)

LeetCode hot 100 (12-16,自用2026.04.06)53. 最大子数组和给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例 1输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。进阶如果你已经实现复杂度为O(n)的解法尝试使用更为精妙的分治法求解。思考第一反应是前缀和维护一个数组然后在看数组后一个减前一个的大于0贪心当前指针所指元素之前的和小于0丢弃当前元素之前的数列需要当前值之前和当前和最大和Kadane算法 动态规划算法最优子结构当前状态只取决于前一个位置的状态重叠子问题题解classSolution{publicintmaxSubArray(int[]nums){//初始化为 nums[0]而不是 0是为了避免全负数数组返回 0 的错误intpre0,maxAnsnums[0];for(intx:nums){//也就是每次都取《当前和》与《当前值》最大的那个做最优选择继续累加还是重新开始preMath.max(prex,x);//最大和取《当前和》和《原本最大值》中大的那个maxAnsMath.max(maxAns,pre);}returnmaxAns;}}56. 合并区间以数组intervals表示若干个区间的集合其中单个区间为intervals[i] [starti, endi]。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。示例 1输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].思路排序合并按区间起点从小到大排序判断上一个结尾第二个开头说明有重叠合并比较两个结尾哪个大就选哪个不重叠直接加入结果集题解classSolution{publicint[][]merge(int[][]intervals){// 1. 先按区间左端点排序Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0]));Listint[]resnewArrayList();// 2. 遍历每个区间for(int[]interval:intervals){// 如果结果集为空或者当前区间和结果集最后一个区间不重叠if(res.isEmpty()||res.get(res.size()-1)[1]interval[0]){res.add(interval);}else{// 有重叠合并更新最后一个区间的右端点res.get(res.size()-1)[1]Math.max(res.get(res.size()-1)[1],interval[1]);}}// 3. Listint[] 转成 int[][]returnres.toArray(newint[res.size()][]);}}189. 轮转数组给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。示例 1:输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]思路1.新建数组从后往前数k个开始复制到新数组然后再从头开始复制2.原地轮转题解classSolution{public void rotate(int[]nums,intk){intnnums.length;int[]tempnewint[n];for(inti0;in;i){temp[i]nums[(n-ki)%n];}for(inti0;in;i){nums[i]temp[i];}}}https://www.bilibili.com/video/BV12g411p7CC翻转三次数组classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;kk%n;reverse(nums,0,n-1);reverse(nums,0,k-1);reverse(nums,k,n-1);}publicvoidreverse(int[]nums,intstart,intend){while(startend){inttempnums[start];nums[start]nums[end];nums[end]temp;start;end--;}}}238. 除了自身以外数组的乘积给你一个整数数组nums返回 数组answer其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积 。题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。请 **不要使用除法**且在O(n)时间复杂度内完成此题。示例 1:输入: nums [1,2,3,4] 输出: [24,12,8,6]思路最简单的是双层循环但是这道题的要求是O(n)时间复杂度这个思路就不可行了那么除了自己元素的乘积可以是元素左边的乘积*右边的乘积再把这俩乘起来就行维护左乘积数组和右乘积数组还有结果数组循环三轮每轮都是O(n)的话满足时间复杂度要求的题解classSolution{publicint[]productExceptSelf(int[]nums){intlennums.length;int[]Lnewint[len];int[]Rnewint[len];int[]ansnewint[len];L[0]1;for(inti1;ilen;i){L[i]nums[i-1]*L[i-1];}R[len-1]1;for(intilen-2;i0;--i){R[i]nums[i1]*R[i1];}for(inti0;ilen;i){ans[i]L[i]*R[i];}returnans;}}41. 缺失的第一个正数给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。示例 1输入nums [1,2,0] 输出3 解释范围 [1,2] 中的数字都在数组中。思路第一思路绝对是哈希表先把元素存进去然后再循环contains直到最小的正整数……第二是优化法第一轮把负数都变为n1第二轮把正数下标的内容变为负值第三轮得到负数的下标1或者n1就是结果题解classSolution{publicintfirstMissingPositive(int[]nums){SetIntegersetnewHashSet();intnnums.length;for(inti0;in;i){set.add(nums[i]);}intans1;for(ans1;ansn;ans){if(!set.contains(ans)){break;}}returnans;}}优化classSolution{publicintfirstMissingPositive(int[]nums){intnnums.length;for(inti0;in;i){if(nums[i]0){nums[i]n1;}}for(inti0;in;i){if(nums[i]n){intnumMath.abs(nums[i]);if(numn){nums[num-1]-Math.abs(nums[num-1]);}}}for(inti0;in;i){if(nums[i]0){returni1;}}returnn1;}}