博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode_1033. Moving Stones Until Consecutive
阅读量:6088 次
发布时间:2019-06-20

本文共 786 字,大约阅读时间需要 2 分钟。

题意:给定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
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<
<<" "<<<" "<
<
{
0,0}; int lowerbound=0, upperbound=c-a-2; if(b-a<=2||c-b<=2) lowerbound=1; else lowerbound=2; //cout<
<<" "<
<
{lowerbound,upperbound}; }};

 

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

你可能感兴趣的文章
Swing中弹出对话框的几种方式(转)
查看>>
biz处理dao事务处理层
查看>>
毕业论文 一定要自己写 切记不可抄袭
查看>>
洗纸牌算法
查看>>
MongoDB Shell 经常使用的操作
查看>>
Linux 性能监测:Network
查看>>
MySQL: Speed of INSERT Statements
查看>>
SQL like使用 模糊查询
查看>>
java在string和int相互转化
查看>>
谁能在同一文件序列化多个对象并随机读写(反序列化)?BinaryFormatter、SoapFormatter、XmlSerializer还是BinaryReader...
查看>>
uva 1436 - Counting heaps(算)
查看>>
What qualities characterize a great PhD student
查看>>
C#中Abstract和Virtual
查看>>
编写更好的C#代码
查看>>
【数据库设计-1.1】关系的实现
查看>>
UVa 10285 - Longest Run on a Snowboard
查看>>
Android设备管理器漏洞2--禁止用户取消激活设备管理器
查看>>
codeforces Gym 100187A A. Potion of Immortality
查看>>
2016校招内推 -- 腾讯SNG前端 -- 面试经历
查看>>
HDU 4125 Moles 段树+KMP
查看>>