 表示。初始时这些点构成第 0 代。 之后每一代，你从所有已经存在的点中，选择)
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("fmt""maps")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.x+q.x)/2,(p.y+q.y)/2,(p.z+q.z)/2}]=struct{}{}}}iflen(nxt)==len(cur){// 没有产生新的点return-1}cur=nxt}}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):tar=tuple(target)cur=set()forpinpoints:cur.add(tuple(p))ans=0whileTrue:iftarincur:returnans nxt=set(cur)cur_list=list(cur)# 枚举所有点对 (p, q)foriinrange(len(cur_list)):forjinrange(len(cur_list)):p=cur_list[i]q=cur_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-1cur=nxt ans+=1# 测试if__name__=="__main__":points=[[0,0,0],[6,6,6]]target=[3,3,3]result=min_generations(points,target)print(result)C++完整代码如下：
#include<iostream>#include<vector>#include<set>#include<tuple>usingnamespacestd;intminGenerations(vector<vector<int>>&points,vector<int>&target){// 使用 tuple 表示三维点usingPoint=tuple<int,int,int>;Point tar=make_tuple(target[0],target[1],target[2]);set<Point>cur;for(auto&p:points){cur.insert(make_tuple(p[0],p[1],p[2]));}for(intans=0;;ans++){if(cur.find(tar)!=cur.end()){returnans;}set<Point>nxt=cur;// 复制当前集合// 枚举所有点对 (p, q)for(auto&p:cur){for(auto&q:cur){Point new_point=make_tuple((get<0>(p)+get<0>(q))/2,(get<1>(p)+get<1>(q))/2,(get<2>(p)+get<2>(q))/2);nxt.insert(new_point);}}if(nxt.size()==cur.size()){// 没有产生新的点return-1;}cur=nxt;}}intmain(){vector<vector<int>>points={{0,0,0},{6,6,6}};vector<int>target={3,3,3};intresult=minGenerations(points,target);cout<<result<<endl;return0;}
