字節跳動2019春招第二次筆試編程題

• • 1.變身程序員
  • • 題目描述
    • 輸入描述
    • 輸出描述
    • 示例
    • • 示例1
      • 示例2
      • 示例3
    • 分析
    • 參考代碼
  • 2.特征提取
  • • 題目描述
    • 輸入描述
    • 輸出描述
    • 示例
    • • 示例1
    • 備注
    • 分析
    • 參考代碼
  • 3.機器人跳躍問題
  • • 題目描述
    • 輸入描述
    • 輸出描述
    • 示例
    • • 示例1
      • 示例2
      • 示例3
    • 備注
    • 分析
    • 參考代碼
  • 4.畢業旅行問題
  • • 題目描述
    • 輸入描述
    • 輸出描述
    • 示例
    • • 示例1
    • 分析
    • 參考代碼
  • 4.過河問題
  • • 題目描述
    • 輸入描述
    • 輸出描述
    • 示例
    • • 示例1
    • 分析
    • 參考代碼

個人主頁：http://redtongue.cn or https://redtongue.github.io/

1.變身程序員

題目描述

公司的程序員不夠用了，決定把產品經理都轉變為程序員以解決開發時間長的問題。

在給定的矩形網格中，每個單元格都可以用以下三個值之一：

• 值0代表空單元格

• 值1代表產品經理

• 值2代表程序員

每分鐘，任何與程序員（在四個正方向上）相鄰的產品經理都會變成程序員。
返回知道單元格中沒有產品經理為止所必須經過的最小分鐘數。
如果沒有可能，返回-1.

輸入描述

不固定多行（行數<=10），每行是按照空格分割的數字（不固定，每行數字個數<=10） 其中每個數組項的取值僅為0,1,2三種 （讀取時可以按行讀取，知道讀取到空行為止，再對讀取的所有行做轉換處理）

輸出描述

如果能夠將所有的產品經理變為程序員，則輸出最小的分鐘數 如果不能夠將所有的產品經理變為程序員，則返回-1

示例

示例1

輸入： 0 2 1 0 輸出： -1

示例2

輸入： 1 2 1 1 1 0 0 1 1 輸出： 3

示例3

輸入： 1 2 2 1 1 2 0 1 0 1 1 1 輸出： 4

分析

• 深度優先搜索，區別在每一次（每分鐘）只會將程序員周圍的產品經理變為程序員，不會迭代下去
• manage記錄產品經理的個數，若每一個傳播之后，manage不再變化，停止；
• 若manage=0返回傳播時間，反之返回-1。

參考代碼

import sys if __name__ == "__main__":def get(A):s=0for a in A:for x in a:if(x==1):s+=1return slines = sys.stdin.readlines()a=[]for line in lines:a.append(list(map(int,line.split())))s=0print("a",a)manage=get(a)row=len(a)col=len(a[0])def dfs(x,y):if(x-1>=0 and a[x-1][y]==1):a[x-1][y]=2if(x+1<row and a[x+1][y]==1):a[x+1][y]=2if(y-1>=0 and a[x][y-1]==1):a[x][y-1]=2if(y+1<col and a[x][y+1]==1):a[x][y+1]=2returnwhile(manage>0):li=[]for i in range(row):for j in range(col):if(a[i][j]==2):li.append((i,j))for l in li:dfs(l[0],l[1])nmanage=get(a)print(a)s+=1if(manage==nmanage):breakmanage=nmanageif(manage==0):print(s)else:print('-1')

2.特征提取

題目描述

小明是一個算法工程師，同時也是一名鏟屎官。某天，他突發奇想，想從貓咪的視頻里挖掘一些貓咪的運動信息。為了提取運動信息，他需要從視頻的每一幀提取“貓咪特征”。一個貓咪特征是一個兩維的vector<x,y>。如果x_1=x_2 and y_1=y_2，那么這倆是同一個特征。

因此，如果貓咪特征連續一致，可以認為貓咪在運動。也就是說，如果特征<a,b>在持續幀里出現，那么它將構成特征運動。比如，特征<a,b>在第2/3/4/7/8幀出現，那么該特征形成兩個特征運動2-3-4和7-8.

