LeetCode—Largest Number

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つの数字の比較であり,ここでは数値的な比較ではなく,最上位からの比較である.
簡単な比較関数で結果を得ることができます
 bool cmp(string str1,string str2) { return (str1+str2) >= (str2+str1); }
次は私の答えです:(複数の0が発生した場合、直接0として使用することに注意してください)

<span style="color:#333333;">#include <sstream> 
#include <string>
#include <vector>
using namespace std;

bool cmp(string str1,string str2)
{
	return (str1+str2) >= (str2+str1);
}
string GetSort(vector<string> vecString)
{
	int length = vecString.size();
	string maxStr = "";
	bool flag = false;
	while (!vecString.empty())
	{
		string maxVal = "0";
		vector<string>::iterator maxRecode;
		vector<string> :: iterator it = vecString.begin();
		for (;it < vecString.end(); it++)
		{
			if (cmp(*it,maxVal))
			{
				maxVal = *it;
				maxRecode = it;
			}
		}
		vecString.erase(maxRecode);
		if (maxVal != "0")
		{
			maxStr += maxVal;
			flag = true;
		}
		else if(flag)
		{
			maxStr += maxVal;
		}
     }
	if (!flag)
	{
		maxStr += "0";
	}
	return maxStr;
}
string largestNumber(vector<int> &num) {
	vector<string> vecString;
	string maxValNum = "";
	int length = num.size();
	if(length == 0)
	{
		return NULL;
	}
	if(length == 1)
	{
		stringstream ss;
</span><span style="color:#ff0000;">		ss << num[0];
		return ss.str();  //< int   string</span><span style="color:#333333;">
	}	
	for (int i = 0; i < num.size(); i++)
	{
		stringstream ss;
		ss << num[i];
		vecString.push_back(ss.str());
	}
	//stack<int> stackStr = GetSort(vecString);
	maxValNum = GetSort(vecString);
	return maxValNum;
}	
	

void main()
{
	vector<int> it;
	it.push_back(13);
	it.push_back(9);
	it.push_back(0);
	string x = largestNumber(it);
}</span>

中にはSTL対応のsort関数を直接利用して,対応するソートを行う方法もある.

<span style="color:#333333;">#include <sstream> 
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(const string s1, const string s2) {
	return (s1 + s2) > (s2 + s1);
}

string largestNumber(vector<int> &num) {
	vector<string> s_num(num.size());
	stringstream stream;
	for (int i = 0; i < num.size(); ++i) {
		stream << num[i];
		stream >> s_num[i];
		stream.clear();
	}
	</span><span style="color:#ff0000;"><strong>sort(s_num.begin(), s_num.end(), cmp);</strong></span><span style="color:#333333;">
	string tmp_res;
	for (int i = 0; i < s_num.size(); ++i) {
		tmp_res += s_num[i];
	}
	string res;
	bool flag = false;
	for (int i = 0; i < tmp_res.size(); ++i) {
		if (tmp_res[i] != '0') {
			res.push_back(tmp_res[i]);
			flag = true;
		} else if (flag) {
			res.push_back(tmp_res[i]);
		}
	}
	if (!flag) res.push_back('0');
	return res;
}	
	

void main()
{
	vector<int> it;
	it.push_back(13);
	it.push_back(9);
	it.push_back(0);
	string x = largestNumber(it);
}</span>