2026-08-18得到目标点的最少代数。用go语言你有若干个三维空间中的整数点每个点由三个坐标 (x, y, z) 表示。初始时这些点构成第 0 代。之后每一代你从所有已经存在的点中选择两个不同的点坐标不能完全相同计算它们坐标的平均值并对每个坐标分别向下取整得到一个新点。这些新点共同组成新一代。所有新点是在同一时间生成的并且生成后立即可以被用于后续的生成过程。现在给定一个目标点问最早在哪一代会出现这个目标点。如果它一开始就存在返回 0如果永远无法生成返回 -1。1 points.length 20。points[i] [xi, yi, zi]。0 xi, yi, zi 6。target.length 3。​​​​​​​0 target[i] 6。初始点集合不包含重复项。输入 points [[0,0,0],[6,6,6]], target [3,3,3]。输出 1。解释第 0 代 初始 points [[0, 0, 0], [6, 6, 6]]。target [3, 3, 3] 不存在于第 0 代中。第 1 代 对于第 0 代中的每一对点我们创建新的点。使用 [0, 0, 0] 和 [6, 6, 6]我们生成 [3, 3, 3]。第 1 代之后points [[0, 0, 0], [6, 6, 6], [3, 3, 3]]。target [3, 3, 3] 在第 1 代中被找到因此最小的 k 为 1。题目来自力扣3923。整体过程描述1. 初始化第 0 代将输入的points数组中的所有点存入一个集合或映射中作为第 0 代。集合的作用是去重因为题目保证初始点没有重复但后续生成过程中可能会产生重复点集合可以自动去除重复。目标点也转换为同样的表示形式方便后续比较。2. 逐代生成新点从第 0 代开始进行循环每一轮代表一代2.1 检查目标点首先检查当前代的点集合中是否已经包含目标点。如果包含直接返回当前代数第 0 代返回 0第 1 代返回 1以此类推。2.2 生成下一代如果目标点不在当前代中则开始生成下一代。复制当前代的点集合作为下一代的基础下一代包含上一代的所有点因为旧点会保留。遍历当前代中的所有点对允许同一个点与自身配对但代码中实际是双重循环遍历集合中的所有点包括相同点不过题目要求两个不同点这里代码实现上可能稍宽松但根据题意如果两点坐标相同生成的还是同一个点不会有新贡献。对于每一对点p和q计算新点的三个坐标新 x (p.x q.x) 整除 2新 y (p.y q.y) 整除 2新 z (p.z q.z) 整除 2这里整除是向下取整对于非负整数来说就是普通整数除法。将新点加入下一代集合中。由于集合自动去重最终下一代集合包含了所有上一代点以及所有新生成的点。2.3 判断是否继续比较下一代集合的大小与当前代集合的大小。如果两者大小相同说明这一代没有产生任何新的点所有可能的平均值点都已经在上一代中存在那么再往后也不会有新点出现目标点不可能再出现返回 -1。如果下一代集合更大说明有新的点产生将当前代更新为下一代代数加 1继续循环。3. 终止条件循环只有在两种情况下结束找到目标点返回对应代数。无法产生新点且目标点未找到返回 -1。复杂度分析时间复杂度设初始点数量为n题目限制n 20。每一代中点对枚举需要O(m^2)的时间其中m是当前代点集合的大小。由于坐标范围被限制在0到6之间题目给定的范围整个三维空间中的可能点数量是有限的最多为7 * 7 * 7 343个点。因此随着代数增加点集合大小m最多增长到 343 后就不再增长或很快饱和。在最坏情况下每一代都需要遍历所有m个点的所有点对复杂度为O(m^2)。因为m上界是 343所以单代复杂度上界是O(343^2) O(117649)这是一个常数级的上界。代数数量也不会无限增加因为点集合大小有限最多经过343 - n次增长后就会停止每次增长至少增加 1 个点。所以总的时间复杂度在最坏情况下是O(343^2 * 343)级别但实际远小于这个值因为通常不会每一代都达到最大点集。从渐进角度看由于坐标范围固定可以认为是常数时间如果推广到一般情况坐标范围很大则时间复杂度会与坐标空间大小有关但本题中坐标范围固定所以整体是O(1)常数级。更准确地若以V表示所有可能点的数量本题中V 343则时间复杂度为O(V^3)以内但实际操作中远低于此。额外空间复杂度主要使用两个集合当前代和下一代每个集合最多存储V个点V 343。每个点存储三个整数空间占用常数。因此额外空间复杂度为O(V)即O(343)也是常数级。如果推广到坐标范围较大的情况额外空间为O(V)其中V是三维坐标空间中所有可能点的数量。总结算法核心是模拟“逐代生成”的过程利用集合去重和有限坐标空间的特性保证循环能终止。由于坐标范围很小0~6整体时间和空间复杂度都是常数级实际运行效率很高。Go完整代码如下packagemainimport(fmtmaps)funcminGenerations(points[][]int,target[]int)int{typepointstruct{x,y,zint}tar:point{target[0],target[1],target[2]}cur:make(map[point]struct{},len(points))for_,p:rangepoints{cur[point{p[0],p[1],p[2]}]struct{}{}}forans:0;;ans{if_,ok:cur[tar];ok{returnans}nxt:maps.Clone(cur)forp:rangecur{forq:rangecur{// 枚举 cur 中的所有点对 (p, q)nxt[point{(p.xq.x)/2,(p.yq.y)/2,(p.zq.z)/2}]struct{}{}}}iflen(nxt)len(cur){// 没有产生新的点return-1}curnxt}}funcmain(){points:[][]int{{0,0,0},{6,6,6}}target:[]int{3,3,3}result:minGenerations(points,target)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmin_generations(points,target):tartuple(target)curset()forpinpoints:cur.add(tuple(p))ans0whileTrue:iftarincur:returnans nxtset(cur)cur_listlist(cur)# 枚举所有点对 (p, q)foriinrange(len(cur_list)):forjinrange(len(cur_list)):pcur_list[i]qcur_list[j]new_point((p[0]q[0])//2,(p[1]q[1])//2,(p[2]q[2])//2)nxt.add(new_point)iflen(nxt)len(cur):# 没有产生新的点return-1curnxt ans1# 测试if__name____main__:points[[0,0,0],[6,6,6]]target[3,3,3]resultmin_generations(points,target)print(result)C完整代码如下#includeiostream#includevector#includeset#includetupleusingnamespacestd;intminGenerations(vectorvectorintpoints,vectorinttarget){// 使用 tuple 表示三维点usingPointtupleint,int,int;Point tarmake_tuple(target[0],target[1],target[2]);setPointcur;for(autop:points){cur.insert(make_tuple(p[0],p[1],p[2]));}for(intans0;;ans){if(cur.find(tar)!cur.end()){returnans;}setPointnxtcur;// 复制当前集合// 枚举所有点对 (p, q)for(autop:cur){for(autoq:cur){Point new_pointmake_tuple((get0(p)get0(q))/2,(get1(p)get1(q))/2,(get2(p)get2(q))/2);nxt.insert(new_point);}}if(nxt.size()cur.size()){// 没有产生新的点return-1;}curnxt;}}intmain(){vectorvectorintpoints{{0,0,0},{6,6,6}};vectorinttarget{3,3,3};intresultminGenerations(points,target);coutresultendl;return0;}