Участник:Alvant/TaskCandy

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/candy/

from typing import List
 
class Solution:
    def candy(self, ratings: List[int]) -> int:
        if len(ratings) == 0:
            return 0
 
        candies = [1 for r in ratings]
 
        for i in range(0, len(ratings)):
            self.set_candies(candies, i, ratings)
 
        for i in range(len(ratings)-1, -1, -1):
            self.set_candies(candies, i, ratings)
 
        return sum(candies)
 
    def set_candies(self, candies: List[int], index: int, ratings: List[int]) -> None:
        left_border = max(0, index - 1)
        right_border = min(len(ratings), index + 2)
 
        current_ratings = ratings[left_border:right_border]
        sorted_ratings = sorted(current_ratings)
 
        current_candies = candies[left_border:right_border]
        sorted_candies = sorted(current_candies)
 
        candies[index] = sorted_candies[sorted_ratings.index(ratings[index])]
 
        current_indices = list(range(left_border, right_border))
        sorted_indices = [p[0] for p in sorted(zip(current_indices, current_ratings), key=lambda x: x[1])]
        j = sorted_indices.index(index) - 1
 
        while j > -1:  # TODO: excessive check via loop
 
            if (ratings[index] > ratings[sorted_indices[j]] and
                candies[index] <= candies[sorted_indices[j]]):
 
                candies[index] = candies[sorted_indices[j]] + 1
 
            j -= 1