20年华为暑期实习的机试题目
1. 求获胜者——字符串计数+比较
题目描述
输出票数最多者，如果票数相当，按照字母排序，a>b>c,A>B>C,如果字母相同，则字母少的在前面，比如Luc>Lucy
输入：
Tom,Lily,Tom,Lucy,Lucy,Jack
Tom,Tomy,Toc,Toma,Tom,Tomy,Z
输出：Lucy
代码：
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
using namespace std;
// 解法一：
// 1. 整体读入，切分名字，存入map中（去重+计数） ++map[key]
// 2. 将map中的数据放到vector中，用sort函数对vector排序（编写cmp，作为结构体排序交换条件）
struct Info
{
string name;
int cnt;
};
vector<Info> vec;
map<string, int> mp;
bool check(string s)
{
int len = s.size();
if(len == 0)
return false;
if(s[0]<'A' || s[0]>'Z')
return false;
for(int i=1; i<len; ++i)
if(s[i]<'a' || s[i]>'z')
return false;
// 将名字插入到map中，并计数
++mp[s]; // ++map[s]操作符重载：判断s是否在map中，如果在，对应的value++；如果不在，将s插入map，对应的value=1.
return true;
}
bool split(string s)
{
int len = s.size(); // string的函数 .size()返回字符串长度
if(len == 0)
return false;
string cur;
int p=0;
while(p < len)
{
if(s[p] == ',') // string类型可以直接用下标访问
{
if(!check(cur))
return false;
cur = ""; // 清空当前cur
}
else
cur += s[p]; // +=可以在string后面添加字符
++p;
}
if(cur.size() != 0 && !check(cur))
return false;
}
// 升序排列，返回false时对调两元素
bool cmp(const Info &a, const Info &b)
{
if(a.cnt != b.cnt)
return a.cnt < b.cnt; // int类型比较，小的排在前面
if(a.name.size() == b.name.size())
return a.name > b.name; // 长度相等的string类型比较，字母序小的排在后面
if(a.name.find(b.name) != string::npos)
return true; // a.name包含b.name时进入，表明a应该排在b的前面，所以不交换
if(b.name.find(a.name) != string::npos)
return false; // b.name包含a.name时进入，表明b应该排在a的前面，所以交换ab的位置
return a.name > b.name; // 当出现次数相等、两名字不等号长且没有包含关系时，比较两字符串大小，如何比？！！！
}
int main()
{
string input;
cin >> input;
bool valid = split(input);
if(!valid)
cout<<"error.0001"<<endl;
else
{
// 将mp中的元素放到vector中，为了sort
for(auto o : mp)
vec.push_back({o.first, o.second}); // vector的函数，.push_back()，向vector中加入元素
sort(vec.begin(), vec.end(), cmp); // sort函数需要系统学习一下
cout << vec[vec.size() - 1].name << endl;
}
// for (auto o : vec)
// cout << o.name << " " << o.cnt << endl;
system("pause");
return 0;
}
// 解法二：
// 1. 整体读入，切分名字，存入vector（不去重，不计数）
// 2. 直接sort vector，遍历排好序的vector后找到最先出现的最大值
vector<string> name;
bool split(string s)
{
if (s.size() < 1)
return false;
int st = 0;
for (int i=0; i<=s.size(); ++i)
{
if(i==0 || s[i-1]==',')
{
if(s[i]<'A' || s[i]>'Z')
{
cout<<"1"<<endl;
cout<<s[i]<<i<<endl;
return false;
}
}
else if(!(s[i] == ','|| s[i] == '\0') && (s[i]<'a' || s[i]>'z'))
{
cout<<"2"<<endl;
cout<<s[i]<<i<<endl;
return false;
}
if(s[i]==',' || s[i]=='\0')
{
name.push_back(s.substr(st, i-st)); // string.substr(start, length)
st = i+1;
}
}
return true;
}
int main()
{
string s;
cin >> s;
if(!split(s))
{
cout << "error.0001" << endl;
system("pause");
return -1;
}
sort(name.begin(), name.end()); // 直接对string类型的vector进行排序，先按照字母序排序，字母序相同根据长度排序
string ret, tmp = name[0];
int vote = 0, cnt = 0;
for( auto o : name)
{
cout << o <<' ';
if(o == tmp)
{
cnt++;
}
else
{
if(cnt > vote)
{
ret = tmp;
vote = cnt;
cnt == 0;
}
tmp = o;
}
}
cout << endl << ret << endl;
system("pause");
return 0;
}分析
2. 字符串匹配
题目描述
输入：
read
read[addr=0x17,mask=0xff,val=0x7],
read_his[addr=0xff,mask=0xff,val=0x1],
read[addr=0xf0,mask=0xff,val=0x80]
输出：
0x17 0xff 0x7 0xf0 0xff 0x80
代码
分析
3. 函数调用链栈总和最大值——数据存储+DFS
题目描述
函数调用链栈总和为调用链中各个函数栈大小的总和，给定输入，找到调用链中栈总和的最大值，注意入口函数不唯一，比如1调用2、3，5调用6，6调用7，则此时有两个函数入口1和5.
输入：
第1行：调用关系总组数n 第1组被调用函数个数 第2组被调用函数个数 ... 第n组被调用函数个数
第2行：调用函数1 函数1栈大小 被调函数1 ... 被调函数m
...
第n+1行：调用函数n 函数n栈大小 被调函数1 ... 被调函数k
最多100行
输入案例1：
5 2 3 1 0 0
1 20 2 3
2 30 3 4 5
3 50 4
4 60
5 80
输入案例2：
5 2 3 1 0 1
1 20 2 3
2 30 3 4 5
3 50 4
4 60
5 80 1
输出：
- 如果所有调用链中只要存在一个递归调用（即直接或间接调用自己，比如1->2->3->1即为递归调用），则输出R
- 如果调用链中有函数未给出调用栈大小，则输出为NA
输出案例1：
160
输出案例2：
R
代码
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
using namespace std;
vector<int> callnum, fsize;
vector<vector<int>> G; // 记录调用关系，期中值为mp的value
int ans;
map<string, int> mp; // 用于存储函数名和id的对应
vector<bool> vis; // 用于判定是否存在循环调用
// cur为当前调用函数，sum为截止到目前需要的内存空间（包含当前调用）
bool dfs(int cur, int sum)
{
vis[cur] = true;
ans = max(ans, sum);
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = G[cur][i];
if (vis[nxt])
return false;
bool ret = dfs(nxt, sum + fsize[nxt]);
if (!ret)
return false;
}
vis[cur] = false;
return true;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
int num;
cin >> num;
callnum.push_back(num); //callnum 存入调用了多少个函数
}
int id = 0;
for (int i = 0; i < n; ++i) // 共n条数据
{
string name;
cin >> name;
if (mp.count(name) == 0) // 如函数名未出现在mp中，则将其加入字典，并赋值++id
{
mp[name] = ++id;
}
int sz; // 当前函数栈大小
cin >> sz;
fsize.resize(id + 5); // resize函数是分配一个大小为id+5的空间，方便[]取地址，而不用push_back()函数
fsize[mp[name]] = sz;
// cout << sz << endl;
for (int j = 0; j < callnum[i]; ++j) // 读取当前函数会调用的函数名
{
// cout << j << endl;
string s;
cin >> s;
if (mp.count(s) == 0)
mp[s] = ++id;
G.resize(id + 5);
G[mp[name]].push_back(mp[s]);
}
}
// cout << id << endl;
if (id != n)
{
cout << "NA" << endl;
return 0;
}
vis.resize(id + 5);
for (auto o : mp)
{
int enter = o.second;
for (int i = 1; i <= id; ++i)
vis[i] = false;
bool ret = dfs(enter, fsize[enter]);
if (!ret)
{
cout << "R" << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}- 自己编写
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
using namespace std;
vector<vector<int>> G; //每行一个函数，第0列为当前行调用函数的次数，第1列当前函数的序号，第2列为所占空间
vector<bool> flag;
int ans = 0;
bool dfs(int cur_f, int sum)
{
flag[cur_f-1] = false;
ans = max(sum, ans);
for (int i = 3; i < G[cur_f-1][0] + 3; ++i)
{
if (!flag[G[cur_f-1][i]-1])
return false;
if (!dfs(G[cur_f-1][i], sum + G[G[cur_f - 1][i] -1][2]))
return false;
}
flag[cur_f-1] = true;
return true;
}
int main()
{
int n = 0;
cin >> n;
G.resize(n + 5);
flag.resize(n + 5);
for (int i = 0; i < n; ++i)
{
flag[i] = true;
int tmp;
cin >> tmp;
G[i].push_back(tmp);
}
for (int i = 0; i < n; ++i)
{
G[i].resize(G[i][0]+5);
for (int j = 1; j <= G[i][0] + 2; ++j)
{
cin >> G[i][j];
}
}
for (int i = 0; i < n; ++i)
{
if (!dfs(G[i][1], G[i][2]))
{
cout << "R" << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}分析
运用深度优先搜索算法，相当于在图上找路，这里无需做剪枝操作，因为需要全部遍历，否则会遗漏掉循环现象。这里属于邻接表遍历，注意两层循环分别在哪里
注意dfs的参数定义，以及函数返回值和最终答案从哪里计算。这里采用bool类型的返回值，目的在于判断是否产生循环现象。最终答案通过一个全局变量来计算，注意vis/flag在dfs中变化的位置
注意给定数据如何存储和遍历（选择适当的数据结构很重要）
- 当使用不定长数组时，需使用容器vector，这里主要用到了push_back(), resize(), 下标取值, 遍历器取值(auto a : G)
- 后期需要整理vector, map, string的用法
