2021网易实习生笔试题（一场计算机视觉、一场数据研发后端） 计算机视觉.pdf

计算机视觉笔试题解析 本文将对2021网易实习生笔试题（一场计算机视觉、一场数据研发后端）中的计算机视觉算法岗笔试题进行解析。该笔试题共有四道题，分别是找最大公约数、电影票座位安排问题等。 题目一：找最大公约数 该题目要求找出一个最大的正整数d，使得对于所有i，a[i+1]-a[i]是d的倍数，即a[i+1]-a[i]=d×k(k≥1)。输出：若d不存在输出-1，否则输出最大的d。 分析：首先需要计算所有差值，然后对这些差值进行排序，如果最小值小于1那么必然不存在d，如果大于1则求所有差值的最大公约数（gcd）。最后输出最大公约数d。 代码实现： ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; long long a[200010]; long long cha[200010]; long long gcd(long long a, long long b){ return b ? gcd(b, a%b) : a; } int main(){ cin >> n; for (int i = 0; i < n; i++){ cin >> a[i]; if (i) cha[i-1] = a[i] - a[i-1]; } sort(cha, cha + n-1); if (cha[0] < 1) cout << -1 << endl; else { long long ans = cha[0]; for (int i = 1; i < n-1; i++) ans = gcd(ans, cha[i]); cout << ans << endl; } return 0; } ``` 题目二：电影票座位安排问题 该题目要求找出所有可能的座位安排方式，保证每个同学都有座位，并且满足关系差的同学不能坐一起。输出：每行输出一组解，按照字典序输出，相邻编号用空格隔开。 分析：由于数据量非常小，可以使用深搜回溯法来解决问题。具体来说，可以使用深搜回溯法来生成所有可能的座位安排方式，并且使用标记数组来记录已经排过位置的同学。 代码实现： ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; int n, k; vector<vector<int> > v; int vis[10]; void dfs(int index, int cnt, vector<int>& now){ if (cnt == n){ for (int i = 0; i < now.size(); i++){ if (i) cout << " "; cout << now[i]; } cout << endl; return; } for (int i = 1; i <= n; i++) if (!vis[i]){ int flag = 1; for (int j = 0; j < v[index].size(); j++) if (v[index][j] == i) { flag = 0; break; } if (flag){ vis[i] = 1; now.push_back(i); dfs(i, cnt+1, now); now.pop_back(); vis[i] = 0; } } } ``` 计算机视觉笔试题涵盖了算法、数据结构、搜索等多个方面，要求考生具备广泛的计算机视觉知识和编程能力。