期中考试
这篇文章是我对期中考试上机部分的题解。共有三道题。后两题都是比较简单的,但是第一题码量比较大,而且细节处理比较多,事实上,考试时第一题我花的时间是后两题加起来的三倍😂。而从结果来看,考试的八十余人中,后两题都拿到100的有30+,而第一题拿到100的仅有5人,当然,可能也有很多人卡在了处理输入数据上。所以我们倒着来看这三道题吧。
第三题
![data-structure-mid-term-test-t3](https://picture.heren1229.top/img/data-structure-mid-term-test-t3.png)
广义表的长度,定义为该表中元素的个数,特别地,一张子表视作一个元素,也就是说,(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; }
|
第二题
![data-structure-mid-term-test-t2](https://picture.heren1229.top/img/data-structure-mid-term-test-t2.png)
这也是一道经典题了。思路是这样的:用栈模拟,不断将序列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; }
|
第一题
![data-structure-mid-term-test-t1](https://picture.heren1229.top/img/data-structure-mid-term-test-t1.png)
首先要解决的问题是如何读取输入,这甚至可以单独作为一题了😂。如果是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; }
|