Leetcode solutions

10_regular_expression_matching.cpp

- to be continued...

11_container_with_most_water.cpp

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int n = height.size();
        vector<pair<int, int>> p;
        for (int i = 0; i < n; i++)
            p.push_back(make_pair(height[i], i));
        sort(p.begin(), p.end());
        
        int left, right;
        left = right = p[n-1].second;
        int ans = -1;
        for (int i = n - 2; i >= 0; i--)
        {
            ans = max(ans, abs(p[i].second-left) * p[i].first);
            ans = max(ans, abs(p[i].second-right) * p[i].first);
            left = min(left, p[i].second);
            right = max(right, p[i].second);
        }
        return ans;
    }
};

12_integer_to_roman.cpp

class Solution 
{
public:
    string intToRoman(int num) 
    {
        string ans;
        int thousand = num / 1000;
        if (thousand == 3)
            ans += "MMM";
        else if (thousand == 2)
            ans += "MM";
        else if (thousand == 1)
            ans += "M";
        
        num %= 1000;
        int hundred = num / 100;
        switch (hundred)
        {
            case 9:
                ans += "CM"; break;
            case 8:
                ans += "DCCC"; break;
            case 7:
                ans += "DCC"; break;
            case 6:
                ans += "DC"; break;
            case 5:
                ans += "D"; break;
            case 4:
                ans += "CD"; break;
            case 3:
                ans += "CCC"; break;
            case 2:
                ans += "CC"; break;
            case 1:
                ans += "C"; break;
        }
        
        num %= 100;
        int ten = num / 10;
        switch (ten)
        {
            case 9:
                ans += "XC"; break;
            case 8:
                ans += "LXXX"; break;
            case 7:
                ans += "LXX"; break;
            case 6:
                ans += "LX"; break;
            case 5:
                ans += "L"; break;
            case 4:
                ans += "XL"; break;
            case 3:
                ans += "XXX"; break;
            case 2:
                ans += "XX"; break;
            case 1:
                ans += "X"; break;
        }
        
        num %= 10;
        int one = num;
        switch (one)
        {
            case 9:
                ans += "IX"; break;
            case 8:
                ans += "VIII"; break;
            case 7:
                ans += "VII"; break;
            case 6:
                ans += "VI"; break;
            case 5:
                ans += "V"; break;
            case 4:
                ans += "IV"; break;
            case 3:
                ans += "III"; break;
            case 2:
                ans += "II"; break;
            case 1:
                ans += "I"; break;
        }
        
        return ans;
    }
};

1_two_sum.cpp

class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> ans;
        vector<pair<int, int>> a;
        for (int i = 0; i < nums.size(); i++)
        {
            a.push_back(make_pair(nums[i], i));
        }
        sort(a.begin(), a.end());
        for (int i = 0; i < a.size(); i++)
        {
            int l = lower_bound(a.begin() + i + 1, a.end(), make_pair(target - a[i].first, -1)) - a.begin();
            if (l < a.size() && a[l].first + a[i].first == target)
            {
                ans.push_back(a[i].second);
                ans.push_back(a[l].second);
                sort(ans.begin(), ans.end());
                return ans;
            }
        }
        return ans;
    }
};

2_add_two_numbers.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* i1 = l1, *i2 = l2, *ans = new ListNode(0), *p = ans;
        int rp = 0; // ripple carry
        while (i1 != NULL || i2 != NULL)
        {
            ans->val = rp;
            if (i1 != NULL)
            {
                ans->val += i1->val;
                i1 = i1->next;
            }
            if (i2 != NULL)
            {
                ans->val += i2->val;
                i2 = i2->next;
            }
            rp = ans->val / 10;
            ans->val %= 10;
            
            if (i1 == NULL && i2 == NULL && rp == 0) break;
            ans->next = new ListNode(0);
            ans = ans->next;
        }
        if (rp != 0)
            ans->val = rp;
        return p;
    }
};

3_longest_substring_without_repeating_characters.cpp

class Solution
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int h[1000];
        memset(h, -1, sizeof(h));
        int len = s.length();
        int ml = 0, last = 0;
        for (int i = 0; i < len; ++i)
        {
            if (h[s[i]] == -1)
                h[s[i]] = i;
            else
            {
                ml = max(ml, i - last);
                last = max(last, h[s[i]] + 1);
                h[s[i]] = i;
            }
        }
        ml = max(ml, len - last);
        return ml;
    }
};

4._median_of_two_sorted_arrays.cpp

- to be continued

