网站如何认证,红河网站建设代理,加快网站打开速度,招标网查询文章目录 《替换所有的问号》题目描述#xff1a;代码演示#xff1a;代码解析#xff1a; 《提莫攻击》题目描述#xff1a;代码演示#xff1a;代码解析#xff1a; [《Z 字形变换》](https://leetcode.cn/problems/zigzag-conversion/)题目描述#xff1a;代码演示代码演示代码解析 《提莫攻击》题目描述代码演示代码解析 [《Z 字形变换》](https://leetcode.cn/problems/zigzag-conversion/)题目描述代码演示代码解析 《外观数列》题目描述代码演示代码解析 《数青蛙》题目描述代码演示代码解析 《替换所有的问号》
题目描述
给你一个仅包含小写英文字母和 ? 字符的字符串 s请你将所有的 ? 转换为若干小写字母使最终的字符串不包含任何 连续重复 的字符。
注意你 不能 修改非 ? 字符。
题目测试用例保证 除 ? 字符 之外不存在连续重复的字符。
在完成所有转换可能无需转换后返回最终的字符串。如果有多个解决方案请返回其中任何一个。可以证明在给定的约束条件下答案总是存在的。
示例 1
输入s ?zs
输出azs
解释该示例共有 25 种解决方案从 azs 到 yzs 都是符合题目要求的。只有 z 是无效的修改因为字符串 zzs 中有连续重复的两个 z 。示例 2
输入s ubv?w
输出ubvaw
解释该示例共有 24 种解决方案只有替换成 v 和 w 不符合题目要求。因为 ubvvw 和 ubvww 都包含连续重复的字符。代码演示
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;}
};代码解析
因为该系列为模拟专题其实这部分还是要寻找规律然后就是仔细读题剩下的还是很容易的那么我们就从最简单的一道模拟题开始进行分析。
题目说的是把字符串中的「问号」字符转换成小写字母 而这个小写字母不能与他的前一个和后一个一样。 但是这个「问号」可能会出现在第一个和最后一个
因此我们只需要满足条件 1、当「问号」出现在第一个位置时只需要看「问号」后的那个元素即可。 2、当「问号」出现在最后个位置时只需要看「问号」前的那个元素即可。
《提莫攻击》
题目描述
在《英雄联盟》的世界中有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希编者注寒冰射手进入中毒状态。
当提莫攻击艾希艾希的中毒状态正好持续 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 秒即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态所以总中毒秒数是 3 。代码演示
class Solution
{
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int ret 0;for(int i 1; i timeSeries.size(); i){int len timeSeries[i] - timeSeries[i - 1];if(len duration) ret duration;else ret len;}return ret duration;}
};代码解析
对于这道题我们只需要在自己的草稿本上画画图就能很快理解题目并想出算法思路 通过图就能很清楚的看到所谓的中毒时间是会有重复的问题但是我们可以发现
1、如果两个时间点之间的距离 duration那么「中毒时间」就代表**前一个时间点**可以满足duration这个时间段
2、如果两个时间点之间的距离 duration那么「中毒时间」就代表前一个时间点到后一个时间点的距离
3、因为我们是要从第二个时间点开始算然后比较前一个因此在最后还要加上最后一个时间点的中毒持续时间。
《Z 字形变换》
题目描述
将一个给定字符串 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代码演示
class Solution
{
public:// 找规律string convert(string s, int numRows) {// numRows为1时 需单独讨论if(numRows 1) return s;int d 2 * numRows - 2;string ret; // 接收答案for(int i 0; i numRows; i){int j i;if(i 0 || i numRows - 1){while(j s.size()) {ret s[j];j d;}}else{int k d - j;while(j s.size() || k s.size()){if(j s.size()) ret s[j];if(k s.size()) ret s[k];j d;k d;}}}return ret;}
};代码解析
据我所知的模拟题一般都是这种是需要我们找规律的这道题还是很好读懂和理解的那接下来我就介绍介绍这道题的算法思路 我们将字母按照下标顺序来模拟那么不难发现有一个重要的规律
第一行和最后一行每个下标之间都差 2(numRows - 1)距离
拿第一个numRows为4举例子 1、第一行和最后一行每个元素之间差了6正好满足公式2(numRows - 1) 2、中间的这些行1和5相差47和11相差4而5和11相差了6.
第一行和最后一行好求难求的点也只在于中间各个元素之间的规律还是拿numRows为4的时候举例1和7也相差6那就可以得知0123和6789这两列永远相差2(numRows - 1)距离。
我们将2(numRows - 1)的计算结果计为 d那么1要想到5就得取(d - 1)同理2要想到4就得取(d - 2)
所以在计算中间的规律时只需要一对一对的比较即可意思就是加上1号下标后再加上(d - 1)号下标的然后他们都加上d这时就加上7号和11号即可。
《外观数列》
题目描述
「外观数列」是一个数位字符串序列由递归公式定义
countAndSay(1) 1countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
行程长度编码RLE是一种字符串压缩方法其工作原理是通过将连续相同字符重复两次或更多次替换为字符重复次数运行长度和字符的串联。例如要压缩字符串 3322251 我们将 33 用 23 替换将 222 用 32 替换将 5 用 15 替换并将 1 用 11 替换。因此压缩后字符串变为 23321511。
给定一个整数 n 返回 外观数列 的第 n 个元素。
示例 1
**输入**n 4
输出“1211”
解释
countAndSay(1) “1”
countAndSay(2) “1” 的行程长度编码 “11”
countAndSay(3) “11” 的行程长度编码 “21”
countAndSay(4) “21” 的行程长度编码 “1211”
示例 2
**输入**n 1
输出“1”
代码演示
class Solution
{
public:string countAndSay(int n) {if(n 1) return 1;string s countAndSay(n - 1); // 获取上一次数据string ret;for(int left 0, right 0; right s.size(); ){while(right s.size() s[left] s[right]) right;ret to_string(right - left) s[left];left right;} return ret;}
};代码解析
这道题目的描述完全就是阅读理解我先来介绍下题目是让我们干嘛的。 简单来说就是去描述第n - 1时的字符串个数如果n - 1的字符串是21那么就是1个2、1个1变成字符串就是1211.
那在这里有两种做法一种就是循环 双指针因为每次都是对上一次结果的统计那就从1开始慢慢统计然后就是用递归也就是迭代的方法来解决方法都是一致的。
就简单来讲讲双指针的逻辑
《数青蛙》
题目描述
给你一个字符串 croakOfFrogs它表示不同青蛙发出的蛙鸣声字符串 croak 的组合。由于同一时间可以有多只青蛙呱呱作响所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
要想发出蛙鸣 “croak”青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成请返回 -1 。
示例 1
输入croakOfFrogs croakcroak
输出1
解释一只青蛙 “呱呱” 两次示例 2
输入croakOfFrogs crcoakroak
输出2
解释最少需要两只青蛙“呱呱” 声用黑体标注
第一只青蛙 crcoakroak
第二只青蛙 crcoakroak示例 3
输入croakOfFrogs croakcrook
输出-1
解释给出的字符串不是 croak 的有效组合。代码演示
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string t croak;int n t.size();vectorint hash(n);// 记录下标unordered_mapchar, int index; for(int i 0; i n; i) index[t[i]] i;for(const auto ch : croakOfFrogs){if(ch c){if(hash[n - 1]) hash[n - 1]--;hash[0];}else{// 针对r, o, a, kint pos index[ch]; // 找到当前字母对应的下标if(hash[pos - 1]){hash[pos - 1]--;hash[pos];}else return -1;}}// 额外判断for(int i 0; i n - 1; i) if(hash[i]) return -1;return hash[n - 1];}
};代码解析
这题意对我来说又是一道阅读理解我先简单讲讲题目意思吧。 简单来说就是有一声蛙叫croak一只青蛙可以连续叫多次croak但是当一只青蛙在叫croak的过程中这时又来了一个c那么就得叫另外一只青蛙过来了。同时一定要满足字符串排序完之后肯定可以出现一个或多个croak。
所以具体的解决方法其实就是去一个一个的判断
第一步我们需要去给每个 croak 每个字符都编一个号从0开始然后利用哈希表讲给的的字符串一个一个比较
