【语法】
一、隐蔽陷阱
任务链按 next 映射逐格跳转,怀疑某条链绕回了旧节点。用 visited 表记录走过的节点能判环,2000 个节点的链就要 2000 份表内存;能不能只花两个变量就把环找出来?
二、底层原理
快慢指针从同一起点出发,慢的每步走 1 格,快的每步走 2 格。链无环,快的先到终点;链有环,两者先后入环,快的每追一圈把差距缩短 1 格,最多环长步内必然相遇。相遇即有环,全程只占 2 个变量,与链长无关。
三、正确代码
错误写法:
slow = nextOf(slow)
fast = nextOf(fast) -- 两个指针同速,永远追不上
正确写法:
local function hasLoop(start)
local slow = nextOf(start)
local fast = nextOf(nextOf(start))
while fast ~= nil and slow ~= fast do
slow = nextOf(slow)
fast = nextOf(nextOf(fast))
end
return fast ~= nil
end
-- 环长 6 的链:4 步后 slow 与 fast 落在同一点
四、引擎验证
构造一条 12 节点、末尾绕回第 7 节点的链,hasLoop 返回 true,相遇点走了 4 步;断开回边后返回 false,且快指针第 12 步到达 nil。
五、FAQ
问:快指针一次走 3 格行吗?
答:行,但可能在环上跨过慢指针,相遇步数变多,2 格是最省的稳定选法。
问:怎么顺带求环入口?
答:相遇后把一个指针放回起点,两指针同速再走,再次相遇处即入口。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、规则机制 隐蔽的坑:折叠列表收起分组时只把子项 setVisible(false),占位还留在原地,列表下半截…
【语法】 一、机制原理 一行代码拆解:a, b = b, a % b。最大公约数的辗转相除法:两数相除取余数,余数再与除数继…
【游戏】 一、规则机制 线上事故:聊天里 @ 了某人,消息混在普通流水里,对方根本没注意,集合迟到的锅全甩给没提醒。点名提醒…
【游戏】 一、规则机制 一行定骨架:text = LANG[cur][key] or LANG.zh[key]。多语言文案的…
【语法】 一、机制原理 抛个坑:模板"$(name),您的$(item)已到账"这种带命名槽位的文案怎么填值?string.…
【游戏】 一、规则机制 抛个坑:横屏竖屏一切界面,控件坐标全按竖屏摆,一旋转错位满屏——适配该怎么做?两条策略配合:界面元素…