[LeetCode] Course Schedule II

The question can be found here: https://leetcode.com/problems/course-schedule-ii/

Analysis:
1) find the sink node which doesn't have any directed neighbors
2) put it at the head of the list and remove it
3) repeat 1) and 2)
See more at :https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html

class Solution {
    bool isSinkNode(unordered_map<int, unordered_set<int>>& map, 
                    vector<int> &visited, int cur, 
                    vector<int> & res, bool &cycle){
                        
        if(visited[cur] == 1) 
        {
            cycle = true;
            return false;
        }
        // 1 means its being visited in a path
        visited[cur] = 1;
        int nonSinkNeighbors = map[cur].size();
        for(auto e: map[cur])
        {
            if(visited[e] == 2|| 
                isSinkNode(map, visited, e,
                res, cycle)) nonSinkNeighbors--;
            else if(cycle) return false;
        }
        // if all the neighbors are sink node
        if(0 == nonSinkNeighbors) 
        {
            res.push_back(cur);
            //2 means this node is a sink node
            visited[cur] = 2;
        }
        // 3 means its visited in a path but not a sink node
        // we need to set it a value other than 1 to 
        else visited[cur] = 3; 
        return visited[cur] == 2;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res;
        unordered_map<int, unordered_set<int>> map;
        for(auto p: prerequisites) map[p.first].insert(p.second);
        bool cycle = false;
        
        vector<int> visited(numCourses, 0);
        for(int i=0;i<numCourses;i++)
        {
            //0 means its not ever visited.
            if(visited[i] == 0) isSinkNode(map, visited, i, res, cycle);
        }
        if(cycle) return vector<int>();
        return res;
    }
};

[LeetCode] 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: It's the same question as get Binary Tree Paths

