字节2020笔试题总结
第一题：
这种字符串模式匹配的题经常采用有限状态机的方法，差一点的方法是双指针，一般会更加麻烦，要熟悉状态机的使用。
我的代码：
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main() {
int n = 0;
cin>>n;
while (n--) {
string s;
cin>>s;
char cur = s[0];
string res = "";
res += cur;
int state = 0;
for (int i = 1; i < s.size(); i++) {
if (state == 0) {
res += s[i];
if (s[i] == cur) state = 1;
else {
cur = s[i];
continue;
}
}
else if (state == 1) {
if (s[i] == cur) continue;
else {
state = 2;
res += s[i];
cur = s[i];
}
}
else if (state == 2) {
if (cur == s[i]) continue;
else {
state = 0;
cur = s[i];
res += s[i];
}
}
}
cout<<res<<endl;
}
return 0;
}第二题：
这道题可以利用双指针来做，第一个指针指向A特工的位置，第二个指针去找A特工在该位置下另外两名特工的最远位置，利用组合数求解总次数后取模即可。
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main() {
long long n = 0, dis = 0;
cin>>n;
cin>>dis;
long long left = 0;
long long right = 0;
vector<int> buildings(n);
long long res = 0;
for (long i = 0; i < n; i++) cin >> buildings[i];
while (left < n - 2) {
if (right < n && buildings[right] - buildings[left] <= dis) right ++;
else {
res += (right - left - 1)*(right - left - 2)/2;
left ++;
}
}
cout<<res%99997867;
return 0;
}第三题：
这种游戏一般由于数据规模较小，可以利用回溯来暴力穷举可能，关键点在于每次都先加入第14张牌，然后再判断是否可行。
#include<string>
#include<vector>
#include<iostream>
using namespace std;
void dfs(vector<int>& result, unordered_map<int, int>& fly, unordered_map<int, int>& rest, int pos) {
if (pos == 12) {
return;
}
for (int i = 1; i <= 9; i++) {
if (fly[i] >= 2) {
fly[i] -= 2;
dfs(result, fly, pos + 2);
fly[i] += 2;
}
if (i <= 7 && fly[i] && fly[i+1] && fly[i+2]) {
fly[i] --;
fly[i+1] --;
fly[i+2] --;
dfs(result, fly, pos + 3);
fly[i] ++;
fly[i+1] ++;
fly[i+2] ++;
}
}
}
int main() {
unordered_map<int, int> fly;
for (int i = 1; i <= 13; i ++) {
int tmp = 0;
cin>>tmp;
fly[tmp] ++;
}
unordered_map<int, int> rest;
for (int i = 1; i <= 9; i++) {
rest[i] = 4 - fly[i];
}
vector<int> result;
dfs(1)
return 0;
}第四题：
这道题可以采用的数据结构包括哈希表和map。
利用哈希表无法处理pair，因此题解采用了map，代码如下：
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
int n, m;
cin >> n;
int len;
pair<int, int> xy;
while (n--)
{
cin >> m;
int maxCnt = 0;
map<pair<int, int>, int> preFeaTimes;
map<pair<int, int>, int> feaTimes;
while (m--)
{
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> xy.first >> xy.second;
if (preFeaTimes.count(xy))
feaTimes[xy] = preFeaTimes[xy] + 1;
else
feaTimes[xy] = 1;
if (feaTimes[xy] > maxCnt)
maxCnt = feaTimes[xy];
}
preFeaTimes.clear();
preFeaTimes.swap(feaTimes);
}
cout << maxCnt << endl;
}
return 0;
}我的方法如下：
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int check(vector<int>& seq) {//0 1 2 6 7
int tmp = -1;
for (int i = 0; i < seq.size(); ) {
int cur = i;
while (cur < seq.size() - 1 && seq[cur + 1] - seq[cur] == 1) cur ++;
tmp = max(tmp, cur - i + 1);
if (i == cur) i ++;
else i = cur;
}
return tmp;
}
int main() {
int loop = 0;
cin >> loop;
while (loop --) {
int frame = 0;
cin >> frame;
unordered_map<int, unordered_map<int, vector<int> > > map;
for (int i = 0; i < frame; i++) {
int sz = 0;
cin >> sz;
while (sz --) {
int a, b;
cin >> a;
cin >> b;
map[a][b].push_back(i);
}
}
int resVal = -1;
for (auto m:map) {
for (auto n:m.second) {
int cur = check(n.second);
resVal = max(resVal, cur);
}
}
cout<< resVal<<endl;
}
return 0;
}第五题：
旅行商问题，利用动态规划可以求解
状态设置得比较有意思，利用二进制得知识求解
#include<vector>
#include<iostream>
using namespace std;
int helper(vector<vector<int>>& dis, vector<vector<int>>& dp, int city, int mode, int n) {
if (dp[city][mode] != 20001) return dp[city][mode];
if (mode == ((1<<n) - 1)) return dis[city][0];
for (int i = 1, index = 0; i < (1<<n); i<<=1, index ++) {//一定要<<=而不是<<
if ((mode | i) != mode) {
dp[city][mode] = min(dp[city][mode], dis[city][index] + helper(dis, dp, index, (mode|i), n));
}
}
return dp[city][mode];
}
int main() {
int n = 0;
cin >> n;
vector<vector<int>> dis(n, vector<int> (n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) cin>>dis[i][j];
}
int k = (1 << n) + 1;
vector<vector<int>> dp(n, vector<int>(k, 20001));
cout<<helper(dis, dp, 0, 1, n);
return 0;
}第六题：
传统的动态规划，找零钱问题
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n = 0;
cin>>n;
int dp[1024 - n + 1];
dp[0] = 0;
for (int i = 1; i <= 1024 - n; i++) {
dp[i] = 2048;
dp[i] = min(dp[i], dp[i - 1] + 1);
if (i >= 4) dp[i] = min(dp[i], dp[i - 4] + 1);
if (i >= 16) dp[i] = min(dp[i], dp[i - 16] + 1);
if (i >= 64) dp[i] = min(dp[i], dp[i - 64] + 1);
}
cout<<dp[1024 - n];
return 0;
}第七题：
类似力扣地下城问题，要求反向dp
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n = 0;
cin>>n;
vector<int> H(n);
for(int i = 0; i < n; i++) cin>>H[i];
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i --) dp[i] = (dp[i + 1] + H[i])/2;
cout<<dp[0] + 1;
return 0;
}
，校友加油
