首页 > 9.6字节跳动笔试部分题解
头像
Carits
编辑于 2020-09-06 21:13
+ 关注

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或者大数
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%,想着三题差不多就跑路了


全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