今日头条2018校招编程题思路
第一题,串珠
颜色用二进制存储。枚举颜色后twp-point/滑动窗口解决。 每次往右边加进来一个点判断该点是否存在目前枚举的颜色，存在cnt++; 弹出最左边的点，如果最左边的点存在目前枚举的颜色，cnt--。如果cnt>1. ans++。
复杂度O(n)
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<time.h>
#include<cmath>
#include<sstream>
#include<assert.h>
using namespace std;
typedef long long int LL;
const LL INF = 0x7FFFFFFFFFFFFFFF;
const int inf = 0x3f3f3f3f;
const int MAXN = 10000 + 1024;
LL col[MAXN * 2];
int main(){
int n, m, c;
while (~scanf("%d%d%d", &n, &m, &c)){
memset(col, 0, sizeof(col));
for (int i = 1; i <= n; i++){
int Size, val;
scanf("%d", &Size);
for (int j = 1; j <= Size; j++){
scanf("%d", &val);
col[i] |= (1LL << val);
}
col[i + n] = col[i];
}
if (m > n){ printf("0\n"); }
else{
int ans = 0;
for (int k = 1; k <= c; k++){
int cnt = 0; bool flag = false;
for (int i = 1; i <= m; i++){
if (col[i] & (1LL << k)){ cnt++; }
}
if (cnt > 1){ flag = true; }
for (int i = m + 1; i <= n * 2 && i - m <= n && !flag; i++){
if (col[i - m] & (1LL << k)){ cnt--; }
if (col[i] & (1LL << k)){ cnt++; }
if (cnt > 1){ flag = true; }
}
if (flag){ ans++; }
}
printf("%d\n", ans);
}
}
return 0;
}
第二题, 区间内k值的多少
离线处理，把询问全部读入，分块排序询问，用map来维护某个值出现的次数，莫队转移。
复杂度O(q*sqrt(n)*log(n))
另外一种方式是离散化k，然后对于每个k用一个vector保存值为k的人的下标。对于询问我们可以定位到vector[k]这个数组，然后用二分查找看有多少个人在[l,r]之间。
复杂度O(n*log(n)+q*log(n))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long int LL;
const int MAXN = 300000+1024;
int be[MAXN], ans[MAXN];
LL a[MAXN];
map<LL, int> mp;
struct Qry{
int l, r, id;
LL k;
bool operator<(const Qry &o)const{
if (be[l] == be[o.l]) return (be[l] & 1) ? r > o.r:r < o.r;
return l < o.l;
}
}Q[MAXN];
void add(LL x){
mp[x]++;
}
void del(LL x){
mp[x]--;
}
int main(){
#ifdef kirito
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, q;
while (~scanf("%d", &n)){
int S = (int)sqrt(n + 0.5);
for (int i = 0; i <= n; ++i) be[i] = i / S;
for (int i = 1; i <= n; ++i) scanf("%lld",&a[i]);
scanf("%d", &q);
for (int i = 0; i < q; ++i){
scanf("%d%d%lld", &Q[i].l, &Q[i].r, &Q[i].k);
Q[i].id = i;
}
sort(Q, Q + q);
for (int i = 0, l = 1, r = 0; i < q; ++i){
while (r < Q[i].r) add(a[++r]);
while (l > Q[i].l) add(a[--l]);
while (l < Q[i].l) del(a[l++]);
while (r > Q[i].r) del(a[r--]);
ans[Q[i].id] = mp[Q[i].k];
}
for (int i = 0; i < q; ++i){
printf("%d\n", ans[i]);
}
}
return 0;
}
第三题,字符串相邻字符交换有限次数,得到最长的连续相同字符长度
枚举每种字母，计算该字母在字符串中出现的位置。再枚举以该字符每个位置为中心点，两边的字符往这个中心靠拢，计算一个距离的前缀和， 再枚举左端点，二分找右端点。
复杂度O(26*|s|*|s|*log(|s|))
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<time.h>
#include<cmath>
#include<sstream>
#include<assert.h>
using namespace std;
typedef long long int LL;
const LL INF = 0x7FFFFFFFFFFFFFFF;
const int inf = 0x3f3f3f3f;
const int MAXN = 10000 + 1024;
char str[MAXN];
vector<int>pos;
int dst[MAXN],preSum[MAXN];
int main(){
#ifdef kirito
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int m;
while (~scanf("%s%d", str, &m)){
int len = strlen(str);
int ans = 0;
for (int i = 0; i < 26; i++){
pos.clear();
for (int j = 0; j < len; j++){
if (str[j] == ('a' + i)){
pos.push_back(j);
}
}
int Size = pos.size();
for (int j = 0; j < Size; j++){
memset(dst, 0, sizeof(dst));
memset(preSum, 0, sizeof(preSum));
for (int _j = 0; _j < Size; _j++){
dst[_j] = abs(pos[_j] - pos[j]);
}
for (int _j = j + 1; _j < Size; _j++){
preSum[_j] = preSum[_j - 1] + dst[_j] - (_j - j);
}
for (int _j = j - 1; _j >= 0; _j--){
preSum[_j] = preSum[_j + 1] + dst[_j] - (j - _j);
}
preSum[Size] = inf;
for (int _j = j; _j >= 0; _j--){
int need = m - preSum[_j];
if (j + 1 >= Size){ continue; }
int pos = upper_bound(preSum + j + 1, preSum + Size,need) - preSum;
pos--;
if (pos >= j + 1 && pos < Size){
ans = max(ans, pos - j + 1 + (j - _j));
}
}
}
}
printf("%d\n", ans);
}
return 0;
}
#字节跳动#
