面试题 16.16. 部分排序

面试题 16.16. 部分排序

class Solution:
    def subSort(self, array: List[int]) -> List[int]:
        if not array:
            return [-1, -1]
        num_max = array[0]
        max_index = -1
        min_ = float('inf')
        for i in range(1, len(array)):
            if array[i] > num_max:
                num_max = array[i]
            if array[i] < array[i - 1] or array[i] < num_max:
                max_index = i
                if min_ > array[i]:
                    min_ = array[i]
        min_index = 0
        for min_index in range(len(array)):
            if array[min_index] > min_:
                break
        # min_index -= 1
        return [min_index, max_index] if max_index != -1 else [-1, -1]

643. 子数组最大平均数 I

643. 子数组最大平均数 I

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        p0 = 0
        p1 = k - 1
        total = sum(nums[:k])
        ans = total
        while True:
            total -= nums[p0]
            p0 += 1
            p1 += 1
            if p1 == len(nums):
                break
            total += nums[p1]
            if ans < total:
                ans = total
        return ans / k

2640. 一个数组所有前缀的分数

2640. 一个数组所有前缀的分数

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        prefix_sum = 0
        nums_max = 0
        for i in range(len(nums)):
            if nums_max < nums[i]:
                nums_max = nums[i]
            prefix_sum += nums_max + nums[i]
            nums[i] = prefix_sum
        return nums

1785. 构成特定和需要添加的最少元素

1785. 构成特定和需要添加的最少元素

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        sum_nums = sum(nums)
        diff = abs(sum_nums - goal)
        return diff // limit + int(bool(diff % limit))

2360. 图中的最长环

2360. 图中的最长环

颜色标记，或使用时间戳标记

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        unused_point = {i for i in range(len(edges))}
        direction = {i: edges[i] for i in range(len(edges))}
        circle_start = set()
        color = [0] * len(edges)
        c = 0
        while unused_point:
            c += 1
            val = unused_point.pop()
            color[val] = c
            while True:
                val = direction.get(val, None)
                if val == -1 or val is None or (color[val] != 0 and color[val] != c):
                    break
                if color[val] == c:
                    circle_start.add(val)
                    break
                unused_point.discard(val)
                color[val] = c
        ans = -1
        for enter in circle_start:
            cnt = 0
            val = enter
            while True:
                val = direction[val]
                cnt += 1
                if val == enter:
                    break
            if ans < cnt:
                ans = cnt
        return ans