0%

面试算法复盘

面试算法都很简单,感觉准备的太多了,面试的时候疯狂引导面试官多问我算法,因为别的也不太会。

二分、快排

二叉树最大深度:

1
2
3
4
5
6
int dfs(TreeNode *root) {
if(!root) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
return max(l, r) + 1;
}

字符串最长无重复字符字串长度:

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
int n = s.size(), i=0, j=0, res=0;
unordered_map<char,int> vis;
while(i<n && j<n){
vis[s[i]]++, i++;
while(j<i && vis[s[i-1]] > 1) vis[s[j]]--, j++;
res = max(res, i-j);
}
return res;
}

手写最小堆:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int heap[1000010];
int n, sz=0;

void up(int x) {
while(x / 2 && heap[x] < heap[x / 2]) {
swap(heap[x], heap[x / 2]);
x /= 2;
}
}

void down(int x) {
int t = x;
if(2 * x <= sz && heap[2 * x] < heap[t]) t = 2 * x;
if(2 * x + 1 <= sz && heap[2 * x + 1] < heap[t]) t = 2 * x + 1;

if(x != t) {
swap(heap[x], heap[t]);
down(t);
}
}

void push(int x){
heap[++sz] = x;
up(sz);
}

void pop(){
heap[1] = heap[sz--];
down(1);
}
int main(){
cin>>n;
while(n) {
int op;
scanf("%d", &op);
if(op == 1) { // 插入
int x;
scanf("%d", &x);
push(x);
}
else if(op == 2) printf("%d\n",heap[1]); //打印堆中最小值
else pop(); // 删除最小值
n--;
}
return 0;
}