首页 > itarticle > [leetcode] divide and conquer

[leetcode] divide and conquer

admin 11月 27, 2020 0

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
1
2
3
4
5
6
7
 
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class  {
    public double myPow(double x, int n) {
        
        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
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
 
# 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 :
        
    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. 
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
 
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)
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能