Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 6.2k 阅读时长 ≈ 6 分钟

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(m^2n^2)\).
  • Space Complexity: \(O(mn)\).
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

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 \(\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.

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 2 分钟

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.

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution 2 Approaches: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal) of Problem 1302. Deepest Leaves Sum.

Here shows 2 approaches to slove this problem: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal).

BFS

To traverse the tree level by level, we generally use breadth first search. You can refer to this article Traverse the Tree Level by Level: Standard BFS 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
public int deepestLeavesSum(TreeNode root) {
    if (root == null) {
        return root.val;
    }

    int sum = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelCount = queue.size();
        boolean isDeepest = true;
        sum = 0;
        for (int i = 0; i < levelCount; i++) {
            TreeNode curNode = queue.poll();

            if (curNode.left == null && curNode.right == null) {
                sum += curNode.val;
            }

            if (curNode.left != null) {
                isDeepest = false;
                queue.offer(curNode.left);
            }

            if (curNode.right != null) {
                isDeepest = false;
                queue.offer(curNode.right);
            }
        }

        if (isDeepest && queue.isEmpty()) {
            return sum;
        }
    }

    return sum;
}
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution 3 Approaches: BFS, BFS + LinkedList, Recursion of Problem 117. Populating Next Right Pointers in Each Node II.

Here shows 3 Approaches to slove this problem: BFS, BFS + LinkedList, Recursion.

BFS

Use BFS to level traversal, a List to store the Nodes of each level.

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
public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Node> levelNodes = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node curNode = queue.poll();
            levelNodes.add(curNode);
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }

        for (int i = 0; i < levelNodes.size() - 1; i++) {
            Node node = levelNodes.get(i);
            node.next = levelNodes.get(i + 1);
        }
    }

    return root;
}

In fact, we just need a Node to store the Previous Node.

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
public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelCount = queue.size();
        Node prev = null;
        for (int i = 0; i < levelCount; i++) {
            Node curNode = queue.poll();

            if (prev != null) {
                prev.next = curNode;
            }

            prev = curNode;

            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
    }

    return root;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(n)\).
阅读全文 »
0%