1酌壕、求二進制數(shù)字中1的個數(shù)
自帶庫 (binary_num).count('1')
def num_of_one(num):
'''
bin():convert the num to binary string
'''
if num >= 0:
nbin = bin(num)
return nbin.count('1')
else:
num = abs(num)
nbin = bin(num-1)
return 32 - nbin.count('1')
按位運算符有：左移運算符（<<），右移運算符（>>）,按位與（&）歇由，按位或（|）卵牍，按位翻轉（～），
異或運算（^）
沦泌。這些運算符中只有按位翻轉運算符是單目運算符糊昙，其他的都是雙目運算符。
3<<2 解法:11向左移動兩位變?yōu)?100,即12
~3 :3的二進制是11, -(11+1)=-100B=-4D. (注:B和D分別表示二進制和十進制).解法: - (-10+1) =1
鏈接：https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8來源：判磺客網(wǎng)**絕對最佳答案及分析：**
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
}
**答案正確:恭喜释牺！您提交的程序通過了所有的測試用例**
**分析一下代碼：** **這段小小的代碼，很是巧妙回挽。**
**如果一個整數(shù)不為0没咙，那么這個整數(shù)至少有一位是1。如果我們把這個整數(shù)減1千劈，那么原來處在整數(shù)最右邊的1就會變?yōu)?祭刚，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)。其余所有位將不會受到影響墙牌。**
**舉個例子：一個二進制數(shù)1100涡驮，從右邊數(shù)起第三位是處于最右邊的一個1。減去1后喜滨，第三位變成0捉捅，它后面的兩位0變成了1，而前面的1保持不變虽风，因此得到的結果是1011.我們發(fā)現(xiàn)減1的結果是把最右邊的一個1開始的所有位都取反了棒口。這個時候如果我們再把原來的整數(shù)和減去1之后的結果做與運算寄月，從原來整數(shù)最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000.也就是說无牵，把一個整數(shù)減去1剥懒，再和原整數(shù)做與運算，會把該整數(shù)最右邊一個1變成0.那么一個整數(shù)的二進制有多少個1合敦，就可以進行多少次這樣的操作。**
2验游、不通過第三變量進行兩個變量互換
a = 3 #11
b = 8 #1000
a = a^b # a = 1011 b = 11
b = b^a # a = 1011 b = 1000
a = a^b # a = 11
3充岛、一個文本文件，大約有一萬行耕蝉，每行一個詞崔梗，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想垒在，給出時間復雜度分析蒜魄。
http://dataunion.org/21517.html
方案1：這題是考慮時間效率。用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)场躯，時間復雜度是 O(nle)（le表示單詞的平準長度）谈为。然后是找出出現(xiàn)最頻繁的前10個詞，可以用堆來實現(xiàn)踢关，前面的題中已經(jīng)講到了伞鲫，時間復雜度是 O(nlg10)。所以總的時間復雜度签舞，是O(nle)與O(nlg10)中較大的哪一個秕脓。
附、100w個數(shù)中找出最大的100個數(shù)儒搭。
方案1：在前面的題中吠架，我們已經(jīng)提到了，用一個含100個元素的最小堆完成搂鲫。復雜度為O(100wlg100)傍药。
方案2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分默穴，知道比軸大的一部分在比100多的時候怔檩，采用傳統(tǒng)排序算法排序，取前100個蓄诽。復雜度為O(100w100)薛训。
方案3：采用局部淘汰法。選取前100個元素仑氛，并排序乙埃，記為序列L闸英。然后一次掃描 剩余的元素x，與排好序的100個元素中最小的元素比介袜，如果比這個最小的要大甫何，那么把這個最小的元素刪除，并把x利用插入排序的思想遇伞，插入到序列L中辙喂。依 次循環(huán)，知道掃描了所有的元素鸠珠。復雜度為O(100w*100)巍耗。
4、3次稱出12球中重量不同的一個球的解答
解法第一次必須分為三組渐排。
A = 8, B =4
第一次稱量：A組二分稱量
情況1：若相等則在B中炬太，從B中拿出3個，再從A中拿出3個稱量驯耻，若相當亲族，則球為剩的一個。
若不等可缚，則知道該球是重還是輕霎迫，假設為重。從3個球中取兩個球帘靡，稱量女气。若相等則球為剩余那個，若不等测柠，則重的即是所求球炼鞠。
情況2：若第一次不等，記錄兩側輕重轰胁，
設為C組D組谒主，C重D輕
稱量C1,C2,C3,D1===C4,正常3個球
若左重右輕，球在C1C2C3中
若右重左輕赃阀，球為C4
第三次稱量同情況1