/**
 * 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 {
/**
 * 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 {
    vector<string> getAllPaths(TreeNode * node)
    {
        vector<string> res;
        if(!node) return res;
        string cur = to_string(node->val);
        if(!node->left && !node->right) res.push_back(cur);
        
        if(node->left)
        {
            vector<string> left = getAllPaths(node->left);
            for(auto e :left) res.push_back(cur+e);
            
        }
        if(node->right)
        {
            vector<string> right = getAllPaths(node->right);
            for(auto e :right) res.push_back(cur+e);
        }    
        return res;
    }
public:
    int sumNumbers(TreeNode* root) {
        vector<string> paths = getAllPaths(root);
        int res = 0;
        for(auto e:paths) res += stoi(e);
        return res;
    }
};

[LeetCode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

DFS :

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    typedef unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> GraphMap;
    UndirectedGraphNode * clone(UndirectedGraphNode* node, GraphMap &map)
    {
        if(map.count(node)) return map[node];
        UndirectedGraphNode* newNode = new UndirectedGraphNode(node->label);
        map[node] = newNode;
        for(auto neighbor : node->neighbors)
        {
            UndirectedGraphNode* one = clone(neighbor, map);
            newNode->neighbors.push_back(one);
        }
        return newNode;
    }
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(NULL == node) return NULL;
        GraphMap map;
        return clone(node, map);
    }
};

BFS :

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(NULL == node) return NULL;
        queue<UndirectedGraphNode*> visit;
        GraphMap map;
        visit.push(node);
        UndirectedGraphNode * newCopy = new UndirectedGraphNode(node->label);
        map[node] = newCopy;
       
        while(!visit.empty())
        {
            UndirectedGraphNode *cur = visit.front();
            visit.pop();

            for(auto neighbor : cur->neighbors)
            {
                UndirectedGraphNode * newNeighbor;
                if(map.count(neighbor))
                {
                    newNeighbor = map[neighbor];
                }
                else
                {
                    newNeighbor = new UndirectedGraphNode(neighbor->label);
                    visit.push(neighbor);
                    map[neighbor] = newNeighbor;
                }
                map[cur]->neighbors.push_back(newNeighbor);
            }
        }
        
        return map[node];
    }
};

[LeetCode] Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Example

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    bool isMatch(const char *s, const char *p) {
        // write your code here
        if(*p == '\0') return *s == '\0';

        if(*(p+1) == '*')
        {
            while(*p == *s || ((*p) == '.' && (*s) != 0))
            {
                if(isMatch(s, p + 2)) return true;
                s++;
            }
            return isMatch(s, p + 2);
        }
        else
        {
            if (*s != '\0' && *p == *s || *p == '.') return isMatch(s+1, p+1);
        }
        return false;
    }
};

[LeetCode] Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false. Note: 1) Translating string to char* will facilitate solving the problem. 2) Set element of the original matrix to NULL to mark its visited.

class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
    for (int i = 0; i<board.size(); i++)
        for (int j = 0; j<board[0].size(); j++)
            if (exist(board, word.c_str(), i, j))
                return true;
    return false;
}

bool exist(vector<vector<char> > &board, const char* word, int row, int col) {  
    if (*word != board[row][col] || board[row][col] == NULL)
        return false;

    if (*(word + 1) == NULL)
        return true;

    char t = board[row][col];
    board[row][col] = NULL;

    if (row > 0 && exist(board, word + 1, row - 1, col) 
        || col > 0 && exist(board, word + 1, row, col - 1)
        || row < board.size() - 1 && exist(board, word + 1, row + 1, col)
        || col < board[0].size() - 1 && exist(board, word + 1, row, col + 1))
        return true;

    board[row][col] = t;

    return false;
  }
};

[LeetCode] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Analysis:
Note: the maximum path doesn't have to include the root. So, if we do DFS, we need to record the maximum path sum of a sub tree. For root->left, the DFS function should return the maximum path sum that ends at root->left, in order to connect to root. root->right should be the same.

class Solution {
public:
    int maxPathSum(int & maxSum, TreeNode* root) 
    {
        if(!root) return 0;
        int tmp = root->val;
        int left = maxPathSum(maxSum, root->left);
        if(left>0) tmp+=left;
        int right = maxPathSum(maxSum, root->right);
        if(right>0) tmp+=right;
        //Note: maxSum has already been compared with left and right
        //      in recursive calls
        maxSum = max(tmp, maxSum);
        return max(root->val, max(left, right) + root->val);
    }
    int maxPathSum(TreeNode* root) {
        if(!root) return 0;
        int maxSum = INT_MIN;
        int res = maxPathSum(maxSum, root);
        return max(res, maxSum);
    }
};

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the 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:
    TreeNode *buildTree(unordered_map<int, int> &map,
                        vector<int> &postorder,int ps, int pe, 
                        vector<int> &inorder, int is, int ie) 
    {
        if(ps>pe) return NULL;
        int i= map[postorder[pe]];
        TreeNode *node = new TreeNode(postorder[pe]);
        node->left = buildTree(map,postorder, ps, ps+i-is-1, inorder, is, i-1);
        node->right = buildTree(map,postorder, ps+i-is, pe-1, inorder, i+1, ie);
        return node;
    }

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        unordered_map<int, int> map;
        for(int i=0;i<inorder.size();i++)
        {
            map[inorder[i]] = i;
        }
        int len = postorder.size();
        return buildTree(map, postorder, 0, len-1, inorder, 0, len-1);
    }
};

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the 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:

    TreeNode *buildTree(unordered_map<int, int> &map,
                        vector<int> &preorder,int ps, int pe, 
                        vector<int> &inorder, int is, int ie) 
    {
        if(ps>pe) return NULL;
        int i= map[preorder[ps]];
        TreeNode *node = new TreeNode(inorder[i]);
        node->left = buildTree(map,preorder, ps+1, ps+i-is, inorder, is, i-1);
        node->right = buildTree(map,preorder, ps+i-is+1, pe, inorder, i+1, ie);
        return node;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        unordered_map<int, int> map;
        for(int i=0;i<inorder.size();i++)
        {
            map[inorder[i]] = i;
        }
        int len = preorder.size();
        return buildTree(map, preorder, 0, len-1, inorder, 0, len-1);
    }
};

[LeetCode] Course Schedule

The question can be found here: https://leetcode.com/problems/course-schedule/

Analysis:

You can just think of the problem checking if circle exists in a tree. Just need to note:
1) In a search path from any node,  if any node in the path appears more than once, there is a circle.
2) If a node is in a search path that doesn't have circle, any other searches should stop once they meet the node.
These will make the complexity O(n).
DFS solution:

See Course Schedule II

class Solution {
public:
    bool hasCircle(unordered_map<int, vector<int>> &map, 
                int cur, unordered_set<int>& visited)
    {
        if(!map.count(cur) || map[cur].size()==0) return false;
        //if cur course was visited, there is a circle
        if(visited.count(cur)) return true;
        visited.insert(cur);
        for(int i=0;i < map[cur].size();i++)
        {
            if(hasCircle(map, map[cur][i],visited)) return true;
        }  
        //the course cur is good, any other searches should not check it again.
        map[cur].clear();
        return false;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        unordered_map<int, vector<int> > map;
        unordered_set<int> visited;
        for(auto p:prerequisites) map[p[0]].push_back(p[1]);
        for(auto it:map)
        {
            if(hasCircle(map, it.first, visited)) return false;
            visited.clear();
        }
        return true;
    }
};

[LeetCode] Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

/**
 * 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 pathSum(TreeNode *root, int sum, vector<int> & rec, vector<vector<int> >& res)
    {
        if(!root) return;
        rec.push_back(root->val);
        if(!root->left && !root->right)
        {
            if(root->val == sum)
            {
                res.push_back(rec);
                return;
            }
        }
        if(root->left)
        {
            pathSum(root->left, sum - root->val, rec, res);
            rec.pop_back();
        }
        if(root->right)
        {
            pathSum(root->right, sum - root->val, rec, res);
            rec.pop_back();
        }
    }
    vector<vector<int> > pathSum(TreeNode *root, int sum) 
    {
        vector<vector<int> > res;
        vector<int> rec;
        pathSum(root, sum, rec, res);
        return res;
    }
};

[LeetCode] Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    bool getMax(int sum, TreeNode *node, int subSum)
    {
        if(!node) return false;
     subSum += node->val;
     if(!node->right && !node->left) return sum == subSum;
     if(getMax(sum, node->left, subSum)) return true;
     if(getMax(sum, node->right, subSum)) return true;
     return false;
    }
public:
    bool hasPathSum(TreeNode *root, int sum) 
    {
        return getMax(sum, root, 0);
    }
};

[LeetCode] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

DFS Solution:

class Solution {
public:
    void generate(vector<string> & res, string one, 
                  int left, int right, int n)
    {
        if(left == n && right == n)
        {
            res.push_back(one);
            return;
        }
        if(left < n)
        {
            generate(res, one+'(', left+1,right, n);
        }
        if(left > right)
        {
            generate(res, one +')', left,right+1, n);
        }
    }

    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        generate(res, "", 0,0,n);
        return res;
    }
};

BFS Solution :
find the last occurrence position P of '(' in the previous result, and append '(' + the rest + ')' to it from P+1 to end;

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        res.push_back("");
        for(int i=0;i<n;i++)
        {
            vector<string> tmp;
            for(int j=0;j<res.size();j++)
            {
                int pos = res[j].rfind('(');
                for(int k=pos+1;k<=res[j].size();k++)
                {
                    tmp.push_back(res[j].substr(0,k) +
                        '(' + res[j].substr(k) + ')');
                }
            }
            res = tmp;
        }
        return res;
    }
};

[LeetCode] Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Analysis:
If we create a balanced BST using a sorted array, it will be much easier, because we access each element of the array very easily. And the tree can be created by pre-order.
Note, with linked list, we can only easily access the element from left to right, which indicates that we might be able to create the tree by in-order. Each time we create a tree node, we move the linked list pointer to the next.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *listToTreeInner(ListNode*& head, int start, int end) 
    {
        if(start > end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftNode = listToTreeInner(head, start, mid-1);
        TreeNode *current = new TreeNode(head->val);
        current->left = leftNode;
        //Note, we move head to the next for the next node
        head = head->next;
        TreeNode *rightNode = listToTreeInner(head, mid+1, end);
        current->right = rightNode;
        return current;
    }

    TreeNode *sortedListToBST(ListNode *head) 
    {
        if(!head) return NULL;
        int last = 0;
        ListNode* p = head;
        while(p->next) {
            last++;
            p = p->next;
        }
        return listToTreeInner(head, 0, last);
    }
};

[LeetCode] Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

DFS solution:

class Solution {
private:
    // This returns the last node on the right 
    TreeNode* flatTree(TreeNode *root) {
        if(!root->left && !root->right) return root;
        TreeNode *l = NULL; TreeNode *r = NULL;
        if(root->right)  
        {
            r = flatTree(root->right);
        }        
        if(root->left)
        {
            l = flatTree(root->left);
            TreeNode *t = root->right;
            root->right = root->left;
            root->left = NULL;
            l->right = t;
        }
        return r?r:l;
    }
public:
    void flatten(TreeNode *root) {
        if(!root) return;
        flatTree(root);
    }
};

Note: Each node's right child points to the next node of a pre-order traversal

class Solution {
public:
    void flatten(TreeNode *root) {
        stack<TreeNode*> s;
        TreeNode dummy(0);
        TreeNode *last = &dummy;
        while(!s.empty() || root)
        {
            if(root)
            {
                if(root->right) s.push(root->right);
                last->right = root;
                last = root;
                root = root->left;
                last->left = NULL;
            }
            else
            {
                root = s.top();
                s.pop();
            }
        }
    }
};