【算法刷题指南】模拟

---

---

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站

---

---

🌈个人主页： 南桥几晴秋
🌈C++专栏： 南桥谈C++
🌈C语言专栏： C语言学习系列
🌈Linux学习专栏： 南桥谈Linux
🌈数据结构学习专栏： 数据结构杂谈
🌈数据库学习专栏： 南桥谈MySQL
🌈Qt学习专栏： 南桥谈Qt
🌈菜鸡代码练习： 练习随想记录
🌈git学习： 南桥谈Git

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 本科在读菜鸡一枚，指出问题及时改正

---

---

1576.替换所有的问号

1576.替换所有的问号

• 遍历字符串
• 找到当前位置是‘?’
• 分为三种情况：
  • i==0，成立条件：ch!=s[i+1]
  • i==s.size()-1，成立条件：ch!=s[s.size()-2]
  • 处于中间位置，成立条件：ch!=s[i-1]&&ch!=s[i+1]

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

---

495.提莫攻击

495.提莫攻击

• 当前时间和前一个时间的差值大于等于duration，中毒时间为duration
• 当前时间和前一个时间的差值小于duration，中毒时间需要重置
• 最后一个时间要加上duration

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ans=0;for(int i=1;i<timeSeries.size();i++){if(timeSeries[i]-timeSeries[i-1]>=duration) ans+=duration;else ans+=timeSeries[i]-timeSeries[i-1];}return ans+duration;}
};

---

6.Z 字形变换

6.Z 字形变换

• 模拟
• 找规律：
  • 第一行：每两个之间的间隔为d=2*numRows-2
  • 中间行：每两个竖列的间隔为d，斜列和竖列之间的间隔为d-i*2（i是每一行）
  • 最后一行：每两个之间的间隔为d=2*numRows-2
• 注意：在判断斜列的时候需要注意是否超出字符串的大小

class Solution {
public:string convert(string s, int numRows) {int n=s.size();string ans;int d=2*numRows-2;if(numRows==1) return s;//第一行for(int i=0;i<n;i+=d){ans+=s[i];}//中间行for(int i=1;i<numRows-1;i++){for(int j=i;j<n;){ans+=s[j];int dd=d-i*2;if(j+dd<n)ans=ans+s[j+dd];j+=d;}}//最后一行for(int i=numRows-1;i<n;i+=d)ans+=s[i];return ans;}
};

---

38.外观数列

38.外观数列

• 模拟
• 根据概念推出规律：

1
11 
21
1211
111221
312211
...

• 实质上就是依次统计连续相同字符的个数

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

---

1419.数青蛙

1419.数青蛙

• 模拟，遍历字符串
• 遍历到r、o、a、k找前驱字符是否在哈希表中存在：
  • 存在：前驱个数--，当前字符个数++
  • 不存在：返回-1
• 遍历到c时：找最后一个字符k是否在哈希表中存在：
  • 存在：最后一个字符的个数--，当前字符c++
  • 不存在：当前字符++

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t="croak";int n=t.size();vector<int>hash(n);  //数组模拟哈希表(记录t)unordered_map<char,int> index; //记录下标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]++; //c}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];}
};