輸入描述

第一行包含一個正整數N，代表測試用例的個數 每個測試用例的第一行包含一個正整數M，代表視頻的幀數 接下來M行，每一行代表一幀，其中，第一個數字是該幀的特征個數，接下來的數字是在特征的取值：比如樣例輸入第三行里，2表示該幀有兩個貓咪特征，<1,1>和<2,2>。所有用例的輸入特征總數和<=100000 N滿足1<=N<=100000，M滿足1<=M<=100000，一幀的特征個數滿足<=100000.特征取值均為非負整數

輸出描述

對于每一個測試用例，輸出特征運動的長度作為一行

示例

示例1

輸入： 1 8 2 1 1 2 2 2 1 1 1 4 2 1 1 2 2 2 2 2 1 4 0 0 1 1 1 1 1 1 輸出： 3

備注

如果沒有長度大于2的特征運動，返回1

分析

• 用字典存儲每個特征出現的次數，ans記錄特征出現的最大次數，初始為0
• 遍歷每一幀的特征，若字典中存在該特征，則次數加一，反正說明該特征斷了，次數置為1，更新ans
• 返回ans

參考代碼

if __name__ == "__main__":N=int(input())for n in range(N):M=int(input())d={}ans=1for m in range(M):li=list(map(int,input().split()))s=li[0]newd={}for i in range(s):ind=(li[i*2+1],li[i*2+2])if(ind in d):newd[ind]=d[ind]+1else:newd[ind]=+1for nd in newd:ans=max(ans,newd[nd])d=newdprint(ans)

3.機器人跳躍問題

題目描述

機器人正在玩一個古老的基于DOS的游戲。游戲中有N+1座建筑----從0到N編號，從左到右排列。編號為0的建筑高度為0個單位，編號為i的建筑的高度為H(i)個單位。

起初，機器人在編號為0的建筑處。每一步，它跳到下一個（右邊）建筑。假設機器人在第k個建筑，且它現在的能量值是E，下一步它將跳到第k+1建筑。他將會得到或者失去正比于H(K+1)和E之差的能量。如果H(k+1)>E那么機器人就失去H(K+1)-E的能量值，反之它將得到E-H(K+1)的能量值

游戲目標是到達第N個建筑，在這個過程中，能量值不能為負。現在的問題是機器人以多少能量值開始游戲，才可以保證完成游戲

輸入描述

第一行輸入，表示一共有N組數據 第二個是N個空格分割的整數，H1,H2,H3,...,Hn代表建筑的高度

輸出描述

輸出一個單獨的數表示完成游戲所需的最小單位的初始能量

示例

示例1

輸入： 5 3 4 3 2 4 輸出： 4

示例2

輸入： 3 4 4 4 輸出： 4

示例3

輸入： 3 1 6 4 輸出： 3

備注

數據約束：
1<=N<=10^5
1<=H(i)<=10^5

分析

• 用二分查找來找到最小能量值，start=0，end=max(H),高度小于能量值時，能量只增不減，座椅最大值為max(H);
• 遍歷建筑物，更新E值，若中間E小于0，則更新start=mid+1；
• 反之end=mid；
• 最后返回end。

參考代碼

if __name__ == "__main__":N=int(input())H=list(map(int,input().split()))start=0end=max(H)while(start<end):mid=(start+end)//2E=midjudge=Truefor h in H:if(E < h):E-=(h-E)else:E+=(E-h)if(E < 0):start=mid+1judge=Falsebreakif(judge):end=midprint(end)

4.畢業旅行問題

題目描述

小明目前在做一份畢業旅行的規劃。打算從北京出發，分別去若干個城市，然后再回到北京，每個城市之間均乘坐高鐵，且每個城市只去以此。由于經費有限，希望能夠通過合理的路線安排盡可能的省一些路上的開銷。給定一組城市和每對城市之間的火車票的價錢，找到每個城市只訪問一次并返回起點的最小花銷。

輸入描述

城市個數n(1<=n<=20，包括北京) 城市間的車票價錢，n行n列的矩陣m[n][n]

輸出描述

最小花銷s

示例

示例1

