Slient2009

All I need is Twin Island Milk

两个面试算法题

投稿日 編集日

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

字节跳动-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