leetcode Question 130: Sum Root to Leaf Numbers

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Analysis:

Once we see this kind of problem, no matter what sum is required to output, "all root-to-leaf" phrase reminds us the classic Tree Traversal or Depth-First-Search algorithm. Then according to the specific problem, compute and store the values we need. Here in this problem, while searching deeper, add the values up (times 10 + current value), and add the sum to final result if meet the leaf node (left and right child are both NULL).

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void dfs(TreeNode* root,int cur, int &res){
        if (root->left==NULL && root->right==NULL){
            cur=cur*10+root->val;
            res+=cur;
        }else{
            cur=cur*10+root->val;
            if (root->left){
                dfs(root->left,cur,res);
            }
            if (root->right){
                dfs(root->right,cur,res);
            }
        }
    }
    int sumNumbers(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int res=0;
        if (!root){return res;}
        dfs(root,0,res);
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    res = 0
    def search(self, root, path):
        if root.left == None and root.right == None:
            self.res += path + root.val
        else:
            if root.left != None:
                self.search(root.left, (path + root.val)*10)
            if root.right != None:
                self.search(root.right, (path + root.val)*10)
            
    def sumNumbers(self, root):
        self.res = 0
        if root == None:
            return 0
        else:
            self.search(root, 0)
            return self.res
            
        
        

leetcode Question 129: Longest Consecutive Sequence

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Analysis:

At first glance, the "longest" requirement may lead us to DP. But this problem actually tests data structure rather than a certain algorithm.

If there is no O(n) requirement, we can just sort the array (O(n log n)), then find then longest sequence after a scan.

With the time limit O(n), first of all, what comes to my mind is HASH MAP! Because hash map searches value by key in O(1) time. Note that in C++ STL, the map<> data structure is implemented by BST, so the insert in O(log n), therefore we need to use the unordered_map<>, which has O(1) time complexity.

Firstly, we put all the element into a map.
Secondly, how to find the consecutive elements? Since the O(n) requirement, scan the array is a must.
For each element, we need to find its consecutive elements. Consecutive means +1 or -1, a while loop is enough to handle. Search two directions respectively (+1, -1),  during the search if the key is found, remove the current item in the map. This is because if two items are consecutive, the longest elements for this two are the same, no need to search again. In this way, the length of longest consecutive elements can be easily found.

Note that in C++ map<>, find(key) function will return  the end() iterator if key does not exist, But if we use (mp[key]==false), when key is not in the map, the program will insert the key into the map with a default value, so use find function is a safer way.

Code (C++):

class Solution {
public:

    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,bool>mp;
        for (int i=0;i<num.size();i++){
            mp[num[i]]=true;
        }
        
        int res=0;
        for (int i=0;i<num.size();i++){
            int mx=1;      
            int fd = num[i];
            
            mp.erase(num[i]);
            while (mp.find(fd+1)!=mp.end()){
                mx++;
                mp.erase(fd+1);
                fd++;
            }
            
            fd = num[i];
            while (mp.find(fd-1)!=mp.end()){
                mx++;
                mp.erase(fd-1);
                fd--;
            }
            
            if (mx>res){res=mx;}
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        dic = {}
        maxlen = 1
        for n in num:
            dic[n] = 1
        for n in num:
            if dic.has_key(n):
                tmp = n + 1
                l = 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp+=1
                tmp = n - 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp-=1
                maxlen = max(l, maxlen)
            else:
                continue
        return maxlen

leetcode Question 126: Valid Palindrome

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Analysis:
This is an easy and fundamental problem about string and char.

Set two pointers from the start and the end of the string to test Palindrome, skip the chars that are not alphanumeric and compare the lower case of each pair of chars.

Here are some tricks:
(1) upper lower cases:  #include <cctype>, there is a function called "tolower()"
(2) alphanumeric: also in <cctype>(or <ctype.h>), a function called "isalnum()"

Code (updated 2013.08) :

class Solution {
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size()==0)   {return true;}
        
        int st = 0;
        int ed = s.size()-1;
        
        while (st<ed){
            if (isalnum(s[st])==false){st++; continue;}
            if (isalnum(s[ed])==false){ed--; continue;}
            
            if (tolower(s[ed])!=tolower(s[st])){
                return false;
            }else{
                st++;
                ed--;
            }
        }
        
        return true;
    }
};

leetcode Question 105: Subsets II

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Analysis:
Be careful with the question, for [1,2,2], [2,2] is needed.
Here we use another way different from the previous problem to solve this problem.

First, consider there is no duplicates, how to generate the subsets?
Say n is the # of the elements,
when n=1, subsets :  {}, {"1"},  "i" means the ith element.
when n=2, subsets:   {}, {"1"}, {"2"}, {"1", "2"}
when n=3, subsets:   {}, {"1"}, {"2"}, {"1", "2"}, {"3"}, {"1","3"}, {"2","3"}, {"1", "2","3"}
So, the way of generating subsets is:
From 2 to n, COPY the previous subsets, add the current element, push back to the subsets list.

Then we take the duplicates into account, the same example:
when n=1, subsets :  {}, {"1"},  "i" means the ith element.
when n=2, subsets:   {}, {"1"}, {"2"}, {"1", "2"}
when n=3, but "2"=="3" subsets:
   {}, {"1"}, {"2"}, {"1", "2"}, {"3"}, {"1","3"}, {"2","3"}, {"1", "2","3"}
since "2"=="3", which truly is:
   {}, {"1"}, {"2"}, {"1", "2"}, {"2"}, {"1","2"}, {"2","2"}, {"1", "2","2"}
where the bold ones are not needed.
So, how these two subsets are generated? They are from the subsets of n=1.

In sum up, when meet the same element as previous one, then generate new subsets ONLY from the subsets generated from previous iteration, other than the whole subsets list.

See code below for more details.

Code(Updated 201309):

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    sort(S.begin(),S.end());
    vector<vector<int> > res;
    vector<int> r;
    res.push_back(r);
    r.push_back(S[0]);
    res.push_back(r);
    int pre = S[0];
    int count = 1;
    for (int i=1;i<S.size();i++){
      int st=0;  
      int sz = res.size();
      if (S[i]==pre){st = sz-count;}
      count =0;
      for (int j=st;j<sz;j++){
        r = res[j];
        r.push_back(S[i]);
        res.push_back(r);
        count++;
      }
      pre=S[i];
    }
    return res;
  }
};

