9.6字节跳动笔试部分题解
第一题
题意：走阶梯，有限制条件：1.只能走一步或者走两步 2.不能连续跳两步
思路：dp[i][j]表示通过跳j步跳到i个的方案数，那么显然dp[i][1]==dp[i][1]+dp[i-1][2]+dp[i-1][1]
而dp[i][2]=dp[i][2]+dp[i-2][1],最后输出就好了，我用的是python，其他语言的话可能要开long long或者大数
题意：求左边第一个比a[i]大的a[j]的坐标j，定义为L[i]=j，如果没有则L[i]=0
和右边第一个比a[i]的大的a[k]的坐标k，定义R[i]=k，如果没有则R[i]=0
求最大的R[i]*L[i]
做法：没有什么好i说的，单调栈裸题，建议百度看一下。求出所有的R[i]和L{i],然后求他们的乘积即可
题意：给定n长的序列，可以把序列乘以m 倍变成n*m倍的，求最大连续和，且至少包含一个元素
做法：1.求出这个序列本身的最大连续和（这种情况下至少选一个）
2.求包含x个一整个序列（长度为n的）的最大连续和，这种情况下要求序列的和必须大于等于0，并且m大于等于2
将二者求最大值，第一种就是简单的最大连续和，注意一下至少选一个，第二题通过dp求出从左至右包含当前元素的最大连续和（从右至左同理）
那么，答案显然就两者之和加上中间包含的序列总和。
#笔试题目##字节跳动#
题意：走阶梯，有限制条件：1.只能走一步或者走两步 2.不能连续跳两步
思路：dp[i][j]表示通过跳j步跳到i个的方案数，那么显然dp[i][1]==dp[i][1]+dp[i-1][2]+dp[i-1][1]
而dp[i][2]=dp[i][2]+dp[i-2][1],最后输出就好了，我用的是python，其他语言的话可能要开long long或者大数
dp=[] for i in range(0,105): dp.append([0,0,0,0]) dp[1][1]=1 dp[2][2]=1 dp[2][1]=1 n=int(input()) for i in range(3,105): dp[i][1]=dp[i][1]+dp[i-1][2]+dp[i-1][1] dp[i][2]=dp[i][2]+dp[i-2][1] print(dp[n][1]+dp[n][2])第二题：
题意：求左边第一个比a[i]大的a[j]的坐标j，定义为L[i]=j，如果没有则L[i]=0
和右边第一个比a[i]的大的a[k]的坐标k，定义R[i]=k，如果没有则R[i]=0
求最大的R[i]*L[i]
做法：没有什么好i说的，单调栈裸题，建议百度看一下。求出所有的R[i]和L{i],然后求他们的乘积即可
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll L[N],R[N];
ll a[N];
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
stack<ll>st1;
stack<ll>st2;
for(int i=1;i<=n;i++)
{
while(!st1.empty()&&a[i]>=a[st1.top()])
st1.pop();
if(st1.empty())
L[i]=0;
else
L[i]=st1.top();
st1.push(i);
}
for(int i=n;i>=1;i--)
{
while(!st2.empty()&&a[i]>=a[st2.top()])
st2.pop();
if(st2.empty())
R[i]=0;
else
R[i]=st2.top();
st2.push(i);
}
ll ans=0;
for(int i=1;i<=n;i++)
ans=max(L[i]*R[i],ans);
printf("%lld\n",ans);
return 0;
}
第三题：题意：给定n长的序列，可以把序列乘以m 倍变成n*m倍的，求最大连续和，且至少包含一个元素
做法：1.求出这个序列本身的最大连续和（这种情况下至少选一个）
2.求包含x个一整个序列（长度为n的）的最大连续和，这种情况下要求序列的和必须大于等于0，并且m大于等于2
将二者求最大值，第一种就是简单的最大连续和，注意一下至少选一个，第二题通过dp求出从左至右包含当前元素的最大连续和（从右至左同理）
那么，答案显然就两者之和加上中间包含的序列总和。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
const ll INF=1e17;
ll dp[N][2];
ll a[N*2];
int main()
{
ll n,m,i;
scanf("%lld %lld",&n,&m);
ll maxsum=0;
ll sum=0;
ll ans=-INF;
for( i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
if(maxsum+a[i]<0)
{
maxsum=0;
}
else
{
maxsum+=a[i];
ans=max(maxsum,ans);
}
ans=max(ans,a[i]);
}
dp[n][0]=a[n];
dp[1][1]=a[1];
for(i=2;i<=n;i++)
{
dp[i][1]=max(dp[i-1][1]+a[i],a[i]);
}
for(i=n-1;i>=1;i--)
{
dp[i][0]=max(dp[i+1][0]+a[i],a[i]);
}
if(sum>0&&m>=2)
{
ll k=(m-2)*sum;
ans=max(k+dp[1][0]+dp[n][1],ans);
}
if(m>=2)
{
ans=max(dp[1][0]+dp[n][1],ans);
}
printf("%lld\n",ans);
return 0;
}
第四题：没写了，据说输出0也有20%，想着三题差不多就跑路了#笔试题目##字节跳动#
投递美团等公司9个岗位