搬石头直到连续的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解决方案

实施

直到连续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,大小为2的ans数组等,我们还没有创建任何额外的空间,因此空间复杂度也是O(1)。