[剑指Offer] Day 30: Divide and Conquer

Task 1 - Q17. 打印从1到最大的n位数

Question

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def printNumbers(self, n: int) -> List[int]:
        if not n or n == 0: return None
        
        ans = []

        def dfs(pos, nums, numOfDigit):
            if pos == numOfDigit:
                ans.append(int(''.join(nums)))
                return 

            for i in range(0, 10):
                nums.append(str(i))
                dfs(pos+1, nums, numOfDigit) # Move to the next position
                nums.pop()
        
        for numOfDigit in range(1, n+1):
            for head in range(1, 10): # Add the first place ranging from 1 ~ 9
                nums = [str(head)]
                dfs(1, nums, numOfDigit)

        return ans

Explanation

If the num is very large till long type cannot handle it, we can only use String.
Time Complexity: O(10^N)
Space Complexity: O(N)

Task 2 - Q51. 数组中的逆序对

Question

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

Solution

 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


''' This solution exceeds the time limit
class Solution: 
    def reversePairs(self, nums: List[int]) -> int:
        def dfs(head, id):
            if id == len(nums):
                return 0

            cnt = 0
            for i in range(id, len(nums)):
                if head > nums[i]:
                    cnt += 1

            return cnt + dfs(nums[id], id+1)

        return dfs(nums[0], 1) if len(nums) > 1 else 0
'''

class Solution: 
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(nums, low, high):
            if low >= high: return 0 # Don't need to check if only one element in the partition

            mid = 0, low + (high - low) // 2
            ans = mergeSort(nums, low, mid) + mergeSort(nums, mid + 1, high)

            l, r = low, mid + 1
            tmp = []
            while l <= mid and r <= high:
                if nums[l] <= nums[r]:
                    tmp.append(nums[l])
                    l += 1
                else:
                    tmp.append(nums[r])
                    ans += mid - l + 1  # nums[l] ... nums[mid] > num[r]
                    r += 1
            
            while l <= mid:             # Append the rest elements if needed
                tmp.append(nums[l])
                l += 1

            while r <= high:
                tmp.append(nums[r])     # Append the rest elements if needed
                r += 1

            nums[low: high+1] = tmp
            return ans

        return mergeSort(nums, 0, len(nums)-1)

Explanation

When we merge the partitions, we can count the number of reversed pairs.

Time Complexity: O(N * log(N))
Space Complexity: O(N), i.e., recursion O(log(N)) + tmp O(N)