[Lint Code] Pour Water

3924 단어
원제 묘사
We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index? Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules: If the droplet would eventually fall by moving left, then move left. Otherwise, if the droplet would eventually fall by moving right, then move right. Otherwise, rise at it's current position. Here, "eventually fall"means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level"means the height of the terrain plus any water in that column. We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.
1.heights will have length in [1, 100] and contain integers in [0, 99]. 2.V will be in range [0, 2000]. 3.K will be in range [0, heights.length - 1].
응, 완전히, 못 알아보잖아.
물탱크의 밑부분 고도 분포 상황을 대표하는 그룹 고도치를 정한다.K점에 V 부피의 물을 붓고 물을 부은 후의 높이 분포를 구한다.부은 각 부피의 물은 다음과 같은 규칙에 따라 흐른다. 만약 K점 왼쪽에 지세가 비교적 낮고 도달할 수 있는 위치가 존재한다면 물은 우선 왼쪽으로 흐른다.그렇지 않으면 K점 오른쪽에 지세가 낮고 도달할 수 있는 위치가 존재하면 물이 오른쪽으로 흐른다.그렇지 않으면, 물은 K에 머물러 있다
이 문제는 지세가 비교적 낮고 도달할 수 있는 위치가 존재하는 데 있다. 무슨 뜻입니까?[3,2,2,1,3]인덱스 1부터 시작하면 인덱스가 3값이 1인 위치로 처음 분배된다. 이렇게 [3,2,2,2,2,3]로 변한다. 만약에 계속 분배하면 지세가 낮고 도달할 수 없다. 이렇게 [3,3,2,2,3]하고 계속 분배한다[3,3,3,3,2,3].첨부ra 코드lintcode버전:
import time
from functools import wraps
#     
def countTime(func):
    @wraps(func)
    def wrap(*args,**kwargs):
        start = time.time()
        func(*args,**kwargs)
        print(time.time() - start)
    return wrap
class Solution:
    """
    @param heights: the height of the terrain
    @param V: the units of water
    @param K: the index
    @return: how much water is at each index
    """
    @countTime
    def pourWater(self, heights, V, K):
        # Write your code here
        def leftFoundMin(l, c):
            target = c
            while True:
                if heights[l] < heights[c]:
                    c = l
                    l -= 1
                    target = c
                    if l < 0:
                        break
                    continue
                elif heights[l] == heights[c]:
                    c = l
                    l -= 1
                    if l < 0:
                        break
                    continue
                else:
                    break
            return target

        def rightFoundMin(r, c):
            """
            :param r: 
            :param c:
            :return:
            """
            target = c
            while True:
                if heights[r] < heights[c]:
                    c = r
                    r += 1
                    target = c
                    if r >= len(heights):
                        break
                    continue
                elif heights[r] == heights[c]:
                    c = r
                    r += 1
                    if r >= len(heights):
                        break
                    continue
                else:
                    break
            return target

        while V > 0:
            if K - 1 >= 0:
                l = leftFoundMin(K-1,K)
            else:
                l=K
            if K + 1 < len(heights):
                r = rightFoundMin(K+1,K)
            else:
                r=K
            if l K:
                heights[r] += 1
            elif l==r:
                heights[K] += 1
            else:
                pass
            V -= 1
        return heights

좋은 웹페이지 즐겨찾기