今日头条研发岗笔试题

AC了3个第四个交卷发现了一个bug 但是不知道对不对请大佬们看看

T1:DFS搜联通快

import java.util.Scanner;

public class A {

    int m,n;
    int vis[][] = new int[1005][1005];
    int mp[][] = new int[1005][1005];
    int fx[][] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
    int p = 0,q = 0,sum;
    Scanner scanner;

    void solve(){
        scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String []ss = s.split(",");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);

        for(int i=0;i<n;i++){
            String str = scanner.nextLine();
            String[]num = str.split(",");
            for(int j=0;j<m;j++){
                mp[i][j] = Integer.parseInt(num[j]);
            }
        }
        // System.out.println(n+"  "+m);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]==1&&vis[i][j]==0){
                    sum = 0;
                    p++;
                    dfs(i,j);
                    q = Math.max(q,sum);
                }
            }
        }
        System.out.println(p+","+q);
    }

    void dfs(int h,int l){
        sum++;
        vis[h][l] = 1;
        for(int i=0;i<8;i++){
            int hh = fx[i][0]+h;
            int ll = fx[i][1]+l;
            if(check(hh,ll)){
                dfs(hh,ll);
            }
        }
    }

    boolean check(int hh, int ll) {
        if(hh>=0&&hh<n&&ll>=0&&ll<m&&mp[hh][ll]==1&&vis[hh][ll]==0){
            return  true;
        }
        return false;
    }

    public static void main(String[] args) {
        new A().solve();
    }
}

T2：把所有区间做个结构体排序 java写结构体排序写炸了，，浪费了好多时间

import java.util.*;
public class B {
    class Node implements Comparable<Node>{
        public long l;
        public long r;
        public Node(){
        }
        public Node(Long l, Long r) {
            this.l = l;
            this.r = r;
        } @Override public int compareTo(Node o) {
            if(o.l==this.l)return this.r<o.r?-1:1;
            return this.l<o.l?-1:1;
        }
    }
    ArrayList<Node> node = new ArrayList<>();
    ArrayList<Node> ans = new ArrayList<>();
    int n;
    int m;
    Scanner scanner = new Scanner(System.in);
    void solve() {
        m = scanner.nextInt();
        n = 0;
        while (m-- > 0) {
            String str = scanner.next();
            //System.out.println(str);
            String[] str1 = str.split(";");
            for (int i = 0; i < str1.length; i++) {
               // System.out.println(str1[i]);
                String[] s = str1[i].split(",");
                node.add(new Node(Long.parseLong(s[0]), Long.parseLong(s[1])));
                n++;
            }
        }
        Collections.sort(node);
        long l = node.get(0).l;
        long r = node.get(0).r;
        for(int i=0;i<node.size();i++){
            if(node.get(i).l>r){
                ans.add(new Node(l,r));
                l = node.get(i).l;
                r = node.get(i).r;
            }else{
                r = Math.max(r,node.get(i).r);
            }
        }
        ans.add(new Node(l,r));
        StringBuffer ss = new StringBuffer("");
        for(int i=0;i<ans.size();i++){
            ss.append(ans.get(i).l);
            ss.append(",");
            ss.append(ans.get(i).r);
            if(i!=ans.size()-1){
                ss.append(";");
            }
        }
        System.out.println(ss.toString());
    }
    public static void main(String[] args) {
        new B().solve();
    }
}

T3：感觉像背包，，但是有很多不好处理，哪位大佬能提供AC代码不？

T4：没有AC 我的做法是记录a数组每个数左右比他小的连续的数的个数记录b数组左右比他大的数的连续的个数然后就是当ai是最大数 bi是最小数时算下区间个数

不知道对不对因为代码提交的时候把bi写成ai了，，结束后才发现

没有AC的代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
int al[100005],ar[100005];
int bl[100005],br[100005];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    al[0] = 0;
    bl[0] = 0;
    for(int i=1;i<n;i++)
    {
        if(a[i]>=a[i-1])al[i] = al[i-1]+1;
        else al[i] = 0;
        if(b[i]<=b[i-1])bl[i]= bl[i-1]+1;
        else bl[i] = 0;
    }
    ar[n-1] = 0;
    br[n-1] = 0;
    for(int i=n-2;i>=0;i--)
    {
        if(a[i]>=a[i+1])ar[i] = ar[i+1]+1;
        else ar[i] = 0;
        if(b[i]<=b[i+1])br[i] = br[i+1]+1;
        else br[i] = 0;
    }
    long long ans = 0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<b[i])
        {

            int l = min(al[i],bl[i]);
            int r = min(ar[i],br[i]);
            //cout<<l<<" "<<r<<endl;
            ans+=(1ll+l+r+l*r*1ll);
        }
    }
    cout<<ans<<endl;
    return 0;
}

T5：区间结构排序下就是特别注意第二天的情况 r+m 最后还要判断 r<=m 因为只能在第一天看完

#include<bits/stdc++.h>
using namespace std;
struct st
{
    int l,r;
}s[100005];
bool cmp(st a, st b){
    if(a.l==b.l){
        return a.r<b.r;
    }
    return a.l<b.l;
}
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        scanf("%d%d",&s[i].l,&s[i].r);
        if(s[i].l>s[i].r)s[i].r+=m;
    }
    sort(s,s+n,cmp);
    int ans = 0;
    int l = 0,r = 0;
    for(int i=0;i<n;i++){
            if(s[i].r>m)continue;
        if(s[i].l>=r){
            ans++;
            l = s[i].l,r = s[i].r;
        }else{
            if(s[i].r<r)r = s[i].r;
        }
    }
    cout<<ans<<endl;
    return 0;
}

#字节跳动##笔试题目##题解#