字节跳动-夏令营笔试-1
字节跳动-夏令营笔试题-2021.05.30
投了个机器人赛道的，错过了一次笔试，来看看题是什么难度吧haha
还没有春招实习生笔试的题难。。。 但是吧 自己做还是不会
01 - 字符串匹配
给定一个订场的字符串，其中包含若干字符，求该字符串中一个连续子串，满足两个条件：
子串包含该字符串中的所有不同字符
满足上一个条件中最短的一个，如果有多个，则找从左到右第一个出现的字串
可变长度的滑动窗口，力扣应该有原题吧 - Leetcode 70
pair<int, int> findStrMatchLength(string s)
{
int cnt = 0, suc = 0, res = INT_MAX, si = -1;
unordered_map<char, int> sset, window;
// 1. 统计次数
for(auto c : s)
if(!sset.count(c))
sset[c] = 1, cnt++;
// 2. 维护滑动窗口
for(int l = 0, r = 0; r < s.size(); r++)
{
char c = s[r];
window[c]++;
if(window[c] <= sset[c]) suc++;
while(window[s[l]] > sset[s[l]]) window[s[l++]]--;
if(suc == cnt)
{
if(res > r - l + 1)
res = r - l + 1, si = l;
}
}
return {si, res};
}02 - 下象棋
小A 和 小B在下象棋，经过激烈的对决，两个人都只剩下了将和一匹马，因此小A提议，如果小B能计算出在小A不移动棋子，且小B的马只能向右上方移动的情况下，小B的马从原点出发能顺利取胜的路径数（吃掉小A的将，且在移动过程中不被小A的马攻击），就算小B赢的对局；
马行动的规则：马走日，一直一斜。即马每次行动需进行两个步骤，首先向右或向上移动一格（一直），再沿原移动方向倾斜45度的对角线跳动一次（一斜）。例如，假设马的位置为( 0, 0)，那么马行动一次可以移动到( 1, 2)或( 2, 1)。但是，马在直线移动后不能落在一个已有棋子的位置上，否则马将无法沿对角线跳跃。即，当马的位置在( 0, 0)，且（ 1, 0）位置有棋子时，马不能到达( 2, 1)，但可到达( 1, 2)。
给定对方的马和将的位置，默认自己的马在原点
感觉是经典的动态规划；
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int n, m;
int hi, hj, ki, kj;
int f[N][N];
int main()
{
scanf("%d%d%d%d", &hi, &hj, &ki, &kj);
f[0][0] = 1;
set<pair<int, int>> sset = {
// 1. 可攻击范围
{hi - 1, hj - 2},
{hi - 1, hj + 2},
{hi + 1, hj - 2},
{hi + 1, hj + 2},
{hi - 2, hj - 1},
{hi - 2, hj + 1},
{hi + 2, hj - 1},
{hi + 2, hj + 1},
// 2. 有占着
{ki + 1, kj + 1},
{hi + 1, hj + 1},
};
f[2][2] = 1;
for(int i = 2; i <= ki + 1; i++)
for(int j = 2; j <= kj + 1; j++)
{
if(sset.count({i, j})) continue;
f[i][j] += f[i - 1][j - 2] + f[i - 2][j - 1];
// 问题就在于什么样是会被攻击的
// 1. 存在于对面马的日字范围内 会被攻击
// 2. 对面马的行走路径 or 无法转移etc
}
return f[ki + 1][kj + 1];
}03 - 树上dp
淦 树上dp我真的很会，但是每次都轮不到我考sos
和没有上司的舞会是一样的
某公司想在10月24日为每个人定制一件文化衫。文化衫有D、E、F三种款式。 D[i] 表示编号为 i 的员工收到 D 款式的文化衫时的快乐值。 E[i] 表示编号为 i 的员工收到 E 款式的文化衫时的快乐值。 F[i] 表示编号为 i 的员工收到 F 款式的文化衫时的快乐值。 没有人愿意和自己的直系领导撞衫。 求所有人收到文化衫时的快乐值总和的最大值。
输入描述: 共有 2 N 行。 第 1 行是公司的总人数 N( 2 <= N <= 5000)。 第 2 行到第 N + 1 行描述了员工的快乐值。第 i + 2 行是三个空格分隔的整数： D[i]( 0 <= D[i] <= 100)、 E[i]( 0 <= E[i] <= 100)、 F[i]( 0 <= F[i] <= 100) 表示编号为 i 的员工收到文化衫时的快乐值。最大的领导的编号为 0。 第 N + 2 行到第 2 N 行描述了公司的上下级关系。每行有两个空格分隔的整数：A 和 B，表示 A 是 B 直系领导。除大领导之外，每个员工有且只有一个直系领导。
输出描述: 一个整数，快乐值总和的最大值
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 5050;
int n, root;
int h[N], e[N], ne[N], idx;
int happy[N][3];
int f[N][3]
bool has_father[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
f[u][0] = happy[u][0];
f[u][1] = happy[u][1];
f[u][2] = happy[u][2];
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += max(f[j][1], f[j][2]);
f[u][1] += max(f[j][0], f[j][2]);
f[u][2] += max(f[j][0], f[j][1]);
}
}
int main()
{
scanf("%d", &n);
// 1. 统计快乐值
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d", &f[i][0], &f[i][1], &f[i][2]);
}
for(int i = 1; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
has_father[b] = true;
}
// 2. 找到root
for(int i = 1; i <= n; i++)
if(!has_father[i])
{
root = i;
break;
}
dfs(root);
cout << max(max(f[root][1], f[root][1]), f[root][2]) << endl;
return 0;
}Last updated