刷题记录

Probelm: Given an undirected  graph , return  true  if and only if it is bipartite. Recall that a graph is  bipartite  if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B. The graph is given in the following form:  graph[i]  is a list of indexes  j  for which the edge between nodes  i  and  j  exists.  Each node is an integer between  0  and  graph.length - 1 .  There are no self edges or parallel edges:  graph[i]  does not contain  i , and it doesn't contain any element twice. Example 1: Input: [[1,3], [0,2], [1,3], [0,2]] Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}. Example 2: Input: [[1,2,3], [0,2], [0,1,3], [0,2]] Output: false Explanation: The graph looks like this: 0...

Problem: We are given a binary tree (with root node  root ), a  target  node, and an integer value  K . Return a list of the values of all nodes that have a distance  K  from the  target  node.  The answer can be returned in any order. Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4] , target = 5 , K = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1. Note that the inputs "root" and "target" are actually TreeNodes. The descriptions of the inputs above are just serializations of these objects. Analysis: 这道题和之前那道 742. Closest Leaf in a Binary Tree  类似。都是先建图然后BFS。不同点在于，这道题如果按742的图的构建方式，test case [1] 通过不了， 因为node 1根本不会出现在图中。就会出现null pointer错误。 另外一个点就是，在while循环一开始判断k的值，循环底部k--。如果反过来而且k==0, 就得不到结果。 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 32 33 34 35 36 37 38 39 40 41 ...

Problem: Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a  full binary tree , but some nodes are null. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the  null  nodes between the end-nodes are also counted into the length calculation. Example 1: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9). Example 2: Input: 1 / 3 / \ 5 3 Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3). Example 3: Input: 1 / \ 3 2 / 5 Output: 2 Explanation:...

Problem: You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map: 0  represents the  obstacle  can't be reached. 1  represents the  ground  can be walked through. The place with number bigger than 1  represents a  tree  can be walked through, and this positive number represents the tree's height. You are asked to cut off  all  the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1). You will start from the point (0, 0) and you should output the minimum steps  you need to walk  to cut off all the trees. If you can't cut off all the trees, output -1 in that situation. You are guaranteed that no two  trees  have the same height and there is at least one tree needs to be cut off. Example 1: Input: [ [...

Problem: There are  N  rooms and you start in room  0 .  Each room has a distinct number in  0, 1, 2, ..., N-1 , and each room may have some keys to access the next room.  Formally, each room  i  has a list of keys  rooms[i] , and each key  rooms[i][j]  is an integer in  [0, 1, ..., N-1]  where  N = rooms.length .  A key  rooms[i][j] = v  opens the room with number  v . Initially, all the rooms start locked (except for room  0 ).  You can walk back and forth between rooms freely. Return  true  if and only if you can enter every room. Example 1: Input: [[1],[2],[3],[]] Output: true Explanation: We start in room 0, and pick up key 1. We then go to room 1, and pick up key 2. We then go to room 2, and pick up key 3. We then go to room 3. Since we were able to go to every room, we return true. Example 2: Input: [[1,3],[3,0,1],[2],[0]] Output: false Expla...

Problem: Given a non-empty 2D array  grid  of 0's and 1's, an  island  is a group of  1 's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Count the number of  distinct  islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other. Example 1: 11000 11000 00011 00011 Given the above grid map, return  1 . Example 2: 11011 10000 00001 11011 Given the above grid map, return  3 . Notice that: 11 1 and 1 11 are considered different island shapes, because we do not consider reflection / rotation. Analysis: The tricky part is how to make same shape the same. We store the diff of each point in the shape by x-axial and y axial separately from the start to a list.  11000 11000 00011 00011 The coordinates of last three points of the first ...

Problem: Given a binary tree  where every node has a unique value , and a target key  k , find the value of the nearest leaf node to target  k  in the tree. Here,  nearest  to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a  leaf  if it has no children. In the following examples, the input tree is represented in flattened form row by row. The actual  root  tree given will be a TreeNode object. Example 1: Input: root = [1, 3, 2], k = 1 Diagram of binary tree: 1 / \ 3 2 Output: 2 (or 3) Explanation: Either 2 or 3 is the nearest leaf node to the target of 1. Example 2: Input: root = [1], k = 1 Output: 1 Explanation: The nearest leaf node is the root node itself. Example 3: Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 Diagram of binary tree: 1 / \ 2 3 /...

Problem: 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. Example 1: Input: 2, [[1,0]] Output: [0,1] Explanation:  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] . Example 2: Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation:  There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both cours...