交叉乘
#include <bits/stdc++.h>
#define ll long long
const int maxn = 100100;
const int mod = 1000000007;
class Solution {
public:
/**
* 多次求交叉乘
* @param a int整型vector a1,a2,...,an
* @param query int整型vector l1,r1,l2,r2,...,lq,rq
* @return int整型vector
*/
ll s[maxn], s2[maxn];
vector<int> getSum(vector<int>& a, vector<int>& query) {
int n = a.size();
int q = query.size()/2;
s[0]=s2[0]=0;
for (int i=1;i<=n;i++) {
s[i]=s[i-1]+a[i-1];
s2[i]=s2[i-1]+a[i-1]*(ll)a[i-1];
}
vector <int> ret;
for (int i=1;i<=q;i++) {
int l=query[2*i-2], r=query[2*i-1];
ll ans = ((s[r]-s[l-1])*(s[r]-s[l-1])-(s2[r]-s2[l-1]))/2;
ret.push_back(ans % mod);
}
return ret;
}
};
牛牛摆玩偶
/**
* struct Interval {
* int start;
* int end;
* };
*/
#define LL long long
#define INF 2000000000
#define X start
#define Y end
int nn, mm;
vector<Interval> a;
bool ok(int d)
{
LL prev = -1LL * INF * INF;
int cnt = 0;
for(int kk = 0; kk < a.size(); kk ++)
{
Interval i = a[kk];
while (max(prev + d, (LL)i.X) <= i.Y)
{
prev = max(prev + d, (LL)i.X);
cnt++;
if (cnt >= nn) break;
}
if (cnt >= nn) break;
}
return (cnt >= nn);
}
bool cmp(Interval x, Interval y)
{
if(x.X == y.X) return x.Y < y.Y;
return x.X < y.X;
}
class Solution {
public:
/**
*
* @param n int整型 玩偶数
* @param m int整型 区间数
* @param intervals Interval类vector 表示区间
* @return int整型
*/
int doll(int n, int m, vector<Interval>& intervals) {
// write code here
sort(intervals.begin(), intervals.end(), cmp);
a.resize(m);
nn = n;
for(int kk = 0; kk < intervals.size(); kk ++) a[kk] = intervals[kk];
int lo = 1;
int hi = INF;
int res = -1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (ok(mid))
{
res = mid;
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return res;
}
};
百度公司福利 553人发布
，其实说实话，点评真别写，给面试官印象很不好，你去随便找个差不多类型的写一下，也就一周就能搞完，大厂实习最重要的还是算法