[20180812] 今日头条笔试

今日头条AC了前两道,后面一个多小时一道没A出,但是第4题和第5题的测试用例都过了,结果case率0%,哎,凉凉了~~

我分享一下思路,静待大神解惑

1.第一题是一个连通域的问题,找出一个矩阵中有多少个连通域,最大的连通域包含多少个元素

直接dfs解决就可以了(并不会重复,因为检测到1后就设置为0)

java实现

public class TouTiaoqz01 {
    static int cout=0;
    public static void findQ(int i,int j,int[][]a){
        if(i-1>=0&&a[i-1][j]==1){
            cout++;
            a[i-1][j]=0;
            findQ(i-1,j,a);
        }
        if(i-1>=0&&j+1<a[0].length&&a[i-1][j+1]==1){
            cout++;
            a[i-1][j+1]=0;
            findQ(i-1,j+1,a);
        }
        if(j+1<a[0].length&&a[i][j+1]==1){
            cout++;
            a[i][j+1]=0;
            findQ(i,j+1,a);
        }
        if(i+1<a.length&&j+1<a[0].length&&a[i+1][j+1]==1){
            cout++;
            a[i+1][j+1]=0;
            findQ(i+1,j+1,a);
        }
        if(i+1<a.length&&a[i+1][j]==1){
            cout++;
            a[i+1][j]=0;
            findQ(i+1,j,a);
        }
        if(i+1<a.length&&j-1>=0&&a[i+1][j-1]==1){
            cout++;
            a[i+1][j-1]=0;
            findQ(i+1,j-1,a);
        }
        if(j-1>=0&&a[i][j-1]==1){
            cout++;
            a[i][j-1]=0;
            findQ(i,j-1,a);
        }
        if(i-1>=0&&j-1>=0&&a[i-1][j-1]==1){
            cout++;
            a[i-1][j-1]=0;
            findQ(i-1,j-1,a);
        }
    }

    public static void findPQ(int[][]a){
        List<Integer> res= new ArrayList<>();
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a[0].length;j++){
                if(a[i][j]==1){
                    cout=1;
                    a[i][j]=0;
                    findQ(i,j,a);
                    System.out.println(i+","+j+","+cout);
                    res.add(cout);
                }
            }
        }
        System.out.println(res.size()+","+ Collections.max(res));
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int m,n;
        String temp;
        temp=scanner.nextLine();
        String[] mn=temp.split(",");
        m=Integer.parseInt(mn[0]);
        n=Integer.parseInt(mn[1]);
        int a[][]=new int[m][n];
        for(int i=0;i<m;i++){
            temp=scanner.nextLine();
            String[] str=temp.split(",");
            for(int j=0;j<n;j++){
                a[i][j]=Integer.parseInt(str[j]);
            }
        }
        findPQ(a);
    }
}

2. 第二道题是一个合并线段的问题

先对线段的头坐标排序,然后遍历一遍就可以了

python实现

def merge_tuple(tuple_list):
    tuple_list=sorted(tuple_list,key=lambda x:x[0])
    res=[]
    i=0
    while i<len(tuple_list):
        start_index=tuple_list[i][0]
        end_index=tuple_list[i][1]
        while i<len(tuple_list) and end_index>=tuple_list[i][0]:
            end_index=max(end_index,tuple_list[i][1])
            i+=1
        res.append((start_index,end_index))
    print(';'.join(str(item[0])+','+str(item[1]) for item in res))

if __name__=='__main__':
    m=input()
    tuple_list=[]
    for i in range(int(m)):
        s=input()
        temp=s.split(';')
        for item in temp:
            index=item.split(',')
            tuple_list.append((int(index[0]),int(index[1])))
    merge_tuple(tuple_list)

3. 从一个数组中找出两个不相交的子集,使得这两个子集的和相等,找出全部满足条件子集对
这是我对第3道题的理解,没想出来怎么解

