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

2023-12-13 23:24:19

第一题

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。

文章来源:https://blog.csdn.net/zhangsankuangtu/article/details/134853825
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。