338 Counting Bits。輸入一個整數n，對于 0 ≤ i ≤ num，計算每個數的二進制1的個數。例如：num = 5 返回 [0,1,1,2,1,2]。希望能在O(n)的時間內完成。這里有動態規劃的思想。
思路一：

十進制數二進制表示

0	000	0
1	001	1+(0的bits)
2	010	1
3	011	1+(1的bits)
4	100	1
5	101	1+(1的bits)
6	110	1+(2的bits)
7	111	1+(3的bits)
8	1000	1
9	10001	1+(1的bits)
10	10010	1+(2的bits)
11	10011	1+(3的bits)
…

觀察可以發現，值為2n的時候,1的位數為1。其他情況下數，就是1+【從0開始的數1的位數】。

public int[] countBits3(int num) {int[] r = new int[num+1];int p = 1,i=0;while(p<=num){if((p&(p-1))==0) i=0;r[p++] = 1+r[i++];}return r; }

思路二：發現一個規律：,7=111 ，由011->111添加了1個1；6=110，由011->110,1的個數不變，但是1的位置變了。從0daonum是一個不斷變換1的位置或者不斷加1的過程，這樣就將任意一個數i，與i/2聯系起來了。

public int[] countBits(int num) {int[] r = new int[num+1];for(int i =1;i<=num;i++){r[i] = r[i/2]+(i&1);}return r; }

i&1，當數字為偶數就加0，如果是奇數就加1。

318 Maximum Product of Word Lengths。最大的單詞長度乘積。輸入一個字符串數組words，返回最大的length(words[i])*length(words[j]),i≠j，并且單詞i和單詞j不含有公共字符。
思路一：難點是判斷兩個字符串是否包含相同字母。可以一個個遍歷找到，效率會比較低。看看用位運算能怎么做。一共26個小寫字母。表示不同的字母可以用one-hot類型表示（從詞向量表示方法得到的啟示）。

z = 10000…000(一共25個0)
y = 01000…000(一共25個0)
…
a = 0000…001

用26位的二進制表示不同的字母。
這樣一個字符串 abc = 000….111
azc = 100…..101
兩個字符串的值做與操作。如果結果為0，則說明沒有相同字符。

public int maxProduct(String[] words) {int n = words.length;int[] values = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < words[i].length(); j++) {values[i] |= (1 << (words[i].charAt(j) - 'a'));}}int maxproduct = 0;for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if ((values[i] & values[j]) == 0) {if (words[i].length() * words[j].length() > maxproduct) {maxproduct = words[i].length() * words[j].length();}}}}return maxproduct;}

137 Single Number II。給定一個數組，每個數字出現三次，只有一個數字出現了一次。找到這個數字。
思路一：以前有個題目是說每個字母出現兩次，只有一個字母出現了一次。這樣用異或操作，就能找到只出現了一次的字母。但是出現三次？這里方法不管用了。
　計算數組中所有數字的每一bit1的個數。1=01，如果數組中有三個1，那么第0位的1就有3個，3%3=0。你肯定會問題如果數組中有三個1和3呢？那第0位的1就會有6個，6%3=0。但是如果只有2個3，那第0位的1就只有5個，5%3!=0。那3就是要找的數字了。

public int singleNumber(int[] nums) {int result = 0;for (int j = 0; j < 32; j++) {int sum = 0;for (int i = 0; i < nums.length; i++) {sum += ((nums[i] >> j) & 1);}result += ((sum % 3)<<j);}return result; }

260 Single Number III。輸入數組nums，每個數字都恰好出現了兩次。但是有兩個數字，都只出現了一次。找到這兩個數字。
思路：記錄只出現了1次的兩個數分別為a，b。
　出現了2次的時候，找不同，肯定需要異或操作。對所有nums的元素做異或，最后得到的是r=a|b。如果r的第i位等于1，那說明a和b在這個位置是有分歧的。我們利用這一個bit就可以將nums數組分為第i位是0和第i位是1，兩個部分。這個時候再做異或，就能去掉出現了兩次的數，留下只有一次的數。
　只留下一個數某一位為1，其他都為0，的操作是：n &=-n。
　

public int[] singleNumber(int[] nums) {int[] ans = new int[2];int diff = 0;for (int num : nums) {diff ^= num;}diff &= -diff;for (int num : nums) {if ((num & diff) == 0) {ans[0] ^= num;} else {ans[1] ^= num;}}return ans; }

78 subsets
思路：求子集，就是將數組中每一個元素，或者取或者不取，組合起來。從二進制的角度來表示。例如nums=[1,2,3]。下標分別是 0,1,2。每次取一個，2個，三個就遍歷完成了。
用1表示取這一位的數字。

下標： 0 1 2
組合 0 0 0 =0
1 0 0 =4
0 1 0 =2
0 0 1 =1
1 1 0 =6
1 0 1 =5
0 1 1 =3
1 1 1 =7

　發現下標用0 1 表示后的值就是從0到7. 7=2^3-1。所以找到規律。
　做了這么久，第一次直接找到最佳回答。
　顯然還可以用深度優先搜索的思路理解。
　

public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList<List<Integer>>();int n = nums.length;int total = (1<<n)-1;for(int i=0;i<=total;i++){List<Integer> list = new ArrayList<Integer>();for(int j=0;j<n;j++){if(((i>>j) &1)==1){list.add(nums[j]);}}result.add(list);}return result;}

總結：這次關于二進制習題的復盤就結束了。整個做題的過程還是比較沮喪的。平時二進制操作用的比較少。前面的習題基本都是得看答案才能知道二進制該怎么用。這些操作在筆記中，用加粗符號標記出來了。當習題做到中間的時候，已經開始能想到用什么操作，能實現什么功能了。但是還不能完全做對。到了最后終于能找到感覺了。這也說明了練習，總結，才能掌握一門技巧。多次練習、總結終會學到一門技巧。解決問題過程中，對規律的觀察和總結，是解題的關鍵。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的复盘二进制的习题(2)的全部內容，希望文章能夠幫你解決所遇到的問題。

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