Friday, July 31, 2015

Leetcode 207/Leetcode 210: course schedule I II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

The input prerequisites is a graph represented by a list of edges, not adjacency matrices.

这个题目很容易分析出来是check if a directed graph has a cycle.

但是给的graph是 a list of edges, 如果只给定一些edges我们是无法对graph进行遍历的,所以我们可以建立一个adjacent list, 并且带上一个state记录每个node的状态。

这个题目里面的adjacent list 可以用map来做, 然后对map做DFS遍历。
采用的是DFS + mark visitIII -> 3 states
但是需要注意的是,需要对graph里面的每个Node进行遍历,才能遍历到所有的可能。
 这个题目里面没有 sanity check !!! 面试的时候要跟面试官商量sanity check的问题。 
class Solution {
private:
    bool dfs(map<int, vector<int>> &nmap, int start, vector<int> &M) {
        //base case
        if (M[start] == 1) return true;//has visited
        if (M[start] == -1) {
            return false;
        }
        M[start] = -1; //visiting node
        //expand
        for (int i = 0; i < nmap[start].size();i++) {
           if(dfs(nmap, nmap[start][i], M) == false) return false;
        }
        M[start] = 1; //mark visit
        return true;
    }
public:
    //to check if a directed graph has a cycle or not
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //map
        map<int, vector<int>> nmap;
        for (int i = 0; i < prerequisites.size(); i++) {
            nmap[prerequisites[i].second].push_back(prerequisites[i].first);//prere->course
        }
        //use map to do dfs + visit
        vector<int> M(numCourses, 0); //unvisited
        for (int i = 0; i < numCourses;i++) {
            if (dfs(nmap, i, M) == false) return false;
        }

        return true;
    }
};
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

这个题目读完就是一个明显的topological sort的问题。
 topological sort DFS写法的一般思路: DFS+ mark visit III, 每次当一个点被mark成visited,之后将这个点加入rst中。
注意在用DFS + mark visit III之前,graph的表示是 course ->  pre-dependency,与判断directed graph里面有没有circle是相反的表示方式。
L Empty list that will contain the sorted nodes
for each of the node n in the graph do
visit(n)

function visit(node n)
if n is visited then return   
if n is visiting then stop (not a DAG, there is a cycle)
if n is not visited or visiting then
mark n visiting
                        for each node m which is n’s dependency do            
visit(m)        
      mark n visited        
      add n to head of L


class Solution {
private:
    bool visit(int start, unordered_map<int, vector<int>> &gmap, int *M, vector<int> &rst) {
        //base case
        if (M[start] == 1) return true;
        if (M[start] == -1) return false; //cycle
        //mark
        M[start] = -1;//mark visiting
        for (int i = 0; i < gmap[start].size();i++) {
            if (visit(gmap[start][i], gmap, M, rst) == false) return false;
        }
        M[start] = 1; //visited
        rst.push_back(start);
        return true;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> rst;
        unordered_map<int, vector<int>> gmap;
        for (int i = 0; i < prerequisites.size(); i++) {
            gmap[prerequisites[i].first].push_back(prerequisites[i].second);
        }
        //vector<int> M(numCourses, 0);
        int M[numCourses] = {0};
        //for each node in the graph do visit n
        for (int i = 0; i < numCourses; i++) {
            if (visit(i, gmap, M, rst) == false) {
                rst.clear();
                break;
            }
        }
        return rst;
    }
};

Leetcode 205: isomorphic strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

isomorphic string 其实考察的是找一一映射的关系,最直接的方法就是用两个map来记录两个string 的各个字符对应的位置,而同一位置上的字符在Map对应的位置应该相同。
由于map对象是string,所以用256个int的 array更加节省空间,可以直接用256个int array来代替map,其实对于string,更加节省空间的方式是bit map, 每一个bit对应一个字符,但是bit map的缺点是只能取值0 , 1.所以只能判断duplicate情况,对于更加复杂一些的情况是不好进行处理的。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        //sanity check
        if (s.size() == 0 && t.size() == 0 ) return true;
        if (s.size() != t.size()) return false;
        int M1[256] = {0};
        int M2[256] = {0};
        for (int i = 0; i < s.size();i++) {
            if (M1[s[i]] != M2[t[i]]) return false;
            M1[s[i]] = i+1;
            M2[t[i]] = i+1;
        }
        return true;
    }
};

