华为笔试4.1场
问题1：
给个字符串，一个逻辑运算式子，有AND OR NOT逻辑运算，无括号。
比如a AND b OR c AND NOT d，问一个逻辑运算式子是否合法。
思路：字符串处理题，把AND和OR周围的字符串提出，分别判断他们是不是一个合法的逻辑表达式子（NOT x或者x）。
细节比较多，会io流操作的话用io流会好写一些，我不会，就只能打状态做了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 7;
char s[N];
int main() {
while(gets(s)) {
int isand = 1, isnot = 0, n = strlen(s), is1 = 1;
/* isand表示当前位置能不能摆and和or
* isnot表示当前位置能不能摆not
* 0表示可以，1表示不行
* is1表示目前是否存在中途就能判断不合法的情况
*/
string temp;
for(int i = 0; i <= n; i++) {
if(s[i] != ' ' && s[i] != '\0')temp += s[i];
else {
if(temp == "NOT") {
if(isnot) {
is1 = 0;
puts("0");
break;
}
else isnot = 1;
}
else if(temp == "AND" || temp =="OR") {
if(isand) {
is1 = 0;
puts("0");
break;
}
else isnot = 0, isand = 1;
}
else {
int legal = 1;
for(auto c : temp) {
if('a' <= c && c <= 'z');
else legal = 0;
}
if(!legal || !isand) {
is1 = 0;
puts("0");
break;
}
else isand = 0, isnot = 1;
}
temp = "";
}
}
if(is1) {
if(!isand && isnot)puts("1");
else puts("0");
}
}
return 0;
}
问题2：给定n个工号，问每个工号出现了几次，按照工号字典序输出。
思路：map+iterator就好了，考你会不会stl，如果不会可以手写AVL，我也不知道暴力能不能过。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
map<string, int> M;
map<string, int>::iterator it;
int n; cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
M[s]++;
}
for(it = M.begin(); it != M.end(); it++)
cout << it -> first << " " << it -> second << endl;
return 0;
}
问题3：给出若干个头文件的依赖，问某个头文件自己是否会间接的依赖自己，也就是循环依赖，如果会，输出所有的循环依赖可能（应该是这个意思吧）
思路：先把输入的东西处理一下，把头文件视作点，依赖关系视作边，跑dfs，找出这个点所在的所有环输出。
感觉没写错，不知道为什么最后20%死活过不去，如果有AC的大佬麻烦留个言教教我。
80%通过代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
char s[N];
vector<int> G[N], sta;
map<string, int> M;
vector<string> rM, msb;
int pool = 0;
int insta[N] = {0};
void addEdge(string s, string t) {
if(!M[s])M[s] = ++pool, rM.push_back(s);
if(!M[t])M[t] = ++pool, rM.push_back(t);
G[M[s]].push_back(M[t]);
}
void dfs(int x, int rt) {
sta.push_back(x);
insta[x] = 1;
for(auto v:G[x]) {
if(insta[v] && v == rt) {
string msg;
for(int i = 0; i < sta.size(); i++) {
msg += rM[sta[i] - 1];
if(i + 1 < sta.size())msg += ' ';
}
msb.push_back(msg);
}
else if(!insta[v])dfs(v, rt);
}
insta[x] = 0;
sta.pop_back();
}
void query(string s) {
msb.clear();
dfs(M[s], M[s]);
assert(sta.empty());
if(msb.empty())cout << "none loop include " << s << endl;
else {
cout << "Bad coding -- loop include as bellow:" << endl;
for(int i = 0; i < msb.size(); i++)cout << msb[i] << endl;
}
}
int main() {
while(gets(s)) {
string temp, start;
int n = strlen(s), st = -1;
for(int i = 0; i <= n; i++) {
if(s[i] == ':') {
if(st == -1) {
st = 0;
start = temp;
}
temp = "";
}
else if(s[i] == ' ') {
if(st == -1)st = 1;
if(st == 0)addEdge(start, temp);
temp = "";
}
else if(s[i] == '\0') {
if(st == 0)addEdge(start, temp);
else if(st == 1)query(temp);
temp = "";
}
else temp += s[i];
}
}
return 0;
}
北京银行一面2人在聊
查看34道真题和解析