문자열 배열에서 A 0과 B 1로 구성된 가장 긴 부분 집합의 길이를 찾습니다.-C++-php.cn

문자열 배열에서 A 0과 B 1로 구성된 가장 긴 부분 집합의 길이를 찾습니다.

PHPz

풀어 주다： 2023-09-11 12:09:02

앞으로

870명이 탐색했습니다.

문자열 배열에서 A 0과 B 1로 구성된 가장 긴 부분 집합의 길이를 찾습니다.

이 문제에서는 최대 A 0과 B1을 포함하는 가장 긴 부분 집합을 찾아야 합니다. 우리가 해야 할 일은 배열 요소를 사용하여 가능한 모든 하위 집합을 찾고 최대 A 0 및 B1 을 포함하는 가장 긴 하위 집합을 찾는 것입니다.

이 튜토리얼에서는 먼저 문제를 해결하기 위한 재귀적 방법을 배웁니다. 그런 다음 동적 프로그래밍 방법을 사용하여 코드를 최적화합니다.

문제 설명 - N개의 이진 문자열을 포함하는 배열이 제공됩니다. 또한 A와 B 정수가 제공됩니다. A 0 및 B1 이상을 포함하지 않도록 주어진 이진 문자열을 사용하여 가장 긴 하위 집합을 만들어야 합니다.

으아악 으아악

가장 긴 부분 집합은 2개의 0과 1개의 1을 포함하는 { "0", "0", "1"}입니다.

으아악 으아악

가장 긴 부분 집합은 {"0", "101", "0", "1"}, 3개의 0 및 3개의 1입니다.

방법 1

이번 섹션에서는 재귀를 이용한 간단한 방법을 배워보겠습니다. 배열 요소를 사용하여 가능한 모든 하위 집합을 구성하고 A 0 및 B 1 을 포함하는 가장 긴 하위 집합을 찾습니다.

1단계 - 주어진 이진 문자열에서 총 0 개수를 계산하는 countZeros() 함수를 정의합니다.
1.1단계 - "count" 변수를 0으로 초기화합니다.
1.2단계 - for 루프를 사용하여 문자열을 반복합니다.
1.3단계 - i번째 인덱스의 문자가 "0"이면 "cnt" 값을 1만큼 늘립니다.
1.2단계 - "cnt" 변수의 값을 반환합니다.
2단계 - getMaxSubsetLen()은 정수 값을 반환하고 벡터 arr, int A, int B 및 index를 인수로 사용합니다.
3단계 - 함수 내에서 기본 사례를 정의합니다. 인덱스가 벡터의 크기와 같거나 A와 B의 값이 모두 0인 경우 0을 반환합니다.
4단계 - 이제 인덱스에서 문자열의 총 0 개수를 셉니다.
5단계 - 문자열 길이에서 총 1의 수를 빼서 총 1의 수를 구합니다.
6단계 - "첫 번째" 변수를 0으로 초기화합니다.
7단계 - 0과 1의 총 개수가 각각 A와 B보다 작은 경우 현재 이진 문자열을 포함합니다. 1 + 재귀 함수 호출의 반환 값을 저장합니다. 재귀 호출을 할 때 A와 B에서 0과 1을 뺍니다.
8단계 - 현재 문자열을 제외하고 결과 값을 "두 번째" 변수에 저장합니다.
9단계 - 첫 번째와 두 번째의 최대값을 반환합니다.

으아악

으아악

시간 복잡도 - N개의 배열 요소를 사용하여 가능한 모든 하위 집합을 찾았으므로 O(2N)입니다.

공간 복잡성 - O(1)

이 섹션에서는 위의 방법을 최적화했습니다. 우리는 이 문제를 해결하기 위해 동적 프로그래밍 방법을 사용합니다. 문제의 시간 복잡도를 줄이기 위해 이전 상태의 결과를 저장합니다.

1단계 - 위의 방법에서 했던 것처럼 특정 바이너리 문자열에서 총 0의 개수를 계산하는 countZeros() 함수를 정의하세요.
2단계 - 이전 상태의 결과를 저장하기 위해 A x B x N 크기의 3D 벡터를 만듭니다. 목록에서 총 0이 A와 같고 1이 B와 같을 때 인덱스 "I"에 하위 집합의 길이를 저장합니다. 또한 이를 getMaxSubsetLen() 함수에 인수로 전달합니다.
3단계 - 위의 방법에서 했던 것처럼 기본 사례를 정의합니다.
4단계 - dpTable[A][B][index] 값이 0보다 크면 상태가 계산되어 해당 값이 반환된다는 의미입니다.
5단계 - 현재 문자열에서 0과 1의 총 개수를 셉니다.
6단계 - 현재 문자열을 포함하거나 제외한 결과 값을 가져옵니다.
7단계 - max() 함수를 사용하여 첫 번째와 두 번째의 최대값을 구하고, 이를 dpTable[A][B][index]에 저장하고