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

【数据结构与算法】模拟

news 2025/5/30 15:30:51

成熟不是为了走向复杂，而是为了抵达天真；不是为了变得深沉，而是为了保持清醒。

前言

这是我自己刷算法题的第五篇博客总结。

上一期笔记是关于前缀和算法：

【数据结构与算法】前缀和-CSDN博客https://blog.csdn.net/hsy1603914691/article/details/147953256?sharetype=blogdetail&sharerId=147953256&sharerefer=PC&sharesource=hsy1603914691&spm=1011.2480.3001.8118

技巧

1. 模拟题思路比较简单，先模拟算法流程，再把流程转换成代码。

2. 模拟题需要特别注意开始和结束，可能需要特殊处理。

3. 模拟题的重点是找规律。

例题

1. leetcode-724题：

1576. 替换所有的问号 - 力扣（LeetCode）https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/

class Solution {
public:string modifyString(string s) {int cur=0;while(cur<s.size()){if(s[cur]=='?'){for(char replace='a';replace<='z';replace++){if(cur==0&&replace!=s[cur+1])s[cur]=replace;else if(cur==s.size()-1&&replace!=s[cur-1])s[cur]=replace;else if(cur!=0&&cur!=s.size()-1&&replace!=s[cur+1]&&replace!=s[cur-1])s[cur]=replace;else{}}}cur++;}return s;}
};

2. leetcode-495题：

495. 提莫攻击 - 力扣（LeetCode）https://leetcode.cn/problems/teemo-attacking/description/

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int cur=0,sum=0;while(cur<timeSeries.size()){if((cur!=timeSeries.size()-1&&timeSeries[cur]+duration<=timeSeries[cur+1])||(cur==timeSeries.size()-1)){sum+=duration;cur++;}else{sum+=timeSeries[cur+1]-timeSeries[cur];cur++;}}return sum;}
};

3. leetcode-6题：

6. Z 字形变换 - 力扣（LeetCode）https://leetcode.cn/problems/zigzag-conversion/

class Solution {
public:string convert(string s, int numRows) {if(numRows==1)return s;string ret;int d=2*numRows-2,n=s.size();for(int i=0;i<n;i+=d)ret+=s[i];for(int k=1;k<numRows-1;k++){for(int i=k,j=d-k;i<n||j<n;i+=d,j+=d){if(i<n)ret+=s[i];if(j<n)ret+=s[j];}}for(int i=numRows-1;i<n;i+=d)ret+=s[i];return ret;}
};

4. leetcode-38题：

38. 外观数列 - 力扣（LeetCode）https://leetcode.cn/problems/count-and-say/

class Solution {
public:string countAndSay(int n) {string s="1";for(int i=1;i<n;i++){string temp;int left=0,right=0,count=0;while(right<s.size()){while(s[right]==s[left]&&right<s.size())right++;count=right-left;temp.push_back(count+'0');temp.push_back(s[left]);left=right;}s=temp;}return s;}
};

5. leetcode-1419题：

1419. 数青蛙 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {unordered_map<char,int> m;int right=0;while(right<croakOfFrogs.size()){if(croakOfFrogs[right]=='c'){if(m['k']==0)m['c']++;elsem['k']--,m['c']++;}else if(croakOfFrogs[right]=='r'){if(m['c']==0)return -1;elsem['c']--,m['r']++;}else if(croakOfFrogs[right]=='o'){if(m['r']==0)return -1;elsem['r']--, m['o']++;}else if(croakOfFrogs[right]=='a'){if(m['o']==0)return -1;elsem['o']--,m['a']++;}else if(croakOfFrogs[right]=='k'){if(m['a']==0)return -1;elsem['a']--,m['k']++;}elsereturn -1;right++;}if(m['c']==0&&m['r']==0&&m['o']==0&&m['a']==0)return m['k'];elsereturn -1;}
};