Code:

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(S.begin(),S.end());
        vector<vector<int> > res;
        vector<int> ss;
        res.push_back(ss);
        ss.push_back(S[0]);
        res.push_back(ss);
        int count=1;
        int pre = S[0];
        for (int i=1;i<S.size();i++){
                int sz = res.size();                
                if (S[i]!=pre){
                    count=0;
                    for (int j=0;j<sz;j++){
                        ss=res[j];
                        ss.push_back(S[i]);
                        res.push_back(ss);
                        count++;
                    }
                }else{
                    int ind=count;
                    count=0;
                    for (int j=sz-ind;j<sz;j++){
                        ss=res[j];
                        ss.push_back(S[i]);
                        res.push_back(ss);
                        count++;
                    }
                    
                }              
            pre = S[i];
        }
        return res;
    }
};

leetcode Question 104: Subsets

Subsets:

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Analysis:

The easiest idea is using the binary numbers.
e.g.
set [a,b,c], write the binary numbers of length 3.

000    []
001    [a]
010    [b]
011    [ab]
100    [c]
101    [ac]
110    [bc]
111    [abc]

Then the problem is pretty easy, for each number in binary format,  check which bit is 1 or 0, we just add the ith number into the set if the ith bit in the number is 1.

Bit manipulation is enough for the check, we just have to shift the number 1 one bit left each time, a simple AND operation will give us the bit value.

