欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25

程序员文章站 2023-12-24 22:09:03
...

文中没给代码的后期补上,有AC的同学欢迎评论发一下代码
牛客讨论帖 https://www.nowcoder.com/discuss/98663?type=2&order=0&pos=5&page=1
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
这道题考察的是并查集(或者DFS),看代码前请先了解一下并查集
并查集解释
上面那个链接的博客里面代码有点错误,错误之处在评论中有指出

并查集思路:

#include <stdio.h>
#define N 100020
int friends[N];//每个人所属的连通分量,即构成朋友树时每个人的父节点
int rank[N];//连通分量的权值,即朋友树的大小
int res;
void init(int n)//初始化initialization
{
    for(int i=0;i<n;i++)
    {
        friends[i]=i;
        rank[i]=0;
    }
}

int findRoot(int x)//寻找x所属的朋友树的根节点
{
    //一直向上遍历寻找根节点
    while(x != friends[x])
        x = friends[x];
    return x;
}

void connect(int x,int y)
{
    int xRoot = findRoot(x);
    int yRoot = findRoot(y);
    if(xRoot == yRoot)
        return ;
    //判断树高,小树并在大树下
    if(rank[xRoot] < rank[yRoot])
        friends[xRoot]=yRoot;
    else
    {
        friends[yRoot] = xRoot;
        if(rank[xRoot]==rank[yRoot])//两树高相等,合并后树高+1
            rank[xRoot]++;
    }
    --res;
}
int main()
{
    int n;
    init(N);//初始化
    scanf("%d",&n);
    res = n;
    for(int i=1;i<=n;i++){
        int t;
        while(~scanf("%d",&t)){
            if(t == 0)
                break;
            connect(i,t);
        }
    }
    printf("%d",res);
/*
10
0
5 3 0
8 4 0
9 0
9 0
3 0
0
7 9 0
0
9 7 0
*/
    return 0;
}

DFS思路:

#include <iostream>
#include <vector>
using namespace std;
int n;
int res;
void dfs(vector<vector<int>>& friends, int x, int y,vector<vector<bool>>& mark){
    if(x >=  friends.size() || y >= friends[0].size() || x < 0 || y < 0)
        return;
    if(mark[x][y] == true)
        return;
    if(friends[x][y] == 0){
        mark[x][y] = true;
        return;
    }
    // 对于已经搜索过的点要进行标记
    mark[x][y] = true;
    res--;
    for(int j=1; j<n; j++){
        dfs(friends, x, j, mark);
    }

}
void minM(vector<vector<int>>& friends) {
    if(friends.empty())
        return;
    res = n;
    vector<vector<bool>> vecMark(friends.size(),vector<bool>(friends[0].size(),false));// 定义标记数组
    //开始搜索
    for(int i = 1;i < friends.size();i++){
        for(int j = 1;j < friends[0].size();j++){
            if(vecMark[i][j] == true)
                continue;
            if(friends[i][j] == 0){
                vecMark[i][j] = true;
                continue;
            }

            dfs(friends, i, j, vecMark);
        }

    }
    cout << num << endl;
}
int main()
{
    cin >> n;
    vector<vector<int>> friends(n+1, vector<int>(n+1,0));
    int temp = 0;
    for(int i=1; i<=n; i++){
        int j = 1;
        while(cin>>temp){
            if(temp == 0)
                break;
            friends[i][j] = temp;
            j++;
        }
    }
    minM(friends);
    return 0;
}

字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
思路:
本来是在全局序列之中求最长上升子序列,但是因为是重复的序列,
其实只需在第一个序列之中求最长上升序列,并且其中的最大元素在后面的每个序列之中一定存在,最后加上b-1(b为重复序列个数)
ans[] 存储给定序列
tmp[i] 表示从第0位到第i位的最长子序列个数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{

    int a,b;
    scanf("%d%d", &a, &b);
    vector<int> ans(a, 0),tmp(a,1);
    for (int i = 0;i<a;i++)
    {
        scanf("%d", &ans[i]);
    }
    for (int i = 1;i<a;i++)
    {
        for (int j = 0;j<i;j++)
        {
            if (ans[i]>=ans[j])
            {
                tmp[i] = max(tmp[i], tmp[j] + 1);
            }
        }
    }
    cout << *max_element(tmp.begin(), tmp.end())+b-1;
    return 0;
}

字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25
字节跳动2019校园招聘研发岗位第二次笔试-2018.08.25

上一篇:

下一篇: