두 개의 1 사이에 최소한 K개의 0이 있도록 주어진 이진 배열을 뒤집을 0의 수를 최대화합니다.

이진 배열은 숫자 0과 1만 포함하는 특수한 유형의 배열입니다. 이 문제에는 이진 배열과 정수 K가 주어졌습니다. 우리의 임무는 두 개의 1 사이에 최소한 K개의 0이 있도록 주어진 이진 배열에서 1로 바뀔 수 있는 0의 최대 수를 계산하는 것입니다.

예제 예

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

위 배열의 3번째와 6번째 인덱스는 유일한 유효한 인덱스이며 두 1 사이에 최소 2개의 0이 있는지 확인하기 위해 뒤집어질 수 있습니다. 따라서 결과 배열은 {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

입니다. 으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

위 배열의 세 번째 인덱스는 유일하게 유효한 반전 인덱스입니다.

접근

위에 주어진 배열과 정수 k의 예를 보았습니다. −

메소드로 넘어가겠습니다.

이 방법의 아이디어는 두 개의 1 사이에 연속되는 0의 수를 세고 그 사이에 일부 0을 1로 바꾸는 것이 적합한지 확인하는 것입니다. 두 개의 0 사이에 X개의 0이 있다고 가정합니다. 관찰에 따르면 뒤집을 수 있는 0의 개수는 (X-K) / (K+1)입니다. 따라서 배열을 반복하고 각 1 쌍 사이에 연속적인 0이 몇 개 있는지 기록하십시오. 그런 다음 원하는 응답인 변수 개수에 뒤집힐 수 있는 0의 개수를 추가합니다.

아래 방법을 단계별로 논의해 보겠습니다.

• 먼저, 주어진 배열 'arr'과 정수 'K'를 매개변수로 취하고 필요한 정수 'count'를 반환 값으로 반환하는 'onesCount'라는 함수를 만듭니다.

• 변수 count 및 lastIdx를 생성합니다.

• 채우기 0의 개수를 저장하려면 변수 개수를 0으로 초기화하세요.

• (-(K+1))을 사용하여 lastIdx 변수를 초기화하여 배열의 마지막 인덱스를 값 1로 저장합니다.

• for 루프를 사용하여 배열을 반복하고 현재 요소가 1인지 확인한 다음 연속된 두 1 사이에 또 ​​다른 1을 추가할 수 있는 0이 충분한지 확인합니다. 마지막으로 마지막 1의 인덱스 값을 업데이트합니다.

• 배열에서 0의 마지막 세그먼트를 세는 조건을 작성하고 이를 변수 개수에 추가합니다.

• 마지막으로 최종 답변 개수가 반환됩니다.

Example

의 중국어 번역은

Example

입니다.

아래는 두 개의 1 사이에 최소한 k개의 0이 있는지 확인하기 위해 0을 1로 변환하는 최대값을 계산하는 C++ 프로그램입니다.

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 배열을 통해서만 반복하기 때문에 O(N)입니다. 여기서 N은 주어진 배열의 크기입니다.

위 코드의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

결론

이 튜토리얼에서는 두 개의 1 사이에 최소한 K개의 0이 있도록 주어진 이진 배열에서 뒤집을 수 있는 0의 최대 수를 찾는 프로그램을 구현했습니다. 이 문제는 두 1 사이의 연속된 0의 수를 세고 그 사이에 일부 0을 뒤집는 것이 적합한지 확인하여 해결됩니다. 시간복잡도는 O(N), 공간복잡도는 O(1)이다. 여기서 N은 문자열의 크기입니다.

위 내용은 두 개의 1 사이에 최소한 K개의 0이 있도록 주어진 이진 배열을 뒤집을 0의 수를 최대화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!