文章目录

网易1、奖学金2、路灯 工行1、压缩字符串2、最佳直线3、完全平方数

网易

1、奖学金

#include <bits/stdc++.h> using namespace std; struct Stu{ int a; int b; }stu[10000]; bool com(Stu s1,Stu s2) { return s1.b<s2.b; } int main() { int n,r,avg; while(cin>>n>>r>>avg) { long long time=0; for(int i=0;i<n;++i) { cin>>stu[i].a>>stu[i].b; } sort(stu,stu+n,com); avg=avg*n; for(int i=0;i<n;++i) { avg=avg-stu[i].a; } for(int i=0;i<n;++i) { if(avg<=0) break; else if((r-stu[i].a)<avg) { time+=(r-stu[i].a)*stu[i].b; avg-=(r-stu[i].a); } else{ time+=avg*stu[i].b; break; } } cout<<time<<endl; } return 0; }

2、路灯

#include <bits/stdc++.h> using namespace std; int main() { int n,l,num; vector<int > index; while(cin>>n>>l) { for(int i=0;i<n;++i) { cin>>num; index.push_back(num); } sort(index.begin(),index.end()); float maxlen=index[0]*2; for(int i=1;i<n;++i) { if(index[i]-index[i-1]>maxlen) maxlen=index[i]-index[i-1]; } if((maxlen/2.0)>(l-index[n-1])) maxlen=maxlen/2.0; else maxlen=l-index[n-1]; printf("%.2f\n",maxlen); } return 0; }

工行

1、压缩字符串

力扣三道 面试题01.06字符串压缩

class Solution { public: string compressString(string S) { int N = S.length(); string res; int i = 0; while (i < N) { int j = i; while (j < N && S[j] == S[i]) { j++; } res += S[i]; res += to_string(j - i); i = j; } if (res.length() < S.length()) { return res; } else { return S; } } };

力扣443 原地压缩，支持部分压缩

int compress(vector<char>& chars) { if (chars.empty()) return 0; size_t j = 0; int cnt = 0; for (size_t i = 1; i <= chars.size(); i++) { cnt++; if (i == chars.size() || chars[i] != chars[j]) { j++; if (cnt != 1) { string scnt = to_string(cnt); for (auto c : scnt) { chars[j++] = c; } } if (i == chars.size()) break; chars[j] = chars[i]; cnt = 0; } } return j; }

2、最佳直线

力扣最佳直线 散列表 直线表示的一般式

// 记录直线上的点的个数，以及最小的两个编号 struct Record { vector<int> ids; int cnt; Record() : cnt(0) { } }; using LL = long long; LL gcd(LL a, LL b) { LL r; do { r = a % b; a = b; b = r; } while (r != 0); return a; } class Solution { public: vector<int> bestLine(vector<vector<int>>& points) { // (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) // (y2 - y1) x + (x1 - x2) y = (y2 - y1) * x1 + (x1 - x2) * y1 int n = points.size(); map<array<LL, 3>, Record> ABC_ma; int best = 0; vector<int> ans; // 如果A与B和A与C都在一条直线上，那么B与C也在该条直线上 for (int i = 0; i < n; ++i) { vector<int> &pi = points[i]; int dup = 0; // 与pi位置相同的点数 ABC_ma.clear(); int local_best = 0; vector<int> local_ans; for (int j = i + 1; j < n; ++j) { vector<int> &pj = points[j]; LL A = (LL)pj[1] - pi[1]; LL B = (LL)pj[0] - pi[0]; if (A == 0 && B == 0) { // pi与pj相同 ++dup; if (local_ans.empty()) local_ans = {i, j}; continue; } LL C = A * pi[0] + B * pi[1]; if (A == 0) { if (C == 0) { B = 1; } else { LL g = gcd(B, C); B /= g; C /= g; } } else if (B == 0) { if (C == 0) { A = 1; } else { LL g = gcd(A, C); A /= g; C /= g; } } else { // A != 0 and B != 0 LL g = gcd(A, B); if (C == 0) { A /= g; B /= g; } else { LL w = gcd(g, C); A /= w; B /= w; C /= w; } } Record &r = ABC_ma[{A, B, C}]; if (r.cnt == 0) { r.ids = {i, j}; } ++r.cnt; } update_ans(ABC_ma, local_best, local_ans); local_best += dup; if (local_best > best) { ans = std::move(local_ans); best = local_best; } } return ans; } template <typename T> void update_ans(map<T, Record> &ma, int &best, vector<int> &ans) { for (auto &p : ma) { Record &r = p.second; if (r.cnt > best) { best = r.cnt; ans = std::move(r.ids); } else if (p.second.cnt == best) { // 如果穿过相同数量的点 if (r.ids[0] < ans[0] || (r.ids[0] == ans[0] && r.ids[1] < ans[1])) { ans = std::move(r.ids); } } } } };

3、完全平方数

力扣279 找到最少的，平方数之和

class Solution { public: int numSquares(int n) { vector<int> result(n+1, 0x7FFFFFFF); // 每个数的最优解都存在result数组里 result[0] = 0; for (int i = 1; i <= n; i++){ for(int j = 1; i-j*j >= 0 ; j++) { // 观察比N小的数，且符合N = IxI + N'的数值 result[i] = min(result[i], result[i-j*j] + 1); // 把最优解（最小值）+ 1 写入result } } return result[n]; } }; class Solution { public: int numSquares(int n) { vector<int> dp(n + 1); for (int i = 1; i <= n; i++) { dp[i] = i; for (int j = 1; j * j <= i; j++) dp[i] = min(dp[i], dp[i - j * j] + 1); } return dp[n]; } };

力扣633 判断是否存在，构成平方数之和

class Solution { public: bool judgeSquareSum(int c) { long i = 0, j = sqrt(c); while (i <= j) if (i * i + j * j == c) return true; else if (i * i + j * j > c) j --; else i ++; return false; } };