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

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

https://leetcode.com/problems/super-egg-drop

from typing import List
 
class Solution(object):
    def superEggDrop(self, K, N):
 
        drops_for_previous_num_eggs = [i for i in range(N + 1)]
 
        for num_eggs in range(2, K + 1):
            drops_for_current_num_eggs = [None for _ in range(N + 1)]
            drops_for_current_num_eggs[0] = 0
 
            drop_floor = 1
 
            for target_floor in range(1, N + 1):
 
                while (
                    drop_floor < target_floor and
                    # If one use the method here, she/he is going to exceed time limit
                    # self.is_split_better_than_previous(floor, drop_floor, drops_for_previous_num_eggs, drops_for_current_num_eggs)
                    max(
                        drops_for_previous_num_eggs[drop_floor - 1],
                        drops_for_current_num_eggs[target_floor - (drop_floor - 1) - 1]
                    ) > max(
                        drops_for_previous_num_eggs[drop_floor],
                        drops_for_current_num_eggs[target_floor - drop_floor - 1]
                    )
                ):
                    drop_floor += 1
 
                drops_for_current_num_eggs[target_floor] = (
                    # Same here concerning time limit
                    # 1 + self.get_drops_for_floor(floor, drop_floor - 1, drops_for_previous_num_eggs, drops_for_current_num_eggs)
                    1 + max(
                        drops_for_previous_num_eggs[drop_floor - 1],
                        drops_for_current_num_eggs[target_floor - (drop_floor - 1) - 1]
                    )
                )
 
            drops_for_previous_num_eggs = drops_for_current_num_eggs
 
        return drops_for_previous_num_eggs[-1]
 
    def is_split_better_than_previous(
            self,
            floor: int,
            drop_floor: int,
            drops_for_previous_num_eggs: List[int],
            drops_for_current_num_eggs: List[int]) -> bool:
 
        return (
            self.get_drops_for_floor(
                floor,
                drop_floor - 1,
                drops_for_previous_num_eggs,
                drops_for_current_num_eggs
            ) > self.get_drops_for_floor(
                floor,
                drop_floor,
                drops_for_previous_num_eggs,
                drops_for_current_num_eggs
            )
        )
 
    def get_drops_for_floor(
            self,
            floor: int,
            drop_floor: int,
            drops_for_previous_num_eggs: List[int],
            drops_for_current_num_eggs: List[int]) -> int:
 
        return max(
            drops_for_previous_num_eggs[drop_floor],
            drops_for_current_num_eggs[floor - drop_floor - 1]
        )