Leetcode 203: count prime

Description:
Count the number of prime numbers less than a non-negative number, n.

算法: Sieve of Eeatosthese; 这个在之前的应用密码学里面学过,是在large n 里面找prime的算法, 一个数组标记是不是prime, 从2开始,如果是prime, 那么就将所有该数的
倍数标记为not prime, 怎么高效地除去所有这个数的倍数呢? 首先第一个倍数肯定是 i * i, 因为前面的倍数已经被mark为not prime了。 然后每次 i*i + i必定都是i的倍数, 所以是有一定规律可循的,不用一个个去去除。 这个是重点。

class Solution {
public:
    int countPrimes(int n) {
        //corner case
        if (n < 2) return 0;
        int rst = n-2;
        //must use heap to store M, since M may be very large, and will get out the bound of stack.
        int *M = new int[n];
        for (int i = 0; i < n; i++) {
            M[i] = 0;
        }
        M[0] = -1;
        for (int i = 2; i * i < n; i++) {
            if (M[i-1] != -1) {//is prime
                int j = i*i;
                for (; j < n; j += i) {
                    if (M[j-1] != -1) {
                        M[j-1] = -1;
                        rst--;
                    }
                }
            }
        }
        delete [] M;
        return rst;
    }
};

Thursday, July 30, 2015

Leetcode 203: remove linked list elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

这个题目很简单,要特殊注意的地方就是当链表的head被删除时,可能要进行特殊的处理,所以我们可以用一个dummy head来统一corner case。 其他没有特殊的地方,即使是要被删除的节点连续也是可以generally handle的。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //sanity check
        if (head == NULL) return NULL;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        while (cur) {
            if (cur->val == val) {
                pre->next = cur->next;
            } else {
                pre = cur;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
};

Leetcode 202: happy number

Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
  • 12 + 92 = 82
  • 82 + 22 = 68
  • 62 + 82 = 100
  • 12 + 02 + 02 = 1
这个题目很简单,但是要知道里面的逻辑, 把10进制的每一位取出来进行运算,如果在计算过程中重复出现了之前出现过的数,说明就是有循环出现,此时返回false,如果有结果计算出来为1,那么这个数就是happy number.

class Solution {
public:
    bool isHappy(int n) {
        int rst = 0;
        unordered_set<int> iset;
        while (n != 1) {
            rst = 0;
            while (n) {
                int a = n % 10;
                rst += a * a;
                n = n/10;
            }
            if (iset.find(rst) == iset.end()) iset.insert(rst);
            else return false;
            n = rst;
        }
        if (n == 1) return true;
        return false;
    }
};

Graph DFS/BFS: Leetcode 200: number of island

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3

这个题目分析题目意思其实不难知道题目是求什么,如果能找到所有能连通的1的个数那么就是island的个数了,所以题目转化为求能连通的1的个数。  那么怎么求能连通的1的个数呢?
很显然要么是BFS, 要么是DFS,
如果是BFS来找,对一个‘1’的位置进行expand, 如果expand出来的都是' 0',说明已经找到了一个island, 继续去找另一个‘1’,继续找以它为扩充的island。

如果是DFS来找,连通的区域是一条路径可以走完的,所以是用的mark visit I, mark the node when first visit. 每次只走‘1’的位置,并且走到mark,当可以走到的1全部走完就说明走完了一个连通区域,继续找下一个‘1’。 而这里不需要用mark visit II (back-tracking), 因为mark visit II用在需要遍历所有路径的时候, DFS+ mark visit I ==> BFS, 代码比BFS短,但是可能需要用的空间比BFS大,在分析优劣的时候要注意。

DFS 遍历 graph,一般的步骤是: 1. base case: 一般情况下,在遍历过程中,如果这个node已经visit过了,那么就return,依据题目的意思不同,可能还有其他的base case;2. mark current visiting node  to be visited 3. traverse the node in 4 directions. 如果是mark visit II,最后一步需要把current node mark成 unvisited.

DFS和BFS还有一点不同是, DFS在expand的时候是不需要在那个时候把node mark 成visited的。

BFS 遍历graph, 一般的步骤是: 1. push start node to queue, insert the start node into visited_set; 2. while (!queue.empty()) pop current node, 3. expand the node in 4 direction if unvisited, mark visit, push the node into queue.

class Solution {
private:
    void SearchIsland(int i, int j, vector<vector<char>> &grid) {
        //base caes
        if (grid[i][j] == '#') return; //if node has been visited, return
        if (grid[i][j] == '0') return;
        grid[i][j] = '#'; //mark visited II
        //no need to care about the visit state when expand, this can be checked before expand
        if (i+1 < grid.size()) SearchIsland(i+1, j, grid);
        if (i-1 >= 0) SearchIsland(i-1, j, grid);
        if (j-1 >= 0) SearchIsland(i, j-1, grid);
        if (j+1 < grid[0].size()) SearchIsland(i, j+1, grid);
        return;
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        //sanity check
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int rst = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1' ) {
                    SearchIsland(i, j, grid);
                    rst++;
                }
            }
        }
        return rst;
    }
};

