Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution 5 Approaches: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis of Problem 240. Search a 2D Matrix II.

Here shows 5 Approaches to slove this problem: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis.

Intuition

This problem is like 74. Search a 2D Matrix, we can refer to the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis .

Brute Force

Just scan the \(\textit{matrix}\) to find the answer.

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
public static boolean searchMatrix_bf(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

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

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    for (int i = 0; i < row; i++) {
        if (matrix[i][col - 1] < target) {
            continue;
        }

        for (int j = 0; j < col; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(mn)\).
  • Space Complexity: \(O(1)\).
阅读全文 »

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

By Long Luo

This article is the solution Math Intuition of Dynamic Programming: Shift One and Added of Problem 118. Pascal’s Triangle .

Intuition

To generate a Pascal’s triangle is as the below animated git shows.

PascalTriangleAnimated2.gif

We can find that the Current Layer has only one element more than the Previous Layer. The elements in the Current Layer are equal to the elements in the Previous Layer, which was added one by one after being shifted one bit backward.

Therefore, we only need to deal with the Last Layer. We add a \(0\) at the beginning and the end of the Last Layer. Then sum the corresponding positions to get a New Layer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> oneRow = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                oneRow.add(1);
            } else {
                oneRow.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
        }

        ans.add(oneRow);
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(n^2)\)
  • Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions . 😉😃💗

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

By Long Luo

This article is the solution Leetcode Jump Game Problems Series .

55. Jump Game

55. Jump Game

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canJump(int[] nums) {
    int len = nums.length;
    boolean[] visited = new boolean[len];
    visited[0] = true;
    for (int i = 0; i < len; i++) {
        int steps = nums[i];
        if (visited[i] && steps > 0) {
            for (int j = 1; j <= steps && i + j < len; j++) {
                visited[i + j] = true;
            }
        }
    }

    return visited[len - 1];
}

Analysis

  • Time Complexity: \(O(n^2)\)
  • Space Complexity: \(O(n)\)

Greedy

Jump to the farest postion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canJump(int[] nums) {
    int len = nums.length;
    int maxIdx = 0;
    for (int i = 0; i < len; i++) {
        int steps = nums[i];
        if (maxIdx >= i) {
            maxIdx = Math.max(maxIdx, i + steps);
            if (maxIdx >= len - 1) {
                return true;
            }
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(1)\)

45. Jump Game II

45. Jump Game II

DP

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 jump_dp(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return 0;
    }

    int[] dp = new int[len];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    int minStep = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) {
        int num = nums[i];
        for (int j = 1; j <= num && i + j < len; j++) {
            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            if (i + j >= len - 1) {
                minStep = Math.min(minStep, dp[i] + 1);
                return minStep;
            }
        }
    }

    return minStep;
}

Analysis

  • Time Complexity: \(O(n^2)\)
  • Space Complexity: \(O(n)\)

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int jump(int[] nums) {
    int maxPosition = 0;
    int end = 0;
    int steps = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i]);
        if (i == end) {
            end = maxPosition;
            steps++;
        }
    }

    return steps;
}

Think reverse, from destination to origin position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int jump(int[] nums) {
    int ans = 0;
    int position = nums.length - 1;
    while (position > 0) {
        for (int i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                ans++;
                position = i;
                break;
            }
        }
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(1)\)
阅读全文 »

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

By Long Luo

This article is the solution 2 Approaches: HashSet and Two Pointers with Detailed Explanation of Problem 160. Intersection of Two Linked Lists.

Here shows 2 Approaches to slove this problem: HashSet and Two Pointers.

HashSet

We can use \(\texttt{HashSet}\) to store linked list nodes.

  1. Traverse the linked list \(\textit{headA}\), and add each node in the linked list \(\textit{headA}\) to the \(\texttt{HashSet}\);

  2. Traverse the linked list \(\textit{headB}\). For each node traversed, check whether the node is in the \(\texttt{HashSet}\).

    • If the current node is Not in the \(\texttt{HashSet}\), continue to traverse the next node;

    • If the current node is in the \(\texttt{HashSet}\), then all nodes starting from the current node are in the intersection of the two linked lists. Therefore, the first node traversed in the linked list \(\textit{headB}\) is the node intersected by the two linked lists.

    • If all the nodes in the linked list \(\textit{headB}\) are Not in the \(\texttt{HashSet}\), the two linked lists do not intersect and \(\textit{null}\) is returned.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static ListNode getIntersectionNode_hash(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }

    Set<ListNode> seen = new HashSet<>();
    while (headA != null) {
        seen.add(headA);
        headA = headA.next;
    }

    while (headB != null) {
        if (seen.contains(headB)) {
            return headB;
        }

        headB = headB.next;
    }

    return null;
}

Analysis

  • Time Complexity: \(O(m + n)\)
  • Space Complexity: \(O(m)\)
阅读全文 »

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

By Long Luo

This article is the solution 3 Approaches: BFS(Dijkstra), Binary Search, Union Find of Problem 1631. Path With Minimum Effort .

Here shows 3 Approaches to slove this problem: BFS(Dijkstra), Binary Search, Union Find.

BFS(Dijkstra)

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
public int minimumEffortPath(int[][] heights) {
    if (heights == null || heights.length == 0 || heights[0].length == 0) {
        return 0;
    }

    int rows = heights.length;
    int cols = heights[0].length;

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    PriorityQueue<int[]> pq = new PriorityQueue<>((edge1, edge2) -> edge1[2] - edge2[2]);

    pq.offer(new int[]{0, 0, 0});

    int[] dist = new int[rows * cols];
    Arrays.fill(dist, Integer.MAX_VALUE);

    dist[0] = 0;

    boolean[][] vis = new boolean[rows][cols];

    while (!pq.isEmpty()) {
        int[] edge = pq.poll();

        int x = edge[0];
        int y = edge[1];
        int d = edge[2];

        if (vis[x][y]) {
            continue;
        }

        if (x == rows - 1 && y == cols - 1) {
            break;
        }

        vis[x][y] = true;
        for (int[] dir : dirs) {
            int nextX = x + dir[0];
            int nextY = y + dir[1];

            if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols
                    && Math.max(d, Math.abs(heights[nextX][nextY] - heights[x][y])) < dist[nextX * cols + nextY]) {
                dist[nextX * cols + nextY] = Math.max(d, Math.abs(heights[nextX][nextY] - heights[x][y]));
                pq.offer(new int[]{nextX, nextY, dist[nextX * cols + nextY]});
            }
        }
    }

    return dist[rows * cols - 1];
}

Analysis

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