今日头条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;
}

第三题,字符串相邻字符交换有限次数,得到最长的连续相同字符长度

枚举每种字母，计算该字母在字符串中出现的位置。再枚举以该字符每个位置为中心点，两边的字符往这个中心靠拢，计算一个距离的前缀和，再枚举左端点，二分找右端点。

今日头条2018校招编程题思路

全站热榜

创作者周榜