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%