Han Zhu's Study Notes

Implement pow( x ,   n ). Thought process: Shortest problem description!  Recursively calculate pow(x, n / 2). Base cases: n = 0, return 1. n = 1, return x. n = -1, return 1 / x. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class Solution { public double myPow ( double x , int n ) { if ( n == 0 ) { return 1 ; } if ( n == 1 ) { return x ; } if ( n == - 1 ) { return 1 / x ; } if ( n % 2 == 0 ) { double half = myPow ( x , n / 2 ); return half * half ; } if ( n < 0 ) { return myPow ( x , n / 2 ) * myPow ( x , n / 2 - 1 ); } return myPow ( x , n / 2 ) * myPow ( x , n / 2 + 1 ); } } Time complexity: O(logn).

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are  given the locations and height of all the buildings  as shown on a cityscape photo (Figure A), write a program to  output the skyline  formed by these buildings collectively (Figure B).   The geometric information of each building is represented by a triplet of integers  [Li, Ri, Hi] , where  Li  and  Ri  are the x coordinates of the left and right edge of the ith building, respectively, and  Hi  is its height. It is guaranteed that  0 ? Li, Ri ? INT_MAX ,  0 < Hi ? INT_MAX , and  Ri - Li > 0 . You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. For instance, the dimensions of all buildings in Figure A are recorded as:  [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] . The output is a list ...

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note: The input string may contain letters other than the parentheses  (  and  ) . Examples: "()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""] Thought process: BFS: Graph definition: Vertex: a candidate string. Edge: two strings s1 and s2 have an edge if s1 equals s2 with one parenthesis deleted. Put string into a queue. For the current size of the queue, poll a string from the queue. Iterate through the string. For each character, remove it, and check if the parentheses are valid. If so, iterate over current level and return the result. If not, offer the new string to the queue. 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 38 39 40 41 ...

You are given a  m x n  2D grid initialized with these three possible values. -1  - A wall or an obstacle. 0  - A gate. INF  - Infinity means an empty room. We use the value  2 31  - 1 = 2147483647  to represent  INF  as you may assume that the distance to a gate is less than  2147483647 . Fill each empty room with the distance to its  nearest  gate. If it is impossible to reach a gate, it should be filled with  INF . For example, given the 2D grid: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF After running your function, the 2D grid should be: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 Thought process: Iterate through the grid. Add gates' coordinates to queue. BFS from gates and expand through all rooms. Solution: 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 public class Solution { private final ...

Given  n  nodes labeled from  0  to  n - 1  and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given  n = 5  and  edges = [[0, 1], [0, 2], [0, 3], [1, 4]] , return  true . Given  n = 5  and  edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] , return  false . Note : you can assume that no duplicate edges will appear in  edges . Since all edges are undirected,  [0, 1]  is the same as  [1, 0] and thus will not appear together in  edges . Thought process: A tree is a graph that doesn't have a cycle. BFS. When a node is polled from queue, iterate through its neighbors. If any of them is visited but not the node's parent, there is a cycle. If there are no edges, then the graph is a tree only if it has only one node. Build graph. Use a map of int -> list of int. Iterate through the edg...

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] . Note:...