2020.09.10-深信服笔试复盘

应聘岗位：C/C++软件开发工程师（云计算、网络安全方向）

一、接雨水的变体

1）我的最终代码（72.73%），应该是100%的，样例有问题

我觉得我的这个理解才是正确的，我考虑了水流从左边到右边和右边到左边，然后获取最大的
但是，别人只考虑水流从左边到右边就全AC了，所以我觉得这个题目有误。
PS：吐槽这个题目，我最开始，硬是没有看懂题目，分不清，那个三维的图有没有画错
我还问了监考官，样例有没有错，它说没有错，我就考虑是要把高度改一下，然后就转换为“接雨水”题目的变体了。

但是，最后，谁知道“只考虑水流从左边到右边就全AC了”、、、、

//one.3.cpp
#include<bits/stdc++.h>
using namespace std;

const int maxn=10000+5;
int height[maxn];
//截止到i，最高的是什么？ 包括它本身 
int dpLeft[maxn];
int dpRight[maxn]; 

void solve(int n) 
{
    dpLeft[0]=height[0];
    for(int i=1;i<n;++i)
    {
        if(height[i]>dpLeft[i-1])
        {
            dpLeft[i]=height[i];
        }
        else
        {
            dpLeft[i]=dpLeft[i-1];
        }
    }


    dpRight[n-1]=height[n-1];

    for(int i=n-2;i>=0;--i)
    {
        if(height[i]>dpRight[i+1])
        {
            dpRight[i]=height[i];
        }
        else
        {
            dpRight[i]=dpRight[i+1];
        }
    }
}

int main()
{
    int W,L;
    while(~scanf("%d%d",&W,&L))
    {
        for(int i=0;i<L;++i)
        {
            scanf("%d",&height[i]);
        }

        //代码健壮性 
        if(L<1)
        {
            printf("0\n");
        }


        solve(L) ;


        //水流从左边往右边 
        int leftSum=0;
        for(int i=0;i<L-1;++i)
        {
            int temp=dpRight[i+1]-height[i];
            if(temp>0)
            {
                leftSum+=temp;
            }

        }

        leftSum*=W;


        //水流从右边往左边 
        int rightSum=0;
        for(int i=L-1;i>=1;--i)
        {

            int temp=dpLeft[i-1]-height[i];

            if(temp>0)
            {
                rightSum+=temp;    
            }
        }

        rightSum*=W;

        printf("%d\n",max(leftSum,rightSum));
    }


    return 0;
} 

二、囚犯从牢房逃离

考点：搜索

代码（30%）

时间实在来不及了，只能潦草的写个DFS，然后还忘记记录了。。。尴尬

#include<bits/stdc++.h>
using namespace std;

int sum=0;

int x,y;
int tag[10][10];

int test()
{

    for(int i=0;i<x;++i)
    {
        for(int j=0;j<y;++j)
        {
            if(0==tag[i][j])
            {
                return 0;
            }
        }
    }


    return 1;
}

void DFS(int beginX,int beginY)
{
    if(beginX<0 || beginX>(x-1) || beginY>(y-1) || beginY<0)
    {
        return ;
    }

    tag[beginX][beginY]=1;

    if(1==test())
    {
        ++sum;
    }

    DFS(beginX+1,beginY);
    DFS(beginX-1,beginY);
    DFS(beginX,beginY+1);
    DFS(beginX,beginY-1);
}

int main()
{

    while(~scanf("%d%d",&x,&y))
    {

        int beginX,beginY;
        scanf("%d%d",&beginX,&beginY);

        int endX,endY;
        scanf("%d%d",&endX,&endY);

        sum=0;
        memset(tag,0,sizeof(tag));
        DFS(beginX-1,beginY-1);

        printf("%d\n",sum);
    }

    return 0;
 } 

02.深信服笔试常考

本次笔试
6选择+4填空+2编程

考点：动态规划。DFS，递归

结合以前准备深信服的“星耀计划”等
发现深信服蛮喜欢考

DFS等搜索
递归

好像，字符串也蛮喜欢

题目感觉都喜欢改编剑指offer啥的