모든 공을 각 상자로 옮기기 위한 최소 작업 횟수

1769년. 모든 공을 각 상자로 옮기기 위한 최소 작업 횟수

난이도:중

주제: 배열, 문자열, 접두사 합계

n개의 상자가 있습니다. 길이 n의 이진 문자열 상자가 제공됩니다. 여기서 i^번째 상자가 비어 있는 경우 상자[i]는 '0'이고 을 포함하는 경우 '1'입니다. 하나 공.

한 번의 작업으로 한 개의 공을 상자에서 인접한 상자로 이동할 수 있습니다. abs(i - j) == 1인 경우 상자 i는 상자 j에 인접해 있습니다. 그렇게 하면 일부 상자에는 공이 두 개 이상 있을 수 있습니다.

크기 n의 배열 답을 반환합니다. 여기서 답[i]은 모든 공을 i번째 상자최소 작업 수입니다. >.

각 답변[i]은 상자의 초기 상태를 고려하여 계산됩니다.

예 1:

• 입력: 상자 = "110"
• 출력: [1,1,3]
• 설명: 각 상자의 답은 다음과 같습니다.
  첫 번째 상자: 한 번의 작업으로 공 하나를 두 번째 상자에서 첫 번째 상자로 이동해야 합니다.
  두 번째 상자: 한 번의 작업으로 공 하나를 첫 번째 상자에서 두 번째 상자로 이동해야 합니다.
  세 번째 상자: 두 번의 작업을 통해 첫 번째 상자에서 세 번째 상자로 공 하나를 이동하고, 한 번의 작업으로 두 번째 상자에서 세 번째 상자로 공 하나를 이동해야 합니다.

예 2:

• 입력: 상자 = "001011"
• 출력: [11,8,5,4,3,4]

제약조건:

n == 상자.길이
1 상자[i]는 '0' 또는 '1'입니다.

힌트:

상자 i에서 상자 j로 공을 이동하려면 복근(i-j) 이동이 필요합니다.
모든 공을 상자로 옮기려면 하나씩 옮기면 됩니다.
각 상자 i에 대해 상자 j의 각 공을 반복하고 답변[i]에 abs(i-j)를 추가합니다.

해결책:

각 작업을 명시적으로 시뮬레이션하지 않고도 모든 공을 각 상자로 이동하는 데 필요한 최소 작업 수를 계산할 수 있는

접두사 합 접근 방식을 사용할 수 있습니다.

주요 관찰:

1. 상자 i에서 상자 j로 공을 이동하는 데 필요한 이동 횟수는 단순히 절대(i - j)입니다.
2. 공의 위치와 총 작업 횟수를 활용하여 모든 공을 특정 상자로 이동하는 데 필요한 총 이동 횟수를 계산할 수 있습니다.
3. 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 이동을 계산하여 두 번의 패스로 결과를 확인할 수 있습니다.

접근하다:

1. 왼쪽에서 오른쪽으로 패스: 이 패스에서는 왼쪽부터 시작하여 모든 공을 현재 상자로 가져오는 이동 횟수를 계산합니다.
2. 오른쪽에서 왼쪽으로 패스: 이 패스에서는 오른쪽부터 시작하여 모든 공을 현재 상자로 가져오는 이동 횟수를 계산합니다.
3. 두 패스의 결과를 결합하여 각 상자의 최종 결과를 얻습니다.

해결 단계:

1. 먼저 상자 문자열을 반복하고 각 상자의 왼쪽과 오른쪽에 공이 몇 개 있는지 세어보세요.
2. 반복하는 동안 왼쪽과 오른쪽 정보를 모두 사용하여 모든 공을 현재 상자로 가져오는 데 필요한 이동 횟수를 계산합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1769. 모든 공을 각 상자로 옮기기 위한 최소 작업 횟수

<?php /**
 * @param String $boxes
 * @return Integer[]
 */
function minOperations($boxes) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$boxes = "110";
print_r(minOperations($boxes)); // Output: [1,1,3]

$boxes = "001011";
print_r(minOperations($boxes)); // Output: [11,8,5,4,3,4]
?>

설명:

1. 왼쪽에서 오른쪽으로 패스: 왼쪽에 있는 모든 공을 현재 상자로 가져오는 데 필요한 총 작업 수를 계산합니다. 발견된 각 공('1')에 대해 총 이동 횟수를 업데이트합니다.
2. 오른쪽에서 왼쪽으로 패스: 왼쪽에서 오른쪽으로 패스하는 것과 유사하지만 오른쪽에서 현재 박스로 공을 이동시키는 작업 횟수를 계산합니다.
3. 각 상자의 총 작업 횟수는 왼쪽 패스와 오른쪽 패스의 이동 횟수의 합입니다.

예제 연습:

예시 1:

$boxes = "110";
print_r(minOperations($boxes));

출력:

Array
(
    [0] => 1
    [1] => 1
    [2] => 3
)

예시 2:

$boxes = "001011";
print_r(minOperations($boxes));

출력:

Array
(
    [0] => 11
    [1] => 8
    [2] => 5
    [3] => 4
    [4] => 3
    [5] => 4
)

시간 복잡도:

• 상자 문자열을 두 번(왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번) 반복하기 때문에 솔루션은 O(n) 시간에 실행됩니다.
• 결과를 보관하기 위해 답변 배열을 저장하므로 공간 복잡도는 O(n)입니다.

이 솔루션은 접두사 합계 기술을 사용하여 각 상자의 최소 작업 수를 효율적으로 계산합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 모든 공을 각 상자로 옮기기 위한 최소 작업 횟수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!