이 Java 코드 스 니펫은 어떻게 작동합니까?

Question

자바 인터뷰 질문은

임시 버퍼를 사용하지 않고, 오른쪽으로 모두 0의 왼쪽과 1 개의 배치, 배열에서 0과 1을 구분합니다. 결과를 문자열로 인쇄하십시오. 예를 들어, 주어진 {0,1,1,0,0,1}, 출력은 "000111"입니다.

는 그리고 대답은 다음과 같습니다

public class ZeroOneSeparator { 

    public static void zeroOneSeparator(int[] inputArr){ 

     // for each index, store number of 1's up to the index 
     for (int i = 1; i < inputArr.length; i++) { 
      inputArr[i] = inputArr[i-1] + inputArr[i]; 
     } 

     // This is the "magical math" block I don't understand. 
     // Why does this "work"? 
     for (int i = inputArr.length - 1; i > 0; i--) { 
      if (inputArr[i] > 0) { 
       inputArr[i-1] = inputArr[i] - 1; 
       inputArr[i] = 1; 
      } else { 
       inputArr[i-1] = 0; 
      } 
     } 

     for (int i = 0; i < inputArr.length; i++) { 
      System.out.print(inputArr[i]); 
     } 
    } 

    public static void main(String[] args) { 
     int[] inputArr1 = {1,0,1,0,1,1}; 
     ZeroOneSeparator.zeroOneSeparator(inputArr1); 
     System.out.println(); 
     int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1}; 
     ZeroOneSeparator.zeroOneSeparator(inputArr2); 
     int[] inputArr3 = {}; // intentionally empty 
     System.out.println(); 
     ZeroOneSeparator.zeroOneSeparator(inputArr3); 
     int[] inputArr4 = {0,0,0,0,0,0}; 
     System.out.println(); 
     ZeroOneSeparator.zeroOneSeparator(inputArr4); 
     int[] inputArr5 = {0,1,0,1,0,1,0,1}; 
     System.out.println(); 
     ZeroOneSeparator.zeroOneSeparator(inputArr5); 
     int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0}; 
     System.out.println(); 
     ZeroOneSeparator.zeroOneSeparator(inputArr6); 
    } 
} 

나는 디버거이 코드를 강화,하지만 작동 난 아직도 왜 이해가 안 돼요. 누군가 그것을 통해 나를 걸을 수 있습니까?

Answer 1

무슨 일이 일어나는지 예를 들어 보겠습니다. 우리는 다음과 같은 배열이 있다고 가정 :

0 1 1 0 1 1 0 0 

(댓글이 지정으로) 첫 번째 루프는 (1)의 총 수는 지금까지 각각 1은 수를 증가 어디서 본 것까지 계산하고 각 0 그것을 같은 잎. 따라서 우리 배열의 경우 다음과 같이 끝납니다 :

0 1 2 2 3 4 4 4 

배열의 마지막 요소는 이제 1이며 총 개수는 1입니다. 우리는 다음 루프에서 그 사실을 사용합니다.

마지막 요소에서 시작하여 0보다 큰지 확인합니다. 그렇다면 요소를 1로 대체 한 다음 해당 개수를 1 씩 줄이고 이전 요소에 할당합니다. 우리는 카운트가 0이 될 때까지 계속해서 1을 채 웁니다. 그 시점에서 우리는 우리가 만나는 각 요소를 0으로 설정했습니다.

실제로 여기서 일어나는 것은 얼마나 많은 1이 있는지를 알게되면, 우리는 배열의 끝에서부터 "카운트 다운"하여 1의 수를 채울 수 있습니다. 이 시점에서 나머지 요소는 0이어야하므로 나머지 요소는 0으로 설정할 수 있습니다.

은 시각적으로,이 방식을 볼 때 "카운트 다운"매우 분명한 것 같다

0 1 2 2 3 4 4 [4] -> 
0 1 2 2 3 4 [3] 1 -> 
0 1 2 2 3 [2] 1 1 -> 
0 1 2 2 [1] 1 1 1 -> 
0 1 2 [0] 1 1 1 1 -> 
0 1 [0] 0 1 1 1 1 -> 
0 [0] 0 0 1 1 1 1 -> 
0 0 0 0 1 1 1 1 

주 ([]의에 의해 둘러싸인 "현재 요소"와)과 같습니다.

Answer 2

마지막 색인의 배열에 1의 개수가 있으므로 뒤에서 루프를 만들고 1로 바꾸십시오. 코드에서 수행되는 트릭은 1의 개수를 줄이고 모든 단계에서 이전 배열 요소에 저장하므로 다음 단계에서 현재 요소가 0인지 1인지를 알 수 있습니다. 모든 1 또는 거의 모든 1의 경우에도 (배열에서 단 하나의 0), 인덱스 0에서 요소를 수정할 때 1의 수는 올바른 숫자입니다.

개인적으로 1의 수를 기록하고 0의 수를 파생시키고 2 개의 루프를 사용하여 배열의 수를 인쇄/설정합니다.

Answer 3

첫 번째 은입니다. 루프 개수는 각 항목의 왼쪽에 몇 개입니까? 카운트 결과, 입력이 {0,1,1,0,0,1}이면 입력 배열은 {0,1,2,2,2,3}이됩니다.

마지막 색인 3은 목록에 세 개의 1이 있다고 표시합니다. 두 번째 은이고, 루프는 목록을 역순으로 처리하고 마지막 세 항목을 1로 표시합니다.