Algorithm

3_每日一刷-Range_Sum_Query_Mutable

[每日一刷] (Range Sum Query Mutable)
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.

Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

解题思路


看到对区间的查找和修改，可以判断这是一道非常典型的线段树的问题，直接用线段树求解即可。

然而在实际操作中还是遇到了一点点问题，主要是对python的类不够熟悉。简单做个总结好了

1.python类的构造函数只能有一个，但可以通过默认参数实现多态
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
class TestClass(object):
  val1 = 100 # 类变量，没有self，可以由类名直接调用，也可以由对象调用
  def __init__(self):
    self.val2 = 200 # 成员变量，可以由类的对象来调用，以self.的形式给出
   
  def fcn(self,val = 400):
    val3 = 300 # fcn函数内部的局部变量
    self.val4 = val # 不是成员变量，虽是以self.给出，但并没有在构造函数中初始化
    self.val5 = 500
 if __name__ == '__main__':
  inst = TestClass()
# 运行结果
inst1 = TestClass()
inst2 = TestClass()
 
print TestClass.val1 # 100
print inst1.val1   # 100
 
inst1.val1 = 1000 
print inst1.val1   # 1000
print TestClass.val1 # 100
 
TestClass.val1 =2000
print inst1.val1   # 1000
print TestClass.val1 # 2000
 
print inst2.val1   # 2000   
 
inst3 = TestClass() 
print inst3.val1   # 2000
# 类本身拥有自己的类变量（保存在内存），当一个TestClass类的对象被构造时，会将当前类变量拷贝一份给这个对象，
# 当前类变量的值是多少，这个对象拷贝得到的类变量的值就是多少；而且，通过对象来修改类变量，并不会影响其他对象的类变量的值，
# 因为大家都有各自的副本，更不会影响类本身所拥有的那个类变量的值；只有类自己才能改变类本身拥有的类变量的值。


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]