Thursday, January 29, 2015

Day 97, ##, Largest Number, Compare Version Numbers

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.
-----------------------------------
COME_BACK
class Solution {
public:
    static bool cmp(string s1,string s2) {
        return (s1 + s2) < (s2 + s1);
    }
    
    string largestNumber(vector<int> &num) {
        vector<string> strings(num.size());
        for (int i = 0; i < num.size(); i++) {
            strings[i] = to_string(num[i]);
        }
        
        sort(strings.begin(),strings.end(),cmp);
        if (strings.back() == "0") {
            return "0";
        }
        
        string rt = "";
        for (int i = strings.size() - 1; i >= 0; i--) {
            rt += strings[i]; 
        }
        
        return rt;
    }
};

Compare Version Numbers

Compare two version numbers version1 and version1.
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
----------------------------------------------------------
class Solution {
public:
    int getNextSubString(string &str, int &i) {
        int rt = 0;
        while (i < str.length() && str[i] != '.') {
            rt = rt * 10 + (str[i] - '0');
            i++;
        }
        
        i++;
        return rt;
    }

    int compareVersion(string version1, string version2) {
        int itr1 = 0, itr2 = 0;
        while (itr1 < version1.length() || itr2 < version2.length()) {
            int s1 = getNextSubString(version1,itr1);
            int s2 = getNextSubString(version2,itr2);

            if (s1 > s2) return 1;
            if (s1 < s2) return -1;
        }
        return 0;
    }
};

No comments:

Post a Comment