做卡贴的网站,wordpress大不了,英文网站 icp备案号,莱阳房产交易网个人主页 #xff1a; zxctscl 如有转载请先通知 题目 前言1. 1576. 替换所有的问号1.1 分析1.2 代码 2. 495. 提莫攻击2.1 分析2.2 代码 3. 6. Z 字形变换3.1 分析3.2 代码 4. 38. 外观数列4.1 分析4.2 代码 5. 1419. 数青蛙5.1 分析5.2 代码 前言
模拟算法就是根据题目所给… 个人主页 zxctscl 如有转载请先通知 题目 前言1. 1576. 替换所有的问号1.1 分析1.2 代码 2. 495. 提莫攻击2.1 分析2.2 代码 3. 6. Z 字形变换3.1 分析3.2 代码 4. 38. 外观数列4.1 分析4.2 代码 5. 1419. 数青蛙5.1 分析5.2 代码 前言
模拟算法就是根据题目所给的照葫芦画瓢。 考察的是代码能力。 步骤1.模拟算法流程一定得自己先过一遍流程 2.把流程转化为代码
1. 1576. 替换所有的问号 1.1 分析
题目的意思很显而易见遍历一遍字符串如果是就找一个小写字母来替换它而它的前面一个字符和它不相同它后面一个字符和它也不能相同。得处理一下边界情况如果?在开始位置就不用比较它前面位置比较后面那个位置就行。同样在结尾位置的话就比较前面的一个字符相不相等就行。
1.2 代码
class Solution {
public:string modifyString(string s) {int n s.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. 495. 提莫攻击 2.1 分析
当前这个位置减去前面一个位置的差如果大于等于中毒时间那么就全部加上中毒时间如果差小于中毒时间那么就是加上这个差值。得注意最后一个值没有判断最后的值还得再加上一个中毒时间才行。
2.2 代码
class Solution {
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int ntimeSeries.size();int ret0;for(int i1;in;i){ int ttimeSeries[i]-timeSeries[i-1];if(tduration) {retduration;}else rett;}return retduration;}
};3. 6. Z 字形变换 3.1 分析
一、题目解析 按题目所述像下面图片这样的就是Z字型。 二、算法原理 要想得到最后为Z字型输出的字符串可以直接开一个矩阵直接先把字符一个一个放进去再一行一行输出。 但还可以用另外一个方式就是找规律。
举个例子把字符的下标都写到矩阵里面就发现了规律。 第一行每间隔2n-2就出现一次为了方便描述就把间隔叫做公差d2n-2,第一行只需要输出每次个d个数的字符就可以。 最后一行和第一行一样也是间隔d个字符数。 来看中间几行1和5到11和13中间间隔的也是d个数那么直接一次性输出两个就行。
3.2 代码
class Solution {
public:string convert(string s, int numRows) { if(numRows1)return s;string ret;int d2*numRows-2;int ns.size();for(int i0;in;id)rets[i];、//第一行for(int k1;knumRows-1;k)//中间行{for(int ik,jd-k;in||jn;id,jd){if(in)rets[i];if(jn)rets[j];}}for(int inumRows-1;in;id)//最后一行{rets[i];}return ret;}
};4. 38. 外观数列 4.1 分析
模拟题目的意思 找到连续相同的字符解释一下可以利用双指针来进行如果两个指针指向的位置字符相同就一直走不一样就停下来中间元素的个数就是指针的差值然后让左边指针指向右边指针的位置再重复上面的操作就可以了。
4.2 代码
class Solution {
public:string countAndSay(int n) {string ret1;for(int i1;in;i){string tmp;int lenret.size();for(int left0,right0;rightlen;){while(rightlenret[left]ret[right])right;tmpto_string(right-left)ret[left];leftright;}rettmp;}return ret;}
};5. 1419. 数青蛙 5.1 分析
模拟 用一个哈希表时刻记录每一次字符出现的情况。如果青蛙叫了c时候那么就用1记录一下有一个青蛙叫了c字符;遍历到r的时候看看前面有没有青蛙叫了c,有就让这个青蛙继续叫r,在哈希表了让c减减r加加就行。当又遇到一个c时候表示又有一个青蛙过来然后继续遍历到o的时候要看看哈希表前面有没有青蛙叫过r有的话r减减o加加继续往后重复直到k。 但是题目要求青蛙数目最少这里k中有数的时候此时又有c时候就从k里面搬一个青蛙来从c开始叫k减减c加加重复上面过程。k里面的数存的就刚好是结果。 但是如果除了k里面还有非0元素那么就返回-1。
如果在在哈希表中在r位置之前没有c那么就返回-1
总结都得找前驱字符如果前驱字符有那么前驱字符减减当前字符加加没有就返回-1。 最后一个字符看看它是不是在哈希表里面存在存在就是最后一个字符减减当前字符加加不存在就当前字符加加。
5.2 代码
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs){string t croak;int n t.size();vectorint hash(n); // ⽤数组来模拟哈希表unordered_mapchar, int index; //[x, x这个字符对应的下标]for (int i 0; i n; i)index[t[i]] i;for (auto ch : croakOfFrogs){if (ch c){if (hash[n - 1] ! 0) hash[n - 1]--;hash[0];}else{int i index[ch];if (hash[i - 1] 0) return -1;hash[i - 1]--; hash[i];}}for (int i 0; i n - 1; i)if (hash[i] ! 0)return -1;return hash[n - 1];}
};
