呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

【2018秋招笔试】2018.9.9 字节跳动 算法工程师

前言

字节跳动出了5道编程题,可以说非常实在了……

2个小时,一共过了3道半。第四题的题目描述没看懂,和测试样例对不上……

第一题

思路:

“最长不重复子串”问题,套模板解决。

提交后AC。

代码:

#include<iostream>
#include<string.h>
#include <stdio.h>
using namespace std;

int lengthOfLongestSubstring(char* s) {
    int len=strlen(s);
    int count=0;
    int start=0;   //记录新子串的起始位置
    bool isOk=true;
    //char *tempS;
    //tempS=(char *)malloc(len);     无需额外的数组来存储

    int longLastIndex=0;
    int longLenth=0;

    for(int i=0;i<len;i++){
        isOk=true;
        for(int j=0;j<count;j++){
            if(s[j+start]==s[i]){     //改动处
                isOk=false;
                start=j+start+1;             //改动处
                break;
            }

        }
        if(isOk){
            count++;
            if(i==len-1&&longLenth<count){
                longLenth=count;
            }
        }
        else{
            if(longLenth<count){
                longLenth=count;
            }
            count=i-start+1;   //改动处

        }
    }

    return longLenth;
}

int main(){
    char s[100010] = {0};
    cin>>s;
    //scanf("%d",s);
    printf("%d",lengthOfLongestSubstring(s));
    return 0;
}

第二题



思路:

使用dfs统计矩阵中有多少个连通区域,这里的连通定义为上下左右相邻。

遍历矩阵的每一个元素,如果当前元素是1,部门数+1,同时从当前位置开始进行深搜(dfs),碰到0回退,碰到1则翻成0,这样便把与该位置1相连的所有1都变成了0;如果当前元素是0,则跳过。

遍历结束后便可以统计出连通区域有多少个,即部门数。

提交之后AC。

代码:

#include <iostream>
#include <stdio.h>
using namespace std;
int n;
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};

int a[1010][1010];

bool judge(int a[1010][1010],int x,int y)
{
    if(x<0 || y<0 || x>=n || y>=n)
        return 1;
    if(a[x][y]!=1)
        return 1;
    return 0;
}
void dfs1(int a[][1010],int x,int y)
{
    a[x][y] = 0;
    for(int i=0;i<4;i++){
        int cx = x+dx[i];
        int cy = y+dy[i];
        if(judge(a,cx,cy))
            continue;
        dfs1(a,cx,cy);
    }
}
int main()
{
    int Count=1;
    cin>>n;
    int num1 = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    }
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            if(a[i][j]==1){
                num1++;
                dfs1(a,i,j);
            }
        }
    cout<<num1<<endl;
    return 0;
}

第三题

思路:

可以用搜索暴力穷举可能的IP数量。

将去掉'.'的IP作为字符串输入,穷举每个位置有'.'的可能性,判断每个可能的IP是否符合正确格式(0<=每个位置的数字<=255)。

提交之后过了75%,不知道哪里没考虑到。

代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

char s[1000010] = {0};
int cnt = 0;
int len;
int a[4] = {0};
int h[99999] = {0};

bool isIP(int x)
{
    if(0<=x && x<=255)
        return true;
    else
        return false;
}

int getNum(int x)
{
    int num = 0;
    while(x){
        num++;
        x/=10;
    }
    return num;
}

void dfs(int curi,int num,int x)
{
    //curi 当前考虑的位置,num 剩余 . 的数量,x 当前数
    if(curi >= len || num<=0){
        if(curi >= len && num==0){
            int v = 0;
            int i;
            for(i=0;i<4;i++){
                v = v*10 + getNum(a[i]);
                /*
                if(i==0)
                    printf("%d",a[i]);
                else
                    printf(".%d",a[i]);
                    */
            }
            if(!h[v]){
                cnt++;
            }
            h[v] = 1;
        }
        return ;
    }
    int i;
    for(i=curi;s[i];i++){
        x = x*10 + s[i] - '0';
        if(isIP(x)){
            a[4-num] = x;
            dfs(i+1,num-1,0);
        }
        else
            break;
    }
}

int main()
{
    scanf("%s",s);
    len = strlen(s);
    dfs(0,4,0);
    printf("%d",cnt);
    return 0;
}

第四题


思路:

看题目描述是个模拟题,应该不难。

但是按题目中描述的算法和测试样例对不上啊,不知道是我理解有误还是题目写错了。

这题没提交,0%。

第五题


思路:

做这题的时候只有20分钟了,第三题找异常样例找了太长时间,最后也无果。

这道题瞅了一眼觉得是并查集,于是套模板,改了改提交过了50%。

想了想又觉得是变种并查集,需要大改代码,但是没时间做了,遗憾。

代码:

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAXN 150010

int par[MAXN];    //par[x]表示x的父节点
int num[MAXN] = {0};
int n;

void Init()    //初始化
{
    int i;
    for(i=1;i<=n;i++){
        par[i] = i;
        num[i] = 1;
    }
}

int Find(int x)    //查询x的根节点并路径压缩
{
    if(par[x]!=x){
        par[x] = Find(par[x]);
    }
    return par[x];
}

void Union(int x,int y)    //合并x和y所在集合
{
    num[par[y]] += num[x];
    par[Find(x)] = Find(y);
}

int main()
{
    int m,x,y,i;
    scanf("%d%d",&n,&m);
    //初始化
    Init();
    //m次询问
    while(m--){
        scanf("%d%d",&x,&y);
        Union(x,y);
    }
    int ans = n;
    for(i=1;i<=n;i++)    //统计
        if(par[i]!=i)
            --ans;
    int cnt = 0;
    for(i=1;i<=n;i++)
        if(num[i]==n-1)
            cnt++;
    printf("%d",cnt);
    return 0;
}

原创声明

转载请注明:呓语 » 【2018秋招笔试】字节跳动 算法工程师