2024秋招速腾聚创笔试记录(2023.9.4)

编程题

跳跃游戏

https://leetcode.cn/problems/jump-game/

迷宫找最短路径

https://blog.csdn.net/weixin_46846304/article/details/116125437

问答题

1 手写点云欧式聚类

写一个函数实现点云欧式聚类，类内最大距离为ClusterTolerance，类内最少点数为MinClusterSize

点和点云的结构：

struct Point{
    double x;
    double y;
    double z;
};

struct PointCloud{
    std::vector<Point> points;
    int size;
};

参考pcl中欧式聚类的方法：

(1)先把点云存成kd-tree

(2)初始化一个空类cluster，和一个空队列Q

(3)取一个未分类的点加入队列。

(4)推出队列的第一个点加入类，找所有离这个点距离小于d且未处理过的点加入队列。重复直到队列为空

(5)判断cluster的点数是否足够。足够则保留这个类。返回第（2）步

(6)直到所有点都处理过后结束。

2 求两个坐标系的旋转矩阵

A坐标系x轴朝上，y轴向前，z轴朝左。B坐标系x轴向前，y轴向左，z轴朝上。求A坐标系到B坐标系的旋转矩阵。

首先注意到坐标系是左手坐标系，因此旋转的正方向可以用左手判断。从A到B相当于绕z轴转90度，再绕x轴转90度

\[R = R(Z)R(Y)R(X) = \left[ \begin{matrix} 0& 1& 0 \\ -1& 0 & 0 \\ 0& 0& 1 \end{matrix}\right] \left[ \begin{matrix} 1& 0& 0 \\ 0& 0 & 1 \\ 0& -1& 0\ \end{matrix}\right] \]

3 拟合平面方程

已知n个点\(P_i,i=0,1,...,n-1\)，坐标为\((x_i, y_i, z_i)\)。拟合成平面Ax+By+Cz+D=0.

（1）求最小二乘解的函数形式

\[f=\sum_{i=0}^n(Ax_i+By_i+Cz_i+D)^2\]

（2）求平面的最小二乘解

令\(f'_A=0, f'_B=0, f'_C=0, f'_D=0\)，解方程，具体形式在此处不推导了

（3）若求出平面为Ax+By+Cz+D=0，如何计算该平面与z=(0,0,1)方向的旋转

平面法向量为\(\vec{p}=(A,B,C)\)

\[\vec{n} = \vec{z} \times \vec{p} \] \[R = cos\theta + (1-cos(\theta)\vec{n}\vec{n}^T)+sin\theta n^\wedge\]