輸入： 4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0 輸出： 13 說明： 共四個城市，城市1與城市1的車費是0，城市1和城市2的車費是2，以此類推，無需考慮極端情況。

分析

• 遍歷所有城市，得到每個狀態下的最小車費，s是車費，past記錄已遍歷的城市包含的車票，形如<a,b>是指從a城市到b城市，初始為{(0,0)}，只包含一個城市，車費為0；

• 遍歷，新增加一個城市i，遍歷所有的車票<a,b>，使得<i,a>+<i,b>-<a,b>最小，即遍歷當前城市最小的花費；

• 更新past和s；

• 遍歷完，返回s。

參考代碼

if __name__ == "__main__":n=int(input())m=[]for i in range(n):m.append(list(map(int,input().split())))s=0past=set()past.add((0,0))for i in range(1,n):a,b=0,0cost=m[i][a]+m[i][b]for p in past:c=m[p[0]][i]+m[p[1]][i]-m[p[0]][p[1]]if(c < cost):a=p[0]b=p[1]cost=cs+=costpast.remove((a,b))past.add((a,i))past.add((i,a))print(s)

4.過河問題

題目描述

將所有人送到河對面，每次只能做2或3個人，且時間是船上人過河時間的最大值。

輸入描述

第一行是整數m，表示測試樣例格式 每個測試樣例的第一行是一個正整數n，表示參加過河的人數；（2<=n<100000） 第二行是n個正整數a[i]（0<a[i]<100000），表示n個人的單獨過河時間

輸出描述

每個測試樣例，輸出應該準備的最少過河時間。

示例

示例1

輸入： 2 2 1 2 4 1 1 1 1 輸出： 2 3

分析

• 用貪心算法來解，分為五種情況，time記錄耗時：

• 1人數大于等于7時，按耗時排序得（a,b,c,d,***,m3,m2,m1），先將最耗時的三人送過去，三個同時過去耗時（2d+c+b+m1）,先送過去兩個，再送過去一個，耗時（2c+2b+m1+m3）,逐個送過去，耗時（3b+m1+m2+m3），耗時為三種情況的最小值;

• 2人數大于等于6時，按耗時排序得（a,b,c,***,m3,m2,m1），先將最耗時的三人送過去，三個同時過去耗時（2m3+c+b+m1）,先送過去兩個，再送過去一個，耗時（2c+2b+m1+m3）,逐個送過去，耗時（3b+m1+m2+m3），耗時為三種情況的最小值;

• 3人數等于五個人時，按耗時排序得（a,b,c,d,e），最大兩個先過去后面三個再過去，耗時（e+3c+b）,逐個過去，耗時（e+d+c+2b）;

• 4人數等于四個人時，按耗時排序得（a,b,c,d），耗時（b+c+d）;

• 5人數等與三或二個人時，耗時最大耗時值；

• 返回time。

參考代碼

if __name__ == "__main__":N=int(input())for i in range(N):n=int(input())a=list(map(int,input().split()))a.sort()time=0start=0end=n-1while(end-start+1>=7):p1=a[end]+a[start+1]*2+a[start+2]+a[start+3]*2#過兩個小的，再將三個最大的一起過去p2=a[end]+a[end-2]+a[start+1]*2+a[start+2]*2#過一個小的，將兩個最大的過去，再過去一個大的p3=a[end]+a[end-1]+a[end-2]+a[start+1]*3#逐個過最大的time+=min(p1,p2,p3)end-=3while(end-start+1>=6):p1=a[end]+a[start+1]*2+a[start+2]+a[start+3]*2p2=a[end]+a[end-2]+a[start+1]*2+a[start+2]*2p3=a[end]+a[end-1]+a[end-2]+a[start+1]*3time+=min(p1,p2,p3)end-=3if(end-start+1==5):p4=a[end]+a[start+1]+a[start+2]*3p5=a[start+1]*2+a[start+2]+a[start+3]+a[start+4]time+=min(p4,p5)end=-1if(end-start+1==4):time+=sum(a[start+1:end+1])end=-1if(end-start+1>=2):time+=max(a[start:end+1])print(time)

總結

以上是生活随笔為你收集整理的字节跳动2019春招第二次笔试编程题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。