【阿里】研发工程师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++工程师#
全部评论
思想:保存字典中所有字符串的长度,快速排序; 对给出的字符串切割的时候,先按最长的切,然后查字典,如果有则继续切下一个,没有换短一点的长度。因为时间仓促,字符串的长度都保存了,没有把重复的删除。 //最终耗时0ms,应该测试样例不多。
点赞 回复 分享
发布于 2017-08-25 22:32
一看很简单,写不出来,放弃了
点赞 回复 分享
发布于 2017-08-25 23:44
每次取最长的词,如果得到结果肯定是最优。但是,是不是存在,如果只取最长而导致找不到解。 如例子  解为 i alibab aman,如果只考虑取最长的,就 i alibaba "man" (man not exist)无解。所以我觉得这题还需要用到回溯。 ialibabaman 4 i alibaba alibab aman
点赞 回复 分享
发布于 2017-08-26 00:33
没有什么好的方法,直接用了回溯暴力AC过
点赞 回复 分享
发布于 2017-08-26 03:14

相关推荐

新记话事人:你就和她说去抖音了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务