Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

class Solution {
public:
    int jump(int A[], int n) {
        if (n <= 1) return 0;
        int standpoint = 0;
        int frontier = A[0];
        int count = 1;
        while (true) {
            if (frontier >= n-1) return count;
            int newFrontier = frontier;
            for(int ii = standpoint; ii <= frontier; ++ii) {
                newFrontier = std::max(newFrontier, ii + A[ii]);
            }
            ++count;
            standpoint = frontier;
            frontier = newFrontier;
        }
        return count;
    }
};

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (root == NULL) return true;
        return isMirror(root->left, root->right);
    }
   
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL && t2 == NULL) return true;
        if (t1 == NULL || t2 == NULL || t1->val != t2->val) return false;
        return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
  
};

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

 class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        if (strs.size() < 1) return "";
        string pre = strs[0];
        for(int index = 0; index < pre.length(); ++index) {
            for(int ii = 0; ii < strs.size(); ++ii) {
                string current = strs[ii];
                if (current[index] != pre[index]) return pre.substr(0, index);
            }
        }
        return pre;
    }
};

Palindrome Number

//not the best

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        string s = "";
        while(x > 0) {
            int dig = x % 10;
            x /= 10;
            s.push_back(dig);
        }
        for(int ii = 0; ii < s.size(); ++ii){
            int jj = s.size()-1-ii;
            if (s[ii] != s[jj]) return false;
        }
        return true;
    }
};


// better, without extra space
class Solution {
public:
    bool isPalindrome(int x) {
        if (x == 0 ) return true;
        if (x < 0 || x / 10 * 10 == x) return false;
        int mirror = 0;
        while (mirror < x) {
            int dig = x % 10;
            mirror = mirror * 10 + dig;
            if (mirror == x) return true;
            x /= 10;
            if (mirror == x) return true;
        }
        return false;
    }
};

Reverse Integer

class Solution:
    # @return an integer
    def reverse(self, x):
        if not x:
            return x
        s = str(x)
        first = s[0]
        result = 0
        if (first.isdigit()):
            sub = int(s[::-1])
            if sub < 2147483648:
                result = sub
        else:
            sub = int(s[1:][::-1])
            if sub < 2147483648:
                result = int(first + s[1:][::-1])
        return result
       

Valid Palindrome

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.size() - 1;
        while (left <= right) {
          if (!isLetter(s[left])) {
              ++left;
              continue;
          }
          if (!isLetter(s[right])) {
              --right;
              continue;
          }
          if (toLower(s[left]) != toLower(s[right])) return false;
          ++left;
          --right;
        }
        return true;
    }
   
    bool isLetter(char c) {
        return ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9');
    }
   
    char toLower(char c) {
        if ('A' <= c && c <= 'Z') return c + 'a' - 'A';
        return c;
    }
};

Add Two Numbers