Code(C++):

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector< vector<int> > res;
        if (n == 0){ return res;}
        
        for (int i=0;i< pow(2,n); i++){
            vector<int> tmp;
            for (int j=0;j<n;j++){
                if ( (i& (1<<j)) > 0 ){
                    tmp.push_back(nums[j]);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};

Code (Python):

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        n = len(nums)
        if n==0:
            return res
        
        for i in range(pow(2, n)):
            l = []
            for j in range(n):
                if i & (1 << j) > 0:
                    l.append(nums[j])
            res.append(l)
        return res
                
        

leetcode Question115: Unique Binary Search Trees II

Unique Binary Search Trees II

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

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

Analysis:

The basic idea is still using the DFS scheme. It is a little hard to think the structure of the argument list in the function. It is clear that for each tree/subtree, we will set the root as the start position to the end position, and recursively construct the left subtree with the left part and the right subtree with the right part.
So first we can have
 void dfs (int st, int ed     ){
   if (st>ed) {   // generate a null node }
  else{
    for (int i=st;i<=ed;i++){
       
      dfs(st,i-1,   );     //generate left subtree
      dfs(i+1,ed,   );  // generate right subtree
    }
  }

}

Next step is to think about how to store all the possible solutions.
This is important ! Think about the root node, all the possible solutions of the tree are from the combinations of all the possible solutions of its left subtree, and its right subtree. One step further, if we have a root node and a left node, for the left node, still the subtrees below it are the combinations of the possible solutions of its left and right subtree, until the leaf node.

In other words, we store all the possible solutions for each node, instead of storing the only tree. So, we can have
void dfs(int st, int ed, vector<TreeNode *> res){}
in this function, recursively generate the left tree and right tree, then construct the current node, and push it to the current solution vector.
Details see the code.


Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(int st,int ed,vector<TreeNode *> &res){
        if (st>ed){
            res.push_back(NULL);
        }else{
            for (int i=st;i<=ed;i++){
                vector<TreeNode *> lefts;
                dfs(st,i-1,lefts);
                vector<TreeNode *> rights;
                dfs(i+1,ed,rights);
                
                for (int li = 0; li<lefts.size();li++) {
                    for (int ri =0; ri<rights.size();ri++){
                        TreeNode* node = new TreeNode(i);
                        node->left=lefts[li];
                        node->right=rights[ri];
                        res.push_back(node);
                    }
                }
            }
        }
    }
    
    vector<TreeNode *> generateTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<TreeNode*> res;
        dfs(1,n,res);
        return res;
    }
};

leetcode Question 103: String to Integer (atoi)

String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Analysis:
As there is no need to consider float number, what we need concern here is
(1) "+" and "-"
(2) The boundary INT_MAX and INT_MIN
(3) Eliminate the spaces before.
(4) Meet non-digit after digit then return.

Code(Updated 201309):

class Solution {
public:
    int atoi(const char *str) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!str){return 0;}
        int i=0;
        bool pos=true;
        int res=0;
        while (str[i]==' '){ i++;}
        if (str[i]=='+'){ pos=true;i++;}
        if (str[i]=='-'){ pos = false;i++;}
        if (!isdigit(str[i])){return 0;}
        while (isdigit(str[i])){
           if (pos && res>INT_MAX/10){return INT_MAX;}
           if (pos && res==INT_MAX/10 && int(str[i]-'0')>=7){return INT_MAX;}
           if (!pos && -res<INT_MIN/10){return INT_MIN;}
           if (!pos && -res==INT_MIN/10 && int(str[i]-'0')>=8){return INT_MIN;}
           res = res*10 + int(str[i]-'0');
           i++;
        }
            
        if (pos){return res;}
        else{return -res;}    
           
    }
};

leetcode Question 118: Valid Number

Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.


Analysis:

There are many cases if a number is not valid. Here the solution is definitely not optimal, but still workable and can pass all the tests.

Here are some considerations:

(1)  " . " ,   "1."  true,   "1.e2" true, ".3" true.
(2) " e ",   ".e1" false,  "1e.1" false, "1e1.1" false, "2.3e" false.
(3) "+/-",  "+1.e+5" true.

Details see code below:

Code:

class Solution {
public:

    //del the front and end spaces
    string delspace(const char* s){
        int i=0;
        while (s[i]==' '){
            i++;
        }
        int j=strlen(s)-1;
        while (s[j]==' '){
            j--;
        }
        string res="";
        for (int k=i;k<=j;k++){
            res = res+s[k];
        }
        return res;
    }
    
    
    bool valid(string &s){
        int i=0;
        bool e =false; // check if 'e' exists
        bool dot=false; // check if '.' exists
        bool dig =false;
        
        while (i<s.size()-1){
            if (i==0){ // a number can start with +, -, .
                if (s[i]<'0' || s[i]>'9'){ // if is 0-9 continue
                    if (s[i]=='+' || s[i]=='-' || s[i]=='.'){
                        if (s.size()==1){return false;} // only +, - , . is not a number
                        if (s[i]=='.'){dot=true;}
                    }
                    else {return false;}
                }else{dig=true;}
                i++;continue;
            }
            if (i>0){
                switch (s[i]){
                    case 'e': // e cannot follow +,-
                        if ( e==false && s[i-1]!='+' && s[i-1]!='-' && dig && i!=s.size()-1) {
                            e = true;
                        }else{
                            return false;
                        }
                        break;
                   case 'E': // e cannot follow +,-
                        if ( e==false && s[i-1]!='+' && s[i-1]!='-' && dig && i!=s.size()-1) {
                            e = true;
                        }else{
                            return false;
                        }
                        break;
                   case '+': // + can only occur before e
                        if (s[i-1]=='e' || s[i-1]=='E'){}else{return false;}
                        break;
                   case '-': // - can only occur before e
                        if (s[i-1]=='e' || s[i-1]=='E'){}else{return false;}
                        break;
                   case '.': // . can only occur once and cannot occure after e
                        if (dot==false && e==false){dot=true;}else{return false;}
                        break;
                   default:  // only 0-9 can be valid numbers
                        if (s[i]<'0'||s[i]>'9'){return false;}
                        else{dig = true;}
                        break;
            } 
                i++;continue;
            }
        }
        
        //last dig can only be 0-9, or ., when it is . there is no . and e before
        if (s[s.size()-1]>='0' && s[s.size()-1]<='9'){return true;}
        if (s[s.size()-1]=='.' && !dot && !e && s[s.size()-2]>='0' && s[s.size()-1]<='9') {return true;}        
        return false;
    }
    bool isNumber(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string s1 = delspace(s); //delete spaces in the front and end, don't delete the spaces in middle.
        if (s1.size()==0){return false;} // if null string, return false;
        return valid(s1);
    }
};
        
        
        
        
        
        
        

