Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution 3 Approaches: BFS(Dijkstra), Binary Search, Union Find of Problem 858. Mirror Reflection .

Intuition

What if we assume the Ray Not Reflected and Keeps Going?

Consider that there is a mirrored world behind the mirror, we can expand the room behind the mirror. The ray has not been reflected and keep going cross the room.

As the image below shows, we can easily know which receptor will the ray will meet first.

Leetcode 858
阅读全文 »

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

By Long Luo

This article is the solution 3 Approaches: Sorting, Merge Sort, Binary Search of Problem 378. Kth Smallest Element in a Sorted Matrix .

Here shows 3 Approaches to slove this problem: Sorting, Merge Sort, Binary Search.

Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int[] array = new int[n * n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            array[i * n + j] = matrix[i][j];
        }
    }

    Arrays.sort(array);

    return array[k - 1];  
}

Analysis

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

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;

    PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);

    for (int i = 0; i < n; i++) {
        pq.offer(new int[]{matrix[i][0], i, 0});
    }

    for (int i = 0; i < k - 1; i++) {
        int[] cur = pq.poll();

        if (cur[2] != n - 1) {
            pq.offer(new int[]{matrix[cur[1]][cur[2] + 1], cur[1], cur[2] + 1});
        }
    }

    return pq.poll()[0];
}

Analysis

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

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

By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 62. Unique Paths .

Here shows 3 Approaches to slove this problem: Dynamic Programming, Recursion, Math.

Dynamic Programming

The equation is: \(f(i, j) = f(i−1, j) + f(i, j−1)\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1] + 1, dp[i][j - 1] + dp[i - 1][j]);
        }
    }

    return dp[m - 1][n - 1];
}

Analysis

  • Time Complexity: \(O(mn)\)
  • Space Complexity: \(O(mn)\)

Recursion

The DFS is top-down dynamic programming with memoization. If we do ordinary DFS without proper memoization, it will have a TLE error.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int uniquePaths(int m, int n) {
    return dfs(new HashMap<Pair, Integer>(), 0, 0, m, n);
}

private static int dfs(Map<Pair, Integer> cache, int r, int c, int rows, int cols) {
    Pair p = new Pair(r, c);

    if (cache.containsKey(p)) {
        return cache.get(p);
    }

    if (r == rows - 1 || c == cols - 1) {
        return 1;
    }
    
    cache.put(p, dfs(cache, r + 1, c, rows, cols) + dfs(cache, r, c + 1, rows, cols));
    return cache.get(p);
}

Analysis

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

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

By Long Luo

This article is the solution 4 Approaches: BFS, DFS, Floyd, Union Find of Problem 399. Evaluate Division.

Here shows 4 Approaches to slove this problem: BFS, DFS, Floyd, Union Find.

BFS

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// DFS time: O(n^2 * m) space: O(n)
public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = buildGraph(equations, values);

    int len = queries.size();
    double[] results = new double[len];

    for (int i = 0; i < len; i++) {
        String u = queries.get(i).get(0);
        String v = queries.get(i).get(1);

        if (!graph.containsKey(u) || !graph.containsKey(v)) {
            results[i] = -1.0;
            continue;
        }

        if (u.equals(v)) {
            results[i] = 1.0;
            continue;
        }

        results[i] = bfs(graph, u, v);
    }

    return results;
}


private static double bfs(Map<String, Map<String, Double>> graph, String u, String v) {
    if (graph.get(u).containsKey(v)) {
        return graph.get(u).get(v);
    }

    Set<String> visited = new HashSet<>();

    Queue<String[]> queue = new LinkedList<>();
    queue.offer(new String[]{u, String.valueOf(1.0)});

    visited.add(u);

    while (!queue.isEmpty()) {
        String[] cur = queue.poll();

        String curKey = cur[0];
        double curRatio = Double.parseDouble(cur[1]);

        if (curKey.equals(v)) {
            return curRatio;
        }

        Map<String, Double> curMap = graph.get(curKey);

        for (Map.Entry<String, Double> entry : curMap.entrySet()) {
            String nextKey = entry.getKey();
            double nextRatio = entry.getValue();

            if (visited.contains(nextKey)) {
                continue;
            }

            if (!graph.containsKey(nextKey)) {
                continue;
            }

            double product = curRatio * nextRatio;

            if (!graph.get(curKey).containsKey(nextKey)) {
                graph.get(curKey).put(nextKey, product);
            }

            visited.add(nextKey);
            queue.offer(new String[]{nextKey, String.valueOf(product)});
        }
    }

    return -1.0;
}

private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    Map<String, Map<String, Double>> graph = new HashMap<>();

    int len = equations.size();

    for (int i = 0; i < len; i++) {
        String u = equations.get(i).get(0);
        String v = equations.get(i).get(1);

        double w = values[i];

        graph.putIfAbsent(u, new HashMap<>());
        graph.get(u).put(v, w);

        graph.putIfAbsent(v, new HashMap<>());
        graph.get(v).put(u, 1.0 / w);
    }

    return graph;
}

Analysis

  • Time Complexity: \(O(n^2logn)\)
  • Space Complexity: \(O(n^2)\)
阅读全文 »

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

By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 34. Find First and Last Position of Element in Sorted Array.

Here shows 2 Approaches to slove this problem: Brute Force and Binary Search.

Brute Force

The easiest method is scan the array from left to right. Use two variables to record the index of the first and last element \(\textit{target}\). The time complexity is \(O(n)\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] searchRange(int[] nums, int target) {
    int[] ans = {-1, -1};
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target && ans[0] == -1) {
            ans[0] = i;
        } else if (nums[i] > target && ans[0] >= 0) {
            ans[1] = i - 1;
            return ans;
        }
    }

    if (ans[0] >= 0) {
        ans[1] = len - 1;
    }

    return ans;
}

Analysis

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

Binary Search

Since the array is sorted in ascending order, so we can binary search to speed up the search.

Considering the start and end positions of target, in fact, what we are looking for is “the first position in the array equal to target” (recorded as \(\textit{leftIdx}\) ) and “the first position greater than The position of target minus one” (recorded as \(\textit{rightIdx}\) ).

In binary search, looking for \(\textit{leftIdx}\) is to find the first index greater than or equal to target in the array, and looking for \(\textit{rightIdx}\) is to find the first index greater than target in the array index of target, then decrement the index by one.

Finally, since \(\textit{target}\) may not exist in the array, we need to re-check the two indices we got \(\textit{leftIdx}\) and \(\textit{rightIdx}\) to see if they meet the conditions, if so It returns \([\textit{leftIdx}, \textit{rightIdx}]\), if it does not match, it returns \([-1, -1]\).

阅读全文 »
0%