leetcode1344 钟面追及本寻常,惊觉快慢指针藏

🎮钟面追及本寻常,惊觉快慢指针藏

我盯着屏幕上村长新发来的任务卷轴,眉头皱得能夹死一只苍蝇。

“时钟指针的夹角……” 我念出声来,“给你两个数 hour 和 minutes,请返回在时钟上,由给定时间的时针和分针组成的较小角的角度?” 我揉了揉眼睛,把卷轴翻来覆去看了三遍,就……一个钟?

“村长是不是把我的智商当成了可以随便揉捏的面团?” 我把卷轴往桌上一拍,昨天把我甩到 4.5 PB 的虚空里找第 k 个字符,今天让我算钟表夹角?这跨度简直就像刚打完《艾尔登法环》的玛莲妮亚,突然被塞了一盘《宝宝巴士》。

窗外,那只掉毛的信鸽正好飞过,冲我咕咕叫了两声,语气里充满了“别高兴太早,这是暴风雨前的宁静”的意味。

我懒得理它,拉过椅子坐下,顺手把泡面推到一边。既然村长要考我小学数学,那我就用最优雅的姿态把这个签到题拿下——就当是给被逆推心法摩擦的脑子做个马杀鸡。

真·快慢指针

“经典的小学数学追及相遇问题——” 我拿起笔,在纸上画了一个圆,“只不过把直线轨道换成了圆形——分针一小时跑一圈,时针十二小时跑一圈。追及的两个‘人’换成了时针和分针,速度单位从‘米每秒’变成了‘度每分’。”

整个钟面 360 度,12 个大格,每个大格 30 度,60 个小格,每个小格 6 度。分针是个急性子,1 小时跑一圈 360 度,每分钟跑 6 度。时针是个摸鱼大师,1 小时才挪 30 度,每分钟挪 0.5 度。我轻松地吹了声口哨:“分针每分钟 6 度,时针每分钟 0.5 度,相对速度 5.5 度每分——”

等等。我盯着纸上的两个速度值——脑子里蹦出一个熟悉的画面。

“一个跑得快,一个跑得慢,还在同一个环形轨道上转悠……”我猛地一拍大腿,整个人从椅子上弹了起来,“这特么不就是真·快慢指针吗?!”

想当年刷链表题的时候,为了判环、找入环点,硬生生造了一个 fast 和一个 slow 在链表上赛跑,一个走两步一个走一步,while 循环里每轮都小心翼翼,生怕指针指飞了直接喜提 NullPointerException。

结果现在?人家物理引擎直接给你安排好了!分针就是那个 fast 指针,时针就是那个 slow 指针,它俩天然就在环形轨道上跑,连 while 循环都不用写,相对速度直接做减法就完事了。刷了那么多链表题,快慢指针的终极形态原来藏在钟面上。

“村长这波属于是跨界致敬了。”我轻快地笑了笑,在纸上写下计算公式。

以 12 点方向为 0 度基准:

  • 分针角度 = minutes * 6
  • 时针角度 = (hour % 12) * 30 + minutes * 0.5

那个 hour % 12 纯粹是我的强迫症,十二点当成零来处理,不然算出来是三百六十度,数学上没错,但脑子里总会冒出“这不转了一圈回到原点吗”的自我怀疑。

两针相减取绝对值,如果超过 180 度就用 360 减一下,取较小的那个角。

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        # 分针角度:每分钟6度
        min_degree = minutes * 6
        
        # 时针角度:每小时30度 + 每分钟0.5度
        hour_degree = (hour % 12) * 30 + minutes * 0.5
        
        # 两针夹角的绝对值
        diff = abs(hour_degree - min_degree)
        
        # 取较小角(不超过180度)
        return min(diff, 360 - diff)

点击提交,AC 几乎是在我眨眼的瞬间就弹了出来。

我靠在椅背上,盯着那个绿勾,突然感到一阵前所未有的空虚。没有熟悉的后脑勺崩,没有老勇者的灵魂拷问,连泡面都还没来得及坨。这也太简单了吧,简单到让人觉得有点敷衍。

但转念一想,村长这波跨界致敬还是挺有意思的——小学数学的皮,链表算法的魂。翻开魔法书,我在最新一页写下:

钟面追及本寻常,惊觉快慢指针藏。 寥寥几行破签到,难得泡面尚未凉

写完,我端起泡面,美美地嗦了一大口,享受着这难得的清静。

“砰!” 窗外又传来一声熟悉的闷响。

我条件反射地护住泡面碗,抬头一看——那只掉毛的信鸽又来了,嘴里叼着一张新的小纸条。我把纸条抽出来,上面是村长歪歪扭扭的字迹:“小白,今天热热身。明天再上强度。另外,鸽粮经费已经批了,但被我拿去抽卡了,你继续喂它点泡面。——村长”

“……” 我把纸条揉成一团,精准地投进了垃圾桶。

知识共享许可协议
本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。