Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution 2 Approaches: Backtrack and DP with Follow Up Analysis of Problem 377. Combination Sum IV .

Here shows 2 Approaches to slove this problem: Backtrack and Dynamic Programming.

Backtrack

The Backtrack will be a complete search and its time complexity will be \(O(2^n)\).

Surely it will be TLE!

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
class Solution {
    int total = 0;
    
    public int combinationSum4(int[] nums, int target) {
        total = 0;
        Arrays.sort(nums);
        backtrack(nums, target);
        return total;
    }

    private void backtrack(int[] nums, int remain) {
        if (remain == 0) {
            total++;
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > remain) {
                break;
            }

            backtrack(nums, remain - nums[i]);
        }
    }
}

Analysis

  • Time Complexity: \(O(2^n)\)
  • Space Complexity: \(O(\textit{target})\)
阅读全文 »

发表于 更新于 分类于 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)\)
阅读全文 »
0%