3.31华为软件笔试编程题第3题
输入小写元素组成的字符串str，再输入小写元素组成的需要查找的子串substr（保证子串中的字符至少在str中出现一次）
需要移动游标，以最少的步数找到子串。游标可以向左移动或者向右移动，移动到边界可以循环至另一头。
str长度：[1,1000]; substr长度：[1,100]
in：
aemoyn
amo
0
out:
3
思路：气死我了刚开始以为是贪心算法，每步选择距离最短的下一个index。结果只通过了75%，最后十分钟想通了需要输出总步数最小！！！！所以贪心算法不得行！！！（暴风咆哮）
结果没来得及提交时间就到了，捶胸顿足ing....
贴上代码，递归层数还是挺多的...也不知道能不能ac...
如果有问题请指出，有更好解法请艾特我，谢谢！
#include <bits/stdc++.h>
string str,sustr;
int len;
map< char,vector<int> > mp;
int rec(int before,int index, int supos){
if(supos == sustr.size() ) return before;
if(sustr[supos] == str[index]) return rec(before, index,supos+1);
int res = INT_MAX;
char a = sustr[supos];
for(int j=0;j<mp[a].size();j++ ){
int np = mp[a][j];
res = min(res, rec(before+ min(abs(index - np) , abs( len - abs(index-np) )) , np, supos+1));
}
return res;
}
int main(){
//string str,sustr;
cin>>str;
getchar();
cin>>sustr;
getchar();
int index;
cin>>index;
//cout<< str<<" "<<sustr<<" "<<index<<endl;
len = str.size();
for(int i=0;i<len;i++){
mp[ str[i] ].push_back(i);
}
int res=rec(0, index, 0);
cout<<res<<endl;
return 0;
}
查看3道真题和解析