两个面试算法题

记录两个在面试过程中遇到的题目。

字节跳动-IP限制

类似题目:https://www.nowcoder.com/questionTerminal/8389e1ccd47d40ba859c2497a428d0ca

给出含有大量的IP地址的列表,再进行多次IP询问,返回当前IP是否在列表中出现过。
牛客网上有相似的题目,增加了IP段的记录,这里就实现稍难的版本。

image-20210816204035423

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入
5 3
222.205.58.16
*.58.16
222.205.58.*
*.16
224.*
222.205.58.17
222.205.59.19
223.205.59.16

输出
1 0 1

说明
由于222.205.58.17这个IP匹配到222.205.58.*这条过滤规则,
222.205.59.19没有匹配到任何过滤规则,
223.205.59.16匹配到*.16这条过滤规则,
所以输出1 0 1

比较简单的实现方法是使用HashMap或者类似的结构,比较无脑,但是显然面试官不大想看到这样的做法。
于是反手掏出字典树来实现,每个节点有256个子节点。

这里的通配符*有前驱和后继两种形式,再加上普通的IP地址形式,总共可以分为三类IP地址。
所以我对应建了三棵树,普通IP全匹配,通配符在后的匹配前缀,通配符在前的先逆序一下,转换为匹配前缀的问题。
事实上前缀匹配可以看作是全匹配的特殊形式,所以在插入和查询的时候,这两类问题合在一起完成。

对于字典树的节点,首先是动态添加节点,每个节点包含指向256个子节点的指针数组,和一个bool值标记从根到当前节点是否为一个被记录过的IP段,可以及时返回查询IP是否在目标范围中。
扫描树节点的时候,先检查标记看看当前是否在一个记录过的IP端中,在则返回true;然后检查是否有对应的子节点,没有则返回false;接着再去子节点,能扫完树说明也在目标IP范围内,返回true。

另外,我觉得对于字符串的处理稍微有点儿麻烦。这里把*映射为-1,并补全IP为4位,再调整对齐。
代码如下:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
string str;
struct node{
node *kids[255];
bool full;
};

class Tire{
public:
node *root;
Tire(){
root = (node *)malloc(sizeof(node));
root->full=false;
memset(root->kids, 0, sizeof(root->kids));
}

vector<int> getNum(string s){
vector<int> ret = {-1,-1,-1,-1};

int dotCnt=0;
int ind=0, pre=0;
for(int i=0;i<s.length();i++){
if(s[i]=='.'){
ret[ind++]=pre<0?-1:pre;
pre=0;
}
else if(s[i]=='*'){ pre=-1;}
else{
pre = pre*10 + s[i]-'0';
}
}
ret[ind]=pre;

if(s[0] =='*'){
for(int i=3;i>=0;i--){
ret[i] = (i-(3-ind))<0?-1:ret[i-(3-ind)];
}
}

return ret;
}

void insert(vector<int> ip){
node *now = root;
node *pre = now;

for(int i=0;i<4;i++){
if(ip[i]==-1){
now->full=true;
return;
}
else{
if(now->kids[ip[i]]==NULL){
node *n = (node *)malloc(sizeof(node));
memset(n->kids, 0, sizeof(n->kids));
n->full=false;
now->kids[ip[i]] = n;
pre=now;
now=n;
}
else{
pre=now;
now=now->kids[ip[i]];
}
}
}
}

bool query(vector<int> ip){
node *now = root;
node *pre = now;
for(int i=0;i<4;i++){
if(now->kids[ip[i]]==NULL){
return false;
}
else if((now->kids[ip[i]])->full){
return true;
}
else{
pre=now;
now=now->kids[ip[i]];
}
}
return true;
}
};

int main()
{
Tire fullTire, preTire, postTire;

cin>>n>>m;
while(n--){
cin>>str;
vector<int>v = fullTire.getNum(str);
if(v[0]==-1){
reverse(v.begin(), v.end());
postTire.insert(v);
}
else if(v[3]==-1) preTire.insert(v);
else fullTire.insert(v);
}

while(m--){
cin>>str;
vector<int>v = fullTire.getNum(str);

int ans=0;

ans|=preTire.query(v);
ans|=fullTire.query(v);
reverse(v.begin(), v.end());
ans|=postTire.query(v);

cout<<ans<<endl;
}
return 0;
}

阿里云-大鱼吃小鱼

在线OJ:http://www.51nod.com/Challenge/Problem.html#problemId=1289

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?
输入

第1行:1个数N,表示鱼的数量(1 <= N <= 100000)。
第2 ~ N+1行:每行两个数A[i], B[i],中间用空格分隔,分别表示鱼的大小及游动的方向(1 <= A[i] <= 10^9,B[i] = 0或1)。

输出

输出1个数,表示最终剩下的鱼的数量。

输入样例
5
4 0
3 1
2 0
1 0
5 0

输出样例
2

这个题主要是理解的问题,即如何简化分析,我一开始也没头绪,并且导致面试时写错(不知道面试官看出来没有)。
之后后台我想到了这个:

image-20210816211315081

只需要把向右移动的鱼看作坚果墙,把向左移动的鱼看作僵尸,坚果墙随时添加,僵尸随时出现,要么墙被啃烂,要么僵尸被干掉。
活着的鱼的数量等于剩下来的坚果和吃到脑子的僵尸数量。(略显无聊的转换……)

用栈只维护向右移动的鱼,记录鱼的大小。对于新的鱼,比较方向。向右即添加。向左则和栈顶比较,大于栈顶退栈一次,小于栈顶则扫描下一条鱼。如果栈被退空,则表示有一条鱼游到了左侧,数目+1。

需要注意的是,题目限定鱼的大小均不一样,所以不会出现旗鼓相当的鱼,但是面试的时候要求考虑。
对于大小相同的鱼,肯定不会出现一方被另一方吃掉的情况,所以要么碰撞后各自掉头,要么擦肩而过,但是这两种情况的表现都是一样的。(类似于刘汝佳-蓝书-思维的体操-木棍上的蚂蚁一题)。
因此,我的处理方法是:对于两条等大相碰的鱼,先把栈顶的鱼退出来记录好,然后让向左移动的鱼去与栈里的其他鱼比较。在该鱼游到左侧,或是止步于更大的鱼之后,再把原先退栈出来的重新入栈。

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
#include<cstdio>
#include<stack>
using namespace std;
int n, ans=0;
stack<int>S;
int main()
{
scanf("%d", &n);
while(n--){
int s,d;
scanf("%d%d",&s, &d);
if(S.empty()){
if(d==0) ans++;
else S.push(s);
}
else{
if(d==1){
S.push(s);
}
else{
while(!S.empty()){
if(S.top() < s){ S.pop();}
else if(S.top() == s){
ans++;
S.pop();
}
else{
break;
}
}
if(S.empty()) ans++;
}
}
}
printf("%d\n", S.size() + ans);
return 0;
}

Welcome to my other publishing channels