备案主体负责人 网站负责人,宿州市住房 建设 官方网站,企业网站开发设计,当阳网站建设文章目录 C 模拟题详解#xff1a;基础题解与细致分析前言第一章#xff1a;基础练习1.1 替换所有的问号#xff08;easy#xff09;解法#xff08;模拟#xff09;C 代码实现易错点提示时间复杂度和空间复杂度 1.2 提莫攻击#xff08;easy#xff09;解法#xff0… 文章目录 C 模拟题详解基础题解与细致分析前言第一章基础练习1.1 替换所有的问号easy解法模拟C 代码实现易错点提示时间复杂度和空间复杂度 1.2 提莫攻击easy解法模拟 分情况讨论C 代码实现易错点提示时间复杂度和空间复杂度 1.3 N 字形变换medium解法模拟 找规律C 代码实现易错点提示时间复杂度和空间复杂度 1.4 外观数列medium解法模拟C 代码实现易错点提示时间复杂度和空间复杂度 1.5 数青蛙medium题目描述初始解法优化解法代码讲解易错点提示时间复杂度和空间复杂度 写在最后 C 模拟题详解基础题解与细致分析 欢迎讨论如有疑问或见解欢迎在评论区留言互动。 点赞、收藏与分享如觉得这篇文章对您有帮助请点赞、收藏并分享 分享给更多人欢迎分享给更多对 C 感兴趣的朋友一起学习字符串操作和模拟题解 前言 在算法学习中模拟题往往以其具体的操作流程和生动的应用场景为初学者提供了宝贵的实践机会。这类题型不仅帮助我们理解代码的执行过程还培养了我们对逻辑思维和代码组织的敏锐感。本篇文章将从一道经典的 C 模拟题“替换所有问号”出发带你逐步解析如何在字符操作和条件约束中找到最佳的解决方案帮助你打好算法学习的基础。 第一章基础练习
1.1 替换所有的问号easy
题目链接1576. 替换所有的问号
题目描述
给定一个仅包含小写英文字母和 ? 字符的字符串 s请将所有的 ? 转换为若干小写字母使得最终的字符串不包含任何连续重复的字符。 注意你不能修改非 ? 字符。题目保证除了 ? 字符之外不存在连续重复的字符。 在完成所有转换可能无需转换后返回最终的字符串。如果有多个解决方案返回其中任何一个即可。
示例 1
输入s ?zs输出azs解释该示例共有 25 种解决方案从 azs 到 yzs 都是符合题目要求的。只有 zzs 是无效的修改因为包含连续重复的两个 z。
示例 2
输入s ubv?w输出ubvaw解释该示例共有 24 种解决方案替换成 v 和 w 不符合题目要求因为 ubvvw 和 ubvww 都包含连续重复的字符。
提示
1 s.length 100s 仅包含小写英文字母和 ? 字符 解法模拟
算法思路
纯模拟。我们从前往后遍历整个字符串当遇到 ? 时用 a 到 z 的字符尝试替换确保替换后的字符与相邻字符不重复。 具体步骤如下
遍历字符串使用循环逐个检查字符串中的每个字符。替换问号当遇到 ? 时从 a 开始尝试替换检查替换后的字符是否和前后字符重复。确认替换如果字符与前后字符均不同则进行替换并跳出循环确保每个 ? 替换后都满足题目要求。返回结果遍历完成后返回修改后的字符串。 C 代码实现
class Solution {
public: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; // 替换并跳出内循环break;}}}}return s;}
};易错点提示 检查相邻字符 遍历时要特别注意边界条件确保 i 在第一个或最后一个字符时能够正确处理前后位置的检查。 字符替换的范围 要从 a 开始尝试替换字符一直到 z确保字符替换的选择范围广泛。 循环退出条件 内部循环使用 break一旦找到合适的字符替换就退出以减少不必要的循环操作。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是字符串的长度。每次遇到 ?最多需要检查 26 个字符但 n 较小时这些检查可以在常数时间内完成。空间复杂度O(1)仅使用常数空间来存储中间变量。 1.2 提莫攻击easy
题目链接495. 提莫攻击
题目描述
在《英雄联盟》的世界中有一个叫 提莫 的英雄。他的攻击可以让敌方英雄 艾希寒冰射手进入中毒状态。 当提莫攻击艾希时艾希的中毒状态会持续 duration 秒。 具体来说提莫在 t 秒发起攻击意味着艾希在时间区间 [t, t duration - 1] 内包含 t 和 t duration - 1处于中毒状态。如果提莫在之前的中毒影响结束前再次攻击则中毒状态计时器会重置中毒影响将在新的攻击后 duration 秒后结束。
给定一个非递减的整数数组 timeSeries其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击和一个表示中毒持续时间的整数 duration。 返回艾希处于中毒状态的总秒数。
示例 1
输入timeSeries [1,4], duration 2输出4解释 第 1 秒提莫攻击艾希并使其立即中毒中毒状态持续 2 秒即第 1 秒和第 2 秒。第 4 秒提莫再次攻击艾希艾希中毒状态又持续 2 秒即第 4 秒和第 5 秒。艾希在第 1, 2, 4, 5 秒处于中毒状态总中毒秒数为 4。
示例 2
输入timeSeries [1,2], duration 2输出3解释 第 1 秒提莫攻击艾希并使其立即中毒中毒状态持续 2 秒即第 1 秒和第 2 秒。第 2 秒提莫再次攻击艾希重置中毒计时器中毒状态持续到第 2 秒和第 3 秒。艾希在第 1, 2, 3 秒处于中毒状态总中毒秒数为 3。
提示
1 timeSeries.length 10^40 timeSeries[i], duration 10^7timeSeries 按非递减顺序排列 解法模拟 分情况讨论
算法思路
采用模拟和分情况讨论的方法通过计算相邻两个时间点的差值确定中毒状态的持续时间 相邻时间点差值计算 如果差值大于或等于中毒时间说明上次中毒可以持续 duration 秒。如果差值小于中毒时间那么上次的中毒只能持续 差值 秒因为下一次攻击提前发生。 结果累加循环处理每一次攻击的影响时间最后加上最后一次攻击的 duration即可得到总的中毒时间。 C 代码实现
class Solution {
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int ret 0;for(int i 1; i timeSeries.size(); i) {int tmp timeSeries[i] - timeSeries[i - 1];if(tmp duration) ret duration;else ret tmp;}return ret duration;}
};易错点提示 最后一次攻击时间的处理 最后一段时间直接加上 duration因为最后一次攻击的影响持续完整的 duration 时间。 相邻攻击的差值判断 根据 tmp duration 和 tmp duration 两种情况正确累加中毒时间。 初始化和边界条件 确保 timeSeries 长度至少为 1如果 timeSeries 长度为 1直接返回 duration。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是 timeSeries 的长度需要遍历数组一次。空间复杂度O(1)只使用常数空间来存储结果。 1.3 N 字形变换medium
题目链接6. N 字形变换
题目描述
将一个给定字符串 s 根据给定的行数 numRows以从上往下、从左到右进行 Z 字形排列。 例如输入字符串为 PAYPALISHIRING行数为 3 时排列如下
P A H N
A P L S I I G
Y I R之后你的输出需要从左往右逐行读取产生出一个新的字符串比如PAHNAPLSIIGYIR。
请你实现这个将字符串进行指定行数变换的函数string convert(string s, int numRows);
示例 1
输入s PAYPALISHIRING, numRows 3输出PAHNAPLSIIGYIR
示例 2
输入s PAYPALISHIRING, numRows 4输出PINALSIGYAHRPI解释P I N
A L S I G
Y A H R
P I示例 3
输入s A, numRows 1输出A
提示
1 s.length 1000s 由英文字母小写和大写、, 和 . 组成1 numRows 1000 解法模拟 找规律
算法思路
Z 字形排列的规律字符在 numRows 4 时的排列结构如下
0 2row - 2 4row - 4
1 (2row - 3) (2row - 1) 4row - 5 4row - 3
2 (2row - 4) 2row 4row - 6 4row - 2
3 2row 1 4row - 1不难发现数据是以 2row - 2 为周期进行循环。每一行的字符位置都可以按特定间隔获取
第一行和最后一行形成等差数列间隔为 2 * numRows - 2。中间行字符按两个等差数列交替出现。 C 代码实现
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;}
};易错点提示 周期 d 2 * numRows - 2 这是 Z 字形转换的关键表示字符在行间的周期性跳跃。 中间行的交替字符 每一中间行的字符位置交替出现在两个等差数列上位置 i k 和 j d - k。 最后累加顺序 输出时需要按从上到下的顺序逐行拼接。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是字符串 s 的长度每个字符被遍历和拼接一次。空间复杂度O(n)用于存储结果字符串。 1.4 外观数列medium
题目链接38. 外观数列
题目描述
给定一个正整数 n输出外观数列的第 n 项。 「外观数列」是一个整数序列从数字 1 开始序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列
countAndSay(1) 1countAndSay(n) 是对 countAndSay(n-1) 的描述然后转换成另一个数字字符串。
前五项如下
111211211111221
说明
第 1 项是数字 1第 2 项描述前一项 1即“一个 1”记作 11第 3 项描述前一项 11即“两个 1”记作 21第 4 项描述前一项 21即“一个 2 一个 1”记作 1211第 5 项描述前一项 1211即“一个 1 一个 2 两个 1”记作 111221 例如数字字符串 “3322251” 的描述如下图 示例 1
输入n 1输出1
示例 2
输入n 4输出1211
提示
1 n 30 解法模拟
算法思路
「外观数列」的本质是对前一项字符串中连续相同字符的计数。每一项生成下一项的步骤如下
从第 1 项的 1 开始每一项的字符串通过遍历前一项字符串生成。对于每组连续相同的字符将字符的个数和字符本身组合成新字符串得到下一项。 C 代码实现
class Solution {
public:string countAndSay(int n) {string ret 1;for (int i 1; i n; i) { // 执行 n - 1 次生成第 n 项string tmp;int len ret.size();for (int left 0, right 0; right len;) {// 计算当前字符的连续段while (right len ret[left] ret[right]) right;// 拼接字符的数量和字符本身tmp to_string(right - left) ret[left];left right; // 更新 left 到新段的开始}ret tmp; // 将当前项更新为 ret}return ret;}
};易错点提示 连续字符计数的实现 在每个字符段结束时将计数和字符追加到 tmp 中。 索引更新 遍历完一个字符段后将 left 更新为新的字符段起点 right。 结果更新 ret 表示当前的结果每次生成后更新为新的项。 时间复杂度和空间复杂度
时间复杂度O(n * m)其中 n 是调用次数m 是字符串长度字符串随着项数增加而增大。空间复杂度O(m)用于临时存储字符串。 1.5 数青蛙medium
题目链接1419. 数青蛙
题目描述
给定一个字符串 croakOfFrogs表示青蛙发出的 “croak” 叫声的组合。可以有多只青蛙同时叫因此字符串中可能会包含多个 “croak”。要求返回完成所有叫声所需的最少青蛙数量。如果字符串不是有效的 “croak” 组合则返回 -1。
示例
输入croakcroak输出1输入crcoakroak输出2输入croakcrook输出-1 初始解法
我们可以使用一个大小为 128 的数组 hash因为字符 ASCII 最大为 127以字符 ASCII 值为索引记录每个字符的数量。遍历过程中判断每个字符是否按照 “croak” 顺序出现。比如
遇到 “c” 时增加 hash[c] 的计数。遇到 “r” 时确保 hash[c] 0表示有足够的 “c” 来支撑r再增加 hash[r] 的计数并减少 hash[c]。同理对其他字符处理。
遍历结束后检查各字符状态确保所有青蛙完整发出了 “croak”。
初始代码
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {int hash[128] {0}; // 使用128大小的数组for (auto ch : croakOfFrogs) {if (ch c) {if (hash[k] 0) hash[k]--; // 复用已完成的青蛙hash[c];} else if (ch r) {if (hash[c] 0) return -1; // 检查前序字符hash[c]--; hash[r];} else if (ch o) {if (hash[r] 0) return -1;hash[r]--; hash[o];} else if (ch a) {if (hash[o] 0) return -1;hash[o]--; hash[a];} else if (ch k) {if (hash[a] 0) return -1;hash[a]--; hash[k];}}if(hash[c] 0 hash[r] 0 hash[o] 0 hash[a] 0)return hash[k];return -1;}
};问题这种方法的空间利用率较低因为我们只用到 “croak” 5 个字符但却开辟了大小为 128 的数组。 优化解法
我们可以进一步优化。因为我们只需要追踪 “croak” 这 5 个字符的状态因此
将数组大小减少到 5创建一个大小为 5 的数组 hash每个位置对应 “croak” 中的字符状态。通过映射表 index将 “croak” 中每个字符映射到 hash 数组的索引位置直接通过索引更新字符的计数。
这样可以减少空间浪费代码更清晰。
优化代码
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t croak;int n t.size();vectorint hash(n); // 使用5个位置的数组表示 croakunordered_mapchar, int index; // 映射字符到数组索引for (int i 0; i n; i)index[t[i]] i; // 初始化映射关系for (char ch : croakOfFrogs) {if (ch c) {if (hash[n - 1] 0) hash[n - 1]--; // 若有完整的 croak 可复用hash[0];} else {int i index[ch];if (hash[i - 1] 0) return -1; // 若缺少前一个字符hash[i - 1]--;hash[i];}}// 检查所有青蛙是否都完成了 croak 叫声for (int i 0; i n - 1; i)if (hash[i] ! 0) return -1;return hash[n - 1];}
};代码讲解
数组 hash我们使用大小为 5 的数组 hash每个位置表示 “croak” 中的一个字符。hash[0] 表示“c”的数量hash[4] 表示完整“croak”的青蛙数量。映射 index利用 unordered_map 将 “croak” 中的字符映射到 hash 数组的索引位置。这样每次遇到某字符时可以快速找到其在 hash 中的位置。遍历过程 遇到 “c”表示青蛙开始叫检查是否有复用的青蛙可用若有则减少 hash[4]然后增加 hash[0]。遇到其他字符确保前一个阶段的青蛙数量足够。若不足返回 -1。 结束检查遍历结束后检查 hash[0] 到 hash[3] 是否为 0确保没有青蛙停留在中间阶段。返回结果返回 hash[4]表示需要的最少青蛙数量。 易错点提示 字符顺序检查每只青蛙必须按照 “croak” 的顺序叫。如果某字符的前序字符计数不足则说明顺序出错直接返回 -1。 复用条件当一只青蛙完成 “croak” 后可以复用它从 “c” 开始再次叫减少总青蛙数量。 末尾检查确保所有青蛙完整叫出“croak”防止有青蛙停留在中途。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 为字符串 croakOfFrogs 的长度。我们只需一次遍历。空间复杂度O(1)因为 hash 数组大小固定为 5unordered_map 只存储 5 个字符的映射关系。 写在最后 模拟题的难点在于逻辑的严谨和细节的把握它们就像编程世界中的微小拼图帮助我们逐渐构建完整的逻辑框架。希望通过这篇文章你能感受到代码细节之美获得更丰富的编程技巧。期待在未来的模拟题挑战中你能以更加从容的姿态应对享受算法探索带来的乐趣。感谢你的阅读愿你在算法学习的道路上不断成长 以上就是关于【优选算法篇】算法江湖中的碎玉拾光——C模拟题全解踏步逐章细细品味的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️
