Переміщення каменів до послідовного рішення Leetcode


Рівень складності Легко
Часто запитують у Facebook
Мозгозахисник

Постановка проблеми

У цій задачі нам дано три камені в положеннях a, b і c. Ми повинні зробити їх послідовними, виконавши один або кілька разів наступний крок.
На кожному кроці ми виберемо лівий камінь або правий камінь і помістимо десь посередині між діапазоном зліва направо на камінь.
Давайте зрозуміємо це краще, наступне зображення:
Переміщення каменів до послідовного рішення 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.

Переміщення каменів до послідовного рішення Leetcode2. В іншому випадку, якщо два з трьох каменів є послідовними, тобто якщо lspace = 0 або rspace = 0, тоді ми можемо просто поставити далеко більшість каменів близько до середнього каменю всього за 1 крок, таким чином min_steps = 1.

Мозгозахисник3. В іншому випадку, якщо простір між будь-якими двома з трьох каменів дорівнює 1, тобто якщо lspace = 1 або rspace = 1. Тоді найдальший камінь можна покласти між двома ближніми каменями (зауважте, що біля каміння має лише одне положення між ними) лише за один крок.
Отже, зробити їх послідовними може відбутися всього за 1 крок. Таким чином, min_steps = 1.

Мозгозахисник4. В іншому випадку камені в обох крайніх місцях можна помістити в сусід середніх каменів на 1 крок кожен. Таким чином, min_steps = 1 + 1 = 2.
Переміщення каменів до послідовного рішення Leetcode

Реалізація

Програма C ++ для переміщення каменів до послідовного рішення Leetcode

#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

Програма Java для переміщення каменів до послідовного рішення Leetcode

#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

Аналіз складності переміщення каменів до послідовного рішення Леткоду

Складність часу

O (1): Ми щойно використовували прості умовні твердження в нашому алгоритмі. Таким чином, часова складність становить O (1).

Складність простору 

O (1): Окрім змінних, таких як left, right, lspace, ans масив розміром 2 тощо, ми не створили жодного зайвого простору, тому складність простору теж O (1).