字节跳动9/4笔试讨论
讨论一下字节笔试题目思路，
第一题用的滑动窗口，直接划过去就行
vector<int> mysplit(string& s)
{
string ks;
vector<int>ans;
for (int i = 0;i<s.size();i++)
{
if (s[i] != ',')
{
ks = ks + s[i];
}
else
{
ans.push_back(atoi(ks.c_str()));
ks = "";
}
}
ans.push_back(atoi(ks.c_str()));
return ans;
}
int main()
{
int N, mintinus;
string mys1;
cin >> mys1;
vector<int>kkk = mysplit(mys1);
N = kkk[0];
mintinus = kkk[1];
string mys2;
string mys3;
cin >> mys2;
cin >> mys3;
vector<int>customer = mysplit(mys2);
vector<int>smile = mysplit(mys3);
int left = 0;
int right = 0;
int mymax = 0;
int MAXkk = 0;
while (right<N&&left <= right)
{
if (right - left < mintinus)
{
if (smile[right] == 0)
{
mymax += customer[right];
}
right++;
}
else
{
if (smile[left] == 0)
{
mymax -= customer[left];
}
left++;
}
MAXkk = max(MAXkk, mymax);
}
int sum = 0;
for (int i = 0; i < N; i++)
{
if (smile[i] == 1)
{
sum += customer[i];
}
}
sum = sum + MAXkk;
cout << sum << endl;
system("pause");
return 0;
} 第二题动态规划，定义一个二维dp，dp[i][j]的含义是在第i行第j列开始向下可以得到的最大分数，最后把dp数组第0行取最大 int main02()
{
int N, M;
cin >> N >> M;
vector<vector<int>>marix(N,vector<int>(M));
for (int i = 0;i<N;i++)
{
for (int j = 0;j<M;j++)
{
int a;
cin >> a;
marix[i][j] = a;
}
}
int mymax = 0;
vector<vector<int>>dp(N + 1, vector<int>(M + 1));
for (int j = 0; j <= M; j++)
{
dp[N][j] = 0;
}
for (int j = 0; j <= N; j++)
{
dp[j][M] = 0;
}
for (int curx = N-1;curx>=0;curx--)
{
for (int cury = M-1;cury>=0;cury--)
{
int sorce = 0;
if (marix[curx][cury] == -1)
{
int num1 = dp[curx + 1][cury + 1];
int num2 = 0;
if (cury > 0)
{
num2 = dp[curx + 1][cury - 1];
}
dp[curx][cury] = max(num1, num2);
}
else
{
dp[curx][cury] = marix[curx][cury] + dp[curx + 1][cury];
}
}
}
for (int i = 0; i < M; i++)
{
mymax = max(mymax, dp[0][i]);
}
cout << mymax;
system("pause");
return 0;
} 第三题刚开始没有仔细读题，弄错了，题目要求任意ai+aj+ak都能在数组a中找到，我用了一个比较蠢的方法，把数组a放哈希表，枚举三数之和，若结果都可以在哈希表中找到，返回YES，否则返回NO，这个时间会超，希望大佬可以提供一下思路
int main()
{
int t;
cin >> t;
vector<vector<int>>mk;
//
for (int i = 0;i<t;i++)
{
int a;
cin >> a;
vector<int>nums(a);
for (int j = 0;j<a;j++)
{
int k;
cin >> k;
nums[j] = k;
}
mk.push_back(nums);
}
for (int i = 0; i < t; i++)
{
unordered_map<int, int>myans;
for (int j = 0;j<mk[i].size();j++)
{
auto it = myans.find(mk[i][j]);
if (it == myans.end())
{
myans.insert(pair<int, int>(mk[i][j], 0));
}
}
//枚举三数之和
bool flag = true;
for (int k1 = 0; k1 < mk[i].size(); k1++)
{
for (int k2 = k1+1; k2 < mk[i].size(); k2++)
{
for (int k3 = k2 + 1; k3 < mk[i].size(); k3++)
{
int sum = mk[i][k1] + mk[i][k2] + mk[i][k3];
auto it = myans.find(sum);
if (it == myans.end())
{
flag = false;
cout << "NO" << endl;
break;
}
}
if (flag == false)
{
break;
}
}
if (flag == false)
{
break;
}
}
if (flag == true)
{
cout << "YES" << endl;
}
}
return 0;
} 最后一题自己写题太慢，还没写，希望大家讨论一下
