Depth First Search (DFS) Part 2
695. Max Area of Island
Base Cases:
if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0)
return 0;
Recursion Formula:
grid[r][c] = 0;
return dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1) + 1;
Note: without seting this to 0, this dfs could invoke cyclic calling, which means the program will never ends, cause runtime error. When the area of the island is calculated from any grid on it, we don't need to calculate it again, the grids on it could all be set to 0 to avoid repeated calculation.
733 Flood Fill
Base Cases:
if (sr < 0 || sr >= image.size() || sc < 0 || sc >= image[0].size() || image[r][c] != oldColor)
return 0;
Recursion Formula:
image[sr][sc] = newColor;
DFS(image, sr - 1, sc, oldColor, newColor);
DFS(image, sr + 1, sc, oldColor, newColor);
DFS(image, sr, sc - 1, oldColor, newColor);
DFS(image, sr, sc + 1, oldColor, newColor);
494 Target Sum
(a) DFS Brutal Force Search
Use a helper function calcuate. The first parameter is the num array. The second parameter is index of the nums calculated so far. The third one is the sum calculated till the ith element. When we reach the end of array (index is (nums.size()) compare sum with S, if they are equal increase count.
(b) We could save the result using memoization to reduce time-complexity.
(c) Iterative DP (Don't understand the implementation so far). The state transit formula would be:
dp [i][j] = dp[i-1][[j + a[i]] + dp[i-1][[j - a[i]]
638 Shopping Offers
(1) Calculate the inner product of the price list of needs list as the intial total price
(2) For loop each offer in the special list and try to use it, if use it can cut down the total price
and doesn't exceeds the needs, then use it, otherwise skip it try next one
(3) The result will be the minimum value of all the success trial values in step 2.
690 Employee Importance
(a) For loop the vector<Employee*> input and set up a hash map from the employee id to the Employee object pointer. Use a helper function with two parameters: the map and the employee id
that we want to get its and its subordinates importance. In the helper function using DFS to calculate the total importance. Set the initial importance to its own importance. For each subordinates, DFS-recursively call the helper function to calculate its and its subordinates importance. Finally return the total summation of initial value and the recursively function call value, which is the desired importance value.
529 Minesweeper
(a) the click is on the mine, explode and done. Otherwise:
(b) Search 8 adjacent cells to count how many adjacent mines the current cell(x, y) has:
(b.1) if there is at least 1 adjacent mines, then set the cell to the number of adjacent mines
(b.2) Otherwise, there is no adjacent mine, then set the cell to Blank and recursively (DFS)
reveal the 8 adjacent cells.
547 Friend Circles
Define a n-demision (Matrix size) flag array to denote the friend circle that have been visited and initialize them to all false. Loop over the row of the matrix, if the flag is false then increase the counter and call DFS(M,visited, Row Index). In the DFS function. Set the visited flag to true. And for loop the elements in the current row. If the flag is not set and M[RowIndex][ColumnIndex] is 1 and RowIndex != ColumnIndex, recursively call DFS(M, visited, column Index). Finally return the counter.
394 Decode String
Pass a reference of the current char index (initialized to 0) and the input s to a helper function. In which we define a result string. While the index is less than the input string size and not the last char ']', if the current char is a digit calculate the repeated value in another loop, recursively call the DFS helper function to calculate the embedded string and return a temp string, add repeated copy of the temp string to the result . else the current char is a letter. Add the letter to the result. Finally, return the result string.
491. Increasing Subsequences. (need more understanding)
Pass over reference of vector<vector<int> > res, vector<int> seq and the vector<int> num as well as the start position to a DFS helper function. In which if seq.size() >= 2, push_back to the res array.
Define a hashSet (unordered_set<int> in C++) to avoid put repeated result into the result array.
Loop over the elements from start to the last in the array. if seq is empty or the current element nums[i] is greater or equal than the last element in the current seq and it is not in the hashSet yet. Then push_back the current value nums[i] into the seq and recursively call the helper function with increased start value by 1. After calling the helper function, do backtracking by pop_back the last element in the seq and insert the used pop_back() value into the hashTable to avoid repetition. Finally return the res array.
200. Number of Islands
Double for loop to iterate each element in the matrix if it is equal to char '1' then increase counter and call DFSMark to set the current grid to '0' and recursively call DFSMark to set all the horizontally and vertically connect grids that have value '1' to '0' (i.e.: count only 1 time for all the connect grids, for one island). In the end counter has the number of the islands.
542. 01 Matrix
Push all the 0 value coordinates in the matrix into the queue as the BFS start points. While the queue is not empty. Get the queue front element and explode the 4 direction for it to check whether there is a distance that has value greater than current element value plus 1, if so update it with current element value plus 1 and push that element into the queue to be used as a new start point for updating its neighbors. After updating all the neighbor distance in the queue, return the distance matrix as the result.
473 Matchsticks to Square
(a) if number array is empty or has less than 4 elements return false
(b) if total summation of all the numbers is not the multiple of 4, return false
Otherwise call the dfs helper function in which has 4 parameters: vector<int>& nums, vector<int>& sums, int index, int target (total sum divided by 4)
Base case: if all the elements tried and the 4 sides have exactly the same length then return true, otherwise return false.
Recursive formula:
try to add the current match length to each side, if failed continue to try next one, if one of them succeeded, recursively call the helper function with increased index value to try the next match in the callee level, if the callee succeeded in assigning all the matches equally, then we are able to make a square with all the matches. Otherwise, remove the current match from the current side and do backtracking to retry, if retry succeeds, still able to make a square, otherwise not able to make a square.
Note: the partition problem (or number partitioning) is the task of deciding whether a given multiset
133. Clone Graph
DFS:
The main difficulty here is how to avoid repeated clone a GraphNode. We use hash map to record already cloned Nodes. In my understanding the question assume all the nodes are connected.
Define a hash map from UndirectedGraphNode* to UndirectedGraphNode*.
Base case: if node is nullptr, return nullptr
if the node is not in the hash map yet. Clone the node and link the original node and the cloned node through hash map. For loop all the neighbors of the current node and recursively clone them and push_back them to the newly cloned node neighbor vector list.
Otherwise, if the node is in the hash map, return the already cloned node.
130 Surrounded Regions
Three steps to solve the problem:
Step 1: mark all the border '0' and its neighbors to '#'
Step 2: Convert all the remaining '0' to 'X'
Step 3: Convert all the '#' back to '0'
We want to know the area of each connected shape in the grid, then take the maximum of these.
If we are on a land square and explore every square connected to it 4-directionally (and recursively squares connected to those squares, and so on), then the total number of squares explored will be the area of that connected shape.
To ensure we don't count squares in a shape more than once, We could use
seen flag to keep track of squares we haven't visited before if the original grid cannot be changed. But if it can be changed, we could simple do this by setting visited grid[r][c] = 0 instead. It will also prevent us from counting the same shape more than once.if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0)
return 0;
Recursion Formula:
grid[r][c] = 0;
return dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1) + 1;
Note: without seting this to 0, this dfs could invoke cyclic calling, which means the program will never ends, cause runtime error. When the area of the island is calculated from any grid on it, we don't need to calculate it again, the grids on it could all be set to 0 to avoid repeated calculation.
733 Flood Fill
Base Cases:
if (sr < 0 || sr >= image.size() || sc < 0 || sc >= image[0].size() || image[r][c] != oldColor)
return 0;
Recursion Formula:
image[sr][sc] = newColor;
DFS(image, sr - 1, sc, oldColor, newColor);
DFS(image, sr + 1, sc, oldColor, newColor);
DFS(image, sr, sc - 1, oldColor, newColor);
DFS(image, sr, sc + 1, oldColor, newColor);
494 Target Sum
(a) DFS Brutal Force Search
Use a helper function calcuate. The first parameter is the num array. The second parameter is index of the nums calculated so far. The third one is the sum calculated till the ith element. When we reach the end of array (index is (nums.size()) compare sum with S, if they are equal increase count.
(b) We could save the result using memoization to reduce time-complexity.
(c) Iterative DP (Don't understand the implementation so far). The state transit formula would be:
dp [i][j] = dp[i-1][[j + a[i]] + dp[i-1][[j - a[i]]
638 Shopping Offers
(1) Calculate the inner product of the price list of needs list as the intial total price
(2) For loop each offer in the special list and try to use it, if use it can cut down the total price
and doesn't exceeds the needs, then use it, otherwise skip it try next one
(3) The result will be the minimum value of all the success trial values in step 2.
690 Employee Importance
(a) For loop the vector<Employee*> input and set up a hash map from the employee id to the Employee object pointer. Use a helper function with two parameters: the map and the employee id
that we want to get its and its subordinates importance. In the helper function using DFS to calculate the total importance. Set the initial importance to its own importance. For each subordinates, DFS-recursively call the helper function to calculate its and its subordinates importance. Finally return the total summation of initial value and the recursively function call value, which is the desired importance value.
529 Minesweeper
(a) the click is on the mine, explode and done. Otherwise:
(b) Search 8 adjacent cells to count how many adjacent mines the current cell(x, y) has:
(b.1) if there is at least 1 adjacent mines, then set the cell to the number of adjacent mines
(b.2) Otherwise, there is no adjacent mine, then set the cell to Blank and recursively (DFS)
reveal the 8 adjacent cells.
547 Friend Circles
Define a n-demision (Matrix size) flag array to denote the friend circle that have been visited and initialize them to all false. Loop over the row of the matrix, if the flag is false then increase the counter and call DFS(M,visited, Row Index). In the DFS function. Set the visited flag to true. And for loop the elements in the current row. If the flag is not set and M[RowIndex][ColumnIndex] is 1 and RowIndex != ColumnIndex, recursively call DFS(M, visited, column Index). Finally return the counter.
394 Decode String
Pass a reference of the current char index (initialized to 0) and the input s to a helper function. In which we define a result string. While the index is less than the input string size and not the last char ']', if the current char is a digit calculate the repeated value in another loop, recursively call the DFS helper function to calculate the embedded string and return a temp string, add repeated copy of the temp string to the result . else the current char is a letter. Add the letter to the result. Finally, return the result string.
491. Increasing Subsequences. (need more understanding)
Pass over reference of vector<vector<int> > res, vector<int> seq and the vector<int> num as well as the start position to a DFS helper function. In which if seq.size() >= 2, push_back to the res array.
Define a hashSet (unordered_set<int> in C++) to avoid put repeated result into the result array.
Loop over the elements from start to the last in the array. if seq is empty or the current element nums[i] is greater or equal than the last element in the current seq and it is not in the hashSet yet. Then push_back the current value nums[i] into the seq and recursively call the helper function with increased start value by 1. After calling the helper function, do backtracking by pop_back the last element in the seq and insert the used pop_back() value into the hashTable to avoid repetition. Finally return the res array.
200. Number of Islands
Double for loop to iterate each element in the matrix if it is equal to char '1' then increase counter and call DFSMark to set the current grid to '0' and recursively call DFSMark to set all the horizontally and vertically connect grids that have value '1' to '0' (i.e.: count only 1 time for all the connect grids, for one island). In the end counter has the number of the islands.
542. 01 Matrix
Push all the 0 value coordinates in the matrix into the queue as the BFS start points. While the queue is not empty. Get the queue front element and explode the 4 direction for it to check whether there is a distance that has value greater than current element value plus 1, if so update it with current element value plus 1 and push that element into the queue to be used as a new start point for updating its neighbors. After updating all the neighbor distance in the queue, return the distance matrix as the result.
473 Matchsticks to Square
(a) if number array is empty or has less than 4 elements return false
(b) if total summation of all the numbers is not the multiple of 4, return false
Otherwise call the dfs helper function in which has 4 parameters: vector<int>& nums, vector<int>& sums, int index, int target (total sum divided by 4)
Base case: if all the elements tried and the 4 sides have exactly the same length then return true, otherwise return false.
Recursive formula:
try to add the current match length to each side, if failed continue to try next one, if one of them succeeded, recursively call the helper function with increased index value to try the next match in the callee level, if the callee succeeded in assigning all the matches equally, then we are able to make a square with all the matches. Otherwise, remove the current match from the current side and do backtracking to retry, if retry succeeds, still able to make a square, otherwise not able to make a square.
Note: the partition problem (or number partitioning) is the task of deciding whether a given multiset
S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. The partition problem is NP-complete.133. Clone Graph
DFS:
The main difficulty here is how to avoid repeated clone a GraphNode. We use hash map to record already cloned Nodes. In my understanding the question assume all the nodes are connected.
Define a hash map from UndirectedGraphNode* to UndirectedGraphNode*.
Base case: if node is nullptr, return nullptr
if the node is not in the hash map yet. Clone the node and link the original node and the cloned node through hash map. For loop all the neighbors of the current node and recursively clone them and push_back them to the newly cloned node neighbor vector list.
Otherwise, if the node is in the hash map, return the already cloned node.
130 Surrounded Regions
Three steps to solve the problem:
Step 1: mark all the border '0' and its neighbors to '#'
Step 2: Convert all the remaining '0' to 'X'
Step 3: Convert all the '#' back to '0'
(1) Brute force O(4^N) : TLE
Base case:
if the index get out of the boundary in any direction: left, right, top bottom we have a valid path.
if (i < 0 || i >= m || j < 0 || j >= n) return 1;
Otherwise if it is still within the boundary but the given steps have used up, this is not a valid path.
if (N == 0) return 0
Otherwise, recursively explode 4 directions with decreased step value by 1.
return findPaths(m, n, N - 1, i - 1, j) + findPaths(m, n, N - 1, i + 1, j) + findPaths(m, n, N - 1, i, j - 1) + findPaths(m, n, N - 1, i, j + 1);
(2) Memoization
Same idea with (1), except use a 3 dimension memo[i][j][N] array to save the number of way to get out of the boundary starting at position with at most N steps. The time and space with be both
O(m*n*N)since we need to fill the array once with dimensions . Here, , refer to the number of rows and columns of the given grid respectively. refers to the total number of allowed moves.
Note if you use int type, you must do the mode for every DFS return value, otherwise the total summation may overflow cause weird wrong result. We use long type to avoid this kind of problem
From the internet: https://leetcode.com/problems/reconstruct-itinerary/discuss/78768
Note: multiset<string> maintain lexical order by default.
Note: multiset<string> maintain lexical order by default.
Explanation
First keep going forward until you get stuck. That’s a good main path already. Remaining tickets form cycles which are found on the way back and get merged into that main path. By writing down the path backwards when retreating from recursion, merging the cycles into the main path is easy - the end part of the path has already been written, the start part of the path hasn’t been written yet, so just write down the cycle now and then keep backwards-writing the path.
Example:
From JFK we first visit JFK -> A -> C -> D -> A. There we’re stuck, so we write down A as the end of the route and retreat back to D. There we see the unused ticket to B and follow it: D -> B -> C -> JFK -> D. Then we’re stuck again, retreat and write down the airports while doing so: Write down D before the already written A, then JFK before the D, etc. When we’re back from our cycle at D, the written route is D -> B -> C -> JFK -> D -> A. Then we retreat further along the original path, prepending C, A and finally JFK to the route, ending up with the route JFK -> A -> C -> D -> B -> C -> JFK -> D -> A.
417 Pacific Atlantic Water Flow
DFS/BFS
Like Surrounded Regions, We could do BFS or DFS search from the board flow and marked all their adjacent flow which has a bigger or equal height to be visitable from Pacific or Atlantic. Then in the end we could for loop both the Pacific and Atlantic visited flags to push these flow position that are visitable from both Pacific and Atlantic to the result array and return it.
First keep going forward until you get stuck. That’s a good main path already. Remaining tickets form cycles which are found on the way back and get merged into that main path. By writing down the path backwards when retreating from recursion, merging the cycles into the main path is easy - the end part of the path has already been written, the start part of the path hasn’t been written yet, so just write down the cycle now and then keep backwards-writing the path.
Example:
From JFK we first visit JFK -> A -> C -> D -> A. There we’re stuck, so we write down A as the end of the route and retreat back to D. There we see the unused ticket to B and follow it: D -> B -> C -> JFK -> D. Then we’re stuck again, retreat and write down the airports while doing so: Write down D before the already written A, then JFK before the D, etc. When we’re back from our cycle at D, the written route is D -> B -> C -> JFK -> D -> A. Then we retreat further along the original path, prepending C, A and finally JFK to the route, ending up with the route JFK -> A -> C -> D -> B -> C -> JFK -> D -> A.
417 Pacific Atlantic Water Flow
DFS/BFS
Like Surrounded Regions, We could do BFS or DFS search from the board flow and marked all their adjacent flow which has a bigger or equal height to be visitable from Pacific or Atlantic. Then in the end we could for loop both the Pacific and Atlantic visited flags to push these flow position that are visitable from both Pacific and Atlantic to the result array and return it.
Comments
Post a Comment