LeetCode179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1
2
Input: [10,2]
Output: "210"

Example 2:

1
2
Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.


思路

std::sort + lambda

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string largestNumber(vector<int> &num) {
vector<string> arr;
for(auto i:num)
arr.push_back(to_string(i));
sort(begin(arr), end(arr), [](string &s1, string &s2){ return s1+s2>s2+s1; });
string res;
for(auto s:arr)
res+=s;
while(res[0]=='0' && res.length()>1)
res.erase(0,1);
return res;
}
};

1.将所有int转为string,放入容器中,to_string(int)。

2.用stl将容器中的string按照自定义的方法排序。这是一个很巧的解法。

1
2
std::sort(begin(arr),end(arr),
[](string &s1,string &s2){return s1+s2>s2+s1;})

这是一个lambda表达式。它使得排序后的结果让前面遍历过的string连接起来永远是最大的。

用>可以比较string的大小。两个字符串自左向右逐个字符相比(按ASCII值大小相比较),直到出现不同的字符或遇’\0’为止。

当两个数的位数一样,则直接可以应用字符串的比较。如

1
"1346" > "1111" == true

例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string>
using namespace std;

int main(){
string str1("235");
string str2("121");

bool result;
result = str1 > str2;
cout<<result<<endl; // 1

str1 = "1111";
result = str1 > str2;
cout<<result<<endl; // 0

str1 = "111";
result = str1 > str2;
cout<<result<<endl; // 0

return 0;
}

3.将容器中排序好的string加起来。这里有一个细节,如果第一个数是0或者string的长度不为零,就将0去掉。

1
2
while(res[0]=='0' && res.length()>1)
res.erase(0,1);

复习一下std::vector::erase

  • iterator erase( iterator pos );(C++11 前)
  • iterator erase( const_iterator pos );(C++11 起)
  • iterator erase( iterator first, iterator last );(C++11 前)
  • iterator erase( const_iterator first, const_iterator last );(C++11 起)

1) 移除位于 pos 的元素。
2) 移除范围 [first; last) 中的元素。


C++ code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
string largestNumber(vector<int>& nums) {
std::vector<string> a;
for(auto const & item:nums)
{
a.push_back(to_string(item));
}

sort(a.begin(),a.end(),[](string & a,string &b){return a+b>b+a;});

string ret;
for(auto const & item:a)
{
ret+=item;
}

if(ret[0]=='0')
return "0";
else
return ret;

}
};

改进:结果的第一个字符为0,直接返回”0”.

1
2
if(ret[0]=='0')
return "0";

细节:ret[0]是一个char,而非string,所以用’’,否则报错。


总结

1.本题考的是字符串排序的内容,要用到sort+lambda表达式。其中lambda表达式的写法是重点。

2.语法:to_string(int)。将int转string放入容器。

3.string 的大小比较用>,返回bool值。

4.最后把容器中的值用+操作符重载,将字符串链接起来。

5.如果第一个字符是‘0’,就返回”0”

扩展

如果要求最小的数,也用lambda函数。另外,用类来指定方法比class要更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
vector<string> a;
for (auto const& item : numbers)
{
a.push_back(to_string(item));
}

sort(a.begin(), a.end(), MyCompare);

string ret;
for (auto const& it : a)
ret += it;
if (ret[0] == '0')
return "0";
return ret;
}

private:
static bool MyCompare(const string&str1, const string &str2)
{
return str1 + str2 < str2 + str1;//最小的数
}
};
Thanks for Support.