刷题记录--算法--简单
第一题
2582. 递枕头
已解答
简单
相关标签
相关企业
提示
n 个人站成一排，按从 1 到 n 编号。
最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。
- 例如，当枕头到达第
n个人时，TA 会将枕头传递给第n - 1个人，然后传递给第n - 2个人，依此类推。
给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。
示例 1：
输入：n = 4, time = 5 输出：2 解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。 5 秒后，枕头传递到第 2 个人手中。
示例 2：
输入：n = 3, time = 2 输出：3 解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。 2 秒后，枕头传递到第 3 个人手中。
分析思路：
题目有两个参数time 与n
先分析time参数，有两种可能为0和不为0
time为0，没有时间，不计算后面的数。
time不为0，有时间，需要计算后面的数。
再分析n参数，从题目已知有两种可能n>1和n<1
n>1，数据会随time的变化而变化
n<=1,数据不会随time的变化而变化
最后分析time与n的关系
time与n有三种关系
time>n,会发生往复计数的情况。
time=n，会发生往复计数的情况，但结果一定是n-1啦。
time<n,不会发生往复计数的情况。
至此可以得到第一种解决方案
第一种解决方案数数法
按照先从1开始向右计数，到达n时调转方向向左计数的方法，这种方法不需要考虑time为0的情况，需要屏蔽n为0的情况，需要屏蔽n<=1的情况。
设置一个以time为参数的while循环，当time为0时退出循环，设置flag表明方向，1为向右，2为向左。设置i作为计数参数，程序开始时i为1向右计数，当i等于n时，flag变为-1,i向左计数。
需要注意的是，把n<2剔除。
class Solution {
public:
int passThePillow(int n, int time)
{
int i=1;
int flag=1;
if(n<2)
{
i=n;
}
else
{
while(time)
{
if(flag==1)
{
++i;
if(i==n)
{
flag=-1;
}
}
else if(flag==-1)
{
--i;
if(i==1)
{
flag=1;
}
}
--time;
}
}
return i;
}
};但是第一种思路很挫，非常挫，特别挫，作为代码狗，怎么能看得上这种思路呢，这种屎山代码呢，而且还没用到分析三，相当于刚才的分析白分析啦，不能忍啊，凸(艹皿艹 )。
第二种思路 除余法（厨余垃圾），这种方法也很垃圾
除余法的思路来自于在有限的线段下，除法的结果代表需要往复的次数，余的结果代表他还要走几次，举个栗子。
n=4,time=5
注意一下这里，time=5的意思是从5开始，走到0为止，体现在i上，是i要在1之后走出5步。上面的图表现出time=5时走出了一个往复，用除法体现5/3=1（这里必须是除3也就是n-1,因为向右前进时i只走了三步），剩下的两部5%3=2,所以n=4,time=5时,i走了一个往复，先向右走到4，然后调头走到2，这里的5/3=1的1表示的i走完一个全程（全程指的是1到4，或者4到1，不管方向，总之1代表走完一个全程，就是这样凸(艹皿艹 )这特么的这么难写，凸(艹皿艹 )啊）；
上面写了一段，总结一下就是5/3=1表示i走完一段全程，5%3=2表示走完全程之后再走两步。
确定上面的以后，需要判断方向，以5/3为例，走完一个全程，需要调头，这时候的方向是向左的。所以不能被2整除的此时是向左。
接下来以7/3为例
7/3等于2，此时已经走完两个全程，方向向右。
接下来的余就简单啦，当(time/(n-1))%2==0时，向右走，此时只需要1+time%(n-1)，相反(time/(n-1))%2!=0时向左走，用n-time%(n-1)就好了。
上面是time>n 的情况，接下来看看time=n的情况。
time=n表示走完一个全程多走一步，实际上也是一个全程以上的问题，可以归类到上面。
time<n这是一个没有走完全程的情况，不走完全程时，方向是向右的，那么完全可以带入多个全程的情况，(time/(n-1))%2==0。
接下来看看n,n分为<=1和>1两种情况，n<=1这种情况需要剔除，因为题目给的数从2开始，这个就不写了，也就一个if的事。
再接下来，就是time为0的情况，emmmmmm。。。。。time为0时，完全不影响i=1+time%(n-1);i=n-time%(n-1);计算的结果，所以这个题目的代码是
class Solution {
public:
int passThePillow(int n, int time)
{
int i=0;
if((time/(n-1))%2!=0)
{
i=n-time%(n-1);
}
else if((time/(n-1))%2==0)
{
i=1+time%(n-1);
}
return i;
}
};不用循环，但是懒得想，厨余垃圾啊
最后看一下官方题解，目前么想明白
我们注意到每经过 2×(n−1)2 \times (n - 1)2×(n−1) 的时间，枕头会被传递回起点，所以我们可以直接用 time\textit{time}time 对 2×(n−1)2 \times (n - 1)2×(n−1) 取模求余数。
如果 time<n\textit{time} < ntime<n，枕头没有传递到队尾，传递到 time+1\textit{time} + 1time+1。
如果 time≥n\textit{time} \ge ntime≥n，枕头已经传递过队尾，传递到 n−(time−(n−1))=n×2−time−1n - (\textit{time} - (n - 1)) = n \times 2 - \textit{time} - 1n−(time−(n−1))=n×2−time−1。