BFS 解法:

class Solution {
private:
    void SearchIsland(int i, int j, vector<vector<char>>& grid) {
        queue<pair<int, int>> explore;
        explore.push(make_pair(i,j));
        grid[i][j] = '#';
        while (!explore.empty()) {
            pair<int,int> tmp = explore.front();
            explore.pop();
            if (tmp.first + 1 < grid.size() && grid[tmp.first+1][tmp.second] == '1') {
                explore.push(make_pair(tmp.first+1, tmp.second));
                grid[tmp.first+1][tmp.second] = '#';
            }
             if (tmp.second + 1 < grid[0].size() && grid[tmp.first][tmp.second+1] == '1') {
                explore.push(make_pair(tmp.first, tmp.second+1));
                grid[tmp.first][tmp.second+1] = '#';
            }
             if (tmp.first - 1 >= 0 && grid[tmp.first-1][tmp.second] == '1') {
                explore.push(make_pair(tmp.first-1, tmp.second));
                grid[tmp.first-1][tmp.second] = '#';
            }
             if (tmp.second- 1 >= 0 && grid[tmp.first][tmp.second-1] == '1') {
                explore.push(make_pair(tmp.first, tmp.second-1));
                grid[tmp.first][tmp.second-1] = '#';
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        //sanity check
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int rst = 0;
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                   SearchIsland(i, j, grid);
                   rst++;
                }
            }
        }
        return rst;
    }
};

通过这个题目BFS 和DFS做法的比较发现, 如果用DFS recursion的话,是不需要额外的数据结构和存储在数据结构里的数据形式的(eg: pair), 而BFS除了需要用queue来存储数据,还是需要想想怎么存数据在queue里,对于二维矩阵,有时候可能是一对pair,有时候可能要存储object,所以这个问题也是BFS解决graph问题的一个点。DFS不需要想这么多,但是可能需要对DFS的树理解比较深,DFS和BFS还有一点不同是, DFS在expand的时候是不需要在那个时候把node mark 成visited的。。 

 注意与word search 那题采用DFS + mark visit II (backtracking) 来做的区别,以及解决问题类型的区别。 

class Solution {
private:
    bool SearchWord(int i, int j, vector<vector<char>>& board, string &word, int idx) {
        //base case
        if (board[i][j] == '#' || board[i][j] != word[idx]) return false; // no path to go
        if (idx == word.size()-1) return true;
        //mark
        char c = board[i][j];
        board[i][j] = '#';
        //expand
        if (i + 1 < board.size()) {
            if (SearchWord(i+1, j, board, word, idx+1)) return true;
        }
        if (i - 1>=0 ) {
            if (SearchWord(i-1, j, board, word, idx+1)) return true;
        }
        if (j+1 < board[0].size()) {
            if (SearchWord(i, j+1, board, word, idx+1)) return true;
        }
        if (j-1 >= 0) {
            if (SearchWord(i, j-1, board, word, idx+1)) return true;
        }
        board[i][j] = c;
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        //sanity check
        if (board.size() == 0 || board[0].size() == 0) return false;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++){
                if (board[i][j] == word[0]) {
                    if (SearchWord(i, j, board, word, 0)) return true;
                }
            }
        }
        return false;
    }
};

Wednesday, July 29, 2015

Leetcode235/236: lowest common ancesterI II III IV / lowest common ancester in binary search tree

Lowest common ancester I :
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
         _____3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
 For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

