有没有大佬写一下今天头条的第一个编程题

这个题目很容易做。笔试结束后有人会分享的

def maxAreaOfIsland(grid): m, n = len(grid), len(grid[0]) def dfs(i, j): if 0 <= i < m and 0 <= j < n and grid[i][j]: grid[i][j] = 0 return 1 + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i-1, j-1) + dfs(i-1, j+1) + dfs(i+1, j-1) + dfs(i+1, j+1) return 0 areas = [dfs(i, j) for i in range(m) for j in range(n) if grid[i][j]] return max(areas) if areas else 0, len(areas) print(maxAreaOfIsland(values)) ```

我就做出一道题 其他都凉了，宿舍人又是唱歌又是放歌，还有洗衣服看电视的，根本弄不成。  气的肚子疼嘞！ import java.util.Scanner; public class Main {     static boolean[][] boo;      static int m,n;     static int[][] zuowei;     static int count=0;     static int num=0;     static int max=0;     public static void main(String[] args) {         Scanner scanner=new Scanner(System.in);         String mn = scanner.nextLine();         String[] split = mn.split(",");         m=Integer.parseInt(split[0]);        n=Integer.parseInt(split[1]);         zuowei=new  int[m][n];         boo=new boolean[m][n];         for (int i = 0; i < m; i++) {             String nextLine = scanner.nextLine();             String[] line= nextLine.split(",");             for (int j = 0; j < line.length; j++) {                 zuowei[i][j]=Integer.parseInt(line[j]);             }                      }         for (int i = 0; i < zuowei.length; i++) {             for (int j = 0; j < zuowei[i].length; j++) {                 int findnext = findnext(i,j);                 count+=findnext;             }         }         System.out.println(count+","+max);     }     public  static int  findnext(int i,int j) {         if(zuowei[i][j]==1&&!boo[i][j]) {             boo[i][j]=true;             num++;             //上下             if(i!=m-1&&zuowei[i+1][j]==1&&!boo[i+1][j]) {                 findnext(i+1, j);             }                         if(i!=0&&zuowei[i-1][j]==1&&!boo[i-1][j]) {                 findnext(i-1, j);             }                 //左右             if(j!=n-1&&zuowei[i][j+1]==1&&!boo[i][j+1]) {                 findnext(i, j+1);             }                     if(j!=0&&zuowei[i][j-1]==1&&!boo[i][j-1]) {                 findnext(i, j-1);             }                 //斜的                        if(i!=0&&j!=0&&zuowei[i-1][j-1]==1&&!boo[i-1][j-1]) {                 findnext(i-1, j-1);             }             if(i!=0&&j!=n-1&&zuowei[i-1][j+1]==1&&!boo[i-1][j+1]) {                 findnext(i-1, j+1);             }             if(i!=m-1&&j!=n-1&&zuowei[i+1][j+1]==1&&!boo[i+1][j+1]) {                 findnext(i+1, j+1);             }             if(i!=m-1&&j!=0&&zuowei[i+1][j-1]==1&&!boo[i+1][j-1]) {                 findnext(i+1, j-1);             }         }else {             if(max<num) {                 max=num;             }             num=0;             boo[i][j]=true;             return 0;         }         return 1;     } }

#include <iostream> #include <string> using namespace std; int m,n; int dfs(int** grid, int i, int j) {   if (i < 0 || i >= m || j < 0 || j >= n) return 0;   int count=0;   if (grid[i][j]) {     count++;     grid[i][j] = 0;     count+=dfs(grid, i - 1, j);     count+=dfs(grid, i + 1, j);     count+=dfs(grid, i, j - 1);     count+=dfs(grid, i, j + 1);     count+=dfs(grid, i - 1, j-1);     count+=dfs(grid, i + 1, j - 1);     count+=dfs(grid, i - 1, j + 1);     count+=dfs(grid, i + 1, j + 1);   }   return count; } int numIslands(int** grid,int &q) {     if (m == 0) return 0;     if (n == 0) return 0;     int ans = 0;     int count=0;     q=0;     for (int i = 0; i < m; i++) {         for (int j = 0; j < n; j++) {             if (grid[i][j]==0) continue;             ans++;             count=dfs(grid, i, j);             if(count>q)               q=count;         }     }     return ans; } int main() {   string line1;   getline(cin,line1);   string tmp="";   int itmp;   for(int i=0;i<line1.length();i++)   {     if(line1[i]!=',')     {       tmp+=line1[i];     }     else     {       itmp=stoi(tmp);       m=itmp;       tmp="";     }   }   itmp=stoi(tmp);   n=itmp;   tmp="";   int **grid;   grid=new int *[m];   for(int i=0;i<m;i++)   {     grid[i]=new int[n];   }   int row,col;   row=m;   col=n;   for(int i=0;i<row;i++)   {     string rowtmp;     getline(cin,rowtmp);     int k=0;     for(int j=0;j<rowtmp.length();j++)     {       if(rowtmp[j]!=',')       {         tmp+=rowtmp[j];       }       else       {         itmp=stoi(tmp);         grid[i][k]=itmp;         tmp="";         k++;       }     }     itmp=stoi(tmp);     grid[i][k++]=itmp;     tmp="";   }   int P;   int Q;   P=numIslands(grid,Q);   cout<<P<<","<<Q<<endl; }

联通块问题，BFS就可以了 #include<iostream> #include<string> #include<vector> #include<queue> using namespace std; class point { public:     int x;     int y;     point(int i,int j)     {         x = i;         y = j;     } }; int main() {     string s;     int m=1;     int n = 1;     cin >> s;     int mark = s.find(',');     m=atoi(s.substr(0, mark).c_str());     n = atoi(s.substr(mark+1,s.size()).c_str());     bool ** a = new bool*[m];     bool ** visited = new bool*[m];     for (int i = 0; i < n; i++)     {         a[i] = new bool[n];         visited[i] = new bool[n];         for (int j = 0; j < n; j++)         {             visited[i][j] = false;         }     }     for (int i = 0; i < m; i++)     {         s = "";         cin >> s;         int k = 0;         for (int j = 0; j < s.size(); j++)         {             if (s[j] == '0')             {                 a[i][k] = false;                 k++;             }             if (s[j] == '1')             {                 a[i][k] = true;                 k++;             }         }     }     //input finished     vector<int> group;     queue<point>que;     for (int i = 0; i < m; i++)     {         for (int j = 0; j < n; j++)         {             if (a[i][j] == true&&visited[i][j]!=true)             {                 int number = 0;                 //push queue                 point p(i,j);                 que.push(p);                 while (!que.empty())                 {                     point p1 = que.front();                     que.pop();                     number++;                     //visit p1                     visited[p1.x][p1.y] = true;                                          //check                     for (int ii = p1.x - 1; ii <= p1.x + 1; ii++)                     {                         for (int jj = p1.y - 1; jj <= p1.y+1; jj++)                         {                             if (ii < 0 || ii >= m || jj < 0 || jj >= n)                             {                                 continue;                             }                             if (a[ii][jj] == true&&visited[ii][jj]!=true)                             {                             que.push(point(ii, jj));                                     visited[ii][jj] = true;                             }                         }                     }                 }                 group.push_back(number);             }         }     }     int max = 0;     for (int i = 0; i < group.size(); i++)     {         max = max > group[i] ? max : group[i];     }     cout << group.size() << "," << max << endl; }

赶时间瞎写的，凑活着看吧，反正AC了 while 1: try: m, n = list(map(int, input().split(','))) mtx = [] for i in range(m): mtx.append(list(map(int, input().split(',')))) except: break def isValid(x, y): # print(x,y) return x >= 0 and x < m and y >= 0 and y < n team_count = 0 max_count = 0 seen = set() for i in range(m): for j in range(n): if mtx[i][j] == 0 or (i, j) in seen: continue else: count = 1 q = [(i, j)] seen.add((i, j)) while q: x, y = q.pop() if isValid(x - 1, y) and mtx[x - 1][y] == 1 and (x - 1, y) not in seen: q.append((x - 1, y)) seen.add((x - 1, y)) count += 1 if isValid(x + 1, y) and mtx[x + 1][y] == 1 and (x + 1, y) not in seen: q.append((x + 1, y)) seen.add((x + 1, y)) count += 1 if isValid(x, y - 1) and mtx[x][y - 1] == 1 and (x, y - 1) not in seen: q.append((x, y - 1)) seen.add((x, y - 1)) count += 1 if isValid(x, y + 1) and mtx[x][y + 1] == 1 and (x, y + 1) not in seen: q.append((x, y + 1)) seen.add((x, y + 1)) count += 1 if isValid(x - 1, y - 1) and mtx[x - 1][y - 1] == 1 and (x - 1, y - 1) not in seen: q.append((x - 1, y - 1)) seen.add((x - 1, y - 1)) count += 1 if isValid(x - 1, y + 1) and mtx[x - 1][y + 1] == 1 and (x - 1, y + 1) not in seen: q.append((x - 1, y + 1)) seen.add((x - 1, y + 1)) count += 1 if isValid(x + 1, y - 1) and mtx[x + 1][y - 1] == 1 and (x + 1, y - 1) not in seen: q.append((x + 1, y - 1)) seen.add((x + 1, y - 1)) count += 1 if isValid(x + 1, y + 1) and mtx[x + 1][y + 1] == 1 and (x + 1, y + 1) not in seen: q.append((x + 1, y + 1)) seen.add((x + 1, y + 1)) count += 1 if count > max_count: max_count = count team_count += 1 print(str(team_count) + ',' + str(max_count))

#include <iostream> #include <stack> #include <cstring> #include <cstdio> using namespace std; const int size = 1000 + 10; int m[size][size]; typedef struct{     int x, y; }P; int pos[8][2] = {     1,0,     0,1,     -1,0,     0,-1,     1,1,     1,-1,     -1,1,     -1,-1 }; int main(){     int M, N;     while(scanf("%d,%d", &M, &N) != EOF){         memset(m, 0, sizeof(m));         for(int i=1; i<=M; i++){             for(int j=1; j<N; j++){                 scanf("%d,", &m[i][j]);             }             scanf("%d", &m[i][N]);         }                          int st = 2;//start         int now;         int maxn = 0;         for(int i=1; i<=M; i++)             for(int j=1; j<=N; j++){                 if(m[i][j] == 1){                     P p;                     p.x = i;                     p.y = j;                     stack<P> s;                     s.push(p);                     int cnt = 1;                     while(!s.empty()){                         P tp = s.top();                         s.pop();                         m[tp.x][tp.y] = st;                         for(int k=0; k<8; k++){                             P newp;                             newp.x = tp.x + pos[k][0];                             newp.y = tp.y + pos[k][1];                             if(newp.x <=M && newp.x >= 1 && newp.y <=N && newp.y >=1 && m[newp.x][newp.y] == 1){                                 s.push(newp);                                 m[newp.x][newp.y] = st;                                 cnt++;                             }                         }                     }                     st++;                     if(cnt > maxn)                         maxn = cnt;                 }             }         cout << st-2 << "," << maxn << endl;     }          return 0; }

''' 10,10 0,0,0,0,0,0,0,0,0,0 0,0,0,1,1,0,1,0,0,0 0,1,0,0,0,0,0,1,0,1 1,0,0,0,0,0,0,0,1,1 0,0,0,1,1,1,0,0,0,1 0,0,0,0,0,0,1,0,1,1 0,1,1,0,0,0,0,0,0,0 0,0,0,1,0,1,0,0,0,0 0,0,1,0,0,1,0,0,0,0 0,1,0,0,0,0,0,0,0,0 output 6,8 ''' import sys option = [(-1, -1), (-1, 0), (0, -1), (1, -1), (-1, +1), (0, +1), (+1, +1), (+1, 0)] def get_max_num(list_num, m, n): list_temp = [[0 for i in range(m)] for j in range(n)] stacks = [] P = 0 Q = 0 q = 0 for i in range(m): for j in range(n): if list_num[i][j] == 1 and list_temp[i][j] == 1: continue if list_num[i][j] == 1 and list_temp[i][j] == 0: P += 1 # print((i,j)) list_temp[i][j] = 1 q += 1 for s in option: if (i + s[0]) < m and (j + s[1]) < n \ and (i + s[0]) >= 0 and (j + s[1]) >= 0: if list_num[i + s[0]][j + s[1]] == 1 and list_temp[i + s[0]][j + s[1]] != 1: stacks.append((i + s[0], j + s[1])) q += 1 # print(stacks) while(stacks): list_n = [] for stack_index in range(len(stacks)): st = stacks[stack_index] list_temp[st[0]][st[1]] = 1 for s in option: if (st[0] + s[0]) < m and (st[1] + s[1]) < n \ and (st[0] + s[0]) >= 0 and (st[1] + s[1]) >= 0: if list_num[st[0] + s[0]][st[1] + s[1]] == 1 \ and list_temp[st[0] + s[0]][st[1] + s[1]] == 0: if(st[0] + s[0], st[1] + s[1]) not in stacks: stacks.append((st[0] + s[0], st[1] + s[1])) q += 1 list_n.append(stack_index) # print(stacks, list_n) list_n.sort(reverse = True) for ls in list_n: stacks.pop(ls) Q = max(Q, q) q = 0 return P, Q if __name__ == "__main__": m, n = sys.stdin.readline().strip().split(',') list_num = [] for i in range(int(m)): # 读取每一行 line = sys.stdin.readline().strip() # 把每一行的数字分隔后转化成int列表 values = list(map(int, line.split(','))) list_num.append(values) if m == 0 and n == 0: print('0,0') else: a, b = get_max_num(list_num, int(m), int(n)) print(str(a)+','+str(b)) 80...就是过不去

import java.util.Scanner; public class worldCup {     static int nums=0;     public static void main(String[] args){         Scanner sc=new Scanner(System.in);         String[] str=sc.next().split(",");         int m=Integer.valueOf(str[0]);         int n=Integer.valueOf(str[1]);         int[][] a=new int[m][n];         for (int i=0;i<m;i++){           String[] str1=sc.next().split(",");           for (int j=0;j<n;j++){               a[i][j]=Integer.valueOf(str1[j]);           }         }         int[][] vis=new int[m][n];         int max_nums=0;int P=0;         for (int i=0;i<m;i++){             for (int j=0;j<n;j++){                 if (a[i][j]==1 && vis[i][j]==0){                     P+=1;nums=1;                     dfs(a,vis,i,j);                     if (nums>max_nums)                         max_nums=nums;                 }             }         }         //max_nums=max_nums==0?0:max_nums-1;         System.out.println(P+","+max_nums);     }     private static void dfs(int[][] a,int[][] vis,int curr_i,int curr_j){         System.out.println(nums);         vis[curr_i][curr_j]=1;         if (a[curr_i][curr_j]==0){             return;         }         int[][] dir={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};         for (int i=0;i<dir.length;i++){             int x=curr_i+dir[i][0];             int y=curr_j+dir[i][1];             if (x>=a.length || x<0 || y<0 ||y>=a[0].length)                 continue;             if (a[x][y]==1 && vis[x][y]==0){                 nums+=1;                 vis[x][y]=1;                 dfs(a,vis,x,y);             }         }     } }

往8个方向访问就行了多说一句，我没看到输入是 m,n 这样的，所以最开始我是scanf("%d %d", &m, &n);后来发现牛客的case是可以复制的。。才debug出来这个问题，浪费了10min+。以下是代码 #include using namespace std; int visit(vector>& matrix, int i, int j) { int ret=0; if(i=matrix.size() || j>=matrix[0].size()) return ret; if(matrix[i][j]==1) { ++ ret; matrix[i][j] = -1; } else return ret; for(int x=-1; x<=1; ++x) { for(int y=-1; y<=1; ++y) { if(x!=0 || y!=0) ret += visit(matrix, i+x, j+y); return ret; } int main() { int m, n; int p,q; p=0, q=0; scanf("%d,%d", &m, &n); { vector > matrix(m, vector(n, 0)); for(int i=0; i<m; ++i) { scanf("%d", &matrix[i][0]); for(int j=1; j<n; ++j) { scanf(",%d", &matrix[i][j]); } } for(int i=0; i<m; ++i) { for(int j=0; j<n; ++j) { if(matrix[i][j]==1) { q = max(q, visit(matrix, i, j)); ++p; } } } printf("%d,%d", p, q); } return 0; }

第一题是：联通块问题，bfs，dfs都行。。

递归搞的，死活都是80%，也没说超时。。。。哎。被虐的感觉还是真的爽，都快麻木了。。。。。

dfs裸题啊。。。

public class Main {     private static int pNums = 0;     private static int qNums = 0;     private static int qTmpSum = 0;     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         String[] line1 = scanner.nextLine().split(",");         int m = Integer.parseInt(line1[0]);         int n = Integer.parseInt(line1[1]);         int[][] grids = new int[m][n];         for (int i = 0; i < m; i++) {             String[] line2 = scanner.nextLine().split(",");             for (int j = 0; j < n; j++) {                 grids[i][j] = Integer.parseInt(line2[j]);             }         }         pNums = numIslands(grids);         System.out.println(pNums + "," + qNums);     }     public static int numIslands(int[][] grid) {         int m = grid.length;         int n = grid[0].length;         boolean[][] visited = new boolean[m][n];         int result = 0;         for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 if (grid[i][j] == 1 && !visited[i][j]) {                     qTmpSum = 0;                     numIslandsDFS(grid, visited, i, j);                     result++;                 }             }         }         return result;     }     private static void numIslandsDFS(int[][] grid, boolean[][] visited, int x, int y) {         if (x < 0 || x >= grid.length)             return;         if (y < 0 || y >= grid[x].length)             return;         if (grid[x][y] != 1 || visited[x][y])             return;         visited[x][y] = true;         qTmpSum++;         if (qNums < qTmpSum)             qNums = qTmpSum;         numIslandsDFS(grid, visited, x - 1, y);         numIslandsDFS(grid, visited, x - 1, y + 1);         numIslandsDFS(grid, visited, x, y + 1);         numIslandsDFS(grid, visited, x + 1, y + 1);         numIslandsDFS(grid, visited, x + 1, y);         numIslandsDFS(grid, visited, x + 1, y - 1);         numIslandsDFS(grid, visited, x, y - 1);         numIslandsDFS(grid, visited, x - 1, y - 1);     } }

iOS Swift import Foundation /** m行, n列 10,10 0,0,0,0,0,0,0,0,0,0 0,0,0,1,1,0,1,0,0,0 0,1,0,0,0,0,0,1,0,1 1,0,0,0,0,0,0,0,1,1 0,0,0,1,1,1,0,0,0,1 0,0,0,0,0,0,1,0,1,1 0,1,1,0,0,0,0,0,0,0 0,0,0,1,0,1,0,0,0,0 0,0,1,0,0,1,0,0,0,0 0,1,0,0,0,0,0,0,0,0 6,8 */ class Node { let value: Int var check: Bool = false init(_ value: Int) { self.value = value } } let first = readLine()!.split(separator: ",") let (m, n) = (Int(first[0])!, Int(first[1])!) var teamCount = 0 var count = 0 var maxCount = 0 var dict: [String: Node] = [:]; for row in 0..<m { let line = readLine()!.split(separator: ",").map{ Int($0) }.compactMap { $0 } for column in 0..<n { let location = "\(row)\(column)" dict[location] = Node(line[column]) } } func traverse(node: Node, row: Int, column: Int) { count += 1 node.check = true if column != 0, row != 0, let topleft = dict["\(row - 1)\(column - 1)"], topleft.value == 1, !topleft.check { traverse(node: topleft, row: row - 1, column: column - 1) } if row != 0, let top = dict["\(row - 1)\(column)"], top.value == 1, !top.check { traverse(node: top, row: row - 1, column: column) } if row != 0, column != n - 1, let topright = dict["\(row - 1)\(column + 1)"], topright.value == 1, !topright.check { traverse(node: topright, row: row - 1, column: column + 1) } if column != 0, let left = dict["\(row)\(column - 1)"], left.value == 1, !left.check { traverse(node: left, row: row, column: column - 1) } if column != n - 1, let right = dict["\(row)\(column + 1)"], right.value == 1, !right.check { traverse(node: right, row: row, column: column + 1) } if row != m - 1, column != 0, let buttomleft = dict["\(row + 1)\(column - 1)"], buttomleft.value == 1, !buttomleft.check { traverse(node: buttomleft, row: row + 1, column: column - 1) } if row != m - 1, let buttom = dict["\(row + 1)\(column)"], buttom.value == 1, !buttom.check { traverse(node: buttom, row: row + 1, column: column) } if row != m - 1, column != 0, let buttomright = dict["\(row + 1)\(column + 1)"], buttomright.value == 1, !buttomright.check { traverse(node: buttomright, row: row + 1, column: column + 1) } } for row in 0..<m { for column in 0..<n { let location = "\(row)\(column)" guard let node = dict[location], node.value == 1, !node.check else { continue } teamCount += 1 maxCount = count > maxCount ? count : maxCount count = 0 traverse(node: node, row: row, column: column) } } maxCount = count > maxCount ? count : maxCount print(teamCount, maxCount)

#include <bits/stdc++.h> using namespace std; int visit(vector<vector<int>>& matrix, int i, int j) { int ret=0; if(i<0 || j<0 || i>=matrix.size() || j>=matrix[0].size()) return ret; if(matrix[i][j]) { ++ ret; matrix[i][j] = 0; } else return ret; for(int x=-1; x<=1; ++x) for(int y=-1; y<=1; ++y) if(x!=0 || y!=0) ret += visit(matrix, i+x, j+y); return ret; } int main() { int m, n; int p,q; p=0, q=0; scanf("%d,%d", &m, &n); { vector<vector<int> > matrix(m, vector<int>(n, 0)); for(int i=0; i<m; ++i) { scanf("%d", &matrix[i][0]); for(int j=1; j<n; ++j) { scanf(",%d", &matrix[i][j]); } } for(int i=0; i<m; ++i) { for(int j=0; j<n; ++j) { if(matrix[i][j]==1) { q = max(q, visit(matrix, i, j)); ++p; } } } printf("%d,%d", p, q); } return 0; }