leetcode_1033. Moving Stones Until Consecutive

蔚落 2021-12-23 02:29 149阅读 0赞

[https://leetcode.com/problems/moving-stones-until-consecutive/][https_leetcode.com_problems_moving-stones-until-consecutive]

题意：给定3个点，每次从两个端点（位置最小或位置最大）中挑选一个点进行移动，将其移动到原先两个端点之间的空位置上，直到3个点位置连续，问最少多少步，和最多多少步。

思路：

对于(x,y,z),x<y<z:

最多步数：

固定一端，一直选择另一端的端点移动。具体地，固定右端点，一直选择左端点进行移动，每次将左端点移动至最左边的空位置上（greedy），每一步这样的操作，消耗\[x,y\]区间中的一个空位置，直至用掉所有空位置；或者说每一次操作后，最新的\[x1,y1\]相对\[x,y\]长度减1，一直减到xn+2==yn。

故，最多的步数为，z-x-2。

最少步数：

若x+1=y，y+1=z，则需0步；

若y-x<=2或者z-y<=2，则需1步；

否则，需2步。

class Solution
    {
    public:
        vector<int> numMovesStones(int a, int b, int c)
        {
            if(a>b)
                swap(a,b);
            if(a>c)
                swap(a,c);
            if(b>c)
                swap(b,c);
            //cout<<a<<" "<<b<<" "<<c<<endl;
            if(a+1==b && b+1==c)
                return vector<int>{
        0,0};
            int lowerbound=0, upperbound=c-a-2;
            if(b-a<=2||c-b<=2)
                lowerbound=1;
            else
                lowerbound=2;
            //cout<<lowerbound<<" "<<upperbound<<endl;
            return vector<int>{lowerbound,upperbound};
        }
    };

转载于:https://www.cnblogs.com/jasonlixuetao/p/10833589.html

[https_leetcode.com_problems_moving-stones-until-consecutive]: https://leetcode.com/problems/moving-stones-until-consecutive/