2021年百度公司春季實習生招聘附加題(編程)面試題

小編:管理員 548閱讀 2021.06.15

第1題:


[編程題] 今天要吃點好的!

加班了一個通宵的度度熊,神經有點恍惚,想到依然未能解決的Bug,眼淚禁不住霹靂嘩啦往下掉……他抬頭看了看帝都灰蒙蒙的天空,一咬牙,一跺腳,大叫一聲——勞資今天要吃點好的! 已知本廠有n個食堂,第i(i屬于[1,n])個食堂有m[i]種食物,每種食物有一個價錢c,享受度v,度度熊希望去一個食堂就餐,花費[bot,top]范圍內的錢數(也可以拍桌子走人,哪里都不吃了),選擇若干種食物,使得自己所能獲得的享受度最大。(注意,度度熊還有一個挑食的特點,同一種食物他最多只會點一份。) 現在告訴你所有食堂食物的信息,希望你進行選擇搭配,使得度度熊可以得到最大的享受度,并輸出這個享受度的值。 

輸入描述:

第一行是一個正整數T(1<=T<=20),表示有T組測試數據。
對于每組數據——
第一行是三個數n,bot,top,n代表食堂數1<=n<=10),bot是這次吃飯的最低消費,top是這次吃飯的最高消費(0<=bot,top<=10000)
接下來依次是n個食堂的信息,對于第i個食堂
第一行是一個數m[i](o<=m[i]<=100),代表第i個食堂的食物數
第二行有2*m[i]個數,分別是c[i][1],v[i][1],c[i][2],v[i][2],……c[i][m[i]],v[i][m[i]]
c[i][j]表示第i個餐廳第j種食物的價錢,v[i][j]代表第i個餐廳第j種食物給度度熊帶來的享受度。

輸出描述:

對于每組數據,請輸出一行,每行一個正整數。表示度度熊所能獲得的最大享受度。
數據結果保證不會超過2^31-1.

輸入例子:

2
2 10 20
5 1 1 2 1 5 1 10 1 20 1
5 1 2 2 2 5 2 10 2 20 2
2 10 10
1 5 1
1 5 1

輸出例子:

8
0



第2題:


[編程題] 01排序

給定一個01串(僅由‘ 0’或‘1’組成的字符串),現在想把這個數字串排序成“非遞減”有序序列,請問至少需要多少次交換(任意兩個位置交換)? 

輸入描述:

輸入數據第一行是一個正整數T(T<=100),表示有T組測試數據;
接下來的T行,每行給出01串。
數據保證——
50%的字符串長度在[1,100 ]
95%的字符串長度在[1,10000]
100%的字符串長度在[1,1000000]


輸出描述:

對于每組測試數據,請輸出排成“非遞減有序序列”的最小交換次數。
每組輸出占一行。


輸入例子:

3
01
10
110


輸出例子:

0
1
1

第3題:

實現一個函數,對一個正整數n,算得到1需要的最少操作次數。操作規則為:如果n為偶數,將其除以2;如果n為奇數,可以加1或減1;一直處理下去。

例子:
func(7) = 4,可以證明最少需要4次運算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求:實現函數(實現盡可能高效) int func(unsign int n);n為輸入,返回最小的運算次數。給出思路(文字描述),完成代碼,并分析你算法的時間復雜度。

關聯標簽:
最近中文字幕2018_最近中文字幕完整版2019_最近更新中文字幕第1