Leetcode普通数组-day5、6

Leetcode普通数组-day5/6记录自己刷力扣备战秋招的刷题笔记❤️​ ——wosz普通数组普通数组没什么需要说的其实最简单的办法就是遍历因为普通数组它是连续的因此不会涉及到很复杂的算法。因为是遍历嘛我们就可以用到我们前面学习过的一些方法如双指针去减少遍历次数滑动窗口去实习相对应的数组处理最大子数组和给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。**输入**nums [-2,1,-3,4,-1,2,1,-5,4]**输出**6**解释**连续子数组 [4,-1,2,1] 的和最大为 6 。自己题解classSolution{public:intmaxSubArray(vectorintnums){intnum_sizenums.size();intcur0;// 当前前缀和intmin_prevalue0;// 到当前位置之前最小的前缀和inttagnums[0];for(inti0;inum_size;i){curnums[i];//计算当前前缀和if(tagcur-min_prevalue)//当前前缀和减去之前最小前缀和{tagcur-min_prevalue;}if(curmin_prevalue){min_prevaluecur;}}returntag;}};我的思路受到前面做到一个关于子串的题是用的前缀和的方式这道题我想了一下感觉可以使用前缀和来解决。我们用当前前缀和减去之前最小前缀和就表示以当前位置结尾的最大子数组和。遍历一遍后取最大值即可。我一开始还想错了直接使用最大减去最小还去进行分段讨论呢官方题解classSolution{public:intmaxSubArray(vectorintnums){intpre0,maxAnsnums[0];for(constautox:nums){premax(prex,x);maxAnsmax(maxAns,pre);}returnmaxAns;}};官方我选取的是采用动态规划的题解因为我本人也没有学习过动态规划就趁机再学习一下动态规划。dp[i] 表示以nums[i]结尾的连续子数组的最大和。此时我们的考虑就是两种一种是1.前面的dp[i-1]nums[i]就是此时的dp 2.从自己开始num[i] (前面的和可能是负贡献)dp[i] max(dp[i-1] nums[i], nums[i])补充动态规划因为后面还会再次学所以这里我就大概简单先了解一下方便理解本题的动态规划解法动态规划从初始状态出发到经过一系列的状态转移到达目标状态的最优解。同时具有条件状态转移必须有方向同时整体不能成环状状态的个数必须要在可接收的范围内解题的几个重点dp数组就是表示状态要知道具体的下标是什么意思递推公式dp数组初始化遍历的一个顺序合并区间以数组intervals表示若干个区间的集合其中单个区间为intervals[i] [starti, endi]。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。**输入**intervals [[1,3],[2,6],[8,10],[15,18]]输出[[1,6],[8,10],[15,18]]**解释**区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]自己题解classSolution{public:vectorvectorintmerge(vectorvectorintintervals){intnum_sizeintervals.size();sort(intervals.begin(),intervals.end());//先排序vectorvectorinttag;inttemp_endintervals[0][1];inttemp_startintervals[0][0];intindex10,index21;while(index2num_size){//判断if(intervals[index2][0]temp_end)//必定出现重合{if(temp_endintervals[index2][1]){temp_endintervals[index2][1];}if(temp_startintervals[index2][0]){temp_startintervals[index2][0];}}else{//出现不重合此时直接添加到结果同时移动index1tag.push_back({temp_start,temp_end});index1index2;temp_endintervals[index1][1];temp_startintervals[index1][0];}//扩张index2;}tag.push_back({temp_start,temp_end});//er:最后一个没有放returntag;}};我的思路其实我就准备使用双指针来解决先进行排序然后让 index1 去指向合并区间的起点让 index2 去不断扩张然后同时用值去记录当前和合并区间的末尾方便判断。之后如果遇到不可以可以合并的就将已经合并的添加到结果中去同时让 index1 直接移动到 index2 处让index2继续扩张持续。官方题解classSolution{public:vectorvectorintmerge(vectorvectorintintervals){if(intervals.size()0){return{};}sort(intervals.begin(),intervals.end());vectorvectorintmerged;for(inti0;iintervals.size();i){intLintervals[i][0],Rintervals[i][1];if(!merged.size()||merged.back()[1]L){merged.push_back({L,R});}else{merged.back()[1]max(merged.back()[1],R);}}returnmerged;}};思路是一致的都是先对数组进行排序然后比较首尾进行判断合并区间。轮转数组给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。输入: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]自己题解classSolution{public:voidrotate(vectorintnums,intk){intnum_sizenums.size();vectorintnew_num(num_size,0);for(inti0;inum_size;i){inttemp(ik)%num_size;new_num[temp]nums[i];}//再来赋值for(inti0;inum_size;i){nums[i]new_num[i];}}};我的思路我感觉我有点苯我的想法就是新开一个数组然后直接进行位移进去就行我就是用求余的形式来进行按照indexk-1%size来进行位移计算就可以了。最后再来一次遍历就行确实感觉有点蠢了但是胜在简单啊。官方题解classSolution{public:voidreverse(vectorintnums,intstart,intend){while(startend){swap(nums[start],nums[end]);start1;end-1;}}voidrotate(vectorintnums,intk){k%nums.size();reverse(nums,0,nums.size()-1);reverse(nums,0,k-1);reverse(nums,k,nums.size()-1);}};官方的方法我就学习一下翻转法这个翻转法的意思就是多次翻转就可以实现数组的轮转大致的思路就是下面这样除了自身以外的数组乘积给你一个整数数组nums返回 数组answer其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积 。题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。请 **不要使用除法**且在O(n)时间复杂度内完成此题。输入:nums [1,2,3,4]输出:[24,12,8,6]自己题解classSolution{public:vectorintproductExceptSelf(vectorintnums){intnum_sizenums.size();vectorintmy_v(num_size,1);intpre1;//前缀积//先计算前缀积for(inti0;inum_size;i){my_v[i]pre;pre*nums[i];}intlast1;//后缀积//计算后缀积for(intinum_size-1;i0;i--){my_v[i]*last;last*nums[i];}returnmy_v;}};我的思路拿到这道题之后自然而然的想到了两种方法1.直接所有乘起来然后依次除以每一个元素当然这道题不能用 2.直接暴力for循环进行判断一下这个下标条件即可当然不出意外我们这个的复杂度不满足会超出时间限制让AI给我提供了一下新思路就是前缀积和后缀积tag[i]前缀积*后缀积官方的题解classSolution{public:vectorintproductExceptSelf(vectorintnums){intlengthnums.size();// L 和 R 分别表示左右两侧的乘积列表vectorintL(length,0),R(length,0);vectorintanswer(length);// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 0 的元素因为左侧没有元素所以 L[0] 1L[0]1;for(inti1;ilength;i){L[i]nums[i-1]*L[i-1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 length-1 的元素因为右侧没有元素所以 R[length-1] 1R[length-1]1;for(intilength-2;i0;i--){R[i]nums[i1]*R[i1];}// 对于索引 i除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for(inti0;ilength;i){answer[i]L[i]*R[i];}returnanswer;}};最经典的解法就是前缀积和后缀积这道题官方给出的也是这个解法进行的前缀积和后缀积的形式。缺失的第一个正数给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。**输入**nums [1,2,0]**输出**3**解释**范围 [1,2] 中的数字都在数组中。我的题解classSolution{public:intfirstMissingPositive(vectorintnums){intnum_sizenums.size();unordered_mapint,intmap;inttag1;intflag0;for(inti0;inum_size;i){map[nums[i]]i;}//查找while(flag0){if(map.find(tag)!map.end()){tag;}else{flag1;}}returntag;}};我看到这个题的时候首先想到的就是哈希表查询然后时间复杂度应该是满足的但是空间不是常数级别。还想到一个就是先对数组进行排序之后利用双指针进行滑动应该也可以的。然后让AI大哥帮我修改了一下就用classSolution{public:intfirstMissingPositive(vectorintnums){intnnums.size();// 第一步把无关数字变成 n1// 因为我们只关心 1~nfor(inti0;in;i){if(nums[i]0||nums[i]n){nums[i]n1;}}// 第二步用下标做标记// 如果数字 x 出现过就把 nums[x-1] 标记成负数for(inti0;in;i){intxabs(nums[i]);if(x1xn){nums[x-1]-abs(nums[x-1]);}}// 第三步找第一个没被标记的位置for(inti0;in;i){if(nums[i]0){returni1;}}returnn1;}};因为我们要找到的是一个1~n之间所以直接把无关的数组变为n1之后就在原地实现桶的功能不用新开哈希表。官方题解classSolution{public:intfirstMissingPositive(vectorintnums){intnnums.size();for(intnum:nums){if(num0){numn1;}}for(inti0;in;i){intnumabs(nums[i]);if(numn){nums[num-1]-abs(nums[num-1]);}}for(inti0;in;i){if(nums[i]0){returni1;}}returnn1;}};这个官方的题解就是主要采用的原地桶查找和我们上面让AI修改的大致是一样的思路。我们对数组进行遍历对于遍历到的数 x如果它在[1,N]的范围内那么就将数组中的第x−1个位置注意数组下标从 0 开始打上「标记」。在遍历结束之后如果所有的位置都被打上了标记那么答案是N1否则答案是最小的没有打上标记的位置加 1。就是先将无关的数组去掉然后利用nums充当标记即可。