字节跳动2019校园招聘研发岗位第一次在线笔试-2018.08.12

思路：
参照LeetCode 695. 岛屿的最大面积思路，采用DFS方法，对看台观众进行遍历，求最大的球迷群体的人的个数时，顺便求球迷群体的群体个数

AC代码 C++

#include <iostream>
#include <vector>
using namespace std;
int dfs(vector<vector<int>>& grid, int x, int y,vector<vector<bool>>& mark){if(x >=  grid.size() || y >= grid[0].size() || x < 0 || y < 0)return 0;if(mark[x][y] == true)return 0;if(grid[x][y] == 0)return 0;// 对于点[x,y]搜索上下左右4个点是否是岛屿// 即[x-1,y],[x+1,y],[x,y-1],[x,y+1]// 对于已经搜索过的点要进行标记mark[x][y] = true;// 遍历周围8个点return 1 + dfs(grid, x+1, y, mark) + dfs(grid, x-1, y, mark) + dfs(grid, x, y+1, mark) + dfs(grid, x, y-1, mark)+ dfs(grid, x+1, y+1, mark) + dfs(grid, x-1, y-1, mark) + dfs(grid, x+1, y-1, mark) + dfs(grid, x-1, y+1, mark);
}
void maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.empty())return;int num = 0;int res = 0;vector<vector<bool>> vecMark(grid.size(),vector<bool>(grid[0].size(),false));// 定义标记数组// 定义搜索边界int mostDeep = grid.size();int mostRight = grid[0].size();//开始搜索for(int i = 0;i < mostDeep;i++){for(int j = 0;j < mostRight;j++){if(vecMark[i][j] == true)continue;if(grid[i][j] == 0){vecMark[i][j] = true;continue;}int temp = dfs(grid, i, j, vecMark);++num;//grid[i][j] = 8;res = res>temp ? res : temp;}}cout << num << ',' << res << endl;
}int main()
{int x,y;char c;cin >> x >> c >> y;vector<vector<int>> grid(x, vector<int>(y,0));int temp;for(int i=0; i<x; i++){for(int j=0; j<y-1; j++){cin >> grid[i][j];cin >> c;}cin >> grid[i][y-1];}maxAreaOfIsland(grid);return 0;
}

注意
主要是字符串的处理相对麻烦，知识点如下：

size_t find (char c, size_t pos = 0) const;
查找对象字符 找到就返回第一个字符的索引
没找到就返回string::npos(代表 -1 表示不存在)

http://www.cplusplus.com/reference/string/string/substr/
s.substr(pos, n)
返回一个string，包含s中从pos开始的n个字符的拷贝
（pos的默认值是0，n的默认值是s.size() - pos，即不加参数会默认拷贝整个s）
如果n == -1 拷贝到字符串结尾

const char *c_str();
c_str()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同.
这是为了与c语言兼容，在c语言中没有string类型，故必须通过string类对象的成员函数c_str()把string 对象转换成c中的字符串样式

ctoi()函数
int atoi(const char *str );
功能：把字符串转换成整型数。
str：要进行转换的字符串
返回值：每个函数返回 int 值，此值由将输入字符作为数字解析而生成。 如果该输入无法转换为该类型的值，则atoi的返回值为 0。
说明：当第一个字符不能识别为数字时，函数将停止读入输入字符串。
string 是C++ STL定义的类型，atoi是 C 语言的库函数，所以要先转换成 char* 类型才可以用 atoi

AC代码 C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>using namespace std;struct node{int start;int end;node() : start(0), end(0) {}node(int s, int e) : start(s), end(e) {}
};vector<node> merge(vector<node> &arr){int n = arr.size();vector<node> res;vector<int> starts, ends;for (int i = 0; i < n; ++i){starts.push_back(arr[i].start);ends.push_back(arr[i].end);}//开始下标和结尾下标数组排序sort(starts.begin(), starts.end());sort(ends.begin(), ends.end());for (int i = 0, j = 0; i < n; ++i){//当starts[i+1] <= ends[i]的时候 证明有交集需要合并//当starts[i+1] > ends[i]的时候 前面的组成新病句段  加入到返回序列res中//当i == n-1 时，证明是最后一段  加入到返回序列res中if (i == n - 1 || starts[i + 1] > ends[i]){res.push_back(node(starts[j], ends[i]));j = i + 1;}}return res;
}int main()
{int n;cin >> n;vector<node> arr;//输入 拆分for (int i = 0; i < n; ++i){string line;cin >> line;int x1 = 0;int x2 = 0;while (x2 != -1){//分割出一个病句下标的集合x2 = line.find(';', x1);//返回首次匹配的;下标string temp;temp = line.substr(x1, x2 - x1);//从字符串line中第x1位开始的长度为(x2-x1)的字符串/*cout << "x2= " << x2 << endl;cout << "temp= " << temp << endl;*///从集合中分出病句的前后下标int y1=0;int y2;y2 = temp.find(',',y1);string tt,yy;tt = temp.substr(y1, y2-y1);yy = temp.substr(y2+1);node tmp_i(atoi(tt.c_str()), atoi(yy.c_str()));arr.push_back(tmp_i);x1 = x2 + 1;//更改下次查询起始位置}}//合并vector<node> res = merge(arr);//输出for(int i=0;i<res.size();++i){if(i != res.size()-1)cout << res[i].start << "," << res[i].end << ";";elsecout << res[i].start << "," << res[i].end << endl;}return 0;
}

