Algorithm

每日一刷-Minimum_Height_Trees

[每日一刷] (Minimum Height Trees)
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Example:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
  0
  |
  1
  / \
  2 3
return [1]

解题思路


本题个人的思路比较麻烦：首先对点0使用DFS，然后判断要求的点会在0点的哪个方向，然后再向那个方向移动
每次移动的时候都会有一部分的点的高度下降，而一部分的点的高度上升
代码稍微复杂了点，晚些时候再看看别人的思路好了-.-

Python:
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n)
"""
n = 11
edges = [[0,1],[0,2],[2,3],[0,4],[2,5],[5,6],[3,7],[6,8],[8,9],[9,10]]
class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1:
            return [0]
        d = {} # 存储相邻的点
        s = {} # 判断点是否访问过
        h = {} # 存储点之后的长度
        res = [0]
        for e in edges:
            v1, v2 = e[0], e[1]
            if d.get(v1, -1) == -1:
                d[v1] = []
            d[v1].append(v2)
            if d.get(v2, -1) == -1:
                d[v2] = []
            d[v2].append(v1)
            s[v1] = s[v2] = -1
        s[0] = 1
        self.DFS(0, d, s, h)
        s[0] = -1
        res = self.getMin(0, d, h, s, 0, h[0]-1, res)
        return res
    def DFS(self, n, d, s, h):
        m = 1 
        for v in d[n]:
            if s[v] != 1:
                s[v] = 1
                m = max(m, self.DFS(v, d, s, h)+1)
        h[n] = m
        return m
    def getMin(self, n, d, h, s, min, height, res):
        max1 = 0 # 高度减少的部分
        max2 = 0 # 高度增加的部分
        i = -1 # 下一个移动的点
        for v in d[n]:
            if s[v] != -1:
                s[v] = -1
                if h[v] > max1:
                    max2 = max1
                    max1 = h[v]
                    i = v
                elif h[v] > max2:
                    max2 = h[v]
        max2 = max(min, max2) # 会增加的最大高度
        if i == -1:
            return res
        temp = max(max1-1, max2+1) # 移动之后的高度
        if temp > height:
            return res
        elif temp == height:
            res.append(i)
        else: # 更新res
            res = []
            res.append(i)
            height = temp
        res = self.getMin(i, d, h, s, max2+1, height, res)
        return res


Algorithm

每日一刷-Burst_Balloon

[每日一刷] (Burst Balloon)


Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.

Example:
Given [3, 1, 5, 8]
Return 167

解题思路


看到maximum coins, 发现是一道求最优解的题，马上想到使用动态规划
本题的最优子结构是opt[i~j] = opt[i~k-1] + score[k] + opt[k+1~j], 其中k指的是最后一个爆破的气球的位置
本题的trick在于在算最优子结构的时候要在两边多算一个位置。例如算opt[1,2]的时候要将0, 3都算进去

代码虽然在leetcode上超时了，不过同样的做法使用JAVA和C++却可以通过，可能还是因为Python太慢了吧-.-

Python:

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
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^3)
"""
prices = [1, 2, 3, 0, 2]
class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.insert(0, 1)
        nums.append(1)
        # table[i][j] stores the optimal result of bursting balloon starts at i and the length is j
        # balloon starts from 1 to n
        table = [[0 for i in xrange(n-I+1)] for I in xrange(n+1)]
        table.insert(0, []) 
        for i in xrange(1, n+1):
            table[i][1] = nums[i-1] * nums[i] * nums[i+1]
        for l in xrange(2, n+1): # length from 2 to n
            for j in xrange(1, n-l+2): # balloon can starts from balloon 1 to balloon n-l+1
                maximum = 0
                for i in xrange(j, j+l): # balloon i is the last burst balloon
                    if i < j+l-1:
                      temp = table[j][i-j] + table[i+1][j+l-i-1] + nums[i]*nums[j-1]*nums[j+l]
                    else:
                      temp = table[j][i-j] + nums[i]*nums[j-1]*nums[j+l]
                    maximum = max(maximum, temp)
                table[j][l] = maximum
        return table[1][n]

Algorithm

线段树-SegmentTree

线段树的优点:
  O(logn)时间内，在一段区间中求最大最小值

线段树的特征:

  • 二叉树

  • 每个节点表示一个区间的最大值

  • 左儿子 = 平分后左区间，右儿子 = 平分后右区间

  • 不可增减节点(线段数结点总数需要在最开始就给定)

  • 空间复杂度: O(n)

    • 线段树的操作:

    线段树的查询: O(logn)

  • 查询的区间 和 线段树节点区间 相等 -> 直接返回

  • 查询的区间 被 线段树节点区间 包含-> 递归向下搜索左右子树

  • 查询的区间 和 线段树节点区间 不相交 -> 结束

  • 查询的区间 和 线段树节点区间 相交且不相等 -> 分裂查询区间

    • 线段树的建立: O(n)

  • 自上而下递归分裂

  • 自下而上回溯更新

    • 线段树的更新: O(logn)

  • 自上而下递归查询

  • 自下而上回溯更新

    • 问题特征:

  • 对区间求sum

  • 对区间求Max/Min

  • 对区间求Count

    • 构建形式

    1. 下标作为建立区间
    2. 值作为建立区间

    Python:

    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    #!/usr/bin/env 
    # -*- coding:utf-8 -*-
    class SegmentTree(object):
        def __init__(self, nums, s=None, e=None): # build
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            n = len(nums)
            if s == None:
                self.start, self.end = 0, n-1
            else:
                self.start, self.end = s, e
            self.mid = self.start + (self.end-self.start)/2
            self.left, self.right = None, None
            self.val = 0
            if self.end < self.start:
                return
            if self.end == self.start:
                self.val = nums[self.start]
            else:
                self.left = SegmentTree(nums, self.start, self.mid)
                self.right = SegmentTree(nums, self.mid+1, self.end)
                self.val = self.left.val + self.right.val
            
        def update(self, i, val): # modify
            """
            :type i: int
            :type val: int
            :rtype: int
            """
            if i == self.start and i == self.end:
                self.val = val
            else:
                if i <= self.mid:
                    self.left.update(i, val)
                else:
                    self.right.update(i, val)
                self.val = self.left.val + self.right.val
            
        def sumRange(self, i, j): # query
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            if i == self.start and j == self.end: # equal
                return self.val
            elif self.start > j or self.end < i: # not intersect
                return 0
            else: # intersect
                if i > self.mid: # all at the right sub tree
                    return self.right.sumRange(i, j)
                elif j <= self.mid: # all at the left sub tree
                    return self.left.sumRange(i, j)
                else: # some at the right & some at the left
                    return self.left.sumRange(i, self.mid) + self.right.sumRange(self.mid+1, j)