记topcoder干一道250分题的坎坷经历

记topcoder做一道250分题的坎坷经历

闲来无聊，想去topcoder做做题。以前从来没有玩过topcoder，抱着一边摸索一遍做题的心态打开了topcoder。

没有比赛，而且我这水平也不能参加比赛。就随便找了一个practice room把以前比赛的题练习一下吧。

如果要参加比赛的话，要在75分钟内做3道题。分值分别是250分，500分和1000分，难度依次递增。

我打开了一道250分的题，看题目+思路完成用了10分钟的时间，编码和查C++的STL用法却用了1个多小时的时间，真是令人拙计。

先说下题目是什么吧：

给你一个string的vector，里面存储着很多人的名字，类似于

{"Tom Jones", "ADAMS", "BOB ADAMS", "Tom Jones", "STEVE jONeS"}

名字越靠后，说明这个人越重要。将这个vector根据人的lastname来进行按字母顺序排序，并且忽视大小写。如果两个人的lastname相同，则越重要的人出现在越前面。若这个人的名字只有一个单词，比如 "ADAMS"，那么这个单词就认为是这个人的lastname。

举个例子，"Tom Jones" > "ADAMS"，因为"Jones" > "ADAMS"。

在上面的{"Tom Jones", "ADAMS", "BOB ADAMS", "Tom Jones", "STEVE jONeS"} 例子中，排序的结果就是

{ "BOB ADAMS", "ADAMS", "STEVE jONeS", "Tom Jones", "Tom Jones" }

我的简单思路：

这就是一个排序问题，但当键值（lastname）一样时，原本靠后的元素出现在靠前，这样我想起了稳定排序。只要把原序先求反序列，然后再用稳定排序就可以了。需要传入的比较函数比较函数就是把lastname取出来然后忽视大小写比较一下就可以了。

然后去查STL里面稳定排序的模板，写完代码以后编译遇到了一个错误：类成员函数指针不能用作函数指针，类型不符。

因为topcoder上所有的函数都是封装在类里面才能提交的，所以普通的函数只能写成类的成员函数。

然后查google，看了很多资料，在stackoverflow上有人问了和我几乎一样的问题（链接），也是在类里面用稳定排序遇到这样的错误，大概原因是成员函数有一个this指针，所以类型错误，解决办法是在成员函数前面加上static使它变成静态函数，没有了this指针就可以了。

我试了下，果然成功了。下面是我最终的代码，transform函数将string小写化；string的find_last_of函数用来提取lastname。整个过程花了大概一个多小时。人家3道题才花75分钟啊........

肯定有效率更高的解法（比如代码里每次compare都要调用keyConvert，对同一个对象可能调用多次keyConvert。可以事先对表遍历一遍把所有的key存起来，避免多次调用keyConvert），等待有兴趣的朋友提出。

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

class NameSort
{
public:
	static bool compare(string s1, string s2)
	{
	    return keyConvert(s1) < keyConvert(s2);
	}

	vector<string> newList(vector<string> list)
	{
		reverse(list);
        stable_sort(list.begin(), list.end(), compare);
        return list;
	}

	void reverse(vector<string> & list)
	{
	    string tmp;
		vector<string>::iterator begin,end;
		for(begin=list.begin(), end=list.end()-1; begin != end; begin++, end--)
		{
		    tmp = *begin;
		    *begin = *end;
		    *end = tmp;
		}
	}

	static string keyConvert(string &s)
	{
	    string tmp;
	    tmp.resize(s.size());
        transform(s.begin(), s.end(), tmp.begin(), ::tolower);
        int found = tmp.find_last_of(' ');
        if(found != string::npos)
            tmp = tmp.substr(found+1);
        return tmp;
	}

};

记topcoder干一道250分题的坎坷经历

相关推荐