阿里巴巴笔试
题型为:编程题($2$ 道)。
编程题 1
题意描述
给定一个数组 $nums$($1 \leq nums[i] < 2^{32}$), 找出某一位($0 \sim 30$),使得该比特位上满足所有数组元素在该位置全为 $1$,有多个答案则输出最低位(序号从 $1$ 开始),不存在则输出 $-1$。
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<unsigned int> a(n, 0);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int res = -1; // 初始化为 -1,表示不存在合理的答案
for (int i = 30; i >= 0; i--) {
bool flag = true;
for (int j = 0; j < n; j++) {
if (a[j] >> i & 1) {
continue;
} else {
flag = false;
break;
}
}
if (flag) {
res = i + 1;
}
}
cout << res << endl;
}
return 0;
}
编程题 2
题意描述
给定一个矩阵 $A$,一共有 $6$ 个操作,分别是:
- 交换矩阵的行(第一行与最后一行交换,第二行与倒数第二行交换,…);
- 交换矩阵的列(第一列与最后一列交换,第二列与倒数第二列交换,…);
- 顺时针$90$ 度旋转矩阵中的元素;
- 逆时针$90$ 度旋转矩阵中的元素;
- 将矩阵分为四个小矩阵,矩阵维度为 $n / 2 * m / 2$,顺时针交换小矩阵的位置;
- 将矩阵分为四个小矩阵,矩阵维度为 $n / 2 * m / 2$,逆时针交换小矩阵的位置;
C++ 部分代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, r;
vector<vector<int>> a;
vector<int> nums; // 执行的操作
void op1(vector<vector<int>>& a) {
int i = 0, j = n - 1;
while(i < j) {
swap(a[i], a[j]);
i++, j--;
}
}
void op2(vector<vector<int>>& a) {
int i = 0, j = m - 1;
while(i < j) {
for (int k = 0; k < n; k++) {
swap(a[k][i], a[k][j]);
}
i++, j--;
}
}
void op3(vector<vector<int>>& a) {
swap(n, m);
vector<vector<int>> tmp = vector<vector<int>>(n, vector<int>(m, 0));
}
void op4(vector<vector<int>>& a) {
}
void op5(vector<vector<int>>& a) {
}
void op6(vector<vector<int>>& a) {
}
int main() {
cin >> n >> m >> r;
a = vector<vector<int>>(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
nums = vector<int>(r, 0);
for (int i = 0; i < r; i++) {
cin >> nums[i];
}
int j = 0;
while (r--) {
if (nums[j] == 1) {
op1(a);
} else if (nums[j] == 2) {
op2(a);
} else if (nums[j] == 3) {
op3(a);
} else if (nums[j] == 4) {
op4(a);
} else if (nums[j] == 5) {
op5(a);
} else {
op6(a);
}
j++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
深信服笔试
题型为:多选题,填空题,编程题($2$ 道)。
多选题、填空题主要设计 C
以及 C++
基础知识。
编程题 1
题意描述
某厨师要出售 $1 \text{~} 6$ 种不同的食物,每种食物需要使用不同的厨具进行烹饪,厨师的灶台最多容纳 $3$ 种厨具,当灶台空间不够时,厨师会更换最久没有使用的厨具。已知每种食物烹饪需要 $15$ 分钟,如果需要更换厨具则每次需要 $6$ 分钟的厨具更换时间。按照点单顺序计算本轮烹饪食物需要花费的总时间。(要求 $C$ 语言实现)
输入
每行一个数字,1-6 代表 6 种订单,7 表示本轮烹饪结束。
2 2 5 6 4 2 4 6 5 2 3 3 3 3 4 6 1 5 1 1 7
输出
厨师所需的总时间
354
模拟
本题只需要考虑清楚所分析问题的全部情况,并维护队列内元素的有序性。
C 语言代码实现
#include<stdio.h>
#include<string.h>
typedef long long LL;
#define N 3
int q[N], head, tail = -1;
LL res;
int flag = 0; // 0:队列未满, 1:队列已满
int main() {
int t;
while(scanf("%d", &t) && t != 7) {
// 判断队列中是否有重复元素
for (int i = head; i <= tail; i++) {
if (t == q[i]) {
flag = 0;
}
}
if (flag == 0) {
int count = tail - head + 1; // 当前队列中元素数量
if (count == 0) {
q[++tail] = t;
}
else if (count == 1) {
if (t != q[0])
q[++tail] = t;
} else if (count == 2) {
if (t != q[0] && t != q[1]) {
q[++tail] = t;
} else if (t == q[0]) {
q[0] = q[1];
q[1] = t;
}
} else if (count == 3) {
if (q[0] == t) {
q[0] = q[1];
q[1] = q[2];
q[2] = t;
} else if (q[1] == t) {
q[1] = q[2];
q[2] = t;
}
}
res += 15;
if (tail == 2) {
flag = 1; // 队列已经满
}
} else { // 维护队列有序性
q[0] = q[1];
q[1] = q[2];
q[2] = t;
res = res + 21;
}
}
printf("%d\n", res);
return 0;
}
编程题 2
LC 原题链接:63. 不同路径 II
动态规划
本题是 LC 原题,分析清楚状态转移过程即可。
C++ 语言代码实现
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int n, m;
int main() {
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
vector<vector<int>> f(n, vector<int>(m, 0));
// 边界处理:第一行
for (int i = 0; i < m; i++) {
f[0][i] = 1;
if (matrix[0][i] == 1) {
f[0][i] = 0;
break;
}
}
// 边界处理:第一列
for (int i = 0; i < n; i++) {
f[i][0] = 1;
if (matrix[i][0] == 1) {
f[i][0] = 0;
break;
}
}
// 从左边来,从上面来
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
f[i][j] = f[i][j - 1] + f[i - 1][j];
if (matrix[i][j] == 1) {
f[i][j] = 0;
}
}
}
cout << f[n - 1][m - 1] << endl;
return 0;
}
友塔笔试
编程题 1
编程题 2
题意:图中有 $n$ 个节点,判断图中是否有循环依赖关系。
编程题 3
类似完全背包问题,不过要求的是可以装满背包(可以超过),但是所得到的价值最小的方案。输出最小价值。