- 相關推薦
百度公司筆試題目
1、實現一個函數,對一個正整數n,算得到1需要的最少操作次數,
百度公司筆試題目
。操作規(guī)則為:如果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為輸入,返回最小的運算次數。給出思路(文字描述),完成代碼,并分析你算法的時間復雜度。
答:
假設n表示成二進制有x bit,可以看出計算復雜度為O(2^x),也就是O(n)。
將n轉換到二進制空間來看(比如7為111,6為110):
- 如果最后一位是0,則對應于偶數,直接進行除2操作。
- 如果最后一位是1,情況則有些復雜。
**如果最后幾位是???01,則有可能為???001,???1111101。在第一種情況下,顯然應該-1;在第二種情況下-1和+1最終需要的步數相同,
資料共享平臺
《百度公司筆試題目》(http://m.msguai.com)。所以在???01的情況下,應該選擇-1操作。**如果最后幾位是???011,則有可能為???0011,???11111011。在第一種情況下,+1和-1最終需要的步數相同;在第二種情況下+1步數更少些。所以在???011的情況下,應該選擇+1操作。
**如果最后有更多的連續(xù)1,也應該選擇+1操作。
如果最后剩下的各位都是1,則有11時應該選擇-1;111時+1和-1相同;1111時應選擇+1;大于四個1時也應該選擇+1;
2、找到滿足條件的數組
給定函數d(n)=n+n的各位之和,n為正整數,如d(78)=78+7+8=93。這樣這個函數可以看成一個生成器,如93可以看成由78生成。
定義數A:數A找不到一個數B可以由d(B)=A,即A不能由其他數生成,F在要寫程序,找出1至10000里的所有符合數A定義的數。
回答:
申請一個長度為10000的bool數組,每個元素代表對應的值是否可以有其它數生成。開始時將數組中的值都初始化為false。
由于大于10000的數的生成數必定大于10000,所以我們只需遍歷1到10000中的數,計算生成數,并將bool數組中對應的值設置為true,表示這個數可以有其它數生成。
最后bool數組中值為false的位置對應的整數就是不能由其它數生成的。
【百度公司筆試題目】相關文章:
百度筆試題目10-26
百度網絡筆試題目07-19
百度用戶廈門筆試題目06-04
百度商業(yè)應用產品筆試題目09-19
百度校招產品經理筆試題目06-29
武漢地區(qū)百度產品經理筆試題目08-23
百度校園招聘產品經理筆試題目09-12
百度校園招聘產品經理筆試題目07-10
大唐公司筆試題目10-10
百度運營類面試筆試題目分享11-01