盘点今年秋招那些“送命”的算法面试题
盘点今年秋招那些“送命”的算法面试题
正文
秋天到了，一场面试一场凉…
随着 2019 年校招结束，“金九银十”的跳槽季也已经接近尾声，不知道在裁员、消减HC、只招中高级岗位等等“悲观”情绪下，你是否已经如愿入职心意的企业？或者还是准备蜷缩过冬厚积薄发？
多年以来，在技术面试中，算法面试已然成为进入大公司必须迈过的一道坎，候选人不仅要向面试官展示自己的算法基本功，还要展示出过人的思维能力和代码编写能力，才可能拿到更丰厚的 Package。
下面精选了几道今年秋招一线大厂和独角兽公司在面试候选人时考察的经典算法题目，你可以先花几分钟思考一下题目，列出几种不同的解法，再分别考虑一下复杂度，最后给出一个最优解。
也欢迎你在文章后面留言，写写你的解法，和大家一起讨论。
顺时针螺旋矩阵
题目描述
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]示例 2：
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]题目解析
这道题目看上去虽然没有涉及复杂的数据结构或者高级的算法，但实际在写代码的过程中会包含多个循环，需要判断多个边界条件，并且在写之前从思维层面一定要先考虑清楚，形成清晰思路，避免出现做题时“一看就会，一写就废”的情况。
这道题的核心思想是，由起点坐标、方向、位移可以定义矩阵中的唯一一条线段，并且可知当前路径下的所有坐标；而螺旋的过程可以抽象为访问多条首尾相连的线段，并且这些线段有如下特征：
- 起点坐标可知：因为多条路线首尾相连，所以下一个线段的起点为上一个线段的尾巴。
- 方向可知：总是按照向右、 向下、 向左、 向上循环切换。
- 位移可知：横向位移为矩阵的宽度、纵向位移为矩阵的高度，并且总是可以根据当前线段的方向，修正之后矩阵的参数。
- - 横向：高度-1
- - 纵向：宽度-1
- 总位移与矩阵的面积相等。
通过这些抽象条件，我们可以根据初始起点坐标、方向、位移，螺旋得到矩阵中所有坐标。
代码实现
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int height = matrix.length, width = height == 0 ? 0 : matrix[0].length;
int size = height * width;
int[] dirX = {0, 1, 0, -1};
int[] dirY = {1, 0, -1, 0};
// 初始化起点坐标:(0,-1) 方向:向右;
int x = 0, y = -1, dir = 0;
for (int step, total = 0; total < size; total += step) {
// 根据方向得到对应的位移, 并修正此后矩阵的参数(此后线段的长度)
if (dir == 0 || dir == 2) {
step = width;
height--;
} else {
step = height;
width--;
}
// 此前确定了起点坐标、方向和位移, 就可以得到当前线段的所有坐标,并输出到结果集;
for (int i = step; i > 0; i--) {
x += dirX[dir];
y += dirY[dir];
result.add(matrix[x][y]);
}
// 调整下一条线段方向
dir = ++dir % 4;
}
return result;复杂度分析
- 时间复杂度：O(N2)，其中 N 是输入矩阵所有元素的个数。
- 空间复杂度：O(N)，存储结果集 result 。
基本计算器
题目描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，“+， - ，*，/” 四种运算符和空格。整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7示例 2:
输入: " 3/2 "
输出: 1示例 3:
输入: " 3+5 / 2 "
输出: 5题目解析
这道题由于存在运算优先级，首先可以想到使用一个栈来保存数字。
- 如果数字之前的符号是加或减，那么就把当前数字压入栈中；
- 如果之前的符号是乘或除，那么就从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中。
这里需要注意，减法是通过加入当前数字的相反数来实现。这样完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了。
代码实现
class Solution {
public:
int calculate(string s) {
// 有个测试用例 int 型会超范围
long n = s.size(), num = 0, result = 0;
// 假设第一个运算符为+，即第一个数直接入栈
char op = '+';
stack<int> nums;
for(int i=0;i<n;++i){
// 是数字
if(s[i]>='0'){
num = num*10+s[i]-'0';
}
// 是运算符或最后一个数字
if((s[i]<'0'&&s[i]!=' ') || i==n-1){
if(op == '+') nums.push(num);
if(op == '-') nums.push(-num);
if(op == '*' || op == '/'){
int temp = (op == '*') ? nums.top()*num : nums.top()/num;
nums.pop();
nums.push(temp);
}
op = s[i];
num = 0;
}
}
// 计算结果
while(!nums.empty()){
result += nums.top();
nums.pop();
}
return result;
}
};复杂度分析
- 时间复杂度：O(N)，其中 N 是输入矩阵所有元素的个数。
- 空间复杂度：O(N)，主要是栈占用的容量。
比特位计算
题目描述
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]示例 2:
输入: 5
输出: [0,1,1,2,1,2]题目解析
这题的解题思路在于，对于所有数字来说，只分为奇数和偶数，关键是在二进制数中找到奇数和偶数的区别。
对于二进制数来说，奇数一定比它前一个偶数多一个最低位的1；而偶数中1的个数一定和它除以2的数是一样多的，因为最低位都是 0。
举个例子：
十进制 | 二进制 |
|---|---|
0 | 0 |
1 | 1 |
2 | 10 |
3 | 11 |
4 | 100 |
6 | 110 |
8 | 1000 |
剩下只用考虑数字 0 的二进制数 1 的个数为 0 ，于是就可以根据奇偶性开始遍历计算了。
具体实现的时候，可以循环一次求两个值，所以要先根据 num 的奇偶性确定循环的范围，以避免最后一次循环只剩下一个数。
同样也要根据奇偶性来确定循环完之后，是否还剩下一个数没求 1 的位数。
代码实现
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num + 1);
res[0] = 0;
int n = num % 2 ? num - 1 : num;
for(int i = 1;i <= n;i++) {
res[i] = res[i-1] + 1;
i++;
res[i] = res[i / 2];
}
if(num % 2)
res[num] = res[n] + 1;
return res;
}
};复杂度分析
- 时间复杂度: O(N)，其中 N 为给定整数 num。
- 空间复杂度：O(N)，其中 N 为给定整数 num。
总结
如果对这些题目的解法没深入思考过，第一次看到题解可能有一种“从天上掉下来”的感觉，自己很难想得到。
其实对于算法面试来说，更多是需要提升自己的算法内功并且持续地训练。
在面试时可以尝试使用“四步切题法”，即
- 第一步：先和面试官沟通下题目的细节和边界条件，确保自己理解是正确的
- 第二步：想所有可能的解法，比较各种不同方法的时空复杂度，不要只想一种就开始写
- 第三步：开始写简洁的代码，注重编码习惯和 Code Style
- 第四步：选择多种测试样例考察边缘情况
腾讯云开发者
