Day 6, 1, Two Sum

Two Sum
Solution #1, sort then look for match, O(nlogn)

struct Node {
  int val;
  int index;
  Node(){}
  Node(int v,int i):val(v),index(i) {}
};

bool comp (const Node &left, const Node &right) {
    return left.val < right.val;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Node> boo;
        for (int i=0;i<numbers.size();i++) {
            boo.push_back(Node(numbers[i],i+1));
        }
        sort(boo.begin(),boo.end(),comp);
        
        int frontI = 0;
        int backI = boo.size() - 1;
        while (frontI < backI) {
            int sum = boo[frontI].val + boo[backI].val;
            if (sum == target) {
                int minI = min(boo[frontI].index,boo[backI].index);
                int maxI = max(boo[frontI].index,boo[backI].index);
                vector<int> re;
                re.push_back(minI);
                re.push_back(maxI);
                return re;
            }
            else if (sum < target) {
                frontI++;
            }else {
                backI--;
            }
        }
    }
};

Solution #2, hashmap, O(n)

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,int> mapping;
        vector<int> result;
        for (int i=0;i<numbers.size();i++) {
            if (mapping.find(numbers[i]) == mapping.end()) {
                mapping[numbers[i]] = i + 1;
            }else if (numbers[i] * 2 == target) {
                result.push_back(mapping[numbers[i]]);
                result.push_back(i+1);
                return result;
            }
        }
         
        for (int i=0;i<numbers.size();i++) {
            int remainder = target - numbers[i];
            if (remainder * 2 != target && mapping.find(remainder) != mapping.end()) {
                result.push_back(i+1);
                result.push_back(mapping[remainder]);
                return result;
            }
        }
        
        return result;
    }
};

Added on Sep-02-2014 
Solution #3

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ret(2);
        unordered_map<int,int> mapping;
        unordered_map<int,int>::iterator itr;
        
        for (int i = 0; i < numbers.size(); i++) {
            itr = mapping.find(numbers[i]);
            if (itr == mapping.end()) {
                mapping.insert(make_pair(numbers[i],i + 1));
            }else {
                if (numbers[i] + itr->first == target) {
                    ret[0] = itr->second;
                    ret[1] = i + 1;
                    return ret;
                } 
            }
        }
        
        for (int i = 0; i < numbers.size(); i++) {
            itr = mapping.find(target - numbers[i]);
            if (itr != mapping.end() && itr->second != i + 1) {
                ret[0] = i + 1;
                ret[1] = itr->second;
                return ret;
            }
        }
        
        return ret;
    }
};

Day 5, leetcode 111, 112, Minimum Depth of Binary Tree, path sum

Minimum Depth of Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int left = minDepth(root->left) + 1;
        int right = minDepth(root->right) + 1;
        
        if (root->left == NULL) return right;
        if (root->right == NULL) return left;
        
        return min(left,right);
    }
};

solution #2 by others

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return 0;  
          
        int left = minDepth(root->left) + 1;  
        int right = minDepth(root->right) + 1;  
        // 叶子节点  
        if (left == 1 || right == 1)  
            return left > right ? left : right;  
              
        return left < right ? left : right;  
    }
};

BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int level = 1;
        int size = 1;
        
        while (!que.empty()) {
            if (size == 0) {
                size = que.size();
                level++;
            }else {
                TreeNode *t = que.front();
                que.pop();
                if (t->left == NULL && t->right == NULL) return level;
                if (t->left != NULL) que.push(t->left);
                if (t->right != NULL) que.push(t->right);
                size--;
            }
        }
        
        return level;
    }
};

Path Sum

