企业官网建设流程全解析

哪里公司建设网站好,贵州省城乡和住房建设厅网站首页,长春本地网站制作,广州小程序开发今天写了四道题#xff01;尽管前两道很简单#xff08;所以没放到标题里面#xff09;。难度范围#xff1a;★~★★★#xff0c;昨天最后一道困难题是打击到我了#xff0c;但没关系#xff0c;我自己会从简单题中找安慰#xff08;倒#xff09;。 今天的主要收获…今天写了四道题尽管前两道很简单所以没放到标题里面。难度范围★~★★★昨天最后一道困难题是打击到我了但没关系我自己会从简单题中找安慰倒。今天的主要收获学到了单调栈的使用认识了tolower函数和emplace_back函数其实收获不止这些但我就是不知道怎么写出来下次一定写得面面俱到一.最大连续1的数 ★☆☆☆☆题目485. 最大连续 1 的个数 给定一个二进制数组nums 计算其中最大连续1的个数。思路遍历数组用count记录当前连续的1的个数res记录count的最大值当遍历到的数字为1时count反之使count0。代码class Solution { public: int findMaxConsecutiveOnes(vectorint nums) { int lennums.size(); int res0; int count0; for(int i0;ilen;i){ count nums[i]1 ? count1 : 0; res count res ? count : res; } return res; } };复杂度n为数组的长度时间复杂度O(n)。循环n次空间复杂度O(1)二.提莫攻击 ★☆☆☆☆题目495. 提莫攻击 在《英雄联盟》的世界中有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希编者注寒冰射手进入中毒状态。当提莫攻击艾希艾希的中毒状态正好持续duration秒。正式地讲提莫在t发起攻击意味着艾希在时间区间[t, t duration - 1]含t和t duration - 1处于中毒状态。如果提莫在中毒影响结束前再次攻击中毒状态计时器将会重置在新的攻击之后中毒影响将会在duration秒后结束。给你一个非递减的整数数组timeSeries其中timeSeries[i]表示提莫在timeSeries[i]秒时对艾希发起攻击以及一个表示中毒持续时间的整数duration。返回艾希处于中毒状态的总秒数。思路用pre记录前一次攻击的时间cur记录这一次攻击的时间如果两次攻击时间间隔duration前一次攻击造成的中毒持续时间仍为duration如果时间间隔duration前一次攻击造成的中毒持续状态为 两次攻击的时间间隔。注意最终的结果res要加上最后一次攻击造成的中毒持续时间duration代码class Solution { public: int findPoisonedDuration(vectorint timeSeries, int duration) { int lentimeSeries.size(); int res0; for(int i1;ilen;i){ int pretimeSeries[i-1]; int curtimeSeries[i]; if(cur-pre duration){ resduration; }else{ rescur-pre; } } //加上最后一次攻击的中毒时间 resduration; return res; } };复杂度n为数组长度时间复杂度O(n)空间复杂度O(1)三.下一个更大的元素 ★★☆☆☆☆题目496. 下一个更大元素 Inums1中数字x的下一个更大元素是指x在nums2中对应位置右侧的第一个比x大的元素。给你两个没有重复元素的数组nums1和nums2下标从0开始计数其中nums1是nums2的子集。对于每个0 i nums1.length找出满足nums1[i] nums2[j]的下标j并且在nums2确定nums2[j]的下一个更大元素。如果不存在下一个更大元素那么本次查询的答案是-1。返回一个长度为nums1.length的数组ans作为答案满足ans[i]是如上所述的下一个更大元素。思路1遍历数组nums1对nums1的每一个元素num都遍历数组nums2找到与之相等的元素的位置再对数组nums2的该位置之后的数组进行遍历找第一个比num大的元素。使用一个变量flag记录是否找到更大的元素如果找到了将其放入结果数组并置flag为1如果将对应位置之后的元素都遍历了flag仍为0说明没找到将-1加入ans中。最后返回ans即可。注意找到之后利用break及时返回避免找的更大的元素不是第一个以及避免找到与nums1[1]相等的元素之后的无效遍历。代码class Solution { public: vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint ans; int index0; //遍历两个数组 for(int i0;ilen1;i){ for(int j0;jlen2;j){ if(nums2[j]!nums1[i]){ continue; } int flag0;//标记是否找到更大的数 //找到和nums1[i]相等的nums2[j] //遍历j之后的数 for(int kj1;klen2;k){ //找第一个更大的数 if(nums2[k]nums2[j]){ ans.push_back(nums2[k]); flag1; break;//直接退出 } } //没找到记作-1 if(flag0){ ans.push_back(-1); } break;//继续nums1的下一个元素nums1[i1] } } return ans; } };复杂度m、n分别是两个数组nums1、nums2的长度时间复杂度O(mn)。虽然看起来有三层循环但是第三层和第二层循环次数加起来最大为n所有总的时间复杂度为O(mn)空间复杂度O(1)。思路2使用哈希表记录数组nums2的元素和索引查找num时可以之间找到对应索引。看起来好像方便但是不仅没有降低时间复杂度还增加了空间复杂度跪地代码class Solution { public: vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint ans; unordered_mapint,int map;//哈希表存储nums2的值 for(int i0;ilen2;i){ map[nums2[i]]i; } for(int i0;ilen1;i){ int jmap[nums1[i]]1;//找到nums2中数值为nums1[i]的数的下一个数的索引 int flag0;//标记是否找到更大的元素 while(jlen2){ if(nums2[j]nums1[i]){ //找到 ans.push_back(nums2[j]); flag1; break;//退出循环 } j; } if(flag0){ //没找到 ans.push_back(-1); } } return ans; } };复杂度m、n分别是两个数组nums1、nums2的长度时间复杂度O(m×n)空间复杂度O(n)。哈希表的空间。官方题解——单调栈哈希表 ★★★☆☆可以将问题分为两个子问题1.如何高效地找到第一个更大的元素2.如何保存第一个子问题的结果解答1.利用单调栈从后往前遍历数组nums2重复操作如果栈顶元素小于当前元素num则将栈顶元素移除并将当前元素num放入栈中。因为要找nums1的元素 num 在nums2中的位置之后的第一个比它大的数字记为x那么在num和x之间的数肯定比 x 小而在 x 之后的数即使比num大也不是第一个2.利用哈希表将元素值与其右边第一个更大的元素值的对应关系存入哈希表。3.在遍历数组nums2的时候就可以将哈希表初始化了如果遍历到元素num时栈为空说明右边没有更大的元素将该位置的哈希表的元素值置为0反之置为栈顶元素因为栈定元素是最靠近当前元素num的。相当于对nums2的所有元素都进行了找其右边第一个更大元素的操作最后再对nums1的元素利用哈希表查找即可。代码class Solution { public: vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { unordered_mapint,int map; stackint st; for(int inums2.size()-1;i0;--i){ int numnums2[i]; while(!st.empty() numst.top()){ st.pop(); } map[num]st.empty()?-1:st.top(); st.push(num); } vectorint ans(nums1.size()); for(int i0;inums1.size();i){ ans[i]map[nums1[i]]; } return res; } };复杂度m、n分别是两个数组nums1、nums2的长度时间复杂度O(mn) —— 遍历 nums2​ 以计算 nums2​ 中每个元素右边的第一个更大的值需要遍历 nums1​ 以生成查询结果空间复杂度O(n) —— 用于存储哈希表四.键盘行 ★★★☆☆题目500. 键盘行 给你一个字符串数组words只返回可以使用在美式键盘同一行的字母打印出来的单词。键盘如下图所示。请注意字符串不区分大小写相同字母的大小写形式都被视为在同一行。思路1.用三个字符串记录每一行的字母通过c的字符串.find()函数判断字符是否存在于字符串中2.通过遍历字符串数组的每一个字符串记录第一个字符所在的行对应的字符串 s遍历剩余字符如果不在同一行直接退出进行下一个字符串的判断。代码1有误class Solution { public: vectorstring findWords(vectorstring words) { vectorstring res;//结果数组 string s1qwertyuiopQWERTYUIOP; string s2asdfghjklASDFGHJKL; string s3zxcvbnmZXCVBNM; for(int i0;iwords.size();i){ string strwords[i]; string s; if(s1.find(str[0])! string::npos){ ss1; }else if(s2.find(str[0])! string::npos){ ss2; }else{ ss3; } for(int j1;jstr.size();j){ char chstr[j]; //和第一个字符不是同一行 if(s.find(ch) string::npos){ break; } //所有字符都是同一行放入结果数组 if(jstr.size()-1){ res.push_back(str); } } } return res; } };上诉代码遇到由单个字母组成的字符串时无法实现正确的处理所以还需要增加对特殊情况的处理代码2class Solution { public: vectorstring findWords(vectorstring words) { vectorstring res;//结果数组 string s1qwertyuiopQWERTYUIOP; string s2asdfghjklASDFGHJKL; string s3zxcvbnmZXCVBNM; for(int i0;iwords.size();i){ string strwords[i]; //当字符串长度为1时直接将其加入res if(str.size()1){ res.push_back(str); }else{ string s; if(s1.find(str[0])! string::npos){ ss1; }else if(s2.find(str[0])! string::npos){ ss2; }else{ ss3; } for(int j1;jstr.size();j){ char chstr[j]; //和第一个字符不是同一行 if(s.find(ch) string::npos){ break; } //所有字符都是同一行放入结果数组 if(jstr.size()-1){ res.push_back(str); } } } } return res; } };代码3增加了flag标志变量不满足条件时赋值为false遍历完每个单词后若仍为true将其加入resclass Solution { public: vectorstring findWords(vectorstring words) { vectorstring res;//结果数组 string s1qwertyuiopQWERTYUIOP; string s2asdfghjklASDFGHJKL; string s3zxcvbnmZXCVBNM; for(int i0;iwords.size();i){ string strwords[i]; string s; if(s1.find(str[0])! string::npos){ ss1; }else if(s2.find(str[0])! string::npos){ ss2; }else{ ss3; } bool flagtrue; for(int j1;jstr.size();j){ char chstr[j]; //和第一个字符不是同一行 if(s.find(ch) string::npos){ flagfalse; break; } } if(flag){ res.push_back(str); } } return res; } };复杂度n为字符串数组的长度即单词的个数m为单词的平均长度时间复杂度O(nm)空间复杂度O(1)代码4来自于豆包看了我的代码后给出的优化建议——创建哈希表存储class Solution { public: vectorstring findWords(vectorstring words) { vectorstring res;//结果数组 // 预先构建字符到行号的映射 unordered_mapchar, int char2row { {q,1},{w,1},{e,1},{r,1},{t,1},{y,1},{u,1},{i,1},{o,1},{p,1}, {Q,1},{W,1},{E,1},{R,1},{T,1},{Y,1},{U,1},{I,1},{O,1},{P,1}, {a,2},{s,2},{d,2},{f,2},{g,2},{h,2},{j,2},{k,2},{l,2}, {A,2},{S,2},{D,2},{F,2},{G,2},{H,2},{J,2},{K,2},{L,2}, {z,3},{x,3},{c,3},{v,3},{b,3},{n,3},{m,3}, {Z,3},{X,3},{C,3},{V,3},{B,3},{N,3},{M,3} }; // 查找行号只需 O(1) int row char2row[str[0]]; for(string word:words){ int firstchar2row[str[0]]; bool flagtrue; for(int j1;jword.size();j){ char chstr[j]; //和第一个字符不是同一行 if(char2row[ch]!first){ flagfalse; break; } //所有字符都是同一行放入结果数组 if(flag){ res.push_back(str); } } } return res; } };复杂度n为字符串数组的长度即单词的个数m为单词的平均长度时间复杂度O(nm)空间复杂度O(1)说明复杂度没变但是在不增加空间复杂度的前提下显著降低了时间复杂度的常数因子——复杂度数量级不变但实际运行速度大幅提升这也是哈希表在算法优化中的核心价值。官方题解为每一个字母标记行号记录为一个字符串rowIdx然后用字符-a获取到对应索引那么rowIdx[字符-a]就是这个字符对所在的行数。这里利用tolower函数将大写字母转换为对应的小写字母更方便所以对应字符的行数为rowIdx[tolower(word[0])-a]。记录第一个字符的行数first并用flag表示当前字符串的字符所在行数是否相同而后遍历每个字符得到其行数与first比较若不等flag变为false遍历完一个字符串后若flag仍为true说明该字符串的字符都在同一行将其放入结果字符串数组res。代码class Solution { public: vectorstring findWords(vectorstring words) { vectorstring res;//结果数组 string rowIdx 12210111011122000010020202; for(autoword:words){ bool isValidtrue; char idxrowIdx[tolower(word[0])-a]; for(int i0;iword.size();i){ if(rowIdx[tolower(word[i])-a]!idx){ isValidfalse; break; } } if(isValid){ res.emplace_back(word); } } return res; } };我的代码我自己理解之后写的代码class Solution { public: vectorstring findWords(vectorstring words) { vectorstring res;//结果数组 string rowIdx 12210111011122000010020202; for(int i0;iwords.size();i){ string wordwords[i]; //第一个字符的行数 int firstrowIdx[tolower(word[0])-a]; bool flagtrue; for(int j0;jword.size();j){ int currowIdx[tolower(word[j])-a]; if(cur!first){ flagfalse; break; } } if(flag){ res.push_back(word); } } return res; } };复杂度L 表示 words 中所有字符串的长度之和C 表示英文字母的个数在本题中英文字母的个数为 26时间复杂度O(L)空间复杂度O(C)push_back VS emplace_backemplace_back少了一次拷贝 / 移动效率更高