[LeetCode][399. Evaluate Division] 4 Approaches: BFS, DFS, Floyd, Union Find

发表于 2022-07-31 更新于 2025-02-13 分类于 Leetcode 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

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

阅读全文 »

[Leetcode][34. Find First and Last Position of Element in Sorted Array] Binary Search Twice

发表于 2022-07-25 更新于 2025-02-13 分类于 Leetcode 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)\).

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

阅读全文 »

[Leetcode][240. Search a 2D Matrix II] 5 Approaches: BF, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis

发表于 2022-07-24 更新于 2025-02-14 分类于 Leetcode 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.

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

阅读全文 »

[LeetCode][118. Pascals Triangle] Math Intuition of Dynamic Programming: Shift One and Added

发表于 2022-07-19 更新于 2025-02-13 分类于 Leetcode 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.

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.

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 . 😉😃💗

[Leetcode] Problem Series of Jump Game

发表于 2022-07-10 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 4k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution Leetcode Jump Game Problems Series .

55. Jump Game

Brute Force

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.

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

DP

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

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.

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

阅读全文 »