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;
}


#笔试题目##华为#
全部评论
这个递归暴力复杂度是O(2^n),想卡时间肯定能卡,只有数据水才能过。正解是dp。众所周知,不能贪心就是dp。
1 回复
分享
发布于 2021-03-31 21:29
同75%
点赞 回复
分享
发布于 2021-03-31 21:14
小红书
校招火热招聘中
官网直投
双指针 75
点赞 回复
分享
发布于 2021-03-31 21:35

相关推荐

2 18 评论
分享
牛客网
牛客企业服务