【刷题10】模拟专题
一、替换所有问号
题目：
思路：
- 遍历字符串，找到问号的位置
- 如果是首字符，只需考虑是否与后一个字符不相等；如果是最后一个字符，只需考虑是否与前一个字符不相等；是中间位置的字符，不能与前后两个字符相同
代码：
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 || s[i-1] != ch) && (i == s.size()-1 || s[i+1] != ch))
{
s[i] = ch;
break;
}
}
}
}
return s;
}
};
二、提莫攻击
题目：
思路：
- 某段时间间隔大于等于中毒持续时间，sum+=d；否则sum+=这段时间间隔
- 最后一个时间点（数组的最后一个元素）还要加上d
代码：
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int sum = 0;
for(int i=1; i<timeSeries.size(); i++)
{
int k = timeSeries[i] - timeSeries[i-1];
if(k >= duration)
{
sum += duration;
}
else
{
sum += k;
}
}
return sum+duration;
}
};
三、Z字形变换
题目：
思路：
细节：如果numRows为1，说明只有一行，直接返回原来的字符串
代码：
class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if(numRows == 1) return s;
string ret;
int d = 2*numRows-2;
for(int i=0; i<numRows; i++)
{
if(i == 0)
{
int k = 0;
while(k*d < n)
{
char ch = s[k*d];
ret += ch;
k++;
}
}
else if(i == numRows-1)
{
int k = 0;
while(numRows-1+k*d < n)
{
char ch = s[numRows-1+k*d];
ret += ch;
k++;
}
}
else
{
int k = 0;
while(i+k*d < n && d-i+k*d < n)
{
char ch = s[i+k*d];
ret += ch;
char c = s[d-i+k*d];
ret += c;
k++;
}
if(i+k*d < n)
{
char ch = s[i+k*d];
ret += ch;
k++;
}
}
}
return ret;
}
};
四、外观数列
题目：
思路：
- 初始化定义的字符串str为"1"，如果n等于1就直接返回str
- 循环次数比n少1，因为前面已经算一次了；定义一个临时的字符串ss，双指针(left right len = 0)
- 如果right位置等于left位置，right++；否则看right是否等于str的长度，或者right位置不等于left位置，满足其中一个条件，计算len的长度，left到right的位置，ss+=len转换为字符串+right的上一个位置的字符
- 双指针循环完，更新str；最后次数循环后，返回str
代码：
class Solution {
public:
string countAndSay(int n) {
string str = "1";
if(n == 1) return str;
while(--n)
{
string ss;
int left = 0, right = 0, len = 0;
while(right <= str.size())
{
if(str[right] == str[left])
{
right++;
}
else if(right == str.size() || str[right] != str[left])
{
len = right-left;
left = right;
ss += to_string(len) + str[right-1];
}
}
str = ss;
}
return str;
}
};
五、数青蛙
题目：
思路：
- 哈希表：hash的每个位置表示次数，index的是每个字符对应下标
- 如果当前字符是c，看最后一个字符是否在哈希表存在；如果是其他字符，看前一个字符是否在哈希表存在
- 最后要遍历下hash（次数），除了最后一个字符，其他字符的次数还有不为0的就直接返回-1，否则返回最后一个字符对应的次数
代码：
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
string str = "croak";
int n = str.size();
vector<int> hash(n);// 次数
unordered_map<char, int> index;// 字符 下标
for(int i=0; i<n; i++)
{
index[str[i]] = i;
}
for(auto ch : croakOfFrogs)
{
if(ch == 'c')
{
if(hash[n-1] == 0)
{
hash[index[ch]]++;
}
else
{
hash[n-1]--;
hash[index[ch]]++;
}
}
else
{
if(hash[index[ch]-1] == 0)
{
return -1;
}
else
{
hash[index[ch]-1]--;
hash[index[ch]]++;
}
}
}
for(int i=0; i<n-1; i++)
{
if(hash[i] != 0) return -1;
}
return hash[n-1];
}
};
原文地址：https://blog.csdn.net/2301_77459845/article/details/142924322
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！