Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 모든 정류장을 통과하려면 최소 버스 수를 찾는 프로그램이 필요합니다.

<시간/>

nums라고 하는 숫자 목록이 있고 nums[i]에서 버스가 역 i에 도착해야 하는 시간을 나타내는 라인에 버스 정류장을 표시한다고 가정합니다. 이제 버스는 앞으로만 이동할 수 있으므로 모든 정류장을 통과하는 데 필요한 최소 버스 수를 찾아야 합니다.

따라서 입력이 nums =[1, 2, 7, 9, 3, 4]와 같으면 출력은 2가 됩니다. 한 버스는 [1, 2, 3, 4] 정차하고 다른 버스는 [ 7, 9].

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

  • 답변 :=0

  • 본 :=길이가 숫자와 같고 처음에 거짓으로 채워진 목록

  • 각 인덱스 i 및 해당 n(숫자)에 대해 수행

    • 본[i]이 거짓이면

      • 본[i] :=사실

      • ans :=ans + 1

      • 이전 :=n

      • 범위 i+1에서 숫자 크기까지의 j에 대해

        • nums[j]> prev 및 see[j]가 거짓이면

          • 본[j] :=사실

          • 이전 :=nums[j]

  • 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, nums):
   ans = 0
   seen = [False] * len(nums)
   for i, n in enumerate(nums):
      if not seen[i]:
         seen[i] = True
         ans += 1
         prev = n
   for j in range(i+1, len(nums)):
      if nums[j] > prev and not seen[j]: seen[j] = True
         prev = nums[j]
   return ans
ob = Solution()
nums = [1, 2, 7, 9, 3, 4]
print(ob.solve(nums))

입력

[1, 2, 7, 9, 3, 4]

출력

2