Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 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\) .
阅读全文 »

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

By Frank Luo

The Tree Traversal Algorithms are used to traversal the tree including Binary Tree and N-ary Tree.

  1. Binary Tree Traversal

94. Binary Tree Inorder Traversal 144. Binary Tree Preorder Traversal 145. Binary Tree Postorder Traversal

  1. N-ary Tree Traversal

589. N-ary Tree Preorder Traversal 590. N-ary Tree Postorder Traversal

Binary Tree

PreOrder

Algorithm Preorder(tree) 1. Visit the root; 2. Traverse the left subtree, i.e., call Preorder(left-subtree); 3. Traverse the right subtree, i.e., call Preorder(right-subtree).

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    preOrder(root, ans);
    return ans;
}

public void preOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    list.add(root.val);
    preOrder(root.left, list);
    preOrder(root.right, list);
}

Analysis

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

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            ans.add(root.val);
            root = root.left;
        }
        
        root = stack.pop();
        root = root.right;
    }
    
    return ans;
}

Analysis

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

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

By Long Luo

This article is the solution The XOR Cheat Sheet and Bit Manipulation with Easy Detailed Explanation of Problem 136. Single Number .

To solve this problem, there are serval solutions. However, the best method is using XOR.

we have this XOR cheatsheet:

1
2
3
4
5
1.  Zero Law: a XOR a = 0
2.  a XOR 0 = a
3.  a XOR b = b XOR a
4.  a XOR b XOR c = a XOR (b XOR c) = (a XOR b) XOR c
5.  a XOR b XOR a = b

According to the Zero law, all the numbers appears twice will be \(0\), and the single one will remain.

So code as follow:

阅读全文 »
0%