第一章 绪论

MAX_VAL, MIN_VAL = (1 << 31) - 1, -(1 << 31)

class Solution:
    def reverse(self, x: int) -> int:

        x, sign = (x, 1) if x >= 0 else (-x, -1)

        res = 0
        while x:
            q, r = divmod(x, 10)
            res = res * 10 + r
            x = q

        res *= sign

        return res if MIN_VAL <= res <= MAX_VAL else 0
        

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)

        res = []
        c = 1
        
        for i in range(n - 1, -1, -1):
            c, d = divmod(digits[i] + c, 10)
            res.append(d)
        
        if c == 1:
            res.append(1)

        return res[::-1]

# begin of merge sort
def merge(arr: List[List[int]], p: int, q: int, r: int) -> None:
    left = arr[p: q + 1]
    right = arr[q + 1: r + 1]

    left.append([inf, inf])
    right.append([inf, inf])
    
    i, j = 0, 0
    for k in range(p, r + 1):
        if left[i][0] <= right[j][0]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1

def merge_sort(arr: List[List[int]], p: int, r: int) -> None:
    if p < r:
        q = (p + r) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)
    
def msort(arr: List[List[int]]):
    merge_sort(arr, 0, len(arr) - 1)

# end of merge sort


# begin of quick sort
def partition(arr: List[List[int]], p: int, r: int) -> int:
    pivot = arr[r][0]
    i = p - 1

    for j in range(p, r):
        if arr[j][0] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[r] = arr[r], arr[i + 1]

    return i + 1

def randomized_partition(arr: List[List[int]], p: int, r: int) -> int:
    i = random.randint(p, r)
    arr[i], arr[r] = arr[r], arr[i]
    return partition(arr, p, r)

def quick_sort(arr: List[List[int]], p: int, r: int) -> None:
    if p < r:
        q = partition(arr, p, r)
        quick_sort(arr, p, q - 1)
        quick_sort(arr, q + 1, r)

def randomized_quick_sort(arr: List[List[int]], p: int, r: int) -> int:
    if p < r:
        q = randomized_partition(arr, p, r)
        randomized_quick_sort(arr, p, q - 1)
        randomized_quick_sort(arr, q + 1, r)

def qsort(arr: List[List[int]]) -> int:
    # quick_sort(arr, 0, len(arr) - 1)
    randomized_quick_sort(arr, 0, len(arr) - 1)

# end of quick sort


# begin of user sort
def user_sort(arr: List[List[int]], mode='merge'):
    if mode == 'merge':
        msort(arr)
        
    elif mode == 'quick':
        qsort(arr)
    else:
        print(f'{mode} sort is not defined!!!')

# end of user sort


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        num2idx = [[num, idx] for idx, num in enumerate(nums)]

        # user_sort(num2idx, mode='quick')
        user_sort(num2idx)

        res = []

        for i in range(n):
            x = target - num2idx[i][0]

            lo, hi = i + 1, n - 1
            while lo <= hi:
                mid = lo + (hi - lo) // 2
                if num2idx[mid][0] == x:
                    res = [num2idx[i][1], num2idx[mid][1]]
                    break
                elif num2idx[mid][0] > x:
                    hi = mid - 1
                else:
                    lo = mid + 1

        return res

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)

        # prefix[i]: i 前缀和，sum(arr[0...i])
        prefix = [0] * n
        prefix[0] = arr[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + arr[i]

        res = 0
        for i in range(n):
            j = i
            while j < n:
                res += prefix[j] - prefix[i] + arr[i]
                j += 2

        return res