刷题记录--算法--简单

第一题

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。