5_longest_palindromic _substring.cpp

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int pc, p; 
        // pc - the length of palindrome with i as center
        // p - the length of palindrome with i as last character of the first half part
        
        int maxLeng = -1e9, ind;
        
        for (int i = 0; i < s.length(); i++)
        {
            int j = 1;
            while (i-j >= 0 && i+j < s.length())
            {
                if (s[i-j] != s[i+j])
                    break;
                j++;
            }
            pc = j - 1;
            if (1 + 2*pc > maxLeng)
            {
                maxLeng = 1 + 2*pc;
                ind = i;
            }
            
            j = 1;
            while (i-j+1 >= 0 && i+j < s.length())
            {
                if (s[i-j+1] != s[i+j])
                    break;
                j++;
            }
            p = j - 1;
            if (2*p > maxLeng)
            {
                maxLeng = 2*p;
                ind = i;
            }
        }
        
        if (maxLeng % 2 == 1) // pc type
            return s.substr(ind - (maxLeng-1)/2, maxLeng); // note: str.substr(startpos, length);
        else // p type
            return s.substr(ind - maxLeng/2 + 1, maxLeng);
    }
};

6_zigzag_conversion.cpp

class Solution
{
public:
    string convert(string s, int numR)
    {
        // corner cases
        if (s.length() == 0)
            return s;
        if (numR == 1)
            return s;
        
        // Prints out the desired Zigzag figure
        // Causes OLE if not commented
        // print(s, numR);
        
        string ans;
        
        // generate the centers
        int n = s.length();
        vector<int> centers;
        int i;
        for (i = 0; i < n; i += 2*numR - 2)
            centers.push_back(i);
        centers.push_back(i);
        
        // print the first line
        for (int i = 0; i < centers.size(); i++)
            if (centers[i] < n)
                ans += s[centers[i]];
        
        // print the body
        for (int i = 1; i < numR - 1; i++)
        {
            if (centers[0] + i < n)
                ans += s[centers[0] + i];
            if (centers.size() < 1) continue; // corner case
            for (int j = 1; j < centers.size(); j++)
            {
                if (centers[j] - i >= 0 && centers[j] - i < n)
                    ans += s[centers[j]-i];
                if (centers[j] + i < n)
                    ans += s[centers[j]+i];
            }
        }
        
        // print the last line
        for (int i = 0; i < centers.size(); i++)
        {
            if (centers[i] + numR - 1 < n)
                ans += s[centers[i]+numR-1];
        }
            
        return ans;
    }

private:
    void printSpaces(int n)
    {
        for (int i = 0; i < n; i++)
            cout << " ";
    }
    
    void print(string s, int numR)
    {
        // generate the centers
        int n = s.length();
        vector<int> centers;
        int i;
        for (i = 0; i < n; i += 2*numR - 2)
        {
            centers.push_back(i);
        }
        centers.push_back(i); /* The centers might exceed the strings */
        
        // print the first line
        for (int i = 0; i < centers.size(); i++)
        {
            if (centers[i] < n)
            {
                cout << s[centers[i]];
                printSpaces(numR-2);
            }
        }
        cout << endl;
        
        // print the body
        for (int i = 1; i < numR - 1; i++)
        {
            if (centers[0] + i < n)
                cout << s[centers[0] + i];
            if (centers.size() < 1) continue; // corner case
            for (int j = 1; j < centers.size(); j++)
            {
                if (centers[j] - i >= 0 && centers[j] - i < n) /* Since the centers may exceed, this can exceed as well */
                {
                    printSpaces(numR-2-i);
                    cout << s[centers[j]-i];
                }
                if (centers[j] + i < n)
                {
                    printSpaces(i-1);
                    cout << s[centers[j]+i];
                }
            }
            cout << endl;
        }
        
        // print the last line
        for (int i = 0; i < centers.size(); i++)
        {
            if (centers[i] + numR - 1 < n)
            {
                cout << s[centers[i]+numR-1];
                printSpaces(numR-2);
            }
        }
        cout << endl;
    }
};

7_reverse_integer.cpp

class Solution 
{
public:
    int reverse(int x) 
    {
        long long int reversed = 0;
        bool sign = true;
        if (x < 0)
        {
            x = -x;
            sign = false;
        }
        while (x > 0)
        {
            int d = x % 10;
            x /= 10;
            reversed = reversed * 10 + d;
        }
        if (sign && reversed >= 2147483647 || !sign && reversed >= 2147483648)
            return 0;
        if (!sign)
            reversed = - reversed;
        return reversed;
    }
};

8_string_to_integer_(atoi).cpp

- to be done

9_palindrome_number.cpp

class Solution 
{
public:
    bool isPalindrome(int x) 
    {
        int y = abs(x);
        long long int z = 0;
        while (y > 0)
        {
            z = z * 10 + (y % 10);
            y /= 10;
        }
        if (x == z)
            return true;
        return false;
    }
};