期中考试
这篇文章是我对期中考试上机部分的题解。共有三道题。后两题都是比较简单的，但是第一题码量比较大，而且细节处理比较多，事实上，考试时第一题我花的时间是后两题加起来的三倍😂。而从结果来看，考试的八十余人中，后两题都拿到100的有30+，而第一题拿到100的仅有5人，当然，可能也有很多人卡在了处理输入数据上。所以我们倒着来看这三道题吧。
第三题
广义表的长度，定义为该表中元素的个数，特别地，一张子表视作一个元素，也就是说，(a,b,(a,b,c,(d)))的长度为3，因为它的元素是a，b和(a,b,c,(d))。所以我们的思路是，维护一个depth，表示嵌套的深度，只有深度为0(不考虑外层括号)时，才可能找到当前表的元素(字母或子表)，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int ans = 0, depth = 0;
for (int i = 3; i < s.size() - 1; ++i)
{
ans += (isalpha(s[i]) || s[i] == '(') && depth == 0;
depth += s[i] == '(' ? 1 : s[i] == ')' ? -1 : 0;
}
cout << ans << endl;
return 0;
}
|
第二题
这也是一道经典题了。思路是这样的：用栈模拟，不断将序列1入栈，直到栈顶==下一个出栈元素，出栈。如果序列一入栈完毕也没找到下一个出栈元素，就失败。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
int main()
{
string pushed, popped;
cin >> pushed >> popped;
stack<char> stk;
int i = 0, j = 0;
for (; j < popped.size(); ++j)
{
while (i < pushed.size() && (stk.empty() || stk.top() != popped[j]))
stk.push(pushed[i++]);
if (stk.top() != popped[j])
{
cout << "No" << endl;
return 0;
}
stk.pop();
}
cout << "Yes" << endl;
return 0;
}
|
第一题
首先要解决的问题是如何读取输入，这甚至可以单独作为一题了😂。如果是Python，处理这种可以直接读一行，然后split，那C++呢？cin是不行的，因为不能确定何时转到下一行，我的做法是先getline读入一行数据，然后用它初始化stringstream。再用stringstream分割数字。关于string流，可以将它视为和cin差不多，它也会自动分割，并进行类型转换。所以这种方法，相当于是将一次输入变为两次输入。更为具体的讲解可以看我的另一篇题解leetcode 1592. 重新排列单词间的空格 | HeRen’s Blog。
处理完输入，就该考虑如何进行计算了。前置知识是：如何实现多项式加法，这可以去看一下1634. 求两个多项式链表的和，不过是一道会员题，可以百度搜一下看看题面。实际上，这就是一个合并两个有序链表的过程，只不过所谓有序变成了指数的大小罢了。所以做一下21. 合并两个有序链表 - 力扣（LeetCode）也是一样的思想。知道了多项式相加怎么做之后，很自然地想到，用多项式2的每一项乘以多项式1，再加起来就好了。一定要注意，如果相加后系数为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
66
67
68
69
70
71
72
73
74
75
76
| #include <bits/stdc++.h>
using namespace std;
struct Node
{
int val, power;
Node *next = NULL;
};
Node *getList(Node *ans, Node *head, int val, int power)
{
Node *newList = NULL;
Node *p1 = ans, *p2 = head, *pre = NULL;
while (p1 != NULL || p2 != NULL)
{
Node *p = new Node;
if (p1 != NULL && (p2 == NULL || p1->power < power + p2->power))
{
p->val = p1->val;
p->power = p1->power;
p1 = p1->next;
}
else if (p2 != NULL && (p1 == NULL || p1->power > power + p2->power))
{
p->val = val * p2->val;
p->power = power + p2->power;
p2 = p2->next;
}
else
{
p->val = p1->val + val * p2->val;
p->power = p1->power;
p1 = p1->next;
p2 = p2->next;
}
if (p->val)
{
if (newList == NULL)
newList = pre = p;
else
{
pre->next = p;
pre = p;
}
}
}
return newList;
}
int main()
{
string s1, s2;
int val, power;
getline(cin, s1);
getline(cin, s2);
stringstream ss1(s1), ss2(s2);
Node *head1 = NULL, *pre = NULL, *ans = NULL;
while (ss1 >> val && ss1 >> power)
{
Node *p = new Node;
p->val = val;
p->power = power;
if (head1 == NULL)
head1 = pre = p;
else
{
pre->next = p;
pre = p;
}
}
while (ss2 >> val && ss2 >> power)
ans = getList(ans, head1, val, power);
while (ans != NULL)
{
cout << ans->val << " " << ans->power << (ans->next ? " " : "\n");
ans = ans->next;
}
return 0;
}
|