树的recursion 经典的3段式, 其实找lowest common ancestor的问题就是以current为root在左右子树找p 和q,current node返回给parent找到的p,q的common ancestor。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //base case
        if (root == NULL) return NULL;
        //find the node
        if (root == p ) return p;
        if (root == q) return q;
        //what current node want from children
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        //what current node do in current level
        //what current node return to parent
        if (left && right) {
            return root;
        }
        if (!left) return right;
        if (!right) return left;
    }
};

time complexity: O (n)

Lowest Common Ancestor II
Data Structure
Given two nodes in a binary tree (with parent pointer available), find their lowest common ancestor.
Assumptions
  • There is parent pointer for the nodes in the binary tree
  • The given two nodes are not guaranteed to be in the binary tree
Examples
        5
      /   \
     9     12
   /  \      \
  2    3      14
The lowest common ancestor of 2 and 14 is 5
The lowest common ancestor of 2 and 9 is 9
The lowest common ancestor of 2 and 8 is null (8 is not in the tree)
 //class TreeNodeP {
// public:
//  int value;
//  TreeNodeP* left;
//  TreeNodeP* right;
//  TreeNodeP* parent;
//  TreeNodeP(int v, TreeNodeP* p)
//      : value(v), left(NULL), right(NULL), parent(p) {}
//};
已知parent node找common ancester,就像是两条链表,找两条链表的intersection point.这个题目里面就是按照parent指针往前找。都不在链表里面的情况是没有相交点。

class Solution {
 public:
  TreeNodeP* solve(TreeNodeP* one, TreeNodeP* two) {
    //sanity cehck
    if (one == NULL && two == NULL) return NULL;
    //step1: find two list length
    int len1 = 0;
    int len2 = 0;
    TreeNodeP* p1 = one;
    TreeNodeP* p2 = two;
    while (p1) {
      len1++;
      p1 = p1->parent;
    }
    while (p2) {
      len2++;
      p2 = p2->parent;
    }
    //step2: move one forward n
    if (len1 > len2) {
      for (int i = 0; i < len1 - len2;i++) {
        one = one->parent;
      }
    } else if (len1 < len2) {
      for (int i = 0; i < len2 - len1; i++) {
        two = two->parent;
      }
    }
    //step3: start from the same position and move forward
    while (one != NULL && two != NULL && one != two) {
      one = one->parent;
      two = two->parent;
    }
    if (one == NULL || two == NULL) return NULL;
    return one;
  }
};
time complexity: O(h)

Lowest Common Ancestor III

Given two nodes in a binary tree, find their lowest common ancestor (the given two nodes are not guaranteed to be in the binary tree).
Return null If any of the nodes is not in the tree.
Assumptions
  • There is no parent pointer for the nodes in the binary tree
  • The given two nodes are not guaranteed to be in the binary tree
Examples
        5
      /   \
     9     12
   /  \      \
  2    3      14
The lowest common ancestor of 2 and 14 is 5
The lowest common ancestor of 2 and 9 is 9
The lowest common ancestor of 2 and 8 is null (8 is not in the tree)

这题选的做法是加了一个find函数, 看这两个节点是不是在树里面,如果在就返回LCA
如果不在,就返回NULL。 
class Solution {
private:
  bool find(TreeNode* root, TreeNode* p) {
    //base caser
    if (p == NULL) return false;
    if (root == NULL) return false;
    if (root == p) return true;
    if (find(root->left, p)) return true;
    if (find(root->right, p)) return true;
    return false;
  }
  TreeNode* LCA(TreeNode* root, TreeNode* one, TreeNode* two) {
    if (root == NULL) return NULL;
    if (root == one || root == two) return root;
    TreeNode* left = LCA(root->left, one, two);
    TreeNode* right = LCA(root->right, one, two);
    if (left && right) return root;
    return left ? left : right;
  }
 public:
  TreeNode* solve(TreeNode* root, TreeNode* one, TreeNode* two) {
    //base case
    if (root == NULL) return NULL;
    if (find(root, one) && find(root, two)) {
      return LCA(root, one, two);
    } else {
      return NULL;
    }
  }
};
Lowest Common Ancestor IV
Given K nodes in a binary tree, find their lowest common ancestor.
Assumptions
  • K >= 2
  • There is no parent pointer for the nodes in the binary tree
  • The given two nodes are guaranteed to be in the binary tree
