이진 목록이 있다고 가정하고 여기서는 1과 0만 사용할 수 있고 또 다른 숫자 k도 있습니다. 최대 k 0에서 1까지 설정할 수 있으며 모든 1을 포함하는 가장 긴 하위 목록의 길이를 찾아야 합니다.
따라서 입력이 nums =[0, 1, 1, 0, 0, 1, 1] k =2와 같은 경우 출력은 6이 됩니다. 두 개의 중간 0을 1로 설정하면 목록이 다음과 같이 됩니다. [0, 1, 1, 1, 1, 1, 1].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 0 :=0, ans :=0, j :=0
- 숫자 단위의 각 인덱스 i와 값 n에 대해 다음을 수행합니다.
- zeros :=zeros + (n이 0과 같으면 1, 그렇지 않으면 0)
- 0인 동안> k, do
- zeros :=zeros - (nums[j]가 0과 같으면 1, 그렇지 않으면 0)
- j :=j + 1
- i - j + 1> ans이면
- an :=i - j + 1
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, nums, k): zeros = 0 ans = 0 j = 0 for i, n in enumerate(nums): zeros += n == 0 while zeros > k: zeros -= nums[j] == 0 j += 1 if i - j + 1 > ans: ans = i - j + 1 return ans ob = Solution() nums = [0, 1, 1, 0, 0, 1, 1] k = 2 print(ob.solve(nums, k))
입력
[0, 1, 1, 0, 0, 1, 1], 2
출력
6