Algorithm

每日一刷-Additive-Number

[每日一刷] (Additive Number)


**Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:

“112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

“199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199**

解题思路


这题个人感觉应该没什么trick，只能硬算了，整个数列其实都是由最开始的两个数决定的，而最开始的两个数只能
通过枚举的方法来尝试符不符合条件了。这题的关键就是要仔细了吧-.-

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
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^2)
"""
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        n = len(num)
        s1 = 0  
        len1, len2 = 1, 1
        while len1 <= n/2:
            s2 = s1 + len1
            len2 = 1
            while len2 <= n/2:
                num1 = int(num[s1:s1+len1])
                num2 = int(num[s2:s2+len2])
                if s2+len2 == n:
                    break
                if self.isAdditive(num, num1, num2, s2+len2, n):
                    return True
                if num[s2] == '0':
                    break;
                len2 += 1
            if num[s1] == '0':
                break
            len1 += 1
        return False
    def isAdditive(self, num, num1, num2, pos, end):
        if pos == end:
            return True
        target = num1 + num2
        i = 1 # target位数
        while target / 10**i != 0:
            i += 1
        num3 = int(num[pos:pos+i])
        if target == num3:
            return self.isAdditive(num, num2, num3, pos+i, end)
        else:
            return 0

Algorithm

每日一刷-Super-Ugly-Number

[每日一刷] (Super Ugly Number)


Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.
For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Example:
Given: primes = [2, 7, 13, 19], n = 10
Return 26

解题思路


这题就是不断的选下一个最小的质数，因此可以想到用heap。
既然是一个Super Ugly的题，就用一个Super Ugly的做法吧- -

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
#!/usr/bin/env 
# -*- coding:utf-8 -*-
from heapq import *
class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        if n == 1:
            return 1
        length = len(primes)
        idxs = [ 0 for i in xrange(length) ]
        minLists = []
        h = []
        for i in xrange(length):
            heappush(h, [primes[i], i])
        for i in xrange(2, n):
            tup = heappop(h) # 第i-1大的数
            num, index = tup[0], tup[1]  # 第i-1大的数和index
            minLists.append([num, index])
            idx = idxs[index]
            while minLists[idx][1] > index:
                idx += 1
            nextNum = primes[index] * minLists[idx][0]
            idxs[index] = idx + 1
            heappush(h, [nextNum, index])
        return h[0][0]

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类的对象被构造时，会将当前类变量拷贝一份给这个对象，
# 当前类变量的值是多少，这个对象拷贝得到的类变量的值就是多少；而且，通过对象来修改类变量，并不会影响其他对象的类变量的值，
# 因为大家都有各自的副本，更不会影响类本身所拥有的那个类变量的值；只有类自己才能改变类本身拥有的类变量的值。