AC代码 C++
别人的代码，暂时没搞懂

还有一个牛客网上的题解，点击跳转

#include <bits/stdc++.h>
#define M 110
#define MV 100100
#define INF 0x3f3f3f3f
using namespace std;
int n;
int x[M];
int y[M];
int dp[2][2][MV];
void Update(int value, int now, int score){int i = 0;int j = value;if(value < 0){i = 1;j = -j;}dp[now][i][j] = max(dp[now][i][j], score);
}
int Solve(){int now = 0, pre = 1;for (int i = 0; i < 2; i++){for (int j = 0; j < MV; j++) {dp[now][i][j] = -INF;}}dp[now][0][0] = 0;for (int i = 0; i < n; i++){swap(now, pre);for (int j = 0; j < 2; j++){for (int k = 0; k < MV; k++){dp[now][j][k] = -INF;}}for (int j = 0; j < 2; j++){for (int k = 0; k < MV; k++){if (dp[pre][j][k] == -INF){continue;}dp[now][j][k] = max(dp[now][j][k], dp[pre][j][k]);int value = k;if(j){value = -value;}Update(value + x[i], now, dp[pre][j][k] + y[i]);Update(value - x[i], now, dp[pre][j][k] + y[i]);            }}}return dp[now][0][0];
}
int main(){scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d%d", &x[i], &y[i]);}printf("%d\n", Solve());
/*
4
3 1
2 2
1 4
1 4
*/return 0;
}

1e5 表示1*10^5
1e9 表示1*10^9
e表示阶码

别人的代码，没有测试，不知道是否AC
回头找到AC代码再更新

#include <iostream>
#include <vector>
#include <string.h>using namespace std;int main() {// input dataint n; cin >> n;vector<int> a, b;for (int i=0;i<n;++i) {int t; cin >> t;a.push_back(t);}for (int i=0;i<n;++i) {int t; cin >> t;b.push_back(t);}// dpint dp_max[n][n], dp_min[n][n]; for (int i=0;i<n;++i) {dp_max[i][i] = a[i];dp_min[i][i] = b[i];for (int j=i+1;j<n;++j) {dp_max[i][j] = max(dp_max[i][j-1], a[j]);dp_min[i][j] = min(dp_min[i][j-1], b[j]);}}// countint count = 0;for (int i=0;i<n;++i)for (int j=i;j<n;++j)if (dp_max[i][j] < dp_min[i][j])count++;cout << count;return 0;
}

AC代码 C++

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{int l, r;
};
node Time[1000005];
bool cmp(node a, node b){return a.r<b.r;
}
int tt[100005];
int main()
{int m, n;cin >> n;cin >> m;for (int i = 1; i <= 2 * n; i++)scanf("%d", &tt[i]);for (int i = 1; i <= n; i++){int x = tt[i * 2 - 1], y = tt[i * 2];if (x>y) y = y + m;//标记跨天直播Time[i].l = x;Time[i].r = y;}sort(Time + 1, Time + 1 + n, cmp);//按照直播结束时间的从早到晚排序int ans = 0;int overTime = 0;//上一场结束时间for (int i = 1; i <= n; i++){if (Time[i].l>m || Time[i].r>m) //题目求一天内看的最多完整直播场数 排除跨天的直播continue;//题目要求尽可能多看直播，每次选择离上一场结束时间最近的直播//由于已经按结束时间排序，每次选中的都是既不和上场冲突，结束又最早的直播if (Time[i].l >= overTime){ans++;overTime = Time[i].r;}if(overTime == m)break;}cout << ans << endl;return 0;
}