阿里笔试(C++)

第一题和之前在leetcode上刷过的一题Word Break II有很多类似之处,感觉就是那道题改变了下?所以侥幸过了。
第二题没看懂题意,感觉自己很菜,不知有没有大神过了。这一贴一下第一题的代码:
#include <string>
#include <cstdio>
#include <set>
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

/***
* ilikealibaba
* i like ali liba baba alibaba
**/
unordered_set<string> wordict;
unordered_map<string, vector<string>> map;

vector<string> wordscut(string s)
{
    if (map.find(s) != map.end())
        return map[s];
    vector<string> sens;
    for (int pos = s.size() - 1; pos >= 0; --pos)
    {
        string word = s.substr(pos);
        if (wordict.find(word) != wordict.end())
        {
            if (pos == 0) sens.push_back(word);
            else
            {
                vector<string> subSens = wordscut(s.substr(0, pos));
                for (auto subSens : subSens)
                    sens.push_back(subSens + " " + word);
            }
        }
    }
    map[s] = sens;
    return sens;
}

vector<string> helper(string s, const set<string> & Dict)
{
    wordict.insert(Dict.cbegin(), Dict.cend());
    return wordscut(s);
}

bool compare(string str1, string str2)
{
    return str1.length() < str2.length();
}

void mincut(const string& str, const set<string>& dict)
{
    int slen = str.length();
    int size = dict.size();
    if (size == 0)
    {
        cout << "n/a" << endl;
        return;
    }
    vector<string> res = helper(str, dict);
    if (res.empty())
    {
        cout << "n/a" << endl;
        return;
    }
    sort(res.begin(), res.end(), compare);
    cout << res[0] << endl;
}


int main(int argc, const char * argv[])
{
    string strS;
    string dictStr;
    int nDict;
    set<string> dict;

    cin >> strS;  //获取字符串
    cin >> nDict; //字典中词的个数
    for (int i = 0; i < nDict; i++)
    {
        cin >> dictStr;
        dict.insert(dictStr);
    }
    mincut(strS, dict);

    return 0;
}


全部评论
大神,hard级别的啊。。。
点赞
送花
回复
分享
发布于 2017-08-25 21:22
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long; using namespace std; bool comp(const string &s1,const string &s2) { return s1.length()<s2.length(); } vectornewStr; void mincut(const string& str, const set& dict,int s,string sstr) { if(s==str.length()) { newStr.push_back(sstr); } for(auto it=dict.begin();it!=dict.end();it++) { string t=*it; int i; for(i=0;i<t.length();++i) if(t[i]!=str[i+s])break; if(i==t.length()&&s+i<=str.length()) { if(s) t=" "+t; mincut(str,dict,s+i,sstr+t); } } } int main(int argc, const char * argv[]) { string strS; string dictStr; int nDict; set dict; cin>>strS; cin>>nDict; for (int i = 0; i < nDict; i++) { cin>>dictStr; dict.insert(dictStr); } mincut(strS, dict,0,string()); if(newStr.size()) { sort(newStr.begin(),newStr.end(),comp); cout<<newStr[0]; } else { cout<<"n/a"; } return 0; } 因为没有看到最后如果不匹配就输出"n/a",所以提交的代码里没有最后的条件判断,通过率75%,可以用一个string代替vector,减小空间复杂度
点赞
送花
回复
分享
发布于 2017-08-25 22:07
滴滴
校招火热招聘中
官网直投
渣渣就是大神的代码贴出来了,还看不懂。。。
点赞
送花
回复
分享
发布于 2017-08-25 22:34

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务