2020/7/4 字节第三批笔试 第一题：找到最小未用的正整数 给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。
算法：用一个辅助数组b[n+1]记录a[n]中元素的是否出现，初始全部为0。例如如果a[0]=1，则b[1]=1，a[3]=2，则b[2]=1； 如果a[i]>n则不记录，因为如果1-n中元素没有全部出现则缺少的元素一定在1-n中无需记录大于n的数是否出现。 遍历一次a数组记录是否出现，再遍历一次b数组看是否存在为0的元素（从下标为1开始循环到n），找到第一个退出循环。 如果没有中途退出而是正常结束循环，说明答案为n+1. 算法时间复杂度为O(n)，因为使用了辅助数组，所以空间复杂度为O(n+1)。
void find_min_miss(int a[],int n){ int b[n+1]; for(int i=0;i<n;i++) if(a[i]>0 && a[i]<=n) b[a[i]]=1; for(int i=1;i<=n;i++) if(b[i]==0) break; if(i==n+1) return n+1; else return i; }字节第四批笔试题 第一题是单调栈，比较简单 第二题是剑指 Offer 31. 栈的压入、弹出序列的改编。
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> st; int n = popped.size(); int j = 0; for (int i = 0; i < pushed.size(); ++i){ st.push(pushed[i]); while(!st.empty() && j < n && st.top() == popped[j]){ st.pop(); ++j; } } return st.empty(); } };第三题模拟题，按模拟就是了 第四题是最小覆盖串，滑窗思路
8/20 顺丰笔试 第一题，租用服务器 有n台服务器，ai代表不同的宽带，有m个客户要租用，每个客户有自己要求的宽带和预算，怎么租利润最大。可以选择拒绝客户 3 4 //n,m 1 2 3//n个服务器，不同宽带 //下面是m行，代表m个客户，宽带和预算 2 1 1 1 3 3 3 2 思路用贪心法，利润排序
#include <bits/stdc++.h> using namespace std; using Pair = pair<int, int>; void func(vector<int> arr, vector<Pair> client){ sort(arr.rbegin(), arr.rend()); for (int i=0; i<arr.size(); i++) ;//cout << arr[i] << ' '; auto cmp = [](const Pair a, const Pair b){return a.second > b.second;}; sort(client.begin(), client.end(), cmp); for (int i=0; i<client.size(); i++) ;//cout << client[i].first << ' ' << client[i].second << ' '; int res = 0; for (int i=0; i<arr.size(); i++){ for (int j=0; j<client.size(); j++){ if (arr[i] == client[j].first){ res += client[j].second; client.erase(client.begin()+j);//这里会增加时间复杂度，可以用标志位的方法 break; } } } cout << res << endl; } int main(){ int n, m; while (cin >> n >> m){ vector<int> arr(n); for (int i=0; i<n; i++) cin >> arr[i]; vector<Pair> client; for (int i=0; i<m; i++){ int sope, price; cin >> sope >> price; client.push_back(Pair(sope, price)); } func(arr, client); } return 0; }