Algorithm

每日一刷-Range-Sum-Query-2D-Immutable

[每日一刷] (Range Sum Query 2D Immutable)


Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

解题思路


这题思路和一维的时候一致，可以使用动态规划也可以使用线段树。就这题来说使用动态规划会简单很多。
思路就是用dp[i][j]表示从(0, 0)到(i, j)的和

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
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 Query O(1), Build O(n^2)
"""
class NumMatrix(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :type matrix: List[List[int]]
        """
        if matrix == []:
            return
        r = len(matrix)
        c = len(matrix[0])
        self.dp = [[0 for i in xrange(c+1)] for j in xrange(r+1)]
        for i in xrange(1, r+1):
            for j in xrange(1, c+1):
                self.dp[i][j] = self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1] + matrix[i-1][j-1]
    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]

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]