Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution Image Explanation to Understand the Recursion Solution of Problem 114. Flatten Binary Tree to Linked List .

The Binary Tree Traversal Algorithms can be find here Tree Traversal Algorithms: PreOrder, InOrder and PostOrder .

We can use DFS to traversal the binary tree.

PreOrder + List

It’s easy to find that the flatten tree is the PreOrder of the tree. We can preorder the tree and store the TreeNodes in a List.

Traversal the list, make the current node as the preNode’s right node.

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
public void flatten(TreeNode root) {
    if (root == null) {
        return;
    }

    List<TreeNode> nodeList = new ArrayList<>();
    preOrder(root, nodeList);
    int n = nodeList.size();
    for (int i = 1; i < n; i++) {
        TreeNode preNode = nodeList.get(i - 1);
        TreeNode currNode = nodeList.get(i);
        preNode.left = null;
        preNode.right = currNode;
    }
}

public void preOrder(TreeNode root, List<TreeNode> nodeList) {
    if (root == null) {
        return;
    }

    nodeList.add(root);
    preOrder(root.left, nodeList);
    preOrder(root.right, nodeList);
}

We can also traversal the tree iteratively with a Stack:

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
public void flatten(TreeNode root) {
    if (root == null) {
        return;
    }

    List<TreeNode> nodeList = new ArrayList<>();
    Stack<TreeNode> stk = new Stack<>();
    while (root != null || !stk.empty()) {
        while (root != null) {
            nodeList.add(root);
            stk.push(root);
            root = root.left;
        }

        root = stk.pop();
        root = root.right;
    }

    int len = nodeList.size();
    for (int i = 1; i < len; i++) {
        TreeNode preNode = nodeList.get(i - 1);
        TreeNode currNode = nodeList.get(i);
        preNode.left = null;
        preNode.right = currNode;
    }
}

Analysis

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

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

By Long Luo

This article is the solution 3 Approaches: Tricky, Recursion and Base 3 Conversion of Problem 1780. Check if Number is a Sum of Powers of Three .

Here shows 3 Approaches to slove this problem: Tricky, Recursion and Base 3 Convertion.

Brute Froce

This method is tricky.

We can easy get a table that recorded all the numbers using \(\texttt{Math.power}(3, n)\) between \(1\) to \(10^7\).

Then scanning from the largest to the smallest, if find a value smaller or equal to \(n\), then subtract it from \(n\).

Repeat it until to \(0\) .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static boolean checkPowersOfThree(int n) {
    int[] nums = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969};
    int idx = nums.length - 1;
    while (idx >= 0 && n > 0) {
        while (idx >= 0 && nums[idx] > n) {
            idx--;
        }

        if (nums[idx] == n) {
            return true;
        }

        n -= nums[idx];
        idx--;
    }

    return false;
}

Analysis

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

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

By Long Luo

This article is the solution 2 Approaches: Sorting with Two Pointers and HashMap of Problem 350. Intersection of Two Arrays II.

Here shows 2 approaches for this problem: Sorting with Two Pointers and HashMap.

Sorting with Two Pointers

Sorting the two arrays first, then find the same elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] intersect_sort(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int len1 = nums1.length;
    int len2 = nums2.length;
    int[] ans = new int[Math.min(len1, len2)];
    int idx = 0;
    int p = 0;
    int q = 0;
    while (p < len1 && q < len2) {
        if (nums1[p] == nums2[q]) {
            ans[idx++] = nums1[p];
            p++;
            q++;
        } else if (nums1[p] < nums2[q]) {
            p++;
        } else {
            q++;
        }
    }

    return Arrays.copyOfRange(ans, 0, idx);
}

Analysis

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

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

By Long Luo

This article is the solution 2 Approaches: HashSet and Array of Problem 36. Valid Sudoku .

Here shows 2 Approaches to slove this problem: HashSet and Array.

HashSet

We can use a HashSet to record the number of occurrences of each number in each row, each column and each sub-box.

Traverse the Sudoku once, update the count in the HashMap during the traversal process, and determine whether the Sudoku board could be valid.

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
public static boolean isValidSudoku(char[][] board) {
    Map<Integer, Set<Integer>> rowMap = new HashMap<>();
    Map<Integer, Set<Integer>> colMap = new HashMap<>();
    for (int i = 0; i < 9; i++) {
        rowMap.put(i, new HashSet<>());
        colMap.put(i, new HashSet<>());
    }

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char ch = board[i][j];
            if (ch != '.') {
                int num = ch - '0';
                Set<Integer> rowSet = rowMap.get(i);
                if (!rowSet.add(num)) {
                    return false;
                }

                Set<Integer> colSet = colMap.get(j);
                if (!colSet.add(num)) {
                    return false;
                }
            }
        }
    }

    for (int subIdx = 0; subIdx < 9; subIdx++) {
        int subRow = 3 * (subIdx / 3);
        int subCol = 3 * (subIdx % 3);
        Set<Integer> grpSet = new HashSet<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char ch = board[subRow + i][subCol + j];
                if (ch != '.') {
                    int num = ch - '0';
                    if (!grpSet.add(num)) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

This is version 1.0 code.

In fact, we can only traversal once. The index of each sub-box is \(3 \times (i / 3) + j / 3\), so we can write better code.

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
public static boolean isValidSudoku_better(char[][] board) {
    Map<Integer, Set<Integer>> rowMap = new HashMap<>();
    Map<Integer, Set<Integer>> colMap = new HashMap<>();
    Map<Integer, Set<Integer>> subMap = new HashMap<>();

    for (int i = 0; i < 9; i++) {
        rowMap.put(i, new HashSet<>());
        colMap.put(i, new HashSet<>());
        subMap.put(i, new HashSet<>());
    }

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char ch = board[i][j];
            if (ch != '.') {
                int num = ch - '0';
                Set<Integer> rowSet = rowMap.get(i);
                if (!rowSet.add(num)) {
                    return false;
                }

                Set<Integer> colSet = colMap.get(j);
                if (!colSet.add(num)) {
                    return false;
                }

                int subIdx = 3 * (i / 3) + j / 3;
                Set<Integer> subSet = subMap.get(subIdx);
                if (!subSet.add(num)) {
                    return false;
                }
            }
        }
    }

    return true;
}

Analysis

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

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

By Long Luo

This article is the solution 3 Approaches: HashMap, Sorting and Counting of Problem 242. Valid Anagram .

Here shows 3 Approaches to slove this problem: HashMap, Sorting and Counting.

HashMap

\(\textit{t}\) is an anagram of \(\textit{s}\) which means that the characters in both strings appear in the same kind and number of times.

We can use two \(\texttt{HashMap}\) to store the characters and the number of times, then compare the keys and values.

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
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int len = s.length();

    Map<Character, Integer> sMap = new HashMap<>();
    Map<Character, Integer> tMap = new HashMap<>();

    for (int i = 0; i < len; i++) {
        sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
        tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
    }

    for (Map.Entry<Character, Integer> entry : sMap.entrySet()) {
        char ch = entry.getKey();
        int cnt = entry.getValue();
        if (!tMap.containsKey(ch) || cnt != tMap.get(ch)) {
            return false;
        }
    }

    return true;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(S)\) , \(S = 26\) .
阅读全文 »
0%