Tuesday, January 27, 2015

Day 95, ##, Excel Sheet Column Title, Excel Sheet Column Number, Missing Ranges

Excel Sheet Column Title
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
-----------------------------------
similar to convert a base 10 number to any base number
可以考虑1-26 为 0 - 25,进行转换
class Solution {
public:
    string convertToTitle(int n) {
        string s = "";
        
        while (n > 0) {
            char c;
            if (n % 26 == 0) {
                c = 'Z';
                n--;
            }else 
                c = n % 26 - 1 + 'A';
            n = n / 26;
            s = c + s;
        }
        
        return s;
    }
};

Excel Sheet Column Number

Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
----------------------------------------------------
class Solution {
public:
    int titleToNumber(string s) {
        int rt = 0;
        for (int i = 0; i < s.length(); i++) {
            int temp = s[i] - 'A' + 1;
            rt = rt * 26 + temp;
        }
        
        return rt;
    }
};

Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"]. ----------------------------------------------------------------------
class Solution {
public:
    vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
        vector<string> rt;
        string mid = "->";
        string s = "";
        
        if (n == 0) {
            if (lower == upper) {
                rt.push_back(to_string(lower));
            }else {
                rt.push_back(to_string(lower) + mid + to_string(upper));
            }
            
            return rt;
        }
        
        if (A[0] > lower) {
            int temp = A[0] - 1;
            if (A[0] - 1 == lower) {
                s = to_string(lower);
            }else 
                s = to_string(lower) + mid + to_string(A[0] - 1);
            rt.push_back(s);
        }
        
        for (int i = 1; i < n; i++) {
            if (A[i] == A[i - 1] + 1) continue;
            string low = to_string(A[i - 1] + 1);
            string up = to_string(A[i] - 1);
            if (low == up) 
                s = low;
            else
                s = low + mid + up;
            rt.push_back(s);
        }
        
        if (A[n - 1] < upper) {
            if (A[n - 1] + 1 == upper)
                s = to_string(upper);
            else
                s = to_string(A[n - 1] + 1) + mid + to_string(upper);
            rt.push_back(s);
        }
        
        return rt;
    }
};

更新
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        nums.insert(nums.begin(),lower - 1);
        nums.push_back(upper + 1);
        
        vector<string> rt;
        int start = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1] + 1 || nums[i] == nums[i - 1]) {
                continue;
            }else if (nums[i] - 2 == nums[i - 1]) {
                rt.push_back(to_string(nums[i] - 1));
            }else {
                rt.push_back(to_string(nums[i - 1] + 1) + "->" + to_string(nums[i] - 1));
            }
        }
        
        return rt;
    }
};

No comments:

Post a Comment