8月12日头条笔试第一、二题

没参加笔试，帮实验室的人看看题

第一题：leetcode岛屿的个数改一下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>
#include<string>
using namespace std;

void numIslandsDFS(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int& max_num)
{
if (x < 0 || x >= grid.size())
return;
if (y < 0 || y >= grid[0].size())
return;
if (grid[x][y] != 1 || visited[x][y])
return;
visited[x][y] = true;
max_num++;
numIslandsDFS(grid, visited, x - 1, y, max_num);
numIslandsDFS(grid, visited, x + 1, y, max_num);
numIslandsDFS(grid, visited, x, y - 1, max_num);
numIslandsDFS(grid, visited, x, y + 1, max_num);
numIslandsDFS(grid, visited, x - 1, y-1, max_num);
numIslandsDFS(grid, visited, x + 1, y+1, max_num);
numIslandsDFS(grid, visited, x+1, y - 1, max_num);
numIslandsDFS(grid, visited, x-1, y + 1, max_num);
}

int numIslands(vector<vector<int>>& grid, int& max_num) {
if (grid.empty() || grid[0].empty())
return 0;
int m = grid.size(), n = grid[0].size(), res = 0, tmp_max = 0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1 && !visited[i][j])
{
tmp_max = 0;
numIslandsDFS(grid, visited, i, j, tmp_max);
if (tmp_max > max_num)
max_num = tmp_max;
++res;
}
}
}
return res;
}

int main()
{
string m_n;
int m, n;
cin >> m;
if (cin.get() == ',')
cin >> n;
vector<vector<int> > data(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
{
cin >> data[i][0];
for (int j = 1; j < n; j++)
{
if (cin.get() == ',')
cin >> data[i][j];
}
}
int max_people = 0, max_num = 0;
max_num = numIslands(data, max_people);
cout << max_num << ',' << max_people << 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
*/

第二题后来改的，感谢XDHZR同学给的输入输出，也是leetcode原题：合并区间：

#include<iostream>
#include<vector>
#include<algorithm>
#include <sstream>
#include<string>

using namespace std;

struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};

vector<Interval> merge(vector<Interval>& intervals) {
if (intervals.empty())
return{};
sort(intervals.begin(), intervals.end(), [](Interval &a, Interval &b) {return a.start < b.start; });
vector<Interval> res{ intervals[0] };
for (int i = 0; i < intervals.size(); i++)
{
if (res.back().end < intervals[i].start)
res.push_back(intervals[i]);
else
res.back().end = max(res.back().end, intervals[i].end);
}
return res;
}

int main()
{
int m;
cin >> m;
cin.ignore();
vector<Interval> data;
string raw_input, temp1, temp2;
for (int i = 0; i < m; i++)
{
cin >> raw_input;
stringstream inputa(raw_input);
while (getline(inputa, temp1, ';'))
{
vector<int> tmp;
stringstream inputb(temp1);
while (getline(inputb, temp2, ','))
{
tmp.push_back(stoi(temp2));
}
Interval tmp_Interval(tmp[0], tmp[1]);
data.push_back(tmp_Interval);
}
}
vector<Interval> res_Interval = merge(data);
for (int i = 0; i < res_Interval.size()-1; i++)
{
int b = res_Interval[i].start;
int e = res_Interval[i].end;
cout << b << ',' << e << ';';
}
cout << res_Interval[res_Interval.size()-1].start << ',' << res_Interval[res_Interval.size() - 1].end << endl;
return 0;
}