leetcode Questions 99: Sort Colors

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

Analysis:
This is a relative easy problem.
The goal is to rearrange the array, where 0s are in the 1st part of the array, 1s in the middle, and 2s are in the    last. So, we can just scan the whole array, when meet 0, put it in the front, when meet 2, put it in the last, and leave 1 alone thus in the middle. 0 and 2's positions are stored and modified each time a swap is performed.
Details see the code.


Code:

class Solution {
public:

    void swap(int A[], int i, int j){
        int tmp = A[i];
        A[i]=A[j];
        A[j]=tmp;
    }
    void sortColors(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int red=0;
        int blue=n-1;
        
        while (A[red]==0){red++;}
        while (A[blue]==2){blue--;}
        
        int i=red;
        while (i<=blue){
            if (A[i]==0 && i>red) {swap(A,i,red);red++;continue;}
            if (A[i]==2) {swap(A,i,blue);blue--;continue;}
            i++;
        }
        
    }
};

leetcode Question 90: Same Tree

Same Tree:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Analysis:

Recursively check the left child and right child.  If the value is different, or if one of the two nodes is null, return false.

Code(C++):

/**
 * 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 isSameTree(TreeNode *p, TreeNode *q) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!p && !q) {return true;}
        if ((!p && q) || (!q && p)){return false;}
        if (p->val!=q->val){return false;}
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param p, a tree node
    # @param q, a tree node
    # @return a boolean
    def isSameTree(self, p, q):
        if p == None and q == None:
            return True
        elif p == None and q != None:
            return False
        elif p != None and q == None:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
            
            
        

leetcode Question 89: Rotate List

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Analysis:
The idea is to get the whole length of the list, then compute the rotate position.
And cut the list from the rotate position, link the front part to the last part.

e.g.
1->2->3->4->5->null , k =2;
len = 5;
rotate pos = 5-2 = 3;

cut list:  1->2->3  --->  4->5->null
link :     4->5->1->2->3->null



Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head==NULL || k==0) {return head;}
        
        ListNode* p = head;
        int len=0;
        //get total length 
        while (p!=NULL){
            len++;
            p=p->next;
        }
        //get rotate position
        int r;
        if (k%len==0){
            return head;
        }else{
            r = len-(k%len)-1;    
        }
        p=head;
        while (r>0){
            p=p->next;
            r--;
        }
        
        
        //cut current list, link the back to the front
        ListNode *q =p->next;
        if (q==NULL){return head;}
        while (q->next!=NULL){
            q=q->next;
        }
        q->next = head;
        q=p->next;
        p->next=NULL;
        
        return q;
    }
};

leetcode Question 88: Rotate Image

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Analysis
The classic problem in Career Cup book 1.6.
The key idea is to rotate the matrix according to layers. For the nth layer(the out layer), rotate 90 degree is to move all the elements n times in a circle. In each layer, the rotation can be performed by first swap 4 corners, then swap 4 elements next to corner until the end of each line.


Code:

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = matrix.size();
        for (int layer=0; layer<n/2; layer++){
            int first = layer;
            int last  = n-1-layer; 
            for (int i=first;i<last;i++){
                int offset = i-first;
                int top = matrix[first][i];
                //left->top            
                matrix[first][i]=matrix[last-offset][first];
                //bottom->top
                matrix[last-offset][first] = matrix[last][last-offset];
                //right->bottom
                matrix[last][last-offset] = matrix[i][last];
                //top->right
                matrix[i][last] = top;
            }
        }
        
    }
};

leetcode Question 87: Roman to Interger

Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:
 According to the rules from wiki:

• A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 3 (three units). To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.^[4]
• The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear more than three times if they appear non-sequentially, such as XXXIX.) "D", "L", and "V" can never be repeated.^[5][6]
• "I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted^[6]
• Only one small-value symbol may be subtracted from any large-value symbol.^[7]

We can scan the whole string and consider the previous situations then add the relative values to the result.

Details see the code below.

Code:

class Solution {
public:
    int romanToInt(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        // 4:IV, 9:IX, 40:XL, 90:XC, 400:CD, 900:CM,
        // 1:I, 10:X, 100:C, 1000:M
        int res=0;
        char pre = ' ';
        for(int i=0;i<s.size();i++){
            if (s[i]=='M' && pre!='C') {res+=1000;}
            if (s[i]=='C' && pre!='X') {res+=100;}
            if (s[i]=='X' && pre!='I') {res+=10;}
            
            if (s[i]=='M' && pre=='C') {res+=800;}
            if (s[i]=='C' && pre=='X') {res+=80;}
            if (s[i]=='X' && pre=='I') {res+=8;}
            
            if (s[i]=='I' ) {res+=1;}
            
            if (s[i]=='V' && pre!='I'){res+=5;}
            if (s[i]=='L' && pre!='X'){res+=50;}
            if (s[i]=='D' && pre!='C'){res+=500;}
            
            if (s[i]=='V' && pre=='I'){res+=3;}
            if (s[i]=='L' && pre=='X'){res+=30;}
            if (s[i]=='D' && pre=='C'){res+=300;}
            
            pre = s[i];
            
        }
        
        return res;
    }
};

leetcode Question 86: Reverse Nodes in k-Group

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Updated 201309:

Analysis:

First consider the atomic operation in this problem: reverse several nodes.
How to reverse? Let's take an example, we have linked list 3->2->1->4->5->6->7
We wan to reverse 4->5->6 to 6->5->4, so we do the following:
(1) 3->2->1->4->5->6->7
               p              q
(2) 3->2->1----->5->6->4->7
               p             q
(3) 3->2->1--------->6->5->4->7
               p             q

The 1st step is to find the locations q and q, where we want to reverse from p->next to q.
Then while p->next != q,  we do:
     (1) move p->next to q->next
     (2) connect p->next to p->next->next
Note that, p and q are fixed.

Now we solve this reverse problem, the final step is to scan the whole list:
When we finished one reverse, put p k steps further, set q=p, then put q k steps further to find the end node for the new reverse, if meet the end, no more reverse needed, return the list.

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!head){return NULL;}
        ListNode* p=new ListNode(0);
        p->next=head;
        head = p;
        ListNode* q=p;
        while (true){
            int i=0;
            while (q && i<k){q=q->next;i++;}
            if (!q){return head->next;}
            else{
                while (p->next!=q){
                    ListNode* d = p->next;
                    ListNode* l = q->next;
                    p->next=p->next->next;
                    q->next=d;
                    d->next=l;
                }
                for(int j=0;j<k;j++){p=p->next;}
                q=p;
                }
        }
        return head->next;
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def reverseKGroup(self, head, k):
        p = ListNode(0)
        p.next = head
        head = p
        q = p
        while True:
            i = 0
            while i < k and q != None:
                q = q.next
                i = i + 1
            if q == None:
                return head.next
            while p.next != q:
                tmp1 = p.next
                tmp2 = q.next
                p.next = p.next.next
                q.next = tmp1
                q.next.next = tmp2
                
            for j in xrange(k):
                p = p.next
            q = p
            
        return head.next
            
        

Old Version:

Analysis:

The idea is to scan from the 1st node to the last, if there are k nodes, then swap them, and count again, until get the end.

In order to swap k nodes, we can have
(1) The previous node, to link the previous list.  (pre)
(2) The 1st node to swap.   (st)
(3) The kth node to swap.  (ed)

The idea is to insert the current 1st node behind the end node.
e.g.
1->2->3->4->null, when k=4

(1)2->3->4->1->null
               ed
(2)3->4->2->1->null
         ed
(3)4->3->2->1->null
    ed

After this swap, do not forget link the swapped list to the previous list.


Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* p=head;
        ListNode* pre=new ListNode(0);
        pre->next=p;
        head = pre;
        int c=0;
        ListNode* st;
        ListNode* ed;
        
        while(p!=NULL){
            c++;
            if (c==1){st = p;} //get start node of every k nodes
            if (c==k){
                ed = p;         // get end node of every k nodes
                ListNode *last=ed;  //store the list after the k nodes
                ListNode *nst=st;   //store the next node to be reversed
                while (st!=ed){     // reverse the k nodes
                    last = ed->next;
                    nst = st->next;
                    st->next = last;
                    ed->next = st;
                    st=nst;
                }
                pre->next = st;     //link to the previous list
                for (int i=0;i<k-1;i++){    //get the end of the k nodes
                    p=p->next;    
                }
                c=0;                //reset count = 0 
            }
            if (c==0){pre = p;}     //store the previous list
            p=p->next;              //go next nodes
        }
        return head->next;
    }
};

leetcode Question 108: Swap Nodes in Pairs

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Analysis:
This is just a pointer problem which is not that hard to think and implement.
We deal only when the next two nodes exist, e.g. if there are 3 nodes, we only take care of the first 2.
As required only 2 extra ListNodes is needed (definitely you can use only one), to store the current 2 nodes. Then just swap them and link them.

The code is pretty clear , see below for details.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *p = new ListNode(0);
        p->next = head;
        head = p;
        while(true){
            if (p->next==NULL){break;}
            if (p->next->next==NULL){break;}
            ListNode* q1 = p->next;
            ListNode* q2 = q1->next;
            q1->next = q2->next;
            q2->next = q1;
            p->next = q2;
            p=q1;
        } 
        return head->next;
    }
};

leetcode Question 109: Symmetric Tree

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

Note:
Bonus points if you could solve it both recursively and iteratively.

Updated Solution (2014.02)

Analysis:
Use two queue to store each level of nodes back and force instead of storing the level.
Use a special node to store the empty node. (-999 in the code below).
Details see the comments in the code below.

Code:

/**
 * 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 valid(vector<int> &l){
        int i=0;
        int j=l.size()-1;
        while (i<j){
            if (l[i++]!=l[j--]){return false;}
        }
        return true;
    }
    
    
    bool isSymmetric(TreeNode *root) {
        vector<int> l;  //store the values in current level
        
        //q1 and q2 stores the current and next level TreeNodes
        queue<TreeNode*> q1; 
        queue<TreeNode*> q2;
        
        if (!root){return true;}
        
        q1.push(root);
        while ((!q1.empty()) || (!q2.empty())){  // exit only when both queue are empty
            if (q2.empty()){   // current level is q1
                while (!q1.empty()){ // push all the q1 nodes' childeren into q2
                    TreeNode* tmp = q1.front();
                    q1.pop(); 
                    l.push_back(tmp->val);
                    if (tmp->val!=-999){ // if current node is not a empty node
                        if (tmp->left!=NULL){q2.push(tmp->left);}
                        else{TreeNode* emp = new TreeNode(-999); q2.push(emp);} // store the empty node for the balance checking 
                        if (tmp->right!=NULL){q2.push(tmp->right);}
                        else{TreeNode* emp = new TreeNode(-999); q2.push(emp);}
                    }
                }
                
                if (valid(l)==false){return false;}else // all the nodes in current level are stored, check if it is balanced
                {l.clear();}
                
            }else{  //current level is q2
                while (!q2.empty()){  // push all the q2 nodes' childeren into q1
                    TreeNode* tmp = q2.front();
                    q2.pop();
                    l.push_back(tmp->val);
                    if (tmp->val!=-999){
                        if (tmp->left!=NULL){q1.push(tmp->left);}
                        else{TreeNode* emp = new TreeNode(-999); q1.push(emp);}
                        if (tmp->right!=NULL){q1.push(tmp->right);}
                        else{TreeNode* emp = new TreeNode(-999); q1.push(emp);}
                    }
                }
                
                if (valid(l)==false){return false;}else
                {l.clear();}
            }
        }
            
        return true;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a boolean
    def valid(self, l):
        if cmp(l, l[::-1]) == 0:
            return True
        else:
            return False
    def isSymmetric(self, root):
        if root == None:
            return True
        q1 = []
        q2 = []
        l = []
        q1.append(root)
        while len(q1) != 0 or len(q2) != 0:
            if len(q1) == 0:
                while len(q2) != 0:
                    node = q2.pop(0)
                    l.append(node.val)
                    if node.val != -999:
                        if node.left != None:
                            q1.append(node.left)
                        else:
                            q1.append(TreeNode(-999))
                        if node.right != None:
                            q1.append(node.right)
                        else:
                            q1.append(TreeNode(-999))
                if self.valid(l) == False :
                    return False
                else:
                    l = []
            else:
                while len(q1) != 0:
                    node = q1.pop(0)
                    l.append(node.val)
                    if node.val != -999:
                        if node.left != None:
                            q2.append(node.left)
                        else:
                            q2.append(TreeNode(-999))
                        if node.right != None:
                            q2.append(node.right)
                        else:
                            q2.append(TreeNode(-999))
                if self.valid(l) == False :
                    return False
                else:
                    l = []
        return True
            
        

Updated Solution(2013.09)

Analysis:
BFS is a good way solving this problem, since BFS can get the nodes in every level.
But be careful with the empty nodes in this problem, if they are not well treated, it will effect the result.
Idea here is to save the empty nodes, with a special value (e.g. -999 in my code), and when we get all the nodes in one level, just need to do the testing (like palindrome).

Note that, the node with no children also need save its two "empty" children. If not, consider this example:
                   2
           3            3
        4    5      5    4    
            8  9        9  8    
 The last level, if you do not store the empty children from 4 and 5 in previous level, it becomes:
 [8,9,9,8], which seems a true answer. But,  this level here is [#, #, 8, 9, #, #, 9, 8],  #!=8, which is a false answer!

Details see the code below:


Code:

/**
 * 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 valid(vector<int> a){
        int st=0;
        int ed=a.size()-1;
        while (st<ed){
            if (a[st]!=a[ed]){return false;}
            else{ st++; ed--;}
        }
        return true;
    }

    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue<TreeNode* > q1;
        queue<int> q2;      
        if (!root){return true;}
        q1.push(root);
        q2.push(0);
        int l=0;
        vector<int> r;
        while (!q1.empty()){
            if (l==q2.front()){
                r.push_back(q1.front()->val);
            }else{
                if (valid(r)==false){return false;}
                r.clear();
                r.push_back(q1.front()->val);
                l=q2.front();
            }
        
            if (q1.front()->val==-999){
                q1.pop();
                q2.pop();
                continue;
            }

            if (q1.front()->left){
                q1.push(q1.front()->left);
                q2.push(l+1);
            }else{
                TreeNode* tmp = new TreeNode(-999);
                q1.push(tmp);
                   q2.push(l+1);
            }
            
            if (q1.front()->right){
                q1.push(q1.front()->right);
                q2.push(l+1);
            }else{
                TreeNode* tmp = new TreeNode(-999);
                q1.push(tmp);
                q2.push(l+1);
            }
            q1.pop();
            q2.pop();
        }
        if (!valid(r)){return false;}
        return true;
    }
};

leetcode Question 110: Text Justification

Test Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?
  In this case, that line should be left-justified.

Analysis:

The idea of my solution is not efficient, but easily understood.
It is easier to follow the Python code below.

Step 1: Find the level number for each word. Assuming that there is at least 1 space between two words.
Step 2: Find the number of word in each level and the total spaces needed in that level.
Step 3: Compute the number of spaces M in each level that is needed between two words. If the spaces are not evenly distributed. Compute the number of words where 1+M spaces is needed, and the between the rest of words there needed M spaces.
Step 4: Write the levels which has only one word to the result.
Step 5: Find the levels that the last word that level ends with '.' (which is the sentence end).
Step 6: Write the levels to the result.
Step 7: Return result.

Code(Python):

class Solution:
    # @param words, a list of strings
    # @param L, an integer
    # @return a list of strings
    def fullJustify(self, words, L):
        
        lens = 0    # word length + single space in current level
        result = [] # result list of strings
        single_level = [] # list of strings in current level
        
        for word in words:
            lens += len(word)   
            if lens <= L:   
                single_level.append(word)   # add word into current level
                lens += 1   # add single space length
            else: #if word cannot be in current level
            
                #get result string add to final results
                result.append(self.proc_sinlge_lev(single_level, L, False))
                #refresh the current level
                single_level = []
                single_level.append(word)
                lens = len(word) + 1
                
        #handle the last level of words
        result.append(self.proc_sinlge_lev(single_level, L, True))
        #return final result
        return result
        
    
    # @param single_level, a list of strings 
    # @param L, an integer
    # @param last, an bool (True if current level is the last level)
    def proc_sinlge_lev(self,single_level, L, last):
        
        #last level no extra spaces inserted
        if last == True:
            if len(single_level) == 1:  #only 1 word in current level
                str_lev = single_level[0].ljust(L)
            else:
                str_lev = ""  #result string
                for str in single_level[0:-1]:
                    str_lev += str.ljust(len(str)+1) # 1 is a single space
                str_lev += single_level[-1] # add the last word
                str_lev = str_lev.ljust(L) # fill out spaces
            return str_lev
        else:
            # compute lens of this level
            if len(single_level) == 1: # only 1 word in current level
                str_lev = single_level[0].ljust(L)
            else:
                lev_len = sum(len(s) for s in single_level) # sum of word length in current level
                sp = L-lev_len  # total space numbers 
                first = sp % (len(single_level)-1)  # how many spaces needed when the spaces can not be evenly divided
                sp_s = sp / (len(single_level)-1) # how many spaces are needed between two words
                str_lev ="" # result string
                for str in single_level[0:-1]:
                    if first != 0:  # add one more spaces from the left 
                        str_lev += str.ljust(len(str)+sp_s+1)
                        first -=1
                    else:
                        str_lev += str.ljust(len(str)+sp_s)
                        
                str_lev += single_level[-1] #add last word
                
            return str_lev
            
            
        
            
            
                
             

Code(C++):

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> res;
        vector<int> lev;
         
        int len=0;
        int l=0;
         
        for (int i=0;i<words.size();i++){
            len +=words[i].size();
            if (len<=L){lev.push_back(l);len++;}
            else{l++; lev.push_back(l);len=words[i].size()+1;}
        }
         
        lev.push_back(-1);
         
        vector<int> sp(l+1,L);
        vector<int> sp_mode(l+1,0);
        vector<int> nword(l+1,0);
        for (int i=0;i<words.size();i++){
            sp[lev[i]] -= words[i].size();
            ++nword[lev[i]];
        }
         
        for (int i=0;i<=l;i++){
            if (nword[i]>1){
                sp_mode[i] = sp[i]%(nword[i]-1);
                sp[i] = sp[i]/(nword[i]-1);
            }
        }
         
         
        res=vector<string>(l+1,"");        
        for (int i=0;i<words.size();i++){
            if (nword[lev[i]]==1){
                res[lev[i]] += words[i];
                res[lev[i]] += string(sp[lev[i]],' ');
                nword[lev[i]]=0;
            }
        }
         
         
         
        vector<bool> flag(l+1,false);
         
        int prev=-1;
        for (int i=0;i<words.size();i++){
            if (nword[lev[i]]>0){
                if (lev[i+1]!=lev[i]){
                    if (words[i][words[i].size()-1]=='.') {
                        if (prev==-1){
                            prev = i;    
                        }else{
                            flag[lev[prev]]=false;    
                            prev = i;
                        }
                        flag[lev[i]]=true;
                    }
                }
            }
        }
         
         
        for (int i=0;i<words.size();i++){
             
            if (nword[lev[i]]>0){
                 
                if (flag[lev[i]]==true){
                    res[lev[i]] += words[i];
                    nword[lev[i]]--;
                    if (nword[lev[i]]>0){
                        res[lev[i]]+=' ';
                    }else{
                        res[lev[i]]+=string(L-res[lev[i]].size(),' ');
                    }
                }else{
                 
                res[lev[i]] += words[i];
                nword[lev[i]]--;
                             
                if (nword[lev[i]]>0){
                    if (sp_mode[lev[i]]>0){
                        res[lev[i]] += string(sp[lev[i]]+1,' ');
                        sp_mode[lev[i]]--;
                    }else{
                        res[lev[i]] += string(sp[lev[i]],' ');
                    }   
                }
                }
            }
        }
         
        return res;
    }
};

leetcode Question 111: Trapping Rain Water

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. 

Analysis:

For the small test, we can look at the bar graph from level to level. For each level, scan from the 1st to the last, count 0s between two 1's. Add all the valid 0s for all the levels. However, if the highest and lowest bar is too much different, say 0, 100000, the loop while 100000*n, which is not efficient.

An O(n) solution is to consider each bar at a time, we can see that, for each bar, the water itself can trap depends on the max height on its left and right, e.g.  if current bar is of height 2, the max height on its left is 4, max height on its right is 3,   then water can be trapped in this bar is min(4,3)-2 = 1.

Thus, we can scan the whole map twice to get the max height on right and left, respectively. Finally scan the map again to get the water trapped of all.


Code:

class Solution {
public:
    int trap(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n<2){return 0;}    
        
        int *l = new int[n];
        int *r = new int[n];
        
        int water =0;
        
        l[0]=0;
        for (int i=1;i<n;i++){
            l[i]= max(l[i-1], A[i-1]);
        }
                
        r[n-1] = 0;
        for (int i=n-2;i>=0;i--){
            r[i]=max(r[i+1],A[i+1]);
        }
        
        for (int i=0;i<n;i++){
            if (min(l[i],r[i])-A[i] >0 ){
                water += min(l[i],r[i])-A[i];
            }
        }
        
        return water;
        
    }
};