搬石頭直到連續的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。
關於這些寶石的初始位置,只能說以下四種情況之一。

1.如果結石已經連續,即lspace = 0和rspace = 0,則min_steps = 0。

搬石頭直到連續的Leetcode解決方案2.否則,如果三塊寶石中的兩塊是連續的,即如果lspace = 0或rspace = 0,那麼我們只需一步就可以將大部分石頭放在中間的石頭附近,從而使min_steps = 1。

腦筋急轉彎3.否則,如果三塊石頭中的任意兩塊石頭之間的間隔為1,即lspace = 1或rspace = 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

移動石塊的複雜性分析,直到連續的Leetcode解決方案

時間複雜度

O(1): 我們在算法中只使用了簡單的條件語句。 因此,時間複雜度為O(1)。

空間複雜度 

O(1): 除了像left,right,lspace,大小為2的ans數組之類的變量外,我們沒有創建任何額外的空間,因此空間複雜度也是O(1)。