[LeetCode][117. Populating Next Right Pointers in Each Node II] 3 Approaches: BFS, BFS + LinkedList, Recursion

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

By Long Luo

This article is the solution 3 Approaches: BFS, BFS + LinkedList, Recursion of Problem 117. Populating Next Right Pointers in Each Node II .

Here shows 3 Approaches to slove this problem: BFS, BFS + LinkedList, Recursion.

BFS

Use BFS to level traversal, a List to store the Nodes of each level.

public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Node> levelNodes = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node curNode = queue.poll();
            levelNodes.add(curNode);
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }

        for (int i = 0; i < levelNodes.size() - 1; i++) {
            Node node = levelNodes.get(i);
            node.next = levelNodes.get(i + 1);
        }
    }

    return root;
}

In fact, we just need a Node to store the Previous Node.

public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelCount = queue.size();
        Node prev = null;
        for (int i = 0; i < levelCount; i++) {
            Node curNode = queue.poll();

            if (prev != null) {
                prev.next = curNode;
            }

            prev = curNode;

            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
    }

    return root;
}

Analysis

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

阅读全文 »

[LeetCode][1641. Count Sorted Vowel Strings] Image Explanation: Distributing N Balls into 5 Boxes, Some Boxes May Be Empty

发表于 2022-05-11 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 955 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Image Explanation: Distributing N Balls into 5 Boxes, Some Boxes May Be Empty of Problem 1641. Count Sorted Vowel Strings.

Math

Every vowel string is start by \(a, e, i, o, u\), and there are \(N\) strings.

How to distribute \(N\) strings into the \(5\) boxes, some boxes may be empty?

Imaging that there are \(N\) balls, we have to put them in to \(5\) boxes represented by the five vowels, as the picture shows.

Once the number of characters in each box were fixed, the string is fixed.

Therefore, how many ways are there to put \(N\) balls in \(5\) boxes, and the boxes can be empty?

阅读全文 »

[LeetCode][216. Combination Sum III] 2 Approaches: Backtracking and Bit Mask

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

By Long Luo

This article is the solution 2 Approaches: Backtracking and Bit Mask of Problem 216. Combination Sum III .

Here shows 2 Approaches to slove this problem: Backtracking and Bit Mask.

Backtracking

A very easy backtracking solution. Just refer to 17. Letter Combinations of a Phone Number.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();

    // corner cases
    if (k <= 0 || n <= 0 || k > n) {
        return ans;
    }

    // The upper bound of n: [9, 8, ... , (9 - k + 1)], sum is (19 - k) * k / 2
    if (n > (19 - k) * k / 2) {
        return ans;
    }

    backtrack(ans, new ArrayList<>(), 1, k, n);
    return ans;
}

public void backtrack(List<List<Integer>> res, List<Integer> path, int start, int k, int target) {
    if (k < 0 || target < 0) {
        return;
    }

    if (k == 0 && target == 0) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i <= 9; i++) {
        // trim 
        if (i > target) {
            break;
        }
			
        // trim
        if (target - i == 0 && k > 1) {
            break;
        }

        path.add(i);
        backtrack(res, path, i + 1, k - 1, target - i);
        path.remove(path.size() - 1);
    }
}

Analysis

Time Complexity: \(O({M \choose k} \times k)\), \(M\) is the size of combinations, \(M = 9\), the total combinations is \(M \choose k\).
Space Complexity: \(O(M + k)\), size of \(path\) is \(k\), the recursion stack is \(O(M)\).

阅读全文 »

[LeetCode][17. Letter Combinations of a Phone Number] 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explanation

发表于 2022-05-09 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 5.3k 阅读时长 ≈ 5 分钟

By Long Luo

This article is the solution 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explanation of Problem 17. Letter Combinations of a Phone Number .

Here shows 4 Approaches to slove this problem: Brute Force, Backtracking, BFS and Queue.

Intuition

Take the \(234\) for example, look at the tree:

Brute Froce(4 Loops)

Since the \(\textit{digits.length} <= 4\), we can just use the brute force approach \(4\) Loops to search all the possible combinations.

The total states is \(A(n,n)=A(4,4)=4!\). We have to enumerate all these states to get the answer.

public static List<String> letterCombinations_4Loops(String digits) {
    List<String> ans = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return ans;
    }

    String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int len = digits.length();
    int[] digitsArr = new int[len];
    for (int i = 0; i < len; i++) {
        digitsArr[i] = digits.charAt(i) - '0';
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append("a");
    }

    for (int i = 0; i < letters[digitsArr[0] - 2].length(); i++) {
        sb.replace(0, 1, letters[digitsArr[0] - 2].charAt(i) + "");
        if (len == 1) {
            ans.add(sb.substring(0, 1));
        }

        for (int j = 0; len >= 2 && j < letters[digitsArr[1] - 2].length(); j++) {
            sb.replace(1, 2, letters[digitsArr[1] - 2].charAt(j) + "");
            if (len == 2) {
                ans.add(sb.toString());
            }

            for (int k = 0; len >= 3 && k < letters[digitsArr[2] - 2].length(); k++) {
                sb.replace(2, 3, letters[digitsArr[2] - 2].charAt(k) + "");
                if (len == 3) {
                    ans.add(sb.toString());
                }

                for (int l = 0; len >= 4 && l < letters[digitsArr[3] - 2].length(); l++) {
                    sb.replace(3, 4, letters[digitsArr[3] - 2].charAt(l) + "");
                    ans.add(sb.toString());
                }
            }
        }
    }

    return ans;
}

Analysis

Time Complexity: \(O(4^N)\)
Space Complexity: \(O(N)\)

Backtracking

For the first number, there are \(3\) options, and \(3\) options for the second number and so on.

The combinations from the first to the last will expand into a recursive tree.

When the index reaches the end of digits, we get a combination, and add it to the result, end the current recursion. Finally we will get all the combinations.

阅读全文 »

[LeetCode][341. Flatten Nested List Iterator] 2 Approaches: DFS and Iteration(Using Stack)

发表于 2022-05-08 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 2.4k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution 2 Approaches: DFS and Iteration(Using Stack) of Problem 341. Flatten Nested List Iterator.

Here are 2 approaches to solve this problem in Java, DFS and Iteration approach.

DFS

We can store all the integers in an array, just traversing the array.

public class NestedIterator implements Iterator<Integer> {
    List<Integer> numList;
    int idx;

    public NestedIterator(List<NestedInteger> nestedList) {
        numList = new ArrayList<>();
        idx = 0;
        dfs(nestedList);
    }

    private void dfs(List<NestedInteger> nestedList) {
        if (nestedList == null) {
            return;
        }

        for (int i = idx; i < nestedList.size(); i++) {
            NestedInteger nested = nestedList.get(i);
            if (nested.isInteger()) {
                numList.add(nested.getInteger());
            } else {
                dfs(nested.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return numList.get(idx++);
    }

    @Override
    public boolean hasNext() {
        if (idx < numList.size()) {
            return true;
        }

        return false;
    }
}

Analysis

Time Complexity:
- \(\texttt{NestedIterator}\): \(O(n)\).
- \(\texttt{next()}\): \(O(1)\)
- \(\texttt{hasNext()}\): \(O(1)\)
Space Complexity: \(O(n)\).

阅读全文 »