Han Zhu's Study Notes

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. Note: The input prerequisites is a graph represented by  a list of edges , not adjacency matrices. Read more about  how a graph is represented . You may assume that there are no duplicate edges in the input prerequisites. click to show more hints. Hints: This problem is ...

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 Thought process: BFS. islands = 0. Iterate through every number on the grid. For each number, if it's 1: islands++. Change the number to 0. For each neighbor of the number, if it's 1, offer it to the queue. Return islands. Solution 1 (BFS): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { private final int [][] directions = { { - 1 , 0 }, { 0 , - 1 }, { 1 , 0 }, { 0 , 1 } }; public int numIslands ( char [][] grid) { int num = 0 ; for ( int i = 0 ; i < grid....

Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters  a-z  or  . . A  .  means it can represent any one letter. For example: addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note: You may assume that all words are consist of lowercase letters  a-z . click to show hint. You should be familiar with how a Trie works. If not, please work on this problem:  Implement Trie (Prefix Tree)  first. Thought process: Use trie. addWord: iterate through the word. Start from the root trie node. If current character does not map to a trie node, create a new one and map them. Otherwise, go to the next trie node. Search: iterate through the word. If current character is ...

Implement wildcard pattern matching with support for  '?'  and  '*' . '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") ? false isMatch("aa","aa") ? true isMatch("aaa","aa") ? false isMatch("aa", "*") ? true isMatch("aa", "a*") ? true isMatch("ab", "?*") ? true isMatch("aab", "c*a*b") ? false Thought process: Recursively match s and p's substrings. Base case: If s and p are both empty, return true. If p's length is 1: If p is *, return true. If p is ? and s's length is 1, return true. Else if s and p are equal, return true. Recurrence: If p's first char...