2021春招-tx后台开发二面
上来做了三个题,都是字符串,然后都A了,所以后面基本没问,就问了两个问题:
1.TCP三次握手,以及为什么不是两次
2.主键索引/非主键索引的叶子节点存储的内容(这个答的不好
三个字符串的题,第一个题直接暴力,问string数组的最长公共前缀是什么
第二个题双指针,求字符串中不含重复字符的最长字串
第三个也是双指针,求完美子串的个数,完美字串就是字串中包含整个字符串中出现过的所有字符(也就是说出现次数最少也要为1)
第二个题双指针,求字符串中不含重复字符的最长字串
第三个也是双指针,求完美子串的个数,完美字串就是字串中包含整个字符串中出现过的所有字符(也就是说出现次数最少也要为1)
好多人问第三题解法,我在这里发一下qaq,写的不好,有更好的做法可以一起分享下:
#include <bits/stdc++.h> using namespace std; unordered_map<char,int> m; unordered_set<string> cntset; string s; int cnt; int l=0,r=0; int al[26]; int main() { cin>>s; for(char c:s) if(m[c]==0) {m[c]++;cnt++;} int curcnt=0; while(r<s.size()){ if(al[s[r]-97]==0){ al[s[r]-97]++; curcnt++; if(curcnt==cnt) {cntset.insert(s.substr(l,r-l+1));} r++; } else{ al[s[r]-97]++; if(curcnt==cnt){ while(l<r){ al[s[l]-97]--; if(al[s[l]-97]==0){ curcnt--;l++;break; } else{ cntset.insert(s.substr(l,r-l+1));l++; } } } else{ r++; } } } cout<<cntset.size(); return 0; }