4.找出两个数组的对应下标相等的子集a,b,并且满足max(a)<min(b)
这道题我的思路就是将问题分解为两部分,一部分为窗口长度(1层for循环),一部分为对指定窗口长度进行遍历,计算满足条件的个数(知道会超时,但是竟然case%=0%)

def find_num(a,b,i):
    res=0
    for j in range(len(a)):
        if j+i<=len(a) and max(a[j:j+i])<min(b[j:j+i]):
            res+=1
    return res

def find_max(a,b):
    cout=0
    for i in range(1,len(a)+1):
        cout+=find_num(a,b,i)
    return cout

if __name__=='__main__':
    n=input()
    a_str=input()
    b_str=input()
    a=[int(i) for i in a_str.split(' ')]
    b=[int(i) for i in b_str.split(' ')]
    print(find_max(a,b))

5. 给出一些线段,从中选取尽量多的线段,并使得选取的线段不重叠
很明显用dp+for解决,测试案例也通过了,但是case%=0%

def find_max(st_list):
    st_list=sorted(st_list,key=lambda x:x[0])
    dp=[]
    dp.append((0,-1))
    for i in range(len(st_list)):
        temp=0
        for j in range(i+1):
            end_index=st_list[i][1]
            if dp[j][1]<=st_list[i][0]:
                if temp<=dp[j][0]+1:
                    temp = max(temp, dp[j][0] + 1)
                    if temp==dp[j][0]+1 and dp[j][1]>0:end_index =min(dp[j][1],end_index)
        dp.append((temp,end_index))
    print(dp[-1][0])

if __name__=='__main__':
    n=input()
    m=input()
    n,m = int(n),int(m)
    st=input()
    st=st.split(' ')
    st_list=[]
    for i in range(n):
        st_list.append((int(st[2*i]),int(st[2*i+1])))
    find_max(st_list)
