字節(jié)跳動2019屆校招筆試題(小結(jié))
我要評論1.世界杯開幕式會在球場C舉行，球場C的球迷看臺可以容納M*N個球迷。在球場售票完成后，現(xiàn)官方想統(tǒng)計(jì)此次開幕式一共有多少個球隊(duì)球迷群體，最大的球隊(duì)球迷群體有多少人。
經(jīng)調(diào)研發(fā)現(xiàn)，球迷群體在選座時有以下特性：
同球隊(duì)的球迷群體會選擇相鄰座位，不同球隊(duì)的球迷群體會選擇不相鄰的座位（注解：相鄰包括前后相鄰，左右相鄰，斜對角相鄰）
給定一個M*N的二維球場，0代表該位置沒有坐人，1代表該位置已有選擇，希望輸出球隊(duì)群體個數(shù)P，最大的球隊(duì)群體人數(shù)Q
輸入描述：
第一行，2個數(shù)字，M及N，使用英文逗號分隔
接下來M行，每行N的數(shù)字，使用英文逗號分隔
輸出描述：
一行，2個數(shù)字，P及Q，使用英文逗號分隔
其中P表示球隊(duì)群體個數(shù)，Q表示最大的球隊(duì)群體人數(shù)
例：輸入
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
代碼如下：
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int getNum(vector<vector<int>>& people,int i,int j,vector<vector<int>>& reach)
{
int m=people.size(),n=people[0].size();
if(i>=m||j>=n||i<0||j<0){
return 0;
}
else if(people[i][j]==1&&reach[i][j]==0){
reach[i][j]=1;
int n1=getNum(people,i-1,j,reach)+getNum(people,i+1,j,reach);
int n2=getNum(people,i,j-1,reach)+getNum(people,i,j+1,reach);
int n3=getNum(people,i-1,j-1,reach)+getNum(people,i-1,j+1,reach);
int n4=getNum(people,i+1,j-1,reach)+getNum(people,i+1,j+1,reach);
return n1+n2+n3+n4+1;
}else {
return 0;}
}
void getdata(vector<vector<int>>& people,vector<int>& num,vector<vector<int>>& reach)
{
int m=people.size(),n=people[0].size();
for(int i=0;i<m;i++)
for(int j=0;j<n;j++) {
if(people[i][j]==1&&reach[i][j]==0){
int n=getNum(people,i,j,reach);
num.push_back(n);
}
}
}
int main()
{
int m;
int n;
char c;
cin>>m>>c>>n;
vector<vector<int> > people;
vector<int> vtemp(n,0);
vector<vector<int>> reach(m,vtemp);
for(int i=0;i<m;i++){
vector<int> ptemp;
int temp;
char cc;
for(int j=0;j<n-1;j++){
cin>>temp;
cin>>cc;
ptemp.push_back(temp);
}
cin>>temp;
ptemp.push_back(temp);
people.push_back(ptemp);
}
vector<int>num;
if(people.empty()){
cout<<0<<','<<0<<endl;
return 0;
}
getdata(people,num,reach);
vector<int>::iterator max=max_element(nums.begin(),nums.end());
cout<<num.size()<<","<<*max<<endl;
return 0;
}
2.為了提高文章質(zhì)量，每一篇文章（假設(shè)全部都是英文）都會有m民編輯進(jìn)行審核，每個編輯獨(dú)立工作，會把覺得有問題的句子通過下表記錄下來，比如[1,10]，1表示病句的第一個字符，10表示病句的最后一個字符。也就是從1到10著10個字符組成的句子，是有問題的。
現(xiàn)在需要把多名編輯有問題的句子合并起來，送個總編輯進(jìn)行最終的審核。比如編輯A指出的病句是[1,10]，[32,45];編輯B指出的病句是[5,16]，[78,94]那么[1,10]和[5,16]是有交叉的，可以合并成[1,16][32,45][78,94]
輸入描述：
編輯數(shù)量m，之后每行是每個編輯的標(biāo)記的下表組合，第一個和最后一個下標(biāo)用英文逗號分隔，每組下標(biāo)之間用分號分隔
輸出描述：
合并后的下標(biāo)集合，第一個和最后一個下標(biāo)用英文逗號分隔，每組下標(biāo)之間用分號分隔。返回結(jié)果是從小到大遞增排列
例：輸入
3
1,10;32,45
78,94;5,16
80,100;200,220;16,32
輸出： 1,45;78,100;200,220
代碼如下：
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
void mergeIndex(vector<pair<int,int>>& vp)
{
sort(vp.begin(),vp.end(),[](pair<int,int>& temp1,pair<int,int>& temp2){return temp1.first<temp2.first;});
int n=vp.size();
for(auto it=vp.begin();it<vp.end()-1;)
{
if(it->second>=(it+1)->first-1)
{
if((it+1)->second>it->second){
it->second=(it+1)->second;
}
it=vp.erase(it+1);
--it;
}else{
++it;
}
}
}
int main()
{
vector<pair<int,int>> vp;
int m;
cin>>m;
int first,last;
char c1,c2;
for(int i=0;i<m;i++)
{
do
{
cin>>first;
if(cin.get()==',')
{
cin>>last;
vp.push_back(make_pair(first,last));
}
}while(cin.get()==';');
}
mergeIndex(vp);
int i=0;
for(;i<vp.size()-1;i++)
{
cout<<vp[i].first<<","<<vp[i].second<<";";
}
cout<<vp[i].first<<","<<vp[i].second<<endl;
cout<<endl;
return 0;
}
3. 小a和小b玩一個游戲，有n張卡牌，每張上面有兩個正整數(shù)x，y。取一張牌時，個人積分增加x，團(tuán)隊(duì)積分增加y。求小a，小b各取若干張牌，使得他們的個人積分相等，且團(tuán)隊(duì)積分最大。
輸入描述：
第一行n
接下來n行，每行兩個正整數(shù)x，y
輸出描述：
一行一個整數(shù)
表示小a的積分和小b的積分相等時，團(tuán)隊(duì)積分的最大值
例：輸入
4
3 1
2 2
1 4
1 4
輸出：10
說明：當(dāng)a抽?。?,2），b抽?。?,4），（1,4）時，兩人個人積分都是2，團(tuán)隊(duì)積分最大，為10分
代碼如下：
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int, int>> vp;
int a, b,cap=0;
for(int i=0;i<n;i++){
cin >> a >> b;
vp.push_back(make_pair(a, b));
cap = cap < a ? a : cap;
}
sort(vp.begin(), vp.end(), [](pair<int, int>& p1, pair<int, int>& p2) {return p1.second > p2.second; });
int** dp = new int* [n];
for (int i = 0; i<n; i++){
dp[i] = new int[cap+1];
}
for (int j = 0; j <=cap; j++) {
dp[n-1][j] = 0;
}
for (int i = n-2; i>=0; i--){
for (int j = 0; j <= cap; j++){
int point1 = (j >=vp[i].first) ? dp[i + 1][j- vp[i].first] + vp[i].second : 0; //x[i]和cap-x[i]不能確定誰大
int point2 = (j<=cap- vp[i].first) ? dp[i + 1][j+ vp[i].first] + vp[i].second : 0;//這樣省去了劃分區(qū)間的麻煩
dp[i][j] = max({ dp[i + 1][j], point1, point2 });
}
}
cout << dp[0][0] << endl;
for (int i = 0; i < n; i++) {
delete [] dp[i];
}
delete [] dp;
return 0;
}
4. 兩個長度為n的序列a，b。問有多少個區(qū)間[l，r]滿足max(a[l,r])<min(b[l,r])即a區(qū)間的最大值小于b區(qū)間的最小值數(shù)據(jù)范圍：n<1e5，a(i),b(i)<1e9
輸入描述：
第一行一個整數(shù)n
第二行n個數(shù)，第i個為a(i)
第三行n個數(shù)，第i個為b(i)
0<1<=r<n
輸出描述：
一行一個整數(shù)，表示答案
例1：輸入
3
3 2 1
3 3 3
輸出： 3
5. 小明在抖音里關(guān)注了N個主播，每個主播每天的開播時間是固定的，分別在S時刻開始開播，t時間結(jié)束。小明無法同時觀看兩個主播的直播。一天被分成了M個時間單位。請問小明每天最多能完整觀看多少場直播？
輸入描述：
第一行一個整數(shù)，代表N
第二行一個整數(shù)，代表M
第三行空格間隔的N*2個整數(shù)，代表s，t
輸出描述：
一行一個整數(shù)，表示答案
例1：輸入
3
10
0 3 3 7 7 0
輸出：3
例2： 輸入
3
10
0 5 2 7 6 9
輸出：2
備注：數(shù)據(jù)范圍1<=N<=10^5
2<=M<=10^6
0<=s(i),t(i)<M (s(i)!=t(i))
s(i)>t(i)代表時間跨天，但直播時長不會超過一天
6
.
7
本題和尋找圖中路徑的思想一致。代碼如下：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool rfind(int s, int des, int n, int& length, int* reach, int* path, vector<vector<int>>& red)
{
reach[s] = 1;
for (int u = 1; u <= n; u++){
if (red[s][u] != 0 && reach[u] == 0) {
path[++length] = u;
if (u == des || rfind(u, des, n, length, reach, path, red)) {
return true;
}
length--;
}
}
return false;
}
int* findPath(int begin, int end, int n, vector<vector<int>>& red)
{
int* path = new int[n + 1];
path[1] = begin;
int length = 1;
int des = end;
int* reach = new int[n + 1];
for (int i = 1; i <= n; i++) {
reach[i] = 0;
}
if (begin == end || rfind(begin, des, n, length, reach, path, red)) {
path[0] = length - 1;
}
else {
delete[] path;
path = NULL;
}
delete[] reach;
return path;
}
int main()
{
int n, m;
cin >> n;
cin >> m;
vector<int> vtemp(n + 1, 0);
vector<vector<int>> red(n + 1, vtemp);
int row, col;
for (int i = 0; i<m; i++){
cin >> row >> col;
red[row][col] = 1;
}
bool isred = true;
int t = 0;
for (int i = 1; i <= n; i++){
isred = true;
for (int j = 1; j <= n; j++){
int* path = findPath(j, i, n, red);
if (path == NULL){
isred = false;
break;
}
else {
delete[] path;
}
}
if (isred) {
++t;
}
}
cout << t << endl;
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
字節(jié)跳動的三道編碼面試題的實(shí)現(xiàn)
這篇文章主要介紹了字節(jié)跳動的三道編碼面試題的實(shí)現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-04-08字節(jié)跳動抖音C++開發(fā)實(shí)習(xí)一二面涼經(jīng)
這篇文章主要介紹了字節(jié)跳動抖音C++開發(fā)實(shí)習(xí)一二面涼經(jīng)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-03-31
字節(jié)跳動后端開發(fā)視頻架構(gòu)面經(jīng)總結(jié)
這篇文章主要介紹了字節(jié)跳動后端開發(fā)視頻架構(gòu)面經(jīng)總結(jié)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-02-25字節(jié)跳動一面、二面涼經(jīng)(面試小結(jié))
這篇文章主要介紹了字節(jié)跳動一面、二面涼經(jīng)(面試小結(jié))，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-02-03字節(jié)跳動飛書音視頻服務(wù)器開發(fā)面經(jīng) (小結(jié))
這篇文章主要介紹了字節(jié)跳動飛書音視頻服務(wù)器開發(fā)面經(jīng)(小結(jié))，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-01-13
字節(jié)跳動2019春招研發(fā)部分python編程題匯總
這篇文章主要介紹了字節(jié)跳動2019春招研發(fā)部分python編程題匯總,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-04-26
