붉은 색과 파란색 색 줄무늬가 주어지면 클럽끼리의 색을 함께 교환 할 수 있습니다.

Question

RBBR, R- 빨강 및 B- 파랑의 문자열이 주어집니다.

색상을 맞추기 위해 필요한 최소 교체 횟수를 알아야합니다. 위의 경우 RRBB 또는 BBRR을 얻으려면 대답은 1이됩니다.

간단한 정렬은 우리에게 스왑의 수를 줄 것이므로 여기서 부분적으로 정렬 된 배열을 정렬하는 알고리즘이 유용 할 것이라고 생각하지만, 스왑의 수는 minimum입니다.

아이디어가 있으십니까?

이것은 this에 따른 Microsoft 인터뷰 질문입니다.

Answer 1

문자열을 한 번 통과시켜 빨간색 수 (#R)와 파란색 수 (#B)를 계산합니다. 그런 다음 첫 번째 #R 볼 (#r)의 빨간색 수와 첫 번째 #B 볼 (#b)의 파란색 볼 수를 세는 두 번째 패스를 가져옵니다. (#R - #r)과 (#B - #b) 중 적은 수의 스왑이 필요합니다.

Answer 2

예제를 살펴 보겠습니다. 최종 상태는 RRBB 또는 BBRR입니다. 즉, 끝 상태는 항상 nRmB 또는 mBnR입니다. 여기서 n은 R의 수이고 m은 문자열의 수입니다. 최종 상태가 정의되었으므로 어쩌면 경로 찾기 알고리즘이 좋은 방법 일 수 있습니까? 어떻게 각 스왑을 국가 변화로 생각하고 필요한 스왑 스왑의 수를 늘리기위한 발견 적 기능을 생각해 보는 것이 어떻습니까? 나는 공중에서 아이디어를 던지고 있지만 도움이되기를 바랍니다.

Answer 3

우리는 최종 문자열 F = R^a B^b 또는 B^b R^a로 변환해야하는 문자열 S가 주어집니다. S와 F의 차이 수는 모든 잘못된 R에 대해 B가 잘못 배치되어 있기 때문에조차되어야합니다. 따라서 S와 가능한 두 F 사이의 최소 차이 수를 찾아서 2로 나눕니다.

는 예를 들어, 당신은
각 가능성에 대한 각 문자 S와 F 사이의 차이점을 비교 BBBRRRRR

, 각각의 가능한 4 개 차이가 S = RBRRBRBR이 에 RRRRRBBB을 변환해야하는 주어진 것 최종 문자열은 최소값과 관계없이 2 스왑입니다.

Answer 4

문자열의 오른쪽과 왼쪽 끝에서 동시에 두 개의 인덱스로 시작하십시오. R을 찾을 때까지 왼쪽 색인을 전진하십시오. B을 찾을 때까지 올바른 색인을 뒤로 이동하십시오. 그들을 교환하십시오. 왼쪽 인덱스가 오른쪽 인덱스를 충족 할 때까지 반복하고 스왑을 계산합니다. 그런 다음 동일한 작업을 수행하십시오. 왼쪽에 B, 오른쪽에 R이 있는지 확인하십시오. 최소값은 두 스왑 카운트 중 낮은 값입니다.

Answer 5

스왑의 수는 벡터를 정렬하는 데 필요한 역전의 수에서 파생 될 수 있다고 생각합니다. This은 순열 벡터를 사용하여 동일한 작업을 수행하는 예입니다.

Answer 6

이것은 기술적 인 대답이 아니지만보다 직관적으로 살펴 보았습니다.

R의 그룹이 단일 블록으로 이동할 수 있기 때문에 RRBBBBR은 RBR로 줄일 수 있습니다. 즉, 배열은 실제로 RB 세트 N 개입니다.

중요한 것은 RB 블록의 N 세트 수 (마지막 블록의 불완전 블록 포함)입니다.

• RBR -> 1 개 스왑 (RB 블록 2 개 완전 세트) RRBB에 도착 (RB 블록의 2 개 세트, RB 및 R) RRB에
• RBRBRB을
• RBRB-> 1 스왑 도착 -> 2 개 스왑 RRRBBB에 도착 (RB 블록 3 개 완전 세트)
• RBRBRBRB - RB의 RB = 3 개 스왑> 4 개 세트

그래서이 일반화, 교환의 수가 필요 = N 세트 블록 (불완전 블록 포함)을 빼고 1을 뺍니다.