leetcode -- Largest Number

3606 ワード
LeetCode C++ ソフト qsort
原題:
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given  [3, 30, 34, 5, 9] , the largest formed number is  9534330 .
Note: The result may be very large, so you need to return a string instead of an integer.
この問題の最良の解法はシーケンスをソートすることであり,ソートの比較関数が鍵となる.比較の準則は、比較関数の2つのパラメータを見て、1つ前と2つの法案に従って、文字列につづった後、その案で得られた文字列辞書の順序が大きいことです.
ここで,この問題を借りてCにおけるqsort関数とSTLにおけるsort関数の違いを比較する.
解法一:Cのqsort関数を使用する.
string IntToStr(int n) {
	string res;

	if(n == 0) {
		res += '0';
		return res;
	}

	while(n) {
		res += n % 10 + '0';
		n /= 10; 
	}

	reverse(res.begin(), res.end());
	return res;
}
int CMP(const void *iter1, const void *iter2) {
	string s1, s2;
	int * it1 = (int *)iter1;
	int * it2 = (int *)iter2;


	s1 = IntToStr(*it1);
	s2 = IntToStr(*it2);

	if(s1 + s2 < s2 + s1)
		return 1;
	else if(s1 + s2 > s2 + s1)
		return -1;
	else
		return 0;
}	

class Solution {
public:
    string largestNumber(vector<int> &num) {
		int* a = new int[num.size()];
		for(int i = 0; i != num.size(); i++)
			a[i] = num[i];

		//vector<int>::iterator it1 = num.begin();
		//vector<int>::iterator it2 = num.end();

		int (*cmpfunp)(const void *, const void *);
		cmpfunp = CMP;

        qsort(a, num.size(), sizeof(int), cmpfunp);

		string res;

		for(int i = 0; i != num.size(); i++) {
			res += IntToStr(a[i]);
		}
		
		int flag = 0;
		for(int i = 0; i != res.size(); i++) {
			if(res[i] != '0'){
				flag = 1;
				break;
			}
		}
		if(flag == 0) {
			res = "0";
		}

		return res;
	}

};
注意すべきことは、
void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
4つのパラメータは次のとおりです.
1ソート対象配列の先頭アドレス
2配列内のソート対象要素の数
3各要素の占有スペースの大きさ
4ソート順を決定するための関数へのポインタ
関数ポインタの形式はint(*fcmp)(const void*,const void*)でなければなりません.constは少なくなく、voidも他のタイプに変えることはできません.比較関数の内部で実際に比較した要素タイプに基づいて強制的にタイプ変換するしかありません.qsortはCの関数であり、その内部メカニズムはvoidタイプのポインタを直接操作するため、C++のコンテナを直接ソートすることはできない.この問題は入力時のvectorを規定しているので、qsortを使用しなければならない場合はint配列でvectorを一時保存するしかない.
Qsortを使用して他のタイプをソートする場合も注意すべき点があります.詳細はブログを参照してください.http://www.cnblogs.com/syxchina/archive/2010/07/29/2197382.html
解法2:STLのsort関数を使用します.
string IntToStr(int n) {
	string res;

	if(n == 0) {
		res += '0';
		return res;
	}

	while(n) {
		res += n % 10 + '0';
		n /= 10; 
	}

	reverse(res.begin(), res.end());
	return res;
}
	
bool STL_CMP(int &a, int &b) {
	string s1, s2;

	s1 = IntToStr(a);
	s2 = IntToStr(b);

	if(s1 + s2 > s2 + s1)
		return true;
	else 
		return false;
}
class Solution {
public:
    string largestNumber(vector<int> &num) {

		sort(num.begin(), num.end(), STL_CMP);

		string res;

		for(int i = 0; i != num.size(); i++) {
			res += IntToStr(num[i]);
		}
		
		int flag = 0;
		for(int i = 0; i != res.size(); i++) {
			if(res[i] != '0'){
				flag = 1;
				break;
			}
		}
		if(flag == 0) {
			res = "0";
		}

		return res;
	}

};

STLのsort関数には複数のリロードバージョンがあり、3番目のパラメータ(比較関数)は
省略すると、省略するとoperate<で配列されたシーケンスがデフォルトで生成されます.
sortの3番目のパラメータは、関数ポインタ(以上のコードなど)であってもよいし、擬似関数であってもよい.関数ポインタの場合、形式はbool(*cmp)(TYPE&a,TYPE&b)であり、戻り値はboolであり、qsortの戻り値はintである.
ここでのsortはqsortと同様に非安定ソートであり,STLにおけるソートアルゴリズムにはstable_sortなど.
STLのsortの詳細についてはブログを参照してください.
http://blog.163.com/lovelychicken0824@126/blog/static/2277337420071894051206/
http://www.cppblog.com/mzty/archive/2005/12/15/1770.html
Laravelフレームワークgit cloneを使用するときに発生する問題
thisキーワードの役割