Examples
        5
      /   \
     9     12
   /  \      \
  2    3      14
The lowest common ancestor of 2, 3, 14 is 5
The lowest common ancestor of 2, 3, 9 is 9

class Solution {
 private:
  TreeNode* LCA(TreeNode* root, TreeNode* one, TreeNode* two) {
    //base case
    if (root  == NULL) return NULL;
    if (root == one || root == two) return root;
    TreeNode* left = LCA(root->left, one, two);
    TreeNode* right = LCA(root->right, one, two);
    if (left && right) return root;
    return left ? left : right;
  }
 public:
  TreeNode* solve(TreeNode* root, vector<TreeNode*> nodes) {
    //sanity check
    if (root == NULL) return NULL;
    TreeNode* lca = nodes[0];
    for (int i = 1; i < nodes.size(); i++) {
      lca = LCA(root, lca, nodes[i]);
    }
    return lca;
  }
};

lowest common ancester in binary search tree
recursion VERSION: 
binary search tree, 可以分为p, q在root两边, p, q, 在root 左边, p,q在root右边。
 class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //base case
        if (root == NULL) return NULL;
        if (root == p || root == q) return root;
        if ((root->val < q->val && root->val > p->val) || (root->val > q->val && root->val < p->val)) {
            return root;
        }
        if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        }else {
            return lowestCommonAncestor(root->left, p, q);
        }
    }
};
 iterative version:
iterative 解这题好像更好一些。
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //sanity check
        if (root == NULL) return NULL;
        while (root) {
            if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else if (root->val > p->val && root->val > q->val) {
                root =root->left;
            } else break;
        }
        return root;
    }
};

Leetcode 199: Binary tree right side view + Binary tree top to down view

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].

BFS 遍历tree的变形。!!!
这个题目是求从右边往左边看的树上的值,其实如果知道这一题其实是BFSlevel order traverse  tree,每次取每一层的最后那个node的话就是从右往左看树的结果, 所以这一题我是用bfs 取每层的最后那个值。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> rst;
        //sanity check
        if (root == NULL) return rst;
        queue<TreeNode*> explore;
        explore.push(root);
        while (!explore.empty()) {
            int size = explore.size();
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = explore.front();
                if ( i == size-1) rst.push_back(tmp->val);
                explore.pop();
                if (tmp->left) explore.push(tmp->left);
                if (tmp->right) explore.push(tmp->right);
            }
        }
        return rst;
    }
};

Extends:
1. print binary tree in vertical order
   1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9
 
这个题目一开始看起来没有什么思路,在同一个vertical上的node感觉也没有规律,不知道怎么
标示两个Node是不是在一个vertical上,后来看了网上别人的分析才明白原来两个Node在同一个
vertical上意味着它们离某个原点(root)的距离是相同的,所以这题就转化为先求出tree上面
每个node离root的horizonal distance是多少。 最后输出的就是从最小的distance到最大的
distance每个distance上的node,在求distance的时候用一个Map存起来就可以了。
那么怎么求每个node的distance呢?从原点出发,原点的horizontal distance是0,对于每一个
parentNode而言,向左走,distance = parentNode -1, 向右走 , distance = parentNode + 1
很显然用recursion的方法preorder traverse tree就可以做了。
 
class Solution {
public:
//get the horizontal distance of nodes in the tree
void preorder(TreeNode* root, map<int, vector<int>> &tmap, int hd) {
 //base case
 if (root == NULL) return;
 tmap[hd].push_back(root->val);
 preorder(root->left, tmap, hd-1);
 preorder(root->right, tmap, hd+1);
}

vector<vector<int>> TopView(TreeNode* root) {
 vector<vector<int>> rst;
 //sanity check
 if (root == NULL) return rst; 
 map<int, vector<int>> tmap;
 //count the distance
 preorder(root, tmap, 0);
 //get the vector
 map<int,vector<int>> :: iterator it = tmap.begin();
 for (; it != tmap.end(); it++) {
  vector<int> tmp;
  for (int i = 0; i < (it->second).size(); i++) {
   tmp.push_back((it->second)[i]);
  }
  rst.push_back(tmp);
 }
 return rst;
}
};
AS the map is implemented by BST, the insert, find and delete operation is all O(logn), 
so the time complexity is O(nlogn)

