2020年4月3日
LeetCode 179. Largest Number
C++, LeetCode, 算法, 编程
0 Comments
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2] Output: "210"
Example 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.
解析：根据给定的一个数组中的数字，进行组合返回所表示的最大的数值。
思路：自己思考的一个解法是，借助sort函数进行自定义的排序方式，sort函数里面将int转为string，然后挨个比较字符大小，但在实现的时候发现3和30的比较会出问题。后来看到网上别人的解法，对于str1和str2，直接比较str1+str2与str2+str1的大小，这样思路比较灵巧，也更简洁。代码如下：
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> arr;
string result = "";
for(auto num : nums)
arr.push_back(to_string(num));
std::sort(arr.begin(), arr.end(), [](string& str1, string &str2){return str1+str2 > str2+str1;});
for(auto str : arr)
{
result += str;
}
while(result[0]=='0' && result.length()>1)
result.erase(0,1);
return result;
}
};
参考：
https://leetcode.com/problems/largest-number/discuss/53157/A-simple-C%2B%2B-solution
About Author