/**
 * 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 rec (TreeNode *root, int sum, int curSum) {
        if (root == NULL) return false;
        curSum += root->val;
        if (root->left == NULL && root->right == NULL) {
            return sum == curSum;
        }
        return rec(root->left, sum, curSum) || rec(root->right, sum, curSum);
    }

    bool hasPathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return rec(root, sum, 0);
    }
};

Solution #2 by others

/** 
 * 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 hasPathSum(TreeNode *root, int sum) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if (root == NULL)  
        {  
            return false;  
        }  
          
        int leftsum = sum - root->val;  
        // 找到sum，并且为叶子节点  
        if (leftsum == 0 && root->left == NULL && root->right == NULL)  
        {  
            return true;  
        }  
        bool left = hasPathSum(root->left, leftsum);  
        bool right = hasPathSum(root->right, leftsum);  
  
        return left || right;  
    }  
}; 

Day 4, leetcode 104, 110 , Maximum Depth of Binary Tree, Balanced Binary Tree

Maximum Depth of Binary Tree

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return 0;
        int left = maxDepth(root->left) + 1;
        int right = maxDepth(root->right) + 1;    
        if (left > right) return left;
        else return right;
        
        
    }
};

Balanced Binary Tree
---------------------------------------- 
Efficiency: O(n^2), is there a better way to do this?

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

    int depth(TreeNode *root) {
        if (root == NULL) return 0;
        int left = depth(root->left) + 1;
        int right = depth(root->right) + 1;   
        if (left > right) return left;
        else return right;
    }
    
    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return true;
        return isBalanced(root->left) && isBalanced(root->right) && abs(depth(root->left) - depth(root->right)) < 2;
    }
};

Update on Jan-18-2015
O(n), each node is only visited once

/**
 * 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 flag;
    int getHeight(TreeNode *root) {
        if (root == NULL) {
            return 0;
        }
        
        int leftH = getHeight(root->left) + 1;
        int rightH = getHeight(root->right) + 1;
        if (abs(leftH - rightH) > 1) flag = false;
        return max(leftH,rightH);
    }

    bool isBalanced(TreeNode *root) {
        flag = true;
        getHeight(root);
        
        return flag;
        
    }
};

Update on Feb-07-2019, in Java
Get the height of each node

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }
    
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (left == -1 || right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}

Day 3, #100, #101, Same Tree, Symmetric Tree

Same Tree

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

Symmetric Tree
Solution #1

/**
 * 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 isSymmetricRec(TreeNode *p,TreeNode *q) {
        if (p == NULL && q == NULL) return true;
        if (p == NULL || q == NULL) return false;
        if (p->val != q->val) return false;
        return isSymmetricRec(p->left, q->right) && isSymmetricRec(p->right, q->left);
    }

    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return true;
        return isSymmetricRec(root->right,root->left);
        
    }
};

Day 2 leetcode 58, 66, 83

Length of Last Word
Solution#1

int lengthOfLastWord(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int length=0;
        if (*s== NULL) return length;
        while (*s != NULL) {
            length=0;
            while (isalpha(*s)) {
                *s++;
                length++;
            }
            while (*s == ' ') 
                *s++;
        }
        return length;
}

Solution#2

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        bool inAWord = false;
        int length = 0;
        int itr = 0;
        while (s[itr] != NULL) {
            if (isalpha(s[itr])) {
                if (!inAWord) length = 0;
                itr++;
                length++;
                inAWord = true;
            }else if (isspace(s[itr])) {
                itr++;
                inAWord = false;
            }
        }
        
        return length;
    }
};

Plus One
Solution#1

    vector<int> plusOne(vector<int> &digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int length = digits.size();
        int index = 0;
        bool flag = false;
        // look for '9'+
        for (int i=0;i<length;i++) {
            if (digits[i] == 9 && !flag) {
                index = i;
                flag = true;
            }
            else if (digits[i] != 9 && flag)
                flag = false;
        }
        
        if (!flag) digits[length-1] = digits[length-1] + 1;
        else {
            for (int i=index;i<length;i++) {
                digits[i] = 0;
            }
            // if it starts at beginning
            if (index == 0) {
                digits[0] = 1;
                digits.push_back(0);
            }
            else digits[index-1] = digits[index-1] + 1;   
        }
        return digits;     
    }

Solution#2

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        bool carry = true;
        int itr = digits.size() - 1;
        while (carry && itr >= 0) {
            if (digits[itr] == 9) {
                digits[itr] = 0;
            }else {
                digits[itr] = digits[itr] + 1;
                carry = false;
                return digits;
            }
            itr--;
        }

        vector<int> copy(digits.size() + 1);
        copy[0] = 1;
        for (int i = 0; i < digits.size(); i++) {
            copy[i + 1] = digits[i];
        }
            
        return copy;
        
    }
};

找到最后一个非9的数

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int notNine = -1;
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                notNine = i;
                break;
            }
        }
        
        for (int i = notNine + 1; i < digits.size(); i++) {
            digits[i] = 0;
        }
        
        if (notNine == -1) {
            vector<int> rt(digits.size() + 1,0);
            rt[0] = 1;
            return rt;
        }
        
        digits[notNine]++;
        return digits;
    }
};

Remove Duplicates from Sorted List

ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL) return head;
        ListNode *temp = head;
        
        while (temp->next != NULL) {
            if (temp->val == temp->next->val) 
                temp->next =  temp->next->next;
            else temp = temp->next;
        }
        return head;
}

Day 1 - leetcode 26, 27, remove

26 Remove Duplicates from Sorted Array
Solution #1

int removeDuplicates(int A[], int n) {
   // Start typing your C/C++ solution below
   // DO NOT write int main() function
   //int i = 0;
   int index=0,cur = 1;
   if (n==0) return 0;
   while (cur < n) {
           if (A[index] != A[cur]) {
                 index++;
              A[index] = A[cur];
           }
       cur++;
   }
   return index+1;
}

Solution #2

 int removeDuplicates(int A[], int n) {
       // Start typing your C/C++ solution below
       // DO NOT write int main() function
       if (n==0) return 0;
       int start=0;
       for (int i=0;i<n;i++) {
           if (A[start] != A[i]) {
               A[++start] = A[i];
               //start++;
           }
           
       }
       return start+1;
    }

27 Remove Element
Solution #1

int removeElement(int A[], int n, int elem) {
         // Start typing your C/C++ solution below
        // DO NOT write int main() function
         int start = 0;
         for(int i = 0; i < n; i++)
            if (elem != A[i])            {
                 A[start++] = A[i];            }
             
         return start;
   }