个人网站建设技术百度扫一扫

当前位置： 首页 > news >正文

个人网站建设技术,百度扫一扫,相机拍照的图片怎么做网站呀,网络营销是什么工作目录 模拟算法 1.模拟算法流程#xff08;一定要在草稿纸上演算一遍流程#xff09; 2.把流程转换成代码

1. 替换所有的问号#xff08;easy#xff09; 解析#xff1a; 1.暴力#xff1a; 2.优化#xff1a;#xff08;找规律#xff09; 总结#xff1a; …目录 模拟算法 1.模拟算法流程一定要在草稿纸上演算一遍流程 2.把流程转换成代码
2. 替换所有的问号easy 解析 1.暴力 2.优化找规律 总结
3. 提莫攻击easy 解析 1.暴力 2.优化
4. N 字形变换medium 解析 1暴力 2优化 总结
5. 外观数列 (medium) 解析 1暴力 2优化小demo 总结
6. 数⻘蛙medium 解析 1暴力 2优化 总结 模拟算法 特点就是思路比较简单特别考验的是如何把里路转换成代码的能力。 1.模拟算法流程一定要在草稿纸上演算一遍流程 2.把流程转换成代码 相对来说模拟题读题就知道是跟着题目的意思一步一步走但是但凡觉得只是暴力求解时间复杂度和空间复杂度太高了那么就要转换思想去找规律。模拟题的优化就是不断的找规律。 1. 替换所有的问号easy 就是遍历整个字符串然后替换里面的所有 ? 但是不能存在重复的字符。 解析 1.暴力 我开始第一次做的时候就是创建了心得字符串str然后每次再遇到不是? 的时候就加入是就改变这个字符但是在这之前为了保证字符不连续重复我就用a和b来分别定义字符串中没有出现过的字符然后用下标奇偶的关系就可以保证ab交错不连续重复。 class Solution { public:string modifyString(string _s) {string s;unordered_mapchar,int hash;for(auto e : _s) if(e!?) hash[e];char aa,ba;while(hash[a]) a; hash[a];while(hash[b]) b;int i1;for(auto e : _s){if(e!?) se;else{if(i%20) sa;else sb;}i;}return s;} }; 2.优化找规律 线性时间复杂度而且空间复杂度为O(1)只在原来的字符串s上进行修改那么时间复杂度很低O(N)只需要早原串的基础上进行修改就行。 class Solution { public:string modifyString(string s) {int ns.size();for(int i0;in;i){if(s[i]?){for(char cha;chz;ch){if((i0||ch!s[i-1])(in-1||ch!s[i1])){s[i]ch;break;}}}}return s;} }; 总结 像这种模拟题就要尽可能的想到简便的办法来进行优化其实很简单。 2. 提莫攻击easy 这题题意很简单就是再中毒时间内如果继续被攻击那么就刷新中毒时间从头开始那么只需要计算数组每两个数之间的间隙大小是否大于中毒时间即可。 解析 1.暴力 想暴力就是求出每个时间间隔然后再与中毒时间进行比较小于中毒时间的就只加上这个间隙否者就加上完整的中毒时间。 2.优化 根据题目意思就是要看判断再你的下一次攻击时对方是否再中毒期间如果是那么就要进行重置就只要加上从上一次中毒到这次中毒的间隙若这个间隙大于或等于中毒时间那么就只能加上这个中毒时间即可最后遍历完整个数组后就再加上最后一次的中毒时长就是最后的结果其实跟暴力没啥区别。 class Solution { public:int findPoisonedDuration(vectorint timeSeries, int duration) {int ret0;int ntimeSeries.size();for(int i0;in-1;i){int atimeSeries[i1]-timeSeries[i];if(aduration) retduration;else reta;}return retduration;} }; 3. N 字形变换medium 题意就是将字符串按照给出的行数形成N行大小的Z字形然后一行一行的读出字符再进行输出。 解析 1暴力 暴力肯定最开始想到就是按照字符串的下标顺序来进行存入二维数组里面比如这个字符串按照下标开始存入二维数组的第一列然后再开始斜边存入再存入第二列再次斜边存入等接下来存完整个二维数组时间复杂度和空间复杂度都达到O(N^2)但是这题数据量小可以试试还是能过的但是这种办法我想这就头疼。必须要优化一下 2优化 那么说是优化其实就是找规律模拟现根据题目意思进行模拟运算比如创建一个二维数组来分别进行填入字符串的每一位但是这一不管是时间复杂度还是空间复杂度都是O(N^2)都太过于复杂 那么就要对他进行优化对于模拟题优化都是采用找规律的形式 1首先看第一行每两个数字之间都是由一个公差来决定的那么就要想办法求出公差公差就是两倍的行数减去2或者就是二维矩阵行数-1*2得到公差 2那么最后一行同样是由一个公差来得到。 3那么其间的k行[1,n-1]行就都是由两个数来分别公差d来组成的第一个数就是k行的首元素第二个数就是 d-k 为下标的元素 class Solution { public:string convert(string s, int numRows) {int ns.size();if(numRows1) return s;string ret;//第一行//求公差int dnumRows*2-2;int prelude0;while(preluden) rets[prelude],preluded;//中间行for(int k1;knumRows-2;k){for(int ik,jd-k;in||jn;id,jd){if(in) rets[i];if(jn) rets[j];}}//最后一行int knumRows-1;while(kn) rets[k],kd;return ret;} }; 总结 对于这种题目有点复杂的模拟就一定要耐心找到规律就会变得很简单重点就是如何把规律变成代码的形式。 4. 外观数列 (medium) 这题相对来说真的比较简单了只要理解题目意思真的模拟起来so easy~ 题目就是说按照读法生成下一个字符串 1 - 1个1 - 11 那么11 - 2个1 - 21等 解析 1暴力 暴力下就是不停的求出每一个次数条件下的字符串其实优化也大差不差都是再while里进行。 2优化小demo 就是要再while外面记录s每次循环一次们都要记录s最后返回s。再就是在while里面要记住每次循环完都要swap(ret,str) ,这样能保证ret每次都是要更新的新字符串str每次都是上一次的字符串。 模拟这个字符串生成的规律设置三个字符串每次都更新str用双指针left和right来记录重复的字符并更新到ret里面然后每次当right走到结尾时候就把ret赋值给s并且交换ret跟str来达到再次更新的目的最后返回s即可。 class Solution { public:string countAndSay(int _n) {string ret;string strto_string(1);if(_n1) return str;string s;while(–_n){int nstr.size();for(int left0,right0;rightn;right){if(str[left]!str[right]){retto_string(right-left);retstr[left];leftright;}if(rightn-1){retto_string(right-left1);retstr[left];}}sret;swap(str,ret);ret.clear();}return s;} }; 总结 有些比较简单的模拟真的一眼就能只知道怎么写可能这就是提升吧。 5. 数⻘蛙medium 题目意思就是用最少的青蛙喊出最长的字符串并且要满足croak 并且顺序要正确才行。 解析 1暴力 这题如果想不上优化那还真有点暴力5个else if() 来判断条件判断前面是否有字符存在满足条件是我当前字符的前一个如果是就继续不是就直接返回-1 2优化 首先就是解决5个else if()的问题可以用一个unordered_mapchar,int index;来将字符串装起来将字符串的字符与下标进行映射然后创建一个hash表这个hash表专门装入五个字符“蛙叫” hash表来记录最少青蛙的只数。 eg: 我现在读到的字符是ch‘o’那么我就要判断前面的字符‘r’是否存在过如果现在存在就证明这一只青蛙可以喊道我这个‘o’否则就说明是错误的返回-1 又比如我已经有青蛙喊完了一遍又碰到一个字符是ch此时我的hash[k]1就说明有一次青蛙已经喊完了但是有碰到chc 又要从头开始叫那么就可以让这只已经叫过的青蛙重叫就不会增加青蛙只数。 class Solution { public:int minNumberOfFrogs(string croakOfFrogs) {string tcroak;int nt.size();vectorint hash(n);unordered_mapchar,int index;for(int i0;in;i) index[t[i]]i;for(auto ch : croakOfFrogs){if(chc){if(hash[n-1]!0) hash[n-1]–;hash[0];}else{int iindex[ch];if(hash[i-1]0) return -1;hash[i-1]–;hash[i];}}for(int i0;in-1;i) if(hash[i]!0) return -1;return hash[n-1];} }; 总结 主要优化就是要找到其中的规律可以很暴力的求解但是这样往往都十分消耗精力可以多想一步说不定就解决了多次else if()的问题。这个算法里面用index将字符跟下标进行对应很完美的解决了else if()来判断每次读到哪个字符这个位置是否要加减的问题。 总结一下吧~模拟题相对来说确实比较轻松只要读懂题意跟着题目一步步走一般问题不大还是那句话熟能生巧本章节对我有很大促进作用希望对你有用