富途9.18后端笔试
第一题
数组经过+1,-1,不操作后出现次数最多的数的次数
思路:哈希表
#include<iostream> #include<map> #include<math.h> using namespace std; const int N = 3e5 + 10; int q[N]; map<int, int> m; int main() { int n; cin >> n; for(int i = 0; i < n; i ++) cin >> q[i]; for(int i = 0; i < n; i ++) { m[q[i] + 1] ++; m[q[i] - 1] ++; m[q[i]] ++; } int a, b = 0; for(auto & t : m) { if(t.second > b) { a = t.first; b = t.second; } } int sum = 0; //cout << a << endl; for(int i = 0; i < n; i ++) { if(abs(a - q[i]) <= 1) sum ++; } cout << sum; return 0; }第二题
移动杯子,使得所有杯子中都存在饮料
思路:排序+二分
#include<iostream> #include<algorithm> #include<math.h> using namespace std; const int N = 1e5 + 10; int q[N]; //二分查找 int query(int l, int r, int mx) { while(l < r) { int mid = (l + r + 1) >> 1; if(q[mid] <= mx) { l = mid; } else { r = mid - 1; } } return l; } int main() { int n; cin >> n; for(int i = 0; i < n; i ++) cin >> q[i]; sort(q, q + n); int res = 0x3f3f3f3f; for(int i = 0; i < n; i ++) { int mx = q[i] + n - 1; //二分 int j = query(i, n - 1, mx); int num = j - i + 1; res = min(res, n - num); } cout << res; }
#笔试题目##秋招#