Long Luo's Life Notes

每一天都是奇迹

By Long Luo

This article is the solution Two Pointers: Sliding Window with HashSet of Problem 3. Longest Substring Without Repeating Characters.

Intuition

We can just simulate the process.

Using a Sliding Window from left to right of the string, and a HashSet to make every character is unique in the sliding window.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int lengthOfLongestSubstring(String s) {
if (s == null || s.length() <= 1) {
return s.length();
}

int ans = 0;
int len = s.length();
Set<Character> set = new HashSet<>();
int left = 0;
int right = 0;
while (right < len) {
while (right < len && !set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
}

ans = Math.max(ans, right - left);
set.remove(s.charAt(left));
left++;
}

return ans;
}
阅读全文 »

By Long Luo

This article is the solution The Recursive Algorithm with Detailed Image Explanation of Problem 21. Merge Two Sorted Lists.

Intuition

We can use Recursion to solve this problem.

The key points of Recursion are 22.

  1. How to terminate the recursion: Returns when either l1\texttt{l1} or l2\texttt{l2} is null\texttt{null}.

  2. What to do in the process: if l1.vall2.val\texttt{l1.val} \le \texttt{l2.val}, then point l1.next\texttt{l1.next} to the smaller of l1\texttt{l1} and l2\texttt{l2}.

If l1.vall2.val\texttt{l1.val} \le \texttt{l2.val}, we can choose the smaller node, such as l1\texttt{l1}. However, the linked list is not reached the end, we will continue to compare.

Now we are compare l1.next\texttt{l1.next} and l2\texttt{l2}. The l1.next\texttt{l1.next} and l2\texttt{l2} are processed in the recursive functions of the next layer.

We process such process and finally get the result.

阅读全文 »

By Long Luo

This article is the solution 4 Approaches: BFS, Memorization DFS, DP, Topo Sorting of Problem 329. Longest Increasing Path in a Matrix.

Here shows 4 Approaches to slove this problem: BFS, Memorization DFS, DP, Topological Sorting.

BFS

The simplest method that comes to my mind is BFS. We start search from each node, spread out like water, to see how far it can flood, and record the maximum flood path length of all nodes.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}

int row = matrix.length;
int col = matrix[0].length;
if (row == 1 && col == 1) {
return 1;
}

int max = 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
max = Math.max(max, bfs(matrix, i, j));
}
}

return max;
}

public int bfs(int[][] matrix, int x, int y) {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int ans = 0;
int row = matrix.length;
int col = matrix[0].length;

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});

while (!queue.isEmpty()) {
int size = queue.size();
ans++;

for (int i = 0; i < size; i++) {
int[] curPos = queue.poll();

for (int[] dir : dirs) {
int nextX = curPos[0] + dir[0];
int nextY = curPos[1] + dir[1];

if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
continue;
}

if (matrix[nextX][nextY] <= matrix[curPos[0]][curPos[1]]) {
continue;
}

queue.offer(new int[]{nextX, nextY});
}
}
}

return ans;
}
}

Analysis

  • Time Complexity: O(m2n2)O(m^2n^2).
  • Space Complexity: O(mn)O(mn).
阅读全文 »

By Long Luo

This article is the solution Traverse the Tree Level by Level: Standard BFS Solution of Problem 429. N-ary Tree Level Order Traversal.

Intuition

To traverse the tree level by level, we generally use breadth first search. In each round of breadth first search, we will traverse all nodes in the same layer.

For a typical BFS, we put the root node root\textit{root} into the queue fist. In each round of BFS, we first record the number of nodes in the current queue, which is the number of nodes in the upper level.

After that, we remove the front of the queue to take the nodes out of the queue in turn until we get all the nodes of the upper level.

When this round of traversal is completed, we can get all nodes of the current level. In this way, when the BFS is completed, we can get the results.

阅读全文 »

By Long Luo

This article is the solution Why Use BFS? Search Every Possible Path vs Search A Possible Path of Problem 1091. Shortest Path in Binary Matrix.

Intuition

  1. If we want to find a possible path, DFS will be more efficient. Because DFS will return a possible path if found, while it may not the shortest path.

  2. BFS will try every possible path at the same time.

  3. If we want to find the shortest of all possible paths, BFS is more efficient. It’s impossible for DFS to determine which is the shortest before trying all possible paths.

BFS

Use BFS to Level Traversal.

阅读全文 »
0%