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