Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 947 阅读时长 ≈ 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.

1621

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?

阅读全文 »

发表于 更新于 分类于 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.

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
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)\).
阅读全文 »

发表于 更新于 分类于 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:

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.

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

阅读全文 »

发表于 更新于 分类于 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.

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
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)\).
阅读全文 »

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

By Long Luo

This article is the solution 4 Approaches: BF O(n^3), BF O(n^2), TreeMap, Monotonic Stack of Problem 456. 132 Pattern.

Here are 4 approaches to solve this problem in Java: BF \(O(n^3)\), BF \(O(n^2)\), TreeMap, Monotonic Stack.

BF O(n^3)

It’s easy to use 3 loops to find \(3\) elements which is \(132\) pattern, but the time complexity is \(O(n^3)\), so it wouldn’t accepted as TLE!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean find132pattern_bf(int[] nums) {
    int len = nums.length;
    if (len < 3) {
        return false;
    }

    for (int i = 0; i < len - 2; i++) {
        for (int j = i + 1; j < len - 1; j++) {
            for (int k = j + 1; k < len; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(n^3)\).
  • Space Complexity: \(O(1)\).

BF O(n^2)

Noticed that \(\textit{nums}[j]\) is the peak of the \(3\) elements, suppose the current element is \(\textit{nums}[j]\), we have to find the element \(\textit{nums}[k]\) that is smaller than \(\textit{nums}[j]\) after \(j\), and the element \(\textit{nums}[i]\) that is smaller than \(\textit{nums}[k]\) before \(j\).

  1. Scan left from \(j\) to \(0\), \(0 \le i \lt j\), whether there is \(\textit{nums}[i] < \textit{nums}[j]\), update the mininum \(\textit{leftMin}\);

  2. Scan right from \(j\) to the end, \(j + 1 \le k \lt len\), whether there is \(\textit{nums}[k] < \textit{nums}[j]\), update the maxinum \(\textit{rightMax}\);

  3. If exists and \(\textit{leftMin} < \textit{rightMax}\), return true.

阅读全文 »
0%