2. view the tree from top to down
 1
    /     \
   2       3
  /  \    / \
 4    5  6   7
Top view of the above binary tree is
4 2 1 3 7

        1
      /   \
    2       3
      \   
        4  
          \
            5
             \
               6
Top view of the above binary tree is
2 1 3 6

由于有上面那个vertical view of a tree的基础,这个题目就很简单了,只要在上面的那个解法里面对map的操作进行处理,只记录某个hd第一次出现的node, 就是在map里面存node之前进行判断,看是否已经有node存在里面了,如果已经有node存在里面了,那么就不继续存,
class Solution {
public:
//get the horizontal distance of nodes in the tree
void preorder(TreeNode* root, map<int, vector<int>> &tmap, int hd) {
 //base case
 if (root == NULL) return;
        if (tmap.find(hd) == tmap.end()) {
           tmap[hd].push_back(root->val);
           cout<< root->val; 
        }
 preorder(root->left, tmap, hd-1);
 preorder(root->right, tmap, hd+1);
}
int TopView(TreeNode* root) {
 vector<vector<int>> rst;
 //sanity check
 if (root == NULL) return rst; 
 map<int, vector<int>> tmap;
 //count the distance
 preorder(root, tmap, 0);
 //get the vector
 map<int,vector<int>> :: iterator it = tmap.begin();
        return 0 ;
}
};
但是上面的方法由于用了map,所以time complexity 是O(nlogn)
有没有什么方法可以使得时间复杂度降到O(n)呢?
考虑到其实map里面每次都只允许存储一个Node,所以 此时的map相当是当做set来用, 所以如果可以
用hash_set来做的话,时间复杂度是O(1)的查找。但是如何记录哪个node和它的hd的对应关系呢??
为了解决这个问题,我们可以用object来进行存储,每个object里面存储两个变量,一个node,一个hd。
C++里面的unordered_set和unordered_map就是对应java里面hash_set, hash_map, unordered_set的
对某个特定Key的查找效率比一般的set快很多, 但是unordered_set里面是不能进行排序的。

class Solution {
public://get the horizontal distance of nodes in the tree
void preorder(TreeNode* root, unordered_set<int> &uset, int hd) {
 //base case
 if (root == NULL) return;
 if (uset.find(hd) == uset.end()) {
  uset.insert(hd);
  cout<< root->val << ' ';
 }
 preorder(root->left, tmap, hd-1);
 preorder(root->right, tmap, hd+1);
}
int TopView(TreeNode* root) {
 vector<vector<int>> rst;
 //sanity check
 if (root == NULL) return rst; 
        unordered_set<int> uset;
        //count the distance
 preorder(root, uset, 0);
 //get the vector
 map<int,vector<int>> :: iterator it = tmap.begin();
        return 0 ;
}
};
  
以上两个都是dfs version 的代码, 其实这个题目也可以用BFS来做,如果用BFS来做的话,
每遍历一层对已经遍历过的node的hd的值进行操作, 
class TreeItem {
 TreeNode* node;
 int hd;
 TreeItem(TreeNode* t1, int hd1) {
  node = t1;
  hd = hd1;
 }
};

void TopView(TreeNode* root) {
 //sanity cehck
 if (root == NULL) return;
 //BFS
 queue<TreeItem*> explore;
 unordered_set<int> uset;
 explore.push(new TreeItem(root, 0));
 while (!explore.empty()) {
  TreeItem* tmp = explore.front();
  explore.pop();
  if (uset.find(tmp->hd) == uset.end()) {
   uset.insert(hd);
   cout << (tmp->node)->val;
  }
  if (tmp->node->left) explore.push(new TreeItem(tmp->node->left, tmp->hd-1));
  if (tmp->node->right) explore.push(new TreeItem(tmp->node->right, tmp->hd+1));
 } 
 return;
}
time complexity: O(n) for the unordered_set is hash set, O(1) to find a value;
如果这个题目对于BFS的解法不定义TreeItem这个object,那么必须要使用map来存储每个node的hd,因为
在遍历到下一层的时候不知道上一层的parent的hd是多少,这样对于map来说,insert的时间复杂度是O(logn)
时间复杂度为O(nlogn). 没有上面O(n)的情况好。  