/**
 * 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* root = new ListNode(0);
        add(l1, l2, root, 0);
        return root->next;
    }
   
    void add(ListNode *l1, ListNode *l2, ListNode* pre, int carry) {
        if (l1 == NULL) addSingle(l2, pre, carry);
        else if (l2 == NULL) addSingle(l1, pre, carry);
        else {
            int num = l1->val + l2->val + carry;
            pre->next = new ListNode(num % 10);
            add(l1->next, l2->next, pre->next, num/10);
        }
       
    }
   
    void addSingle(ListNode* n, ListNode* pre, int carry) {
        if (n == NULL) {
            if (carry == 0 ) return;
            else {
                pre->next = new ListNode(carry);
                return;
            }
        }
        int num = carry + n->val;
        pre->next = new ListNode(num % 10);
        addSingle(n->next, pre->next, num/10);
    }
};

Two Sum

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        vector n2 = numbers;
        std::sort(n2.begin(), n2.end());
        for (int ii = 0; ii < n2.size(); ++ii) {
            int subTarget = target - n2[ii];
            bool subFound = std::binary_search(n2.begin()+ii+1, n2.end(), subTarget);
            if (subFound) {
                vector result;
                for(int jj = 0; jj < numbers.size(); ++jj) {
                    if (numbers[jj] == n2[ii] || numbers[jj] == subTarget) result.push_back(jj+1);
                }
                return result;
            }
        }
        return vector(2,0);
    }
};

First Missing Positive

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int ii = 0; ii < n; ++ii) {
            while (A[ii] != ii + 1 ) {
                if (A[ii] <= 0 || A[ii] > n || A[ii] == A[A[ii] - 1]) {
                    A[ii] = -1;
                    break;
                }
                swap(A, ii, A[ii]-1);
            }
        }
       
        for (int ii = 0; ii < n; ++ii) {
            if (A[ii] != ii+1) return ii+1;
        }
        return n+1;
    }
   
    void swap(int A[], int here, int other) {
        int temp = A[here];
        A[here] = A[other];
        A[other] = temp;
        return;
    }
};

Edit Distance

class Solution {
public:
    map, int> m;
    int minDistance(string word1, string word2) {
        return minDistHelper(word1, word2, 0, 0);
    }
   
    int minDistHelper(string const& word1, string const& word2, int const index1, int const index2) {
        pair p = make_pair(index1, index2);
        if (m[p]) return m[p];
        if (index1 == word1.size()) return word2.size() - index2;
        if (index2 == word2.size()) return word1.size() - index1;
       
        if (word1[index1] == word2[index2]) return minDistHelper(word1, word2, index1 + 1, index2 + 1);
        m[p] = 1 + min(minDistHelper(word1, word2, index1+1, index2+1), min(minDistHelper(word1, word2, index1+1, index2), minDistHelper(word1, word2, index1, index2+1)));
        return m[p];
    }
};

Majority Element

class Solution {
public:
    int majorityElement(vector &num) {
        map m;
        for (int ii = 0; ii < num.size(); ++ii) {
            int count = m[num[ii]];
            m[num[ii]] = ++count;
        }
        int maxEle = 0;
        int maxCount = 0;
        for(auto it = m.begin(); it != m.end(); ++it) {
            if (it->second > maxCount) {
                maxEle = it->first;
                maxCount = it->second;
            }
        }
        return maxEle;
    }
};

Excel Sheet Column Number

class Solution {
public:
    int titleToNumber(string s) {
        int result = 0;
        for (int ii = 0; ii < s.size(); ++ii) {
            result = result * 26 + s[ii] - 'A' + 1;
        }
        return result;
    }
};

count and say

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        for (int ii = 0; ii < n-1; ++ii) {
            s = getNext(s);
        }
        return s;
       
    }
   
    string getNext(string s) {
        string say = "";
        for(int ii = 0; ii < s.size(); ++ii) {
            int repeat = countRepeat(s, ii);
            say.push_back(repeat + '0');
            say.push_back(s[ii]);
            ii += repeat-1;
        }
        return say;
    }
   
    unsigned int countRepeat(string s, unsigned int pos) {
        char c = s[pos];
        int ii = pos;
        for(; ii < s.size(); ++ii){
            if (s[ii] != c) break;
        }
        return ii - pos;
    }
};

Valid Parentheses

class Solution {
public:
    bool isValid(string s) {
        vector v;
        for(int ii = 0; ii < s.size(); ++ii) {
            switch (s[ii]) {
                case '(':
                case '{':
                case '[': v.push_back(s[ii]); break;
                case ')':
                  if (v.empty() || v.back() != '(') return false;
                  else {
                      v.pop_back();
                      break;
                  }
                case ']':
                  if (v.empty() || v.back() != '[') return false;
                  else {
                      v.pop_back();
                      break;
                  }
                case '}':
                  if (v.empty() || v.back() != '{') return false;
                  else {
                      v.pop_back();
                      break;
                  }
            }
        }
       
        return v.empty();
       
       
    }
};

Compare Version Numbers

Compare Version Numbers

 Total Accepted: 10377 Total Submissions: 70133My Submissions

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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

 https://oj.leetcode.com/problems/compare-version-numbers/

python --

class Solution:
    # @param version1, a string
    # @param version2, a string
    # @return an integer
    def compareVersion(self, version1, version2):
        vlong = version1.split('.')
        vshort = version2.split('.')
        swapflag = 1
        if len(vlong) < len(vshort):
            swapflag = -1
            vlong, vshort = vshort, vlong
        for index in range(0, len(vlong)):
            v1 = float(vlong[index])
            v2 = float(vshort[index]) if (index < len(vshort)) else 0
            if (v1 > v2):
                return 1 * swapflag
            elif (v1 < v2):
                return -1 * swapflag
        return 0

C++
class Solution {
public:
    int compareVersion(string version1, string version2) {
        unsigned int p1 = 0;
        unsigned int p1pre = 0;
        unsigned int p2 = 0;
        unsigned int p2pre = 0;
        while(p1 < version1.size() && p2 < version2.size()) {
            string v1 = "";
            string v2 = "";
            for (p1 = p1pre; p1 < version1.size(); ++p1){
                if (version1[p1] == '.') break;
                v1.push_back(version1[p1]);
            }

            for (p2 = p2pre; p2 < version2.size(); ++p2){
                if (version2[p2] == '.') break;
                v2.push_back(version2[p2]);
            }

            int n1 = stoi(v1);
            int n2 = stoi(v2);
            if (n1 > n2) return 1;
            if (n1 < n2) return -1;
           
            p1pre = p1 + 1;
            p2pre = p2 + 1;
        }
       
        if (p2 >= version2.size()) {
            for(unsigned int ii = p1pre; ii < version1.size(); ++ii) {
                if (version1[ii] != '0' && version1[ii] != '.') return 1;
            }
        }
        else if (p1 >= version1.size()) {
            for(unsigned int ii = p2pre; ii < version2.size(); ++ii) {
                if (version2[ii] != '0' && version2[ii] != '.') return -1;
            }
        }

        return 0;

    }
   
 
};