[Leetcode] Divide and Conquer

Divide and Conquer

Break a problem into roughly equal sized subproblems, solve seperately, and combine results.

Video: https://www.youtube.com/watch?v=2Rr2tW9zvRg

Two steps:

• Split problem to sub-problems
• Combine sub-results to final result

DAC(p):
    if small(P):
        solve(P)
    else:
        divide P into P1, P2, ...Pk
        Apply DAC(P1), DAC(P2),...
        Combine(DAC(P1), DAC(P2)...)

Topics

1. Binary Searxh
2. Finding Maximum and Minimum
3. Merge Sort
4. Quick Sort
5. Strassem’s Matrix Multiplication

Usually solved with recursion.

50. Pow(x, n)

Leetcode: https://leetcode.com/problems/powx-n/description/

• If use normal recursive solution, will raise stackOverFlow error
• Solution: Divide the pow into x^ (n/2) * x ^ (n/2)

class Solution {
    public double myPow(double x, int n) {
        // Edge Case
        if (n == 0) {
            return 1;
        }

        double temp = myPow(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            if (n > 0) {
                return temp * temp * x;
            } else {
                return temp * temp / x;
            }
        }
    }
}

241. Different Ways to Add Parentheses

[Solution]

• Iterate through the input string, if meet operator, split it to left half and right half
• Combine the computation results from left half and right half, append them to the result list

# Input: <str> number, +, -, *
# Output: <list<int>>: all possible combinations (allow repeating)

# Question:
#   - Is the number of parentheses set? 3 numbers -> 2 pair, 4 numbers -> 3 pair
#   - Seems not so relevant with the number of parentheses

# " 2 * 3 - 4 * 5 "
#         ^
# left - operator - right
# [2, 6, ..] left solutions, [4, 20, 5...] right solutions

class Solution:
        
    def diffWaysToCompute(self, s: 'str') -> 'List[int]':
        res = []
        if s.isdigit():
            return [int(s)]
        for i, ch in enumerate(s):
            if ch in "+-*":
                # Compute left and right side of the operator
                l = self.diffWaysToCompute(s[:i])
                r = self.diffWaysToCompute(s[i+1:])
                for numl in l:
                    for numr in r:
                        res.append(self.solve(numl, ch, numr))
        return res
                
    def solve(self, a, ope, b):
        if ope == '+':
            return int(a) + int(b)
        if ope == '-':
            return int(a) - int(b)
        if ope == '*':
            return int(a) * int(b)

222. Count Complete Tree Nodes

Leetcode: https://leetcode.com/problems/count-complete-tree-nodes/

Note:

1. Check whether the height of the left sub-tree equals to the right sub-tree
2. If equal, then the last node would be in the right subtree, and the number of nodes in the left sub-tree would be pow(2, height - 1) - 1, add one root node, would be pow(2, height - 1). Then we recursively calculate the number of nodes in the right sub-tree
3. If not equal, then the last node would be in the left sub-tree.

def countNodes(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
        return 0
    def height(node):
        if not node:
            return 0
        h = 0
        cur = node
        while cur:
            h += 1
            cur = cur.left
        return h
    h = height(root)
    
    if h < 0:
        return 0
    
    if h - 1 == height(root.right):
        return pow(2, h - 1) + self.countNodes(root.right)
    else:
        return pow(2, h - 2) + self.countNodes(root.left)

493. Reverse Pairs

Leetcode: https://leetcode.com/problems/reverse-pairs/

Greate reading: https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22

def reversePairs(self, nums: List[int]) -> int:
    # merge sort
    def merge(l, r):
        nonlocal nums
        
        if l >= r:
            return 0
        res = 0
        mid = (l + r) // 2
        res = merge(l, mid) + merge(mid + 1, r)
        
        merged = [0 for _ in range(r - l + 1)]
        cur = 0
        i, j = l, mid + 1
        p = mid + 1 # small half
        
        while i <= mid:
            while p <= r and nums[p] * 2 < nums[i]:
                p += 1
            res = res + p - (mid + 1)
            while j <= r and nums[j] <= nums[i]:
                merged[cur] = nums[j]
                j += 1
                cur += 1
            merged[cur] = nums[i]
            cur += 1
            i += 1
        while j <= r:
            merged[cur] = nums[j]
            cur += 1
            j += 1
            
        for i in range(l, r + 1):
            q = i - l
            nums[i] = merged[q]
        return res

    return merge(0, len(nums) - 1)

23. Merge k Sorted Lists

Leetcode: https://leetcode.com/problems/merge-k-sorted-lists/

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    # divide and conquer: merge 2 lists
    if not lists:
        return None
    def mergeTwoLists(a, b):
        i, j = a, b
        dummy = ListNode(0)
        h = dummy
        while i:
            while j and i.val > j.val:
                h.next = j
                h = h.next
                j = j.next
            h.next = i
            h = h.next
            i = i.next
        while j:
            h.next = j
            h = h.next
            j = j.next
        return dummy.next

    def mergeLists(l, r):
        if l == r:
            return lists[l]
        mid = (l + r) // 2
        left = mergeLists(l, mid)
        right = mergeLists(mid + 1, r)
        return mergeTwoLists(left, right)
    return mergeLists(0, len(lists) - 1)