三个月算法进阶--day90

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.max = []
        self.min = []

    def addNum(self, num: int) -> None:
        if len(self.max) > len(self.min):
            heapq.heappush(self.min, -heapq.heappushpop(self.max, num))
        else:
            heapq.heappush(self.max, -heapq.heappushpop(self.min, -num))


    def findMedian(self) -> float:
        if len(self.max) == len(self.min):
            return (self.max[0] - self.min[0]) / 2
        else:
            return self.max[0]

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def fast_sort(l, r):
            if l >= r:
                return
            i, j = l, r
            while i < j:
                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j:
                    j -= 1
                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j:
                    i += 1
                strs[i], strs[j] = strs[j],  strs[i]
            strs[i], strs[l] = strs[l],  strs[i]
            fast_sort(l, i-1)
            fast_sort(i+1, r)
        
        strs = [str(num) for num in nums]
        fast_sort(0, len(strs) - 1)
        return ''.join(strs)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        hashmap = {}
        head, res = 0, 0
        for tail in range(n):
            if s[tail] in hashmap:
                head = max(hashmap[s[tail]], head)
            hashmap[s[tail]] = tail + 1
            res = max(res, tail - head + 1)
        return res

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0] * n
        dp[0], a, b, c = 1, 0, 0, 0
        for i in range(1, n):
            dp[i] = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)
            if dp[i] == dp[a] * 2:
                a += 1
            if dp[i] == dp[b] * 3:
                b += 1
            if dp[i] == dp[c] * 5:
                c += 1
        return dp[-1]

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(l, r):
            if l >= r:
                return 0
            mid = (l + r) >> 1
            count = mergeSort(l, mid) + mergeSort(mid + 1, r)
            i, j = l, mid + 1
            pos = l 
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    tmp[pos] = nums[i]
                    i += 1
                    count += (j - (mid + 1))
                else:
                    tmp[pos] = nums[j]
                    j += 1
                pos += 1
            for k in range(i, mid + 1):
                tmp[pos] = nums[k]
                count += (j - (mid + 1))
                pos += 1
            for k in range(j, r + 1):
                tmp[pos] = nums[k]
                pos += 1
            nums[l:r+1] = tmp[l:r+1]
            return count
        
        n = len(nums)
        tmp = [0] * n 
        return mergeSort(0, n-1)

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & (-x)
    
    def query(self, x):
        ret = 0
        while x > 0:
            ret += self.tree[x]
            x -= BIT.lowbit(x)
        return ret

    def update(self, x):
        while x <= self.n:
            self.tree[x] += 1
            x += BIT.lowbit(x)

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        # 离散化
        tmp = sorted(nums)
        for i in range(n):
            nums[i] = bisect.bisect_left(tmp, nums[i]) + 1
        # 树状数组统计逆序对
        bit = BIT(n)
        ans = 0
        for i in range(n - 1, -1, -1):
            ans += bit.query(nums[i] - 1)
            bit.update(nums[i])
        return ans