1.替换所有的问号
- 遍历字符串：通过外层循环逐一检查每个字符。
- 遇到
?时处理：- 内层循环遍历小写字母（
'a'到'z'）。 - 对每个字母检查是否满足：
- 与前一个字符不同（若
?在开头则无需检查）。 - 与后一个字符不同（若
?在末尾则无需检查）。
- 与前一个字符不同（若
- 找到符合条件的字母后，立即将
?替换为该字母。
- 内层循环遍历小写字母（
- 返回结果：修改后的字符串
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;
}
}
}
}
return s;
}
};2.提莫攻击
思路：计算后一个值减前一个值与中毒时间比较，大于等于这个中毒时间就直接加上这个中毒时间，否则就加上这个间隔时间。
class Solution
{
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration)
{
int ret = 0;
ret += duration;
for(int i = 1; i <= timeSeries.size() - 1; i++)
{
if(timeSeries[i] - timeSeries[i - 1] >= duration)
{
ret += duration;
}
else
{
ret += timeSeries[i] - timeSeries[i - 1];
}
}
return ret;
}
};3. Z字形变换
思路：找规律 公差d = 2 * numRows - 2 (n为字符串s的长度)。每一行每一行的处理元素（下标索引）
numRows == 1时直接返回字符串s
第一行：0 -> 0 + d -> 0 + 2d ->......-> 0 + kd。
第x行（1 <= x < numRows - 1）两个数两个数向后走：（x, d - x）-> (x + d, d - x + d) -> ......->(x + kd, d - x + kd)。
最后一行：numRows - 1 -> numRows - 1 + d -> ...... -> numRows - 1 + kd。
- 第一行：索引为0, d, 2d, 3d, ... 直到超出字符串长度。
- 中间行（从第2行到第numRows-1行）：每一行有两个序列。第一个序列起始为当前行号x（从0开始则行号为x，注意第一行是x=0），步长为d；第二个序列起始为d-x，步长也为d。注意这两个序列在同一周期内，且每一行中这两个索引交替出现（但按顺序是先第一个序列的，再第二个序列的，然后进入下一周期）。
- 最后一行（第numRows行，索引为numRows-1）：索引为(numRows-1), (numRows-1)+d, (numRows-1)+2d, ...
class Solution
{
public:
string convert(string s, int numRows)
{
if(numRows == 1)
return s;
int d = 2 * numRows - 2, n = s.size();
string ret;
//处理第一行
for(int i = 0; i < n; i += d)
{
ret += s[i];
}
//处理中间行
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];
}
}
//最后一行
for(int i = numRows - 1; i < n; i += d)
{
ret += s[i];
}
return ret;
}
};4.外观数列
思路：模拟+双指针
- 使用双指针法识别连续相同字符：
left：标记当前字符组的起始位置right：向前扫描直到遇到不同字符
- 计算连续字符长度：
len = right - left - 生成描述字符串：
"长度" + "字符" - 每轮处理完成后，将结果赋值给
ret作为下一轮输入
class Solution
{
public:
string countAndSay(int n)
{
string ret = "1";
for(int i = 1; i < n; i++)//解释n - 1次ret
{
string tmp;
for(int left = 0, right = 0; right < ret.size();)
{
while(right < ret.size() && ret[left] == ret[right])
right++;
int len = right - left;
tmp += to_string(len) + ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};5.数青蛙
思路：模拟，要保证找到青蛙的最小个数，遍历字符串，并且将字符放入哈希表中（放入规则如下）
当遍历到字符r , o , a , k时，找前驱字符是否存在哈希表中，存在则前驱个数--，当前字符++；不存在则返回 -1。
当遍历到字符c时，找到最后一个字符是否在哈希表中存在，存在则最后一个字符--，当前字符++；不存在当前字符++。
直接用if-else的写法
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
unordered_map<char, int> hash = {{'c',0}, {'r',0}, {'o',0}, {'a',0}, {'k',0}};
for(int i = 0; i < croakOfFrogs.size(); i++)
{
if(croakOfFrogs[i] == 'c')
{
if(hash['k'] > 0)
{
hash['k']--;
}
hash['c']++;
}
else if(croakOfFrogs[i] == 'r')
{
if(hash['c'] > 0)
{
hash['c']--;
hash['r']++;
}
else
{
return -1;
}
}
else if(croakOfFrogs[i] == 'o')
{
if(hash['r'] > 0)
{
hash['r']--;
hash['o']++;
}
else
{
return -1;
}
}
else if(croakOfFrogs[i] == 'a')
{
if(hash['o'] > 0)
{
hash['o']--;
hash['a']++;
}
else
{
return -1;
}
}
else if(croakOfFrogs[i] == 'k')
{
if(hash['a'] > 0)
{
hash['a']--;
hash['k']++;
}
else
{
return -1;
}
}
}
if(hash['c'] > 0 || hash['r'] > 0 || hash['o'] > 0 || hash['a'] > 0)
return -1;
else
return hash['k'];
}
};这个写法不太好,可以在用一个哈希表来存储这个字符及其对应的下标。
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
string ret = "croak";
int n = ret.size();
vector<int> hash(n);//用数组来模拟哈希表
unordered_map<char,int> index;//当前字符的下标
for(int i = 0; i < n; i++)//映射下标
{
index[ret[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)
{
hash[i - 1]--;
hash[i]++;
}
else
return -1;
}
}
for(int i = 0; i < n - 1; i++)
{
if(hash[i] != 0)
return -1;
}
return hash[n - 1];
}
};