연속적인 Leetcode 솔루션까지 돌 이동


난이도 쉽게
자주 묻는 질문 페이스북 서비스
수수께끼

문제 정책

이 문제에서는 a, b, c 위치에 XNUMX 개의 돌이 주어집니다. 다음 단계를 한 번 이상 수행하여 연속적으로 만들어야합니다.
각 단계에서 우리는 왼쪽 돌 또는 오른쪽 돌을 골라 왼쪽에서 오른쪽 돌의 범위 사이에 놓을 것입니다.
다음 그림으로 이것을 더 잘 이해합시다.
연속적인 Leetcode 솔루션까지 돌 이동
이 돌을 연속적으로 만들기 위해 최소 및 최대 단계 수에 모두 응답해야합니다.

a = 1, b = 2, c = 5
[1,2]

설명 : 돌을 5에서 3으로 이동하거나, 돌을 5에서 4에서 3으로 이동하십시오.

a = 4, b = 3, c = 2
[0,0]

우리는 움직일 수 없습니다.

a = 3, b = 5, c = 1
[1,2]

돌을 1에서 4로 이동하십시오. 또는 돌을 1에서 2에서 4로 이동하십시오.

접근

먼저 최대 걸음 수를 계산하는 방법에 대해 이야기하겠습니다. 극단의 두 돌이 중간 돌에 1 단위 더 가까워 질 때만 이동 횟수가 최대라고 말할 수는 없습니다.
따라서 왼쪽 돌과 중간 돌 사이의 위치 수 + 중간 돌과 오른쪽 돌 사이의 위치 수가 연속으로 만드는 최대 단계 수입니다.
연속적인 Leetcode 솔루션까지 돌 이동
이제 주요 문제는 최소 단계 수를 계산하는 방법입니다. 다음을 이해하면 최소값을 알 수 있습니다. 조건.
왼쪽 돌과 중간 돌 사이의 위치 수는 lspace이고 중간 돌과 오른쪽 돌 사이의 위치 수는 rspace라고합시다.
이 돌의 초기 위치에 대해 다음 4 가지 상황 중 하나만 말할 수 있습니다.

1. 돌이 이미 연속적이면 즉 lspace = 0 및 rspace = 0이면 min_steps = 0입니다.

연속적인 Leetcode 솔루션까지 돌 이동2. 그렇지 않으면 0 개의 돌 중 0 개가 연속적인 경우 즉, lspace = 1 또는 rspace = 1이면 가장 멀리있는 돌을 XNUMX 단계 만에 중간 돌 근처에 놓을 수 있으므로 min_steps = XNUMX입니다.

수수께끼3. 그렇지 않으면 세 돌 중 두 돌 사이의 간격이 1이면 즉, lspace = 1 또는 rspace = 1이면됩니다. 그런 다음 가장 먼 돌을 두 개의 가까운 돌 사이에 놓을 수 있습니다 (근처 돌 사이에는 단 하나의 위치 만 있음).
따라서 연속적으로 만드는 것은 단 한 단계로 이루어질 수 있습니다. 따라서 min_steps = 1입니다.

수수께끼4. 그렇지 않으면 양쪽 끝의 돌을 중간 돌의 이웃에 각각 1 단계 씩 넣을 수 있습니다. 따라서 min_steps = 1 + 1 = 2입니다.
연속적인 Leetcode 솔루션까지 돌 이동

실시

연속적인 Leetcode 솔루션까지 돌을 움직이는 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

연속적인 Leetcode 솔루션까지 돌을 옮기는 Java 프로그램

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

연속적인 Leetcode 솔루션까지 움직이는 돌에 대한 복잡성 분석

시간 복잡성

O (1) : 알고리즘에서 간단한 조건문을 사용했습니다. 따라서 시간 복잡도는 O (1)입니다.

공간 복잡성 

O (1) : left, right, lspace, ans array of size 2 등과 같은 변수를 제외하고는 추가 공간을 만들지 않았으므로 공간 복잡성도 O (1)입니다.