#字节跳动##内推##笔试题目##题解#
全部评论
// 我的第1题AC代码 #include <iostream> #include <vector> using namespace std; int M, N, P = 0, Q = 0; void search(vector<vector<int>> &G, int i, int j, int &Max) {     if (i < 0 || i >= M || j < 0 || j >= N)         return;     if (G[i][j] == 1) {         G[i][j] = 0; Max += 1;         search(G, i - 1, j, Max); search(G, i + 1, j, Max);         search(G, i, j - 1, Max); search(G, i, j + 1, Max);         search(G, i - 1, j + 1, Max); search(G, i + 1, j - 1, Max);         search(G, i - 1, j - 1, Max); search(G, i + 1, j + 1, Max);     } } int main() {     scanf("%d,%d", &M, &N);     vector<vector<int>> G(M, vector<int>(N));     for (int i = 0; i < M; ++i)         for (int j = 0; j < N; ++j)             scanf("%d,", &G[i][j]);     for (int i = 0; i < M; ++i) {         for (int j = 0; j < N; ++j) {             if (G[i][j] == 1) {                 int Max = 0; P++;                 search(G, i, j, Max);                 if (Max > Q) Q = Max;             }         }     }         cout << P << "," << Q;     return 0; } // 我的第2题AC代码 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; struct region {     int l, r; }; region str2region(const string &s) {     struct region res;     int a = s.find(',');     res.l = stoi(s.substr(0, a));     res.r = stoi(s.substr(a + 1, s.length() - 1));     return res; } struct compare {     bool operator() (region a, region b) {         if (a.l != b.l)             return a.l < b.l;         else             return a.r < b.r;     }  }; int main() {     int m, a;     string s, r;     vector<region> regions;     cin >> m;     for (int i = 0; i < m; ++i) {         cin >> s;         while ((a = s.find(';')) != -1) {             r = s.substr(0, a);             s = s.substr(a + 1, s.length() - 1);             regions.push_back(str2region(r));         }         regions.push_back(str2region(s));     }     sort(regions.begin(), regions.end(), compare());     for (int i = 0; i < regions.size() - 1; ++i) {         if (regions[i].r >= regions[i + 1].l) {             regions[i].r = regions[i + 1].r;             regions.erase(regions.begin() + i + 1);             --i;         }     }     int i;     for (i = 0; i < regions.size() - 1; ++i)         cout << regions[i].l << ',' << regions[i].r << ';';     cout << regions[i].l << ',' << regions[i].r << endl;     return 0; } // 我的第5题AC代码 #include<iostream> #include<vector> #include<algorithm> using namespace std; struct Anchor {     int s, e; }; struct compare {     bool operator() (Anchor a, Anchor b) {         if (a.e != b.e)             return a.e < b.e;         else             return a.s < b.s;     } }; int main() {     int N, M, res = 0, curr = 0;     cin >> N >> M;     Anchor anchor;     vector<Anchor> anchors;     for (int i = 0; i < N; ++i) {         cin >> anchor.s >> anchor.e;         if (anchor.e < anchor.s && anchor.e == 0)             anchor.e += N;         if (anchor.e >= anchor.s)             anchors.push_back(anchor);     }     sort(anchors.begin(), anchors.end(), compare());     for (int i = 0; i < anchors.size(); ++i) {         if (curr <= anchors[i].s) {             res++;             curr = anchors[i].e;         }     }     cout << res << endl;     return 0; } // 第3题20% 哎 - -~!浪费了太多时间 /* 我的思路是转换成0-1背包问题的,先取若干张卡,然后用canDivide判断这些卡片 * 能不能被分为和相等的两组,我的直觉感觉我的canDivide有问题,时间紧没有去推导 * 然后canDivide传入的参数已经从大到小排列了的。 */ #include<iostream> #include<vector> #include<algorithm> using namespace std; struct Card {     int person;     int group; }; struct compare {     bool operator() (Card a, Card b) {         if (a.person != b.person)             return a.person > b.person;         else             return a.group > b.group;     } }; bool canDivide(const vector<Card> &cards) {     int res = 0, i;     for (i = 0; i < cards.size(); i++) {         if (res > 0)             res -= cards[i].person;         else             res += cards[i].person;     }     return res == 0; } int sumCard(const vector<struct Card> &cards) {     int i;     int sum = 0;     for (int i = 0; i < cards.size(); i++)         sum += cards[i].group;     return sum; } int bag(const vector<Card> &cards, vector<Card> curr, int i) {     if (i == cards.size()) {         if (canDivide(curr))             return sumCard(curr);         else             return 0;     }     else {         int a = bag(cards, curr, i + 1);         curr.push_back(cards[i]);         int b = bag(cards, curr, i + 1);         return a > b ? a : b;     } } int main() {     int n;     vector<Card> cards, curr;     Card card;     cin >> n;     for (int i = 0; i < n; ++i) {         cin >> card.person >> card.group;         cards.push_back(card);     }     sort(cards.begin(), cards.end(), compare());     cout << bag(cards, curr, 0) << endl;     return 0; } // 第3题最后没时间了,投机取巧拿了40% #include <cstdio> using namespace std; int main() {     int n;     scanf("%d", &n);     int sum = 0;     for(int i = 0; i < n; ++i) {         int a, b;         scanf("%d %d", &a, &b);         sum += b;     }     printf("%d", sum); } // 第4题60% 哎 - -~! 不想说啥了,***难受~! 代码就不发了,惭愧~!!!
点赞 回复 分享
发布于 2018-08-12 13:39
第三题,直接输出所有的sum就是,40%,第四题,暴力只能过20%吧
点赞 回复 分享
发布于 2018-08-12 12:42
大佬,膜拜啊,我也是125过了,第四题就过了30%,第三题没有思路
点赞 回复 分享
发布于 2018-08-14 09:06

相关推荐

09-29 17:44
已编辑
蔚来_测(准入职员工)
//鲨鱼辣椒:见不了了我实习了四个月上周再投筛选了一天就给我挂了
点赞 评论 收藏
分享
点赞 30 评论
分享
牛客网
牛客企业服务