leetcode 专题—sort

朱雀 2022-08-08 05:30 155阅读 0赞

此将主要将leetcode中sort专题的解答都放在这里，后续会慢慢加入

一：leetcode179 [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.

分析：这里主要采用stl中的sort函数，注意对与3和33，我们认为其是相等的，另外3要比31大且比34小。最后需要注意的是stl中sort函数对于相等操作要返回false，返回true的话会报异常，警告信息为：

Debug Assertion Failed!  
File: c:\\program files (x86)\\microsoft visual studio   
10.0\\vc\\include\\algorithm  
Line: 3657  
Expression: invalid operator<  
调试的时候查看源码就知道了，源码如下：

bool \_\_CLRCALL\_OR\_CDECL \_Debug\_lt\_pred(\_Pr \_Pred, \_Ty1& \_Left, \_Ty2& \_Right,

const wchar\_t \*\_Where, unsigned int \_Line)

\{// test if \_Pred(\_Left, \_Right) and \_Pred is strict weak ordering

if (!\_Pred(\_Left, \_Right)) // 相等返回true， else if中仍然返回true

return (false);

else if (\_Pred(\_Right, \_Left))

\_DEBUG\_ERROR2("invalid operator<", \_Where, \_Line);//断言出现在这里。

return (true);

代码：

bool cmp(const string &str1, const string &str2){
    	if(str1 == str2) return false;     // 对于STL中的sort 相等不能返回true 看源码就知道了 否则就会报异常
        int m = str1.size(), n = str2.size();
        int i= 0, j = 0;
        while(i < m && j < n){
            if(str1[i] < str2[j]) return true;
            else if(str1[i] > str2[j]) return false;
            else{
                if(i+1 == m && j+1 == n) return false;    // 这个主要处理比如3 和33的情况 可以认为是相等的
                if(i+1 < m)i++;
    			else i = 0;
                if(j+1 < n)j++;
    			else j = 0;
                
            }
        }
        return true;
    }
    
    class Solution {
    public:
        string largestNumber(vector<int>& nums) {
            
          //  if(nums.size() == 0) return str;
            numsStr.resize(nums.size());
            for(int i = 0; i < nums.size(); i++){
                stringstream ss;
                ss << nums[i];
                ss >> numsStr[i];
            }
            sort(numsStr.begin(), numsStr.end(), cmp);
            string str;
            for(vector<string>::reverse_iterator iter = numsStr.rbegin(); iter != numsStr.rend(); iter++)
                str += *iter;
            if(str[0] == '0') str = "0";
            return str;
        }
    private:
        vector<string> numsStr;
    };

[Largest Number]: https://leetcode.com/problems/largest-number/