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)\)

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

By Long Luo

This article is the solution Pattern of Data Pairs Problem: Sorting First then Greedy of Problem 406. Queue Reconstruction by Height .

Intuition

The Data Pair \(\textit{people}[h, k]\), \(h_i\) represents the i-th person of height \(h_i\), \(k_i\) represents the other people in front who have a height greater than or equal to \(h_i\).

Pattern:

When face such kind of problem with Data Pair, sorting first will simplify the problem.

Usually, we will sort the first element in ascending order, while the second element in descending order, or sort the first element in descending order with the second element in ascending order.

Greedy

We sort the \(\textit{people}\) pairs first by \(height\) in descending order, and \(k\) in ascending order.

According to the descending order of \(height\), for each person, the number of people before him is the number of people whose height is greater than or equal to him.

According to the ascending order of \(k\), because the \(k\) is increase later, which can reduce the number of insert operations.

Take the example:

After sorting:

1

[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]

Insert one by one:

1
2
3
4
5
6

[7,0]
[7,0], [7,1]
[7,0], [6,1], [7,1]
[5,0], [7,0], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

By Long Luo

This article is the solution 6 Approaches: Cycle, API, Divide and Conquer, Low Bit, Bit Set, Recursion of Problem 191. Number of 1 Bits.

Here shows 6 Approaches to slove this problem: Cycle, Divide and Conquer, LowBit, Bit Set, Recursion.

Brute Force: Cycle

Juse use a Loop to check if each bit of the binary bits of the given integer \(n\) is \(1\).

1
2
3
4
5
6
7
8
9
10
11
12

public int hammingWeight(int n) {
    int cnt = 0;
    for (int i = 0; i < 32 && n != 0; i++) {
        if ((n & 0x01) == 1) {
            cnt++;
        }

        n = n >>> 1;
    }

    return cnt;
}

Analysis

• Time Complexity: \(O(k)\).
• Space Complexity: \(O(1)\).

API

Use API: \(\texttt{Integer.bitCount}\).

1
2
3

public static int hammingWeight(int n) {
    return Integer.bitCount(n);
}

Analysis

• Time Complexity: \(O(logk)\).
• Space Complexity: \(O(1)\).

By Long Luo

This article is the solution 3 Approaches: Sorting, Priority Queue and Divide and Conquer of Problem 215. Kth Largest Element in an Array.

Here shows 3 Approaches to slove this problem: Sorting, Priority Queue, Divide and Conquer.

Sorting

Sort the array first, then the \(k-th\) element of the array.

1
2
3
4
5
6
7
8
9

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    Arrays.sort(nums);
    return nums[len - k];
}

Analysis

• Time Complexity: \(O(n \log n)\).
• Space Complexity: \(O(\log n)\).