基因数据库网站建设,工农区网站建设,wordpress代码详解,高清的广州网站建设338 Counting Bits。输入一个整数n#xff0c;对于 0 ≤ i ≤ num#xff0c;计算每个数的二进制1的个数。例如#xff1a;num 5 返回 [0,1,1,2,1,2]。希望能在O(n)的时间内完成。这里有动态规划的思想。 思路一#xff1a;
十进制数二进制表示0000010011(0的bits)20101…338 Counting Bits。输入一个整数n对于 0 ≤ i ≤ num计算每个数的二进制1的个数。例如num 5 返回 [0,1,1,2,1,2]。希望能在O(n)的时间内完成。这里有动态规划的思想。 思路一
十进制数二进制表示0000010011(0的bits)2010130111(1的bits)4100151011(1的bits)61101(2的bits)71111(3的bits)8100019100011(1的bits)10100101(2的bits)11100111(3的bits)…
观察可以发现值为2n2^n的时候,1的位数为1。其他情况下数就是1【从0开始的数1的位数】。
public int[] countBits3(int num) {int[] r new int[num1];int p 1,i0;while(pnum){if((p(p-1))0) i0;r[p] 1r[i];}return r;
}
思路二发现一个规律,7111 由011-111添加了1个16110由011-110,1的个数不变但是1的位置变了。从0daonum是一个不断变换1的位置或者不断加1的过程这样就将任意一个数i与i/2联系起来了。
public int[] countBits(int num) {int[] r new int[num1];for(int i 1;inum;i){r[i] r[i/2](i1);}return r;
}
i1当数字为偶数就加0如果是奇数就加1。
318 Maximum Product of Word Lengths。最大的单词长度乘积。输入一个字符串数组words返回最大的length(words[i])*length(words[j]),i≠ji \ne 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的个数。101如果数组中有三个1那么第0位的1就有3个3%30。你肯定会问题如果数组中有三个1和3呢那第0位的1就会有6个6%30。但是如果只有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次的两个数分别为ab。 出现了2次的时候找不同肯定需要异或操作。对所有nums的元素做异或最后得到的是ra|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. 72^3-1。所以找到规律。 做了这么久第一次直接找到最佳回答。 显然还可以用深度优先搜索的思路理解。
public ListListInteger subsets(int[] nums) {ListListInteger result new ArrayListListInteger();int n nums.length;int total (1n)-1;for(int i0;itotal;i){ListInteger list new ArrayListInteger();for(int j0;jn;j){if(((ij) 1)1){list.add(nums[j]);}}result.add(list);}return result;}
总结这次关于二进制习题的复盘就结束了。整个做题的过程还是比较沮丧的。平时二进制操作用的比较少。前面的习题基本都是得看答案才能知道二进制该怎么用。这些操作在笔记中用加粗符号标记出来了。当习题做到中间的时候已经开始能想到用什么操作能实现什么功能了。但是还不能完全做对。到了最后终于能找到感觉了。这也说明了练习总结才能掌握一门技巧。多次练习、总结终会学到一门技巧。解决问题过程中对规律的观察和总结是解题的关键。