对于unordered_map: implementation 是hash_table, average insert , delete, find O(1), worset
case is O(N). 

Sunday, July 26, 2015

Small class: 7/26

Q1. (LinkedIn) Find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1

int distance(vector<string> &input, string start, string end) {
    //sanity check
    if (input.size() == 0) return -1;
    int idx1 = -1;
    int idx2 = -1;
    int minl = input.size()+1;
    for (int fast  = 0; fast < input.size(); fast++) {
        if (input[fast] == start) {
            idx1 = fast;
            if (idx2 != -1) {
                minl = min(minl, idx1 - idx2);
            }
        } else if (input[fast] == end) {
              idx2 = fast;
            if (idx1 != -1) {
                minl = min(minl, idx2 - idx1);
            }
        }
    }
    if (minl == input.size()+1) return -1;
    return minl;
}

time complexity: O(n)

就是一个fast指针在前面跑,两个index来记录位置,每次只要一个index发生变化就更新global_min,其实是很简单的题目,但是第一反应总是不知道用快慢指针,而总是想到利map来记录所有的位置,如果这个题目能想到用快慢指针的思想去实时记录位置并计算最小差值,就很简单了。



Q2: There are N pieces of wood, with their lengths (in meters) stored in Bords[N]. k painters are assigned to paint all these wood together.   For each piece of wood, it can only be painted by 1 and only 1 painter, and each painter can only paint contiguous woods.
Each painter can paint wood at the same speed, say 1 meter per minute.    How can we find an assignments such that the total time for painting the wood is minimized.     

(MINI_MAX problem)

____  ___________ |  _________   …| _______
  B0     B1 B3 BN-1

这个题目问题是求使得painting 时间最短的分配,一般这种最小最大问题,我们直接能想到用DP来做,但是对于DP需要知道dp 的含义和递推式子,这个题目K个人刷N个板子,M[N][K]代表N个人刷K个板子的最小时间,于是需要找到次小号的问题,我们需要求K个人粉刷的最短时间,需要从K-1个人粉刷的最短时间,如果是K-1个人粉刷前N-1个board, 那么第K个人需要粉刷第N个board,所以这样分派时间是Max(M[N-1][k-1], B[N-1]), 如果K-1个人粉刷前N-2个板子,那么第K个人需要粉刷最后两个板子,时间是Max(M[N-2][k-1], B(N-1) + B(N-2)),.......遍历所有可能的分配方式,最后取所有可能的最小值。
base case : 如果板子数比人数少的话,即N <= K, 每个板子分配一个人,最后的时间是粉刷用时最长的那个板子,即Max(board[i]).

int minTime(vector<int> &board, int k) {
     

}



Q3: if-else expression.
Implement a solution to parse a ternary expression in string type into a binary tree.
Example1:      a?   b:c  -->   a
                                             /     \
                                            b      c

Example2:           a?   b?c:d:e  -->   a
                                                 /      \
                                              b       e
                                        /      \
                                                 c       d
       
Example3:  a? b:c?d:e  -->
           0         a
                                        /      \
                                       b       c
                                    /    \
                                            d      e


这是一道serialize tree的问题,serialize tree之前在preorder + inorder等这类题目中做过,思想是先找到root所在index,然后找root的左子树对应的index范围和root的右子树对应的index范围,这个题目中也可以用这个思想做,string 的第一个元素肯定是root,但是难点在于找左子树和右子树的对应范围。 怎么去找左子树和右子树呢? 观察example可以发现,只要找到第一个? 后面(不包括这个?在内的)第一个没有匹配的:, 在这个:左边的就是与这个root对应的左子树,右边的就是与这个root对应的右子树。这样的解法是O(n^2) 时间复杂度

这个题目还有一种O(n)的解法: 一直便利整个string,遇到?就把后面的扔到左子树,:的扔到右子树,只有左子树分配好后,才能去考虑右子树。

Method2  (O(n))  
Node* BuildTree(const string& input, int& index) {
if (index >= input.size()) {
return NULL:
}

Node* curr = new Node(input[index]);
bool already_go_left = false;

// CASE1: Go left if possible
if (index + 1 < input.size() && string[index + 1] == ‘?’) {
 already_go_left = true;
 index = index + 2;
 curr->left = BuildTree(input, index);
}

// CASE2: Go right if possible
    if (index + 1 < input.size() && string[index + 1] == ‘:’
   && already_go_left == true) {
 index = index + 2;
 curr->right = BuildTree(input, index);
}
return curr;

}


