Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution Easy Backtracking Approach: Deduplicating and Pruning of Problem 39. Combination Sum.

Backtracking

It’s a typical Backtracking algorithm.

We can easily draw the tree below.

Tree Path

Take \(\textit{target} = 7\) as the root node and subtract the value of the edge while creating a child node.

Stop it when the value of the node is \(0\) or a negative number.

All paths from the root node to leaf node \(0\) are the results of the question.

Let’s coding.

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || target == 0) {
            return ans;
        }

        backtrack(ans, new ArrayList<>(), candidates, target);
        return ans;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int remain) {
        if (remain < 0) {
            return;
        }

        if (remain == 0) {
            res.add(new ArrayList<>(list));
            return;
        }

        int len = candidates.length;
        for (int i = 0; i < len; i++) {
            int num = candidates[i];
            list.add(num);
            backtrack(res, list, candidates, remain - num);
            list.remove(list.size() - 1);
        }
    }
}

Take \(\textit{target} = 7\) for example, \([[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]\) are the answer.

However, the correct answer is \([[7], [2, 2, 3]]\).

Since it requires that each solution is not in order, so the \([2, 2, 3]\) and \([2, 3, 2]\) are the same answer.

What’s problem?

When and how did we duplicate the path?

Why Duplicated?

At each node of the tree, all the candidates were searched and used, so there is a duplicate list.

Is it possible to deduplicate while searching?

Of course we can.

We have to search the elements in order while searching, since the output is not by order. We search from the certain position in the next round.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int start, int remain) {
    if (remain < 0) {
        return;
    }

    if (remain == 0) {
        res.add(new ArrayList<>(list));
        return;
    }

    int len = candidates.length;
    for (int i = start; i < len; i++) {
        int num = candidates[i];
        list.add(num);
        backtrack(res, list, candidates, i, remain - num);
        list.remove(list.size() - 1);
    }
}

By now we deduplicating it and complete the problem.

阅读全文 »

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

By Long Luo

This article is the solution 9 Approaches：Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers of Problem 287. Find the Duplicate Number.

Here are 9 approaches to solve this problem in Java, which is Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers.

Inspired by @user2670f and his solution [C++] 7 Different solutions to this problem (with relaxed constraints) , I added 3 more approaches.

Brute Force (2 Loops)

Since solve the problem without modifying the array nums and uses only constant extra space, we can use Brute Force to solve it.

It’s easy to use 2 loops to do it, but the time complexity is \(O(n^2)\), so it wouldn’t accepted as timeout.

1
2
3
4
5
6
7
8
9
10
11
12
13
// 2 Loops
public static int findDuplicate_2loops(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }

    return len;
}

Analysis

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

Count

Count the frequency of the num in the array.

With extra \(O(n)\) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
public static int findDuplicate(int[] nums) {
    int len = nums.length;
    int[] cnt = new int[len + 1];
    for (int i = 0; i < len; i++) {
        cnt[nums[i]]++;
        if (cnt[nums[i]] > 1) {
            return nums[i];
        }
    }

    return len;
}

Analysis

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

Hash

Using a \(\texttt{HashSet}\) to record the occurrence of each number.

With extra \(O(n)\) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
public static int findDuplicate_set(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (!set.add(nums[i])) {
            return nums[i];
        }
    }

    return len;
}

Analysis

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

Marking visited value within the array

Since all values of the array are between \([1 \dots n]\) and the array size is \(n+1\), while scanning the array from left to right, we set the \(\textit{nums}[n]\) to its negative value.

With extra \(O(1)\) space, with modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
// Visited
public static int findDuplicate_mark(int[] nums) {
    int len = nums.length;
    for (int num : nums) {
        int idx = Math.abs(num);
        if (nums[idx] < 0) {
            return idx;
        }
        nums[idx] = -nums[idx];
    }

    return len;
}

Analysis

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

Sort

Sorting the array first, then use a loop from \(1\) to \(n\).

With extra \(O(nlogn)\) space, modifying the input.

1
2
3
4
5
6
7
8
9
10
11
public static int findDuplicate_sort(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    for (int i = 1; i < len; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i];
        }
    }

    return len;
}

Analysis

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

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