【阿里】研发工程师C/C++ 笔试第一道AC代码
//原代码有bug,感谢@MingjaLee指出问题,做了修改。 //总的来说,题目不难,感觉考察的是能不能把问题考虑的周到细致。 //最后希望有大神能给出一个时空复杂度最优的解。 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <vector> #include <stack> #include <set> #include <algorithm> #include <functional> #include <iterator> using namespace std; //插入排序,对字典中单词的长度插入排序,存在数组中,长度相同的只存在一个 void insertsort(vector<int> &a, int target) { if (a.empty()) { a.push_back(target); return; } int i = a.size() - 1; while (i >= 0 && a[i] > target) { i--; } if (i >= 0 && a[i] == target) return; else if (i == a.size() - 1) a.push_back(target); else { int k = i + 1; a.insert(a.begin() + k, target); } } void mincut(const string& str, const set<string>& dict) { vector<string> res;//保持结果 set<string>::iterator dictit = dict.begin(); vector<int> lens; //读取字典中所有单词的长度并对长度插入排序 while (dictit != dict.end()) { insertsort(lens, (*dictit).length()); dictit++; } int strlen = str.length(); //建立一个栈,用来存每个分割后的单词的长度 //(存的方式是已经保持的单词长度数组的下表)。 stack<int> wordslen; int k = lens.size() - 1; for (int i = 0; i < strlen;) { //对于每个未被寻找的单词,先假设它的长度为最长的单词 wordslen.push(k); //按当前栈顶所给长度匹配,如果哟匹配到,则i移动单词长度个单位, //没有找到,缩短单词长度,继续找。如果已经到最短了,依然找不到, //删除已保存的字符串,弹出栈顶元素后栈顶元素减一,重新寻找新的 //上一个单词,如果找不到,继续删除,如果栈空了,则说明不匹配, //输出“n/a”。 while (!dict.count(str.substr(i, lens[wordslen.top()]))) { if (wordslen.top() == 0) { wordslen.pop(); if (wordslen.empty()) { cout << "n/a"; return; } res.pop_back(); i -= lens[wordslen.top()]; while (!wordslen.empty() && !wordslen.top()) wordslen.pop(); if (wordslen.empty()) { cout << "n/a"; return; } wordslen.top()--; } else { wordslen.top()--; } } res.push_back(str.substr(i, lens[wordslen.top()])); i += lens[wordslen.top()]; } for (int i = 0; i < res.size(); i++) cout << res[i] << " "; } int main(int argc, const char * argv[]) { string strS; string dictStr; int nDict; set<string> dict; cout << "please input string: \n"; cin >> strS; cout << "Please input the nums of word in dict: \n"; cin >> nDict; for (int i = 0; i < nDict; i++) { cin >> dictStr; dict.insert(dictStr); } mincut(strS, dict); cout << "\n"; system("pause"); return 0; } //这是原答案 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <vector> #include <set> #include <algorithm> using namespace std; void mincut(const string& str, const set<string>& dict) { vector<string> res; set<string>::iterator it; int len = 0; vector<int> nums; for (it = dict.begin(); it != dict.end(); it++) { if ((*it).size() > len) len = (*it).length(); nums.push_back((*it).length()); } sort(nums.begin(), nums.end()); int strlen = str.size(); for (int i = 0; i < strlen;) { int k = nums.size() - 1; int j = nums[k]; if (i + j > strlen) { k--; j = nums[k]; } int l = 0; for (l = k; l >= 0; l--) { k--; if (dict.count(str.substr(i, nums[l]))) break; } if (l < 0) break; res.push_back(str.substr(i, nums[l])); i = i + nums[l]; } int maxlen = 0; for (int i = 0; i < res.size(); i++) { maxlen += res[i].size(); } if (maxlen == str.size()) { for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; } } else { cout << "n/a" << endl; return; } } 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; }
#阿里巴巴##C++工程师#