Q5: 
 Find the smallest window in a string containing all characters of another string
Given two strings s1 and s2, find the shortest substring in s1 containing all characters in s2.
For Example:
s1= “the given test strings”sliding window

left + right + hashtable:  sliding window -> vairiable length of the window. 


string findString (string &input) {
int left = 0;
int right = 0;
int minl = input.size();
map<char, int> imap;
for (int i = 0; i < input.size(); i++ ) {
imap[input[i]]++;
}
int match = 0;
for ( ; right < input.size(); right++) {
if (imap.find(input[right]) != imap.end()) {
imap[input[right]]—;
if (imap[input[right]] == 0) match++;
while (match == imap.size()) {
minl = min(minl, right - slow+1);
for (; slow < input.size(); slow++) {
if (imap.find(input[slow]) != imap.end()) {
imap[input[slow]—;
if (imap[input[slow]] == 1) match—;
break;
}
}
}
}
return minl;

}



Saturday, July 25, 2015

leetcode 198: House Robber//Leetcode 213 : House Robber II


You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
这个题目问的是能盗取的最大的钱数,通过分析肯定是属于一维dp的题目,而一维DP的递推规律也很好找,即跳过左边的房子看盗取之前的房子哪个钱数多。M[i]表示盗到第i 家包含i在内的最多钱数。

时间复杂度是O(n^2). 空间复杂度O(n).


class Solution {
public:
    //use dp
    int rob(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 0;
        int M[nums.size()];
        //base case
        M[0] = nums[0];
        int rst = M[0];
        for (int i = 1; i < nums.size();i++) {
            if (i == 1) M[1] = nums[1];
            else {
                int j = i-2;
                int maxl = 0;
                for (; j >= 0; j--) {
                    maxl = max(M[j] + nums[i], maxl);
                }
                M[i] = maxl;
            }
            rst = max(rst, M[i]);
        }
        return rst;
    }
};

House RobberII

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

 题目分析: 这个题目是house robber的follow up, 如果所有房子是一个circle,怎么处理,其实举几个列子发现,偷东西只可能两种情况,一种是偷了最后一家,那么就不能偷第一家, 所以偷的房子范围是 1-size-1, 另一种是不偷最后一家,那么就可以偷第一家,所以偷房子的范围是0-size-2, 最后取这两种情况下的较大值,而这两种情况下的最大值的可以通过house robber1的dp方法来做。

class Solution {
private:
//get the max money from start to end
    int helper(vector<int> &nums, int start, int end) {
        int rst = 0;
        //sanity check
        if (start > end) return rst;
        int M[end - start +1];
        //base caes
        M[0] = nums[start];
        rst = M[0];
        for (int i = 1; i < end-start+1; i++) {
            if (i == 1) {
                M[i] = nums[start+1];
            } else {
                int tmp_max = INT_MIN;
                for (int j = i-2; j >= 0; j--) {
                    tmp_max = max(tmp_max, M[j] + nums[start+i]);
                }
                M[i] = tmp_max;
            }
            rst = max(rst, M[i]);
        }
        return rst;
    }
public:
    int rob(vector<int>& nums) {
        //sanity cehck
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        //case 1 : stole the end
        int e1 = helper(nums, 1, nums.size()-1);
        //case 2: didn't stole the end
        int e2 = helper(nums, 0, nums.size()-2);
        return max(e1, e2);
    }
};

updated;
这个题目可以进一步优化到O(n)的时间复杂度,只要改变一下M[i]的定义: 走到第i家能盗到的最大钱数,最后直接返回M[size-1]就可以了,比第一种方法效率高。 

class Solution {
public:
    //use dp
    int rob(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 0;
        int M[nums.size()];
        //base case
        M[0] = nums[0];
        int rst = M[0];
        for (int i = 1; i < nums.size();i++) {
            if (i == 1) M[1] = max(nums[1],nums[0]);
            else {
                M[i] = max(M[i-2] + nums[i], M[i-1]);
            }
        }
        return M[nums.size()-1];
    }
};

通过这个题目发现,dp解题时M[i]的定义不同,解法的效率是不同的,要多想几种可能解的M[i]