当前位置：首页 > news >正文

卡码网用友提前批笔试 | 121 大数减法、122 滑动窗口最大值、117 软件架构

news 来源：原创 2024/9/29 12:24:42

121 大数减法

一开始这么写，但是就是有90%的数据通过不了

#include <iostream>
#include <string>
using namespace std;void reverse(string& s,int l, int r) {while (l < r) {char c = s[l];s[l] = s[r];s[r] = c;l++; r--;}
}int main() {string a, b;cin >> a >> b;long long ai = stoi(a);long long bi = stoi(b);string s = "";long int res = ai - bi;int flag = res > 0 ? 1 : 0;if (!flag) res *= -1;while (res) {s += (res % 10 + '0');res /= 10;}reverse(s,0, s.size()-1);if (!flag) s = '-' + s;cout << s << endl;return 0;
}

后来知道会有很多数据甚至超过long long的范围，所以要用字符串模拟减法

代码如下：

#include <iostream>
#include <string>
using namespace std;int main() {string a, b;cin >> a >> b;string flag = "";if (a.size() < b.size()) {string t = a;a = b;b = t;flag = "-";}if (a.size() == b.size()) {for (int i = 0; i < a.size(); i++) {if (a[i] > b[i]) break;else if (a[i] == b[i]) continue;else {string t = a;a = b;b = t;flag = "-";break;}}   }string res = a;int j = a.size() - b.size();for (int i = j; i < a.size(); i++) {if (res[i] >= b[i-j]) res[i] = res[i] - b[i-j] + '0';else {int k = i - 1;while (res[k] < '1') {res[k] = '9'; k--;}res[k] = res[k] - 1;res[i] = (10 - (b[i-j] - res[i]) + '0');}}res = flag + res;cout << res << endl;return 0;
}

122 滑动窗口最大值

本来以为要用最大堆最小堆、优先队列的，但是时间复杂度刚好够用了。需要处理下字符串输入转化为整数数组，由于']'之后还有一个','，需要用一个flag记录状态的变化。其他思路就是一个双重循环控制边界的问题了，小心调试潜在的数组或指针越界的问题就ok了

代码如下：

#include <iostream>
#include <string>
#include <vector>
using namespace std;int main() {string s;getline(cin, s);vector<int> nums;int numE = 0;int k = 0;int flag = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '=') {numE++;if (numE == 2) {string sk = s.substr(i + 2, s.size() - i - 2);k = stoi(sk);}}if (s[i] == ']') flag = 1;if (flag == 0 && (s[i] == '[' || s[i] == ',')) {int end = i + 1;while (s[end+1] != ',' && s[end + 1] != ']') end++;string snum = s.substr(i+1, end - i);int num = stoi(snum);nums.push_back(num);}}int dif = 0;int maxNum = nums[0];int minNum = nums[0];for (int i = 0; i + k - 1 < nums.size(); i++) {maxNum = nums[i];minNum = nums[i];for (int j = i; j < i + k; j++) {if (maxNum < nums[j]) maxNum = nums[j];if (minNum > nums[j]) minNum = nums[j];}if (dif < maxNum - minNum) dif = maxNum - minNum;}cout << dif << endl;return 0;
}

117 软件架构

原本用set删除功能加以辅助计数，后来发现set.erase删除的是按下标访问的数据，而不是实际数据，map应该也差不多。

改进后代码只能通过30%的测试用例，后面要再改改

#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;int main() {int n, m;cin >> n >> m;queue<long int> myque;stack<long int> mysta;map<long int, set<long int>> mymap;map<long int, long int> nummap;set<long int> res;int flag = 0;for (int i = 0; i < m; i++) {long int a, b;cin >> a >> b;mymap[b].insert(a);nummap[b]++;}while (res.size() < n) {int num = res.size();for (int i = 0; i < n; i++) {if (res.find(i) == res.end() && nummap[i] == 0) {mysta.push(i);res.insert(i);myque.push(i);}}if (num == res.size()) break;while (!mysta.empty()) {long int t = mysta.top();mysta.pop();for (int i = 0; i < n; i++) {if (res.find(i) == res.end() &&nummap[i] > 0 && mymap[i].find(t) != mymap[i].end())nummap[i]--;}}}if (res.size() < n) cout << -1 << endl;else {while (!myque.empty()) {cout << myque.front() << ' ';myque.pop();}cout << endl;}return 0;
}