Algorithm

每日一刷-Count of Smaller Numbers After Self

[每日一刷] (Count of Smaller Numbers After Self)


You are given an integer array nums and you have to return a new counts array.
The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:
Given nums = [5, 2, 6, 1]
Return the array [2, 1, 1, 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
"""
时间复杂度 O(nlog(n))
"""
class SegmentTree(object):
    def __init__(self, d, nums, left, right):
        self.left, self.right = left, right
        self.val = 0
        self.mid = self.left + (self.right - self.left) / 2
        self.c1 = self.c2 = None
        if self.left == self.right:
            self.val = d[self.left]
        else:
            self.c1 = SegmentTree(d, nums, self.left, self.mid)
            self.c2 = SegmentTree(d, nums, self.mid+1, self.right)
            self.val = self.c1.val + self.c2.val
            
    def query(self, right):
        if right < self.left:
            return 0
        if self.right == self.left:
            return self.val
        if self.right == right:
            return self.val
        else:
            if right <= self.mid:
                return self.c1.query(right)
            else:
                return self.c1.query(self.mid) + self.c2.query(right)
    
    def modify(self, index):
        if self.left == self.right and self.left == index:
            self.val -= 1
        else:
            if index <= self.mid:
                self.c1.modify(index)
            else:
                self.c2.modify(index)
            self.val = self.c1.val + self.c2.val
        
class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if nums == []:
            return []
        left, right = min(nums), max(nums)
        for i in xrange(len(nums)): # deal with numbers below zero.
            nums[i] -= left
        right -= left
        d = [0 for i in xrange(right+1)]
        for i in nums:
            d[i] += 1
        tree = SegmentTree(d, nums, 0, right) # build segment tree.
        res = []
        for i in nums:
            temp = tree.query(i-1)
            res.append(temp)
            tree.modify(i) # modify the tree after each query
        return res

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