笔试面试相关记录（5）

（1）不包含重复字符的最长子串的长度

#include <iostream>
#include <string>
#include <map>using namespace std;int getMaxLength(string& s) {int len = s.size();map<char, int> mp;int max_len = 0;int left = 0;int i = 0;while (i < len) {if (mp[s[i]] > 0) {max_len = max(max_len, i-left);while (mp[s[i]] > 0) {mp[s[left]]--;left++;}} mp[s[i]]++;i++;}max_len = max(max_len, i-left);return max_len;
}int main() {string str;while(cin >> str) {cout << getMaxLength(str) << endl;}return 0;
}

（2）小米基站问题，基站数组中，每个基站的x,y,q分别表示基站的坐标x和y，以及信号q，radius表示手机可以接收信号的范围，当手机距离基站的距离小于radius时，基站的信号为floor(q/(1+d))，求出一个信号最强的位置，如果有多个位置，按照字典序取第一个。

#include <iostream>
#include <vector>
#include <string>
#include <math.h>using namespace std;double distance(int x1, int y1, int x2, int y2) {return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
}int main() {string str;std::getline(std::cin, str);int t = 0, n, radius;for (long unsigned i = 0; i < str.size(); i++) {if (isdigit(str[i])) {t = t*10 + (str[i]-'0');} else {n = t;t = 0;}}radius = t;int x, y, q;int min_x = 1e8, min_y = 1e8, max_x = 0, max_y = 0;vector<vector<int>> vec;for (int i = 0; i < n; i++) {scanf("%d,%d,%d", &x, &y, &q);vec.push_back({x,y,q});min_x = min(x, min_x);min_y = min(y, min_y);max_x = max(x, max_x);max_y = max(y, max_y);}vector<vector<int>> grid(max_x+1, vector<int>(max_y+1, 0));int max_q = 0, ans_x = 1e8, ans_y = 1e8;for (int i = 0; i < n; i++) {int n_x = vec[i][0], n_y = vec[i][1], q = vec[i][2];for (int j = -radius; j <= radius; j++) {for (int k = -radius; k <= radius; k++) {int new_x = n_x + j, new_y = n_y + k;double dis = distance(new_x, new_y, n_x, n_y);if (new_x >= 0 && new_y >= 0 && new_x <= max_x && new_y <= max_y && dis < radius) {grid[new_x][new_y] +=  floor(q/(1+dis));if (grid[new_x][new_y] > max_q) {max_q = grid[new_x][new_y];ans_x = new_x;ans_y = new_y;} else if (grid[new_x][new_y] == max_q && (new_x < ans_x || (new_x == ans_x && new_y < ans_y))) {ans_x = new_x;ans_y = new_y;}}}}}cout << ans_x << "," << ans_y << endl;}

(3)是一个拓扑排序问题，

输入n，表示n个任务

输入1:0,0:1表示任务1依赖任务0，任务0依赖任务1,问这个任务能不能完成？可以完成输出1，否则输出0；

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;int main() {int n;string str;while (cin >> n) {cin >> str;int t = 0;int a = 0, b = 0;int max_a = 0, max_b = 0;vector<vector<int>> vec;for (long unsigned i = 0; i < str.size(); i++) {if (isdigit(str[i])) {t = t*10 + (str[i]-'0');} else if (str[i] == ':') {a = t;t = 0;} else if (str[i] == ',') {max_a = max(max_a, a);max_b = max(max_b, t);vec.push_back({a, t});t = 0;}}max_a = max(max_a, a);max_b = max(max_b, t);vec.push_back({a, t});vector<vector<int>> grid(max_a+1, vector<int>(max_b+1, 0));for (int i = 0; i < n; i++) {grid[vec[i][0]][vec[i][1]] = 1;}queue<int> q;vector<int> dege(n, 0);for (int i = 0; i < n; i++) {int count = 0;for (int j = 0; j < n; j++) {if (grid[i][j] = 1) {count++;}}dege[i] = count;if (count == 0) {q.push(i);}}while (q.size()) {int node = q.front();q.pop();for (int i = 0; i < n; i++) {if (grid[i][node] == 1) {grid[i][node] = 0;dege[i]--;if (dege[i] == 0) {q.push(i);}}}}bool flag = false;for (int i = 0; i < n; i++) {if (dege[i]) {flag = true;break;}}if (flag) {cout << 0 << endl;} else {cout << 1 << endl;}}return 0;
}

(4)一个数组，表示每个工人的工作能力，现有一个工作需要ceil(n/2.0)个工人去完成，并且要求这些工人的工作能力之和大于等于target，求有多少种安排工人的方法。

输入

1(测试组数）

5 10(n,target）

3 2 3 4 5

输出7

#include <iostream>
#include <vector>
#include <set>
#include <math.h>
#include <string>
using namespace std;void backtrace(vector<int>& nums, int sum, long unsigned path, int& ans, long unsigned start, long unsigned worker_num, int target, string str, set<string>& set_str) {if (path == worker_num && sum >= target && set_str.find(str) == set_str.end()) {ans++;set_str.insert(str);return;}if (start >= nums.size() || path > worker_num) return;int len = nums.size();// 这个语句放在for循环外面，用于记录上次的结果，不放入for循环中string t = str;for (long unsigned i = start; i < len; i++) {// 这里一个错误导致弄了半天也没有弄出来，if (path == 0) str = to_string(i);// 下面的代码之前写的是str = str + "-" + to_string(i);这样写是有错误的// 因为每次选或者不选，是从上一次的结果后面进行添加的，如果这里使用了str = str + "-" + to_string(i);// 就会导致str在for循环中会被修改。else str = t + "-" + to_string(i);// 如果当前位置选择，则在上一次的结果上加上这次的数字backtrace(nums, sum+nums[i], path+1, ans, i+1, worker_num, target, str, set_str);// 当前位置不选择backtrace(nums, sum, path, ans, i+1, worker_num, target, t, set_str);}
}int main() {int T;while (cin >> T) {for (int times = 0; times < T; times++) {int n, target;cin >> n >> target;vector<int> nums(n, 0);int t;for (int i = 0; i < n; i++) {cin >> t;nums[i] = t;}long unsigned path = 0;// 如果使用ceil函数，记得要将其变成float或者double形式，如果是整数，就会出错。long unsigned worker_num = (n%2==1)?(n+1)/2:(n/2);string str = "";int ans = 0;set<string> set_str;backtrace(nums, 0, path, ans, 0, worker_num, target, str, set_str);          cout << ans << endl;}}return 0;
}

（5）

#include <iostream>
using namespace std; void func(int a, int b, int c) {c = a*b;
}int main()
{int c;int a = 3, b = 3;func(a, b, c);cout << c << endl;printf("%d", c);return 0;
}
输出随机数，不是输出0

(6)

#include <iostream>
using namespace std; class T {
public:T() {cout << "T()" << endl;}};
int main()
{T* p = new T[3];return 0;
}
输出
T()
T()
T()