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);
    }
};