leetcode Question: Largest Number

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.

Analysis:

The key to this question is  ---- Don't think it too complicated.
No recursion, no DP, no complicated sorting is needed.

Let's look at the question in this way:
(1) All the numbers are used. (No need to choose)
(2) Order of the numbers is important. (May use sorting algorithm)
(3) How to determine the order of  like 30 and 3?   3>30? 3< 30?

So it is natural to think that sorting is all we need. If I can get the sorted list of numbers, the last step is just concatenate them and output as a string.

Sort can be done by calling library functions (e.g., c++ sort(a.begin(), a.end(), _comp), python sorted(a, comp)), where we need to define the compare function.  Note that in c++,  _comp in sort function need to be static.  

How to define the compare function?
1. Consider two int, a and b.  e.g., 34 and 3.
2. Actually, what we need to compare is not 34 and 3, but  3 43 and 3 34. 
3. If 343 > 334, then 34 should have higher order than 3, and vice versa.


In my code, the int are converted into string in case of long length. In c++, stringstream is a good way to do so.

Note:
(1) In c++, comp function must be static and it returns true and false.
(2) In python, comp function must return positive , 0 and negative numbers to represent greater, equal and smaller.  (see note 8 in here)
(3) In sort function, ascending order is the default. So in my code I change the order in comp function so that the output is descending order.
(4) String compare, either in C++ or Python, is comparing each char from the start. And if the compared string is shorter, it will return "smaller"

Code(C++):

class Solution {
public:
    static bool _comp(int a, int b){
        ostringstream ss;
        ss << a;
        string sa = ss.str();
        ss.clear();
        ss << b;
        string sb = ss.str();
        ss.clear();
        
        sa = sa + sb;
        sb = sb + sa;
        
        if (sa.compare(sb) >=0){
            return true;
        }else{
            return false;
        }
    }

    string num2str(int i){
        ostringstream ss;
        ss << i;
        return ss.str();
    }
    
    string largestNumber(vector<int> &num) {
        
        string res="";
        
        sort(num.begin(),num.end(), _comp);
        
        if (num[0]==0){return "0";}
        
        for(int i=0;i<num.size();i++){
            res = res+ num2str(num[i]);
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        def my_cmp(x,y):
            sx = str(x)
            sy = str(y)
            sx = sx + sy
            sy = sy + sx
            if sx > sy:
                return -1
            if sx == sy:
                return 0
            if sx < sy:
                return 1
           
        num = sorted(num, cmp=my_cmp)
        
        if num[0] == 0:
            return "0"
        else:
            return "".join([str(n) for n in num])
        
        

leetcode Question: Compare Version Numbers

 Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Analysis:

This question is to test the skills of string to int and int to string convention.
In C++, parsing string (e.g., parse string according to ' , ') as well as int to string operation can be done using the stringstream.  In python, it is much easier since we have int() and str() methods to do so.

The idea of this problem could be considered to compare two list of numbers that are separated by '.' Note that when comparing list with different length, if they are the same for the 1st part, if the longer list have all 0s in its tail, then those two lists are the same. E.g.,    1.0.000.0 and 1, two lists generated are [1,0,0,0], and [1]. And it is necessary to check "all" digits instead of checking only the "next" digits because if there exists one digit that is not 0, the two numbers are not equal.  

Code(C++):

class Solution {
public:
    int compareVersion(string version1, string version2) {
        istringstream st1(version1);
        istringstream st2(version2);
        string token;
        vector<int> d1;
        vector<int> d2;
        while (getline(st1,token,'.')){
            stringstream os1;
            os1.str(token);
            int tmp;
            os1 >> tmp;
            d1.push_back(tmp);
        }
        while (getline(st2,token,'.')){
            stringstream os2;
            os2<<token;
            int tmp;
            os2 >> tmp;
            d2.push_back(tmp);
        }
        
        int n1 = d1.size();
        int n2 = d2.size();
        
        for (int i=0;i<min(n1,n2);i++){
            if (d1[i]>d2[i]){ return 1;}
            if (d1[i]<d2[i]){ return -1;}
        }
        
        if (n1<n2){
            for (int i=n1;i<n2;i++){
                if (d2[i]!=0){return -1;}
            }
            return 0;
        }
        if (n1>n2){
            for (int i=n2;i<n1;i++){
                if (d1[i]!=0){return 1;}
            }
            return 0;
        }
        if (n1==n2){return 0;}
    }
};

Code(Python):

class Solution:
    # @param version1, a string
    # @param version2, a string
    # @return an integer
    def compareVersion(self, version1, version2):
        l1 = version1.split('.')
        l2 = version2.split('.')
        for i in range(min(len(l1),len(l2))):
            if int(l1[i]) > int(l2[i]):
                return 1
            if int(l1[i]) < int(l2[i]):
                return -1
                
        if len(l1)<len(l2):
            if all( int(n)==0 for n in l2[len(l1)::]):
                return 0
            else:
                return -1
            
        if len(l1)>len(l2):
            if all( int(n) == 0 for n in l1[len(l2)::]):
                return 0
            else:
                return 1
                
        if len(l2) == len(l2):
            return 0