算法专题六:模拟
2024-01-10 08:20:09
一.替换所有的问号
1.思路一
class Solution {
public:
string modifyString(string s) {
for(int i=0;i<s.size();i++)
{
if(s[i] == '?')
{
for(char j = 'a' ; j<='z' ; j++)
{
//1.注意数组越界
if((i==0 || s[i-1] != j) && (i==s.size()-1 || s[i+1] != j))
{
s[i] = j;
break;
}
}
}
}
return s;
}
};
2.GIF题目解析
二.提莫攻击
1.思路一
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int time = 0;
for(int i=1;i<timeSeries.size();i++)
{
int time_grep = timeSeries[i] - timeSeries[i-1];
//1.时间超过
if(time_grep >= duration)
{
time += duration;
}
//2.时间没有超过
else
{
time += time_grep;
}
}
//3.最后一次攻击一定会走完!
time += duration;
return time;
}
};
三.N字型变换
1.思路一:模拟
class Solution {
public:
string convert(string& s, int numRows) {
//0.只有一行
if (numRows == 1)
return s;
//1.构建二维数组
vector<string> vv(numRows);
//2.字符排放
int flag = 1;
int a = 0;
int b = numRows - 2;
for (int i = 0; i < s.size(); i++)
{
//2-1:从上往下
if (flag == 1)
{
if (a <= numRows - 1)
{
vv[a] += s[i];
a++;
}
if (a == numRows)
{
if(numRows >= 3)
a = 0, flag = -1;
a = 0;
}
}
//2-2:从下往上
else
{
if (b >= 0)
{
vv[b] += s[i];
b--;
}
if (b == 0)
b = numRows-2, flag = 1;
}
}
//3.定义字符串类型进行+=
string ret;
for (int i = 0; i < numRows; i++) ret += vv[i];
return ret;
}
};
2.思路二:找规律进行优化
class Solution{
public:
string convert(string s, int numRows) {
//0.特殊情况判断:
if (numRows == 1)
return s;
//1.计算公差
int d = (2 * numRows) - 2;
int n = s.size();
//2.规律去模拟不需要创建额外的空间:
string ret;
for (int i = 0; i < numRows; i++)
{
//1.第一行字符
if (i == 0)
for (int i_1 = 0; i_1 < n; i_1 += d) ret += s[i_1];
//2.最后一行字符
else if (i == numRows - 1)
for (int i_n = numRows - 1; i_n < n; i_n += d) ret += s[i_n];
//3.中间字符:左在右不在特殊情况
else
for (int i_k_left = i, i_k_right = d - i; (i_k_left < n) || (i_k_right < n); i_k_left += d, i_k_right += d)
{
if(i_k_left < n )
ret += s[i_k_left];
if(i_k_right < n)
ret += s[i_k_right];
}
}
return ret;
}
};
//时间复杂度:O(n)
//空间复杂度:O(1)
四.外观数列
1.思路一:模拟
class Solution {
public:
string countAndSay(int n) {
//1.开始字符串:
string ret("1");
//2.内容的遍历:
while (--n)
{
int left = 0, right = 0;
string s1;
//3.字符串的遍历+数据更新
for (left = 0, right = 0; right < ret.size(); right++)
{
if (ret[right] != ret[left])
{
int n = (right - left ) * 10 + (int)(ret[left] - '0');
//1.数据保存一下:
s1 += to_string(n);
//2.指针数值更新
left = right;
}
}
//4.数据都不去走for中的if产生的问题。
int n = (right - left) * 10 + (int)(ret[left] - '0');
s1 += to_string(n);
ret = s1;
}
return ret;
}
};
五.数青蛙
1.思路一:模拟+哈希记录数据
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
//1.哈希表记录数据
unordered_map<char, int> indx;
vector<int> hash(5);
//2.初始化hash的字符值?
string s1("croak");
//3.遍历一遍
int n = s1.size();
for (int i = 0; i < n; i++) indx[s1[i]] = i;
//4.遍历字符串考虑青蛙!
for (auto ch : croakOfFrogs)
{
//1.第一个c
if (ch == 'c')
{
//1.k有值
if (hash[n - 1] >= 1)
hash[0]++, hash[n - 1]--;
//2.k没有值
else if (hash[n - 1] == 0)
hash[0]++;
}
//2.正常情况:
else
{
int j = indx[ch];
if (hash[j - 1] == 0) return -1;
hash[j - 1]--, hash[j]++;
}
}
//特殊情况:结束之后应该除了k位置hash是有数值其他hash中应该是没有数值的!
for(int i=0;i<n-1;i++)
{
if(hash[i]!=0)
return -1;
}
return hash[n - 1];
}
};
文章来源:https://blog.csdn.net/2201_75943325/article/details/135382793
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!