算法修炼之路之模拟
目录
前言
模拟算法就是根据题目要求,自行将示例模拟一遍,再观察规律将模拟过程转换为代码
二:LeetCode OJ练习
1.第一题
画图分析:
具体代码:
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 || s[i-1]!=ch) && (i==n-1 || s[i+1]!=ch))
{
s[i]=ch;
break;
}
}
}
}
return s;
}
2.第二题
画图分析:
具体代码:
int findPoisonedDuration(vector<int>& timeSeries, int duration)
{
int ret=0;
for(int i=1;i<timeSeries.size();++i)
{
int x=timeSeries[i]-timeSeries[i-1];
if(x>=duration) ret+=duration;
else ret+=x;
}
return ret+duration;//处理最后一次受到的攻击
}
3.第三题
画图分析:
具体代码:
string convert(string s, int numRows)
{
//处理边界情况
if(numRows==1) return s;
string ret;
int d=2*numRows-2;//计算公差
int n=s.size();
//1.处理第一行
for(int i=0;i<n;i+=d) ret+=s[i];
//2.处理中间行
for(int m=1;m<=numRows-2;++m)
{
for(int i=m,j=d-m;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;
}
4.第四题
画图分析:
具体代码:
string countAndSay(int n)
{
string ret="1";
for(int i=1;i<n;++i)//解释n-1次
{
string tmp;
int n=ret.size();
for(int left=0,right=0;right<n;)
{
while(right<n && ret[left]==ret[right])++right;
tmp+=to_string(right-left)+ret[left];
left=right;
}
ret=tmp;
}
return ret;
}
5.第五题
画图分析:
具体代码:
int minNumberOfFrogs(string croakOfFrogs)
{
string str="croak";
int n=str.size();
vector<int> hash(n);//用数组模拟哈希表
unordered_map<char,int> sm;//存储字符x以及x对应的下标
for(int i=0;i<n;++i) sm[str[i]]=i;
for(auto ch:croakOfFrogs)
{
if(ch=='c')
{
if(hash[n-1]) hash[n-1]--;
hash[0]++;
}
else
{
int j=sm[ch];
if(hash[j-1]) hash[j-1]--,hash[j]++;
else return -1;
}
}
//最后遍历一边数组,如果不为0说明字符串不合法
for(int i=0;i<n-1;++i)
{
if(hash[i]) return -1;
}
return hash[n-1];
}
原文地址:https://blog.csdn.net/Miwll/article/details/142822952
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!