<noframes id="dh1vt"><progress id="dh1vt"></progress>

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

          小編:管理員 224閱讀 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為輸入,返回最小的運算次數。給出思路(文字描述),完成代碼,并分析你算法的時間復雜度。

          關聯標簽: