引言
模拟就是用计算机来模拟题目中要求的操作。
模拟题目通常具有码量大、操作多、思路繁复的特点。由于它代码量大,经常会出现难以查错的情况,如果在考试中写错是相当浪费时间的。
注:模拟没有基础思路和模板,所以要多刷题锻炼题感
1. 替换所有问号
题目描述:给你一个仅包含小写英文字母和 '?'
字符的字符串 s
,请你将所有的 '?'
转换为若干小写字母,使最终的字符串不包含任何 连续重复 的字符。
注意:你 不能 修改非 '?'
字符。
题目测试用例保证 除 '?'
字符 之外,不存在连续重复的字符。
思路:从前往后扫描,把所有的?转化,并且不能与前后字符相同即可
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 || ch != s[i - 1]) && (i == s.size() - 1 || ch != s[i + 1])) { s[i] = ch; break; } } } } return s; }};
2. 提莫攻击
题目描述:提莫在 t
发起攻击意味着艾希在时间区间 [t, t + duration - 1]
(含 t
和 t + duration - 1
)处于中毒状态。如果提莫在中毒影响结束 前 再次攻击,中毒状态计时器将会 重置 ,在新的攻击之后,中毒影响将会在 duration
秒后结束。
给你一个 非递减 的整数数组 timeSeries
,其中 timeSeries[i]
表示提莫在 timeSeries[i]
秒时对艾希发起攻击,以及一个表示中毒持续时间的整数 duration
。
返回艾希处于中毒状态的 总 秒数。
思路:
遍历序列,算出非递减序列中每两个数之间的差,若差小于中毒持续时间duration,则其实际在这段区间中毒时间为x
注:当遍历到最后一个数的时候,需要做特判
class Solution {public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int ret = 0, x; for (int i = 0; i < timeSeries.size(); i++) { if(i < timeSeries.size() - 1)x = timeSeries[i + 1] - timeSeries[i]; else x = duration; if (x >= duration) ret += duration; else ret += x; } return ret; }};
3. Z 字形变换
题目描述:
思路:
class Solution {public: string convert(string s, int numRows) { // 处理边界情况 if (numRows == 1) return s; // 公差 string ret; int d = 2 * numRows - 2, n = s.size(); // 1. 先处理第一行 for (int i = 0; i < n; i += d) ret += s[i]; // 2. 处理中间行 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]; } } // 3. 处理最后一行 for (int i = numRows - 1; i < n; i += d) ret += s[i]; return ret; }};
4. 外观数列
题目描述:「外观数列」是一个数位字符串序列,由递归公式定义:
countAndSay(1) = "1"
countAndSay(n)
是 countAndSay(n-1)
的行程长度编码。 行程长度编码(RLE)是一种字符串压缩方法,其工作原理是通过将连续相同字符(重复两次或更多次)替换为字符重复次数(运行长度)和字符的串联。例如,要压缩字符串 "3322251"
,我们将 "33"
用 "23"
替换,将 "222"
用 "32"
替换,将 "5"
用 "15"
替换并将 "1"
用 "11"
替换。因此压缩后字符串变为 "23321511"
。
给定一个整数 n
,返回 外观数列 的第 n
个元素。
思路:
模拟 + 双指针,模拟 n 次,记录上一次模拟结果,然后用指针来计算连续相同字符数目
class Solution {public: string countAndSay(int n) { string ans = "1"; for (int i = 1; i < n; i++) { string tmp; int len = ans.size(); for (int l = 0, r = 0; r < len;) { while (r < len && ans[l] == ans[r]) r++; //连续相同字符的数目 tmp += to_string(r - l) + ans[l]; l = r; } ans = tmp; } return ans; }};
5. 数青蛙
题目解析:给你一个字符串 croakOfFrogs
,它表示不同青蛙发出的蛙鸣声(字符串 "croak"
)的组合。由于同一时间可以有多只青蛙呱呱作响,所以 croakOfFrogs
中会混合多个 “croak”
。
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
要想发出蛙鸣 "croak",青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’
这 5 个字母。如果没有输出全部五个字母,那么它就不会发出声音。如果字符串 croakOfFrogs
不是由若干有效的 "croak" 字符混合而成,请返回 -1
。
思路:
crock中遍历到【r,o,c,k】找一下其前驱字符,是否在哈希表中存在
存在前驱个数--,当前字符++不存在返回 -1遍历到 c 找最后一个字符 k 是否在哈希表中存在,存在则最后一个字符--,当前字符++,不存在当前字符++,这个是用来判断是否是相同青蛙
class Solution {public: int minNumberOfFrogs(string croakOfFrogs) { string s = "croak"; //青蛙叫 int n = s.size(); vector<int> hash(n); //数字来模拟哈希表 unordered_map<char, int> index; // [x,x这个字符对应下标] for (int i = 0; i < n; i++) index[s[i]] = i; //映射青蛙叫 for (auto e : croakOfFrogs) { if (e == 'c') //表示是同一个青蛙叫 { if (hash[n - 1] != 0) hash[n - 1]--; hash[0]++; } else { int i = index[e]; //当前字符 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]; }};
6. 外卖店优先级
题目描述:“饱了么”外卖系统中维护着 NN 家外卖店,编号 11 ∼ NN。每家外卖店都有一个优先级,初始时 (0(0 时刻)优先级都为 00。
每经过 11 个时间单位,如果外卖店没有订单,则优先级会减少 11,最低减到 00;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 22。
如果某家外卖店某时刻优先级大于 55,则会被系统加入优先缓存中;如果优先级小于等于 33,则会被清除出优先缓存。
给定 TT 时刻以内的 MM 条订单信息,请你计算 TT 时刻时有多少外卖店在优先缓存中。
#include<iostream>#include<vector>#include<algorithm>using namespace std;const int N = 1e5 + 10;struct node{ int ts, id;};node a[N]; //存储数据bool cmp(node a, node b) { // 先按店铺排序,再按时刻排序 if (a.id != b.id) return a.id < b.id; return a.ts < b.ts;}int w[N], st[N]; //分别存储id号店优先级,上一次有订单时间,这个主要是避免一个时间多个外卖来了同一家外卖店bool vis[N]; //分别存储id号店是不是在优先缓存中,int main(){ int n, m, t; cin >> n >> m >> t; for (int i = 0; i < m; i++) cin >> a[i].ts >> a[i].id; sort(a, a + m, cmp); for (int i = 0; i < m; i++) { int ts = a[i].ts, id = a[i].id; //获取当前时刻和店铺 if (st[id] != ts) //若当前外卖店上一次时刻不为和当前时刻不同,则表示该外卖店无存储订单 w[id] = w[id] - (ts - st[id] - 1); //当前外卖店剩余优先级,当前时刻和上一个外卖店的时刻差,-1原因是因为[1,2]也表示该外卖店有外卖就不用-1 w[id] = max(0, w[id]); //避免为负数 if (w[id] <= 3) vis[id] = false; //退出优先缓存 w[id] += 2; if (w[id] > 5) vis[id] = true; st[id] = ts; //更新当前外卖店的上一次外卖来的时刻 } //计算 t 时刻内的优先级 for (int i = 1; i <= n; i++) { if (st[i] < t) { w[i] = w[i] - (t - st[i]); if (w[i] <= 3) vis[i] = false; } } int ans = 0; for (int i = 1; i <= n; i++) { if (vis[i]) ans++; } cout << ans << endl; return 0;}