【每日算法】专题六_模拟
1. 算法思路
“模拟” 是一种直观的算法思想,核心是 按照问题的实际逻辑、流程或规则,一步步 “模仿” 执行,将问题场景转化为代码可实现的操作 ,用代码重现问题的运行过程。
2. 例题
2.1 替换所有的问号
1576. 替换所有的问号 - 力扣(LeetCode)
核心思想:
核心思想是模拟人工替换问号的过程:逐个遍历字符串中的每个字符,当遇到?
时,从最小的字母a
开始尝试,找到第一个不与前后字符冲突的字母进行替换,确保替换后的字符串满足相邻字符不重复的条件。
关键步骤解析
- 遍历字符串:按从左到右的顺序检查每个字符。
- 处理问号:当遇到
?
时,尝试用字母表中的字母(从a
到z
)进行替换。 - 验证合法性:对于每个候选字母
ch
,检查其是否满足:- 若当前是第一个字符(
i == 0
),只需确保ch
与下一个字符不同。 - 若当前是最后一个字符(
i == n - 1
),只需确保ch
与前一个字符不同。 - 否则,需确保
ch
与前后两个字符都不同。
- 若当前是第一个字符(
- 替换字符:找到第一个合法的
ch
后,立即替换当前的?
,并继续处理后续字符。
算法特性
- 贪心策略:每次遇到
?
时,优先选择最小的合法字母(按字典序),无需回溯。 - 线性时间复杂度:每个字符最多被检查和处理一次,时间复杂度为 O (n)。
- 原地修改:直接在原字符串上进行替换,空间复杂度为 O (1)。
模拟示例
对于输入字符串"a?b?c"
:
- 处理位置 1 的
?
:- 尝试
a
(冲突,前一个字符是a
)。 - 尝试
b
(冲突,下一个字符是b
)。 - 尝试
c
(合法),替换为c
,字符串变为"acb?c"
。
- 尝试
- 处理位置 3 的
?
:- 尝试
a
(合法),替换为a
,字符串变为"acbac"
。
- 尝试
最终输出"acbac"
。
string modifyString(string s) {int n = s.size();for(int i = 0; i < n; ++i){if(s[i] == '?'){for(char ch = 'a'; ch <= 'z'; ++ch){if((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))s[i] = ch;}}}return s;}
2.2 提莫攻击
495. 提莫攻击 - 力扣(LeetCode)
核心思想:
核心思想是模拟中毒状态的叠加过程,计算提莫攻击造成的总中毒时间。具体思路如下:
关键步骤解析
- 遍历攻击时间点:按时间顺序检查每次攻击的生效时间。
- 判断中毒是否重叠:
- 无重叠:若当前攻击的结束时间(
timeSeries[i] + duration - 1
)早于下一次攻击开始,则中毒时间为完整的duration
。 - 部分重叠:若当前攻击的结束时间晚于下一次攻击开始,则中毒时间为两次攻击的间隔(
timeSeries[i+1] - timeSeries[i]
)。
- 无重叠:若当前攻击的结束时间(
- 累加有效中毒时间:根据每次攻击的重叠情况,累加对应的中毒时长。
算法特性
- 贪心策略:每次只考虑当前攻击与下一次攻击的关系,无需回溯。
- 线性时间复杂度:遍历一次数组,时间复杂度为 O (n)。
- 常数空间复杂度:仅需常数级额外变量,空间复杂度为 O (1)。
模拟示例
假设输入:timeSeries = [1, 4]
,duration = 2
。
- 第一次攻击(i=0):
- 攻击时间:
1
,结束时间:1 + 2 - 1 = 2
。 - 下一次攻击时间:
4
,结束时间晚于下一次攻击开始,无重叠。 - 中毒时间:完整的
duration = 2
。
- 攻击时间:
- 第二次攻击(i=1):
- 攻击时间:
4
,结束时间:4 + 2 - 1 = 5
。 - 无后续攻击,中毒时间:完整的
duration = 2
。
- 攻击时间:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {int timesum = 0;int n = timeSeries.size();for(int i = 0; i < n; ++i){if(i == n - 1 || timeSeries[i] + duration - 1 < timeSeries[i + 1])timesum += duration;else timesum += timeSeries[i + 1] - timeSeries[i];}return timesum;}
2.3 Z 字形变换
6. Z 字形变换 - 力扣(LeetCode)
核心思想:
核心思想是模拟字符在 N 字形路径中的填充过程,将字符串按指定行数重组为 N 字形排列后按行拼接输出。
关键步骤解析
- 初始化行容器:创建一个包含
numRows
个字符串的数组,用于存储每一行的字符。 - 控制移动方向:使用变量
row
跟踪当前字符应放入的行索引,flag
控制移动方向(1 表示向下,0 表示向上)。 - 遍历字符串:
- 将当前字符添加到对应行的字符串中。
- 根据移动方向更新行索引
row
:向下移动时row
递增,向上移动时row
递减。 - 当到达第一行或最后一行时,反转移动方向(通过切换
flag
的值)。
- 按行拼接结果:将所有行的字符串按顺序拼接成最终结果。
算法特性
- 时间复杂度:O (n),其中 n 为字符串长度。每个字符仅被处理一次。
- 空间复杂度:O (n),主要用于存储重组后的字符。
模拟示例
对于输入字符串s = "PAYPALISHIRING"
,numRows = 3
:
- 初始化:
ans = ["", "", ""]
row = 0
,flag = 1
(向下移动)
- 填充过程:
P -> ans[0] += 'P' → ans = ["P", "", ""] A -> ans[1] += 'A' → ans = ["P", "A", ""] Y -> ans[2] += 'Y' → ans = ["P", "A", "Y"] P -> 到达底部,flag=0(向上移动)→ ans[1] += 'P' → ans = ["P", "AP", "Y"] A -> ans[0] += 'A' → ans = ["PA", "AP", "Y"] L -> 到达顶部,flag=1(向下移动)→ ans[1] += 'L' → ans = ["PA", "APL", "Y"] ...
- 最终结果:
- 按行拼接:
ans[0] + ans[1] + ans[2] = "PAHNAPLSIIGYIR"
- 按行拼接:
string convert(string s, int numRows) {int n = s.size();vector<string> ans(numRows);int row = 0;int flag = 1;for(int i = 0; i < n; ++i){ans[row] += s[i];if(numRows != 1){if(flag) ++row;else --row;if(row == 0) flag = 1;else if(row == numRows - 1) flag = 0;}}string ret;for(auto str : ans)ret += str;return ret;}
2.4 外观数列
38. 外观数列 - 力扣(LeetCode)
核心思路:
核心思路是模拟外观数列的生成过程,通过迭代计算前一项的描述字符串,逐步推导出第 n 项的结果。
关键步骤解析
- 初始化:从第 1 项
"1"
开始。 - 迭代生成:循环
n-1
次,每次根据当前字符串生成下一项:- 遍历当前字符串:统计连续相同字符的个数。
- 构造描述:将连续字符的个数和值依次添加到新字符串中。
- 更新结果:用新生成的字符串替换当前字符串。
- 返回结果:迭代结束后,返回第 n 项的字符串。
算法特性
- 时间复杂度:O (n * m),其中 m 是第 n 项的字符串长度。每次迭代需遍历当前字符串。
- 空间复杂度:O (m),用于存储中间结果。
模拟示例
计算第 4 项(n=4):
- 初始值(第 1 项):
"1"
- 第 2 项:描述
"1"
→"11"
(1 个 1) - 第 3 项:描述
"11"
→"21"
(2 个 1) - 第 4 项:描述
"21"
→"1211"
(1 个 2,1 个 1)
最终结果:"1211"
核心逻辑
- 分组统计:将字符串按连续相同字符分组,统计每组的长度和字符。
- 描述拼接:将每组的统计结果(长度 + 字符)拼接成新字符串。
- 迭代更新:重复上述过程,直到生成第 n 项。
string countAndSay(int n) {string ret(1, '1');for(int i = 1; i < n; ++i){string s;for(int j = 0; j < ret.size(); ++j){int count = 1;while(j != ret.size() - 1 && ret[j] == ret[j + 1]) ++count, ++j;s += (count + '0');s += ret[j];}ret = s;}return ret;}
2.5 数青蛙
1419. 数青蛙 - 力扣(LeetCode)
核心思路
核心思路是通过状态机模拟多只青蛙的交替叫声,确保字符串中的每个字符序列都符合 "croak"
的顺序,并计算最少需要的青蛙数量。
关键步骤解析
-
状态映射:
chash
定义字符转移关系:'c' → 'r' → 'o' → 'a' → 'k'
。hash
记录每个状态的青蛙数量,初始时k
状态为 0。
-
遍历字符:
- 遇到
'c'
:- 若有青蛙处于
'k'
状态(已完成一次完整叫声),复用一只青蛙(hash['k']--
)。 - 新增一只青蛙进入
'c'
状态(hash['c']++
)。
- 若有青蛙处于
- 遇到其他字符:
- 检查前一个状态是否存在青蛙(如
'r'
需要'c'
存在)。 - 若存在,则转移一只青蛙到当前状态;否则返回
-1
(非法序列)。
- 检查前一个状态是否存在青蛙(如
- 遇到
-
合法性检查:
- 遍历结束后,若存在未完成叫声的青蛙(非
'k'
状态的青蛙数不为 0),返回-1
。 - 最终
hash['k']
即为最少需要的青蛙数量。
- 遍历结束后,若存在未完成叫声的青蛙(非
算法特性
- 时间复杂度:O (n),其中 n 为字符串长度。
- 空间复杂度:O (1),仅需固定大小的哈希表。
模拟示例
输入:"croakcroak"
- 初始状态:
hash = {'k': 0, 'c': 0, 'r': 0, 'o': 0, 'a': 0}
- 处理过程:
'c'
:新增青蛙 →hash['c'] = 1
'r'
:'c'
→'r'
→hash['c'] = 0
,hash['r'] = 1
'o'
:'r'
→'o'
→hash['r'] = 0
,hash['o'] = 1
'a'
:'o'
→'a'
→hash['o'] = 0
,hash['a'] = 1
'k'
:'a'
→'k'
→hash['a'] = 0
,hash['k'] = 1
- 第二组
"croak"
复用该青蛙,最终hash['k'] = 1
。
输出:1
(仅需 1 只青蛙)
核心逻辑
- 状态转移:每只青蛙必须按
c → r → o → a → k
的顺序叫,且可复用已完成叫声的青蛙。 - 并行处理:通过哈希表记录各状态的青蛙数,允许同时有多只青蛙处于不同状态。
- 合法性验证:确保每个字符都能找到前驱状态,并最终所有青蛙都完成叫声。
// 每只青蛙必须按 c → r → o → a → k 的顺序叫,且可复用已完成叫声的青蛙。// 通过哈希表记录各状态(也就是青蛙叫到哪个字符了)的青蛙数,允许同时有多只青蛙处于不同状态。// 遍历字符串,判断字符是否能找到前驱状态(前一个叫声字符),如果找到了就更新青蛙状态,反之则直接返回-1unordered_map<char, int> hash;hash['k'] = 0;unordered_map<char, char> chash;chash['r'] = 'c', chash['o'] = 'r', chash['a'] = 'o', chash['k'] = 'a'; int n = croakOfFrogs.size();for(int i = 0; i < n; ++i){if(croakOfFrogs[i] == 'c'){if(hash['k'] != 0)--hash['k'];++hash[croakOfFrogs[i]];}else{if(hash.count(chash[croakOfFrogs[i]]) && hash[chash[croakOfFrogs[i]]] >= 1){--hash[chash[croakOfFrogs[i]]];++hash[croakOfFrogs[i]];}else return -1;}}for(auto& e : hash){if(e.first != 'k' && e.second > 0) return -1;}return hash['k'];}