网站建设和运维单位责任网站建设与管理和计算机网络技术

网站建设和运维单位责任,网站建设与管理和计算机网络技术,互动案例的网站,个人网站的设计与实现摘要今天又又是三道题#xff0c;难度范围#xff1a;★★~★★★。难度完全是凭个人做的感觉标的#xff0c;题还是得自己做了才知道。 100天也已经过1/4了#xff0c;非常之不错啊#xff0c;希望这些记录能让我对这些题的理解更深#xff0c;当然#xff0c;也希望能对你…今天又又是三道题难度范围★★~★★★。难度完全是凭个人做的感觉标的题还是得自己做了才知道。100天也已经过1/4了非常之不错啊希望这些记录能让我对这些题的理解更深当然也希望能对你们有所帮助。一.汇总区间 ★★★☆☆题目228. 汇总区间给定一个无重复元素的有序整数数组nums。区间[a,b]是从a到b包含的所有整数的集合。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说nums的每个元素都恰好被某个区间范围所覆盖并且不存在属于某个区间但不属于nums的数字x。列表中的每个区间范围[a,b]应该按如下格式输出a-b如果a ! ba如果a b思路这道题思路不难个人觉得难在如何表示要求的输出。1.区间思路在同一个区间的相邻数字之间肯定只能相差1所以只有相差为1的数字能保存在一个区间由此可以表示结果的区间。用low表示左边界high表示右边界当且仅当数字相差1时右边界才改变2.用临时字符串变量temp表示一个区间先将左边界nums[low]转换为字符串形式赋值给temp再根据low和high的大小决定temp的表示形式即若a ! btempa-b以及若a btempa。然后将temp放入res即可。PSres不用提前设定长度因为vector是动态数组支持自动扩容提前设定长度反而会增加冗余push_back会在尾部添加元素底层会根据需要自动分配内存代码class Solution { public: vectorstring summaryRanges(vectorint nums) { //1.创建结果动态数组res用于存储结果并返回 vectorstring res;//不用设定长度需要时vector会自动分配 int lennums.size(); int i0; while(ilen){ int lowi; i; while(ilen nums[i]nums[i-1]1){ i; } int highi-1; string tempto_string(nums[low]); if(lowhigh){ temptemp-to_string(nums[high]); } res.push_back(temp); } return res; } };官方代码使用了append增加字符串的内容res.push_back(move(temp))中使用了move函数。class Solution { public: vectorstring summaryRanges(vectorint nums) { //1.创建结果动态数组res用于存储结果并返回 vectorstring res;//不用设定长度需要时vector会自动分配 int lennums.size(); int i0; while(ilen){ int lowi; i; while(ilen nums[i]nums[i-1]1){ i; } int highi-1; string tempto_string(nums[low]); if(lowhigh){ temp.append(-); temp.append(to_string(nums[high])); } res.push_back(move(temp)); } return res; } };复杂度时间复杂度O(n)。遍历数组循环n次空间复杂度O(1)。辅助空间只有局部变量且都是常数级与问题规模无关。二.丢失的数字 ★★☆☆☆题目268. 丢失的数字 给定一个包含[0, n]中n个数的数组nums找出[0, n]这个范围内没有出现在数组中的那个数。思路数字范围[0,n]已确定利用sign数组作为范围内数字的存在标识即如果存在对应的sign位置为1反之为0。然后在0~n之间找出sign的值为0的数即为答案。代码int missingNumber(int* nums, int numsSize) { int* sign(int*)calloc(numsSize,sizeof(int)); if(signNULL){ return -1; } int resnumsSize; for(int i0;inumsSize;i){ if(nums[i]numsSize){ sign[nums[i]]1; } } for(int i0;inumsSize;i){ if(sign[i]0){ resi; break; } } free(sign); return res; }注意1.利用calloc申请空间并完成了初始化即将数组元素都赋值为0同时注意申请时要保证括号内对应的参数输入正确2.因为只给sign分配了numsSize个空间所以修改sign元素的值时所以也必须numsSize3.因为无论是遍历数组还是遍历sign范围都是0~numsSize-1所以res需要初始化为numsSize避免遗漏numsSize复杂度n数组长度时间复杂度O(n)。两次循环次数都为n且没有嵌套所以O(nn)O(2n)→O(n)。空间复杂度O(n)。动态数组sign元素个数n与问题规模n有关其余变量空间均与问题规模n无关。官方题解官方真是大显神通思路1——排序先对数组进行排序直接从0~n-1循环对应的nums[i]一定等于i不等于的地方i 就是丢失的数。同理也要先将res初始化为n避免循环时nums索引越界而漏掉这个数字。class Solution { public: int missingNumber(vectorint nums) { int nnums.size(); int resn;//------------------- sort(nums.begin(),nums.end()); for(int i0;in;i){ if(nums[i]!i){ resi; break; } } return res; } };思路2——哈希集合用哈希集合保存数组元素在0~n-1的范围内通过哈希集合的find函数查找没找到的数值就是丢失的数字。同理也要先将res初始化为n。class Solution { public: int missingNumber(vectorint nums) { int nnums.size(); unordered_setint s; int resn; for(int i0;in;i){ s.insert(nums[i]); } for(int i0;in;i){ if(s.find(i)s.end()){ resi; break; } } return res; } };思路3——按位异或异或逻辑与自身异或结果为0与0异或结果还是自身。所以是res与数组中所有元素的异或后在与0~n异或最后剩下的就是丢失的数字其他的数都与自身异或为0了。class Solution { public: int missingNumber(vectorint nums) { int nnums.size(); int res0; for(int i0;in;i){ res^nums[i]; } for(int i0;in;i){ res^i; } return res; } };思路4——数学用 0~n的数的总和 减去 数组元素的总和 的差就是丢失的数。可以使用循环同时计算数组元素总和以及0~n的总和class Solution { public: int missingNumber(vectorint nums) { int nnums.size(); int arrSum0; int sum0; for(int i0;in;i){ arrSumnums[i]; sumi; } sumn; return sum-arrSum; } };也可以先用高斯求和公式求0~n的和class Solution { public: int missingNumber(vectorint nums) { int n nums.size(); int total n * (n 1) / 2;//高斯求和公式 int arrSum 0; for (int i 0; i n; i) { arrSum nums[i]; } return total - arrSum; } };三.两个数组的交集 ★★★☆☆题目349. 两个数组的交集 给定两个数组nums1和nums2返回它们的 交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。思路先对两个数组进行排序这样数组里的数字相等的放在一起且整体是升序排列使得遍历比较更轻松。用temp记录连续相等的数字。第一层循环遍历数组1连续相等的数字中只有在第一个数字时才会进行对数组2的遍历当遍历到数组2中相等的数时赋值到res中并退出第二层循环避免再次遇到相等的数而重复赋值。最后返回res。代码class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint res;//不设定长度遇到符合条件的数自动加入即可 //先排序 sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); //在nums1中找不同的数判断nums2中是否有有就加入res int temp-1; for(int i0;ilen1;i){ if(tempnums1[i]){ continue;//相同的数直接进行下一次循环 } tempnums1[i]; for(int j0;jlen2;j){ if(nums2[j]temp){ res.push_back(temp); break; } } } return res; } };复杂度两个数组长度分别为n、m时间复杂度O(n*m)。排序算法O(nlognmlogm)第一层循环O(n)第二层循环O(m)所以总的时间复杂度为O(nlognmlogmn×m) ≈ O (n × m)空间复杂度O(lognlogm)。排序算法O(lognlogm)res属于输出空间不参与计算所以算法的空间复杂度为O(lognlogm)思路2利用哈希集合一个哈希集合s1存储第一个数组的值一个哈希集合s2存储结果数组的值。将第一个数组的值存入第一个哈希集合后遍历第二个数组的值存在于s1中的数就是两个数组都有的值但是只有不在s2中的才能存入res因为要保证res中的数无重复。代码class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint res; //用两个集合存储 unordered_setint s1;//保存第一个数组 unordered_setint s2;//记录结果数组中的值 //分别将数组元素存入 for(int i0;ilen1;i){ s1.insert(nums1[i]); } for(int i0;ilen2;i){ //在第一个数组中但是不在结果数组中 //先判断s2中有没有 //再判断s1中 if(s2.find(nums2[i])s2.end()){ if(s1.find(nums2[i])!s1.end()){ res.push_back(nums2[i]); s2.insert(nums2[i]); } } } return res; } };思路3利用双指针实现。先将两个数组的数排序在用p、q分别代表指向两个数组的指针这里是整型表示索引相当于指针指向对应的元素。用pre表示前一个存入结果数组res的值当p和q指向的数相等且不等于pre时改变pre并存入res中不相等时移动指向较小数的指针。代码class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint res; //排序 //双指针记录 //pre记录前一个res的值 sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); int p0,q0; int pre-1; while(plen1 qlen2){ if(nums1[p]nums2[q] nums1[p]!pre){ prenums1[p]; res.push_back(pre); p; q; }else if(nums1[p]nums2[q]){ p; }else{ q; } } return res; } };官方代码在两个数相等时如果res为空( ! res.size() )或者当前的数不等于res最后一个元素( nums1[p]!res.back() )时可以存入res反之指向较小数的一个向后移动。class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint res; //排序 //双指针记录 sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); int p0,q0; while(plen1 qlen2){ if(nums1[p]nums2[q]){ if(!res.size() || nums1[p]!res.back()){ res.push_back(nums1[p]); } p; q; }else if(nums1[p]nums2[q]){ p; }else{ q; } } return res; } };