唐山公司网站建设 中企动力唐山,wordpress开发,wordpress 雅黑,做公司永久免费网站什么好本文是对近期二进制专题的leetcde习题的复盘。文中的解决思路来源于leetcode的讨论#xff0c;以及一些网页。 342 判断一个整数(32bits)是否是4的次幂。 写出4i,i0,1,2,3,4...的二进制表示#xff0c;查找规律。会发现这些数的特征是 a 都0#xff1b;b 只有一位是… 本文是对近期二进制专题的leetcde习题的复盘。文中的解决思路来源于leetcode的讨论以及一些网页。 342 判断一个整数(32bits)是否是4的次幂。 写出4i,i0,1,2,3,4...4^i,i=0,1,2,3,4...的二进制表示查找规律。会发现这些数的特征是 a 都0b 只有一位是1代码n(n-1)0c 1都在奇数位置如果从1开始数代码n(0x55555555)!0。
191 数数一个无符号整数n的二进制表示中有几个1。 方法一每次判断最末位置是否为1n11最末位是1接着nn1,继续判断。 方法二每次判断n的某一个位置从最末位开始。n1!0该位是1接着计算(n(11))再继续n(12)如此下午判断32个位置。方法一和二思路是相同的都是通过位移来判断不同的位置都需要32次循环只是一个移动数字一个移动掩码mask。 方法三如果数字n的二进制位只有1位是1循环32次太浪费了。n(n-1) 实际上是把一个数的最低位的有效1给去掉了而且一次还只能去掉一个位置上的1。这样只要n(n(n-1))n不等于0就知道1的位数是加1的。 思考如果是有符号的呢
136 Single Number。给定的数组中每个数都出现了两次只有一个数出现了一次。找到只出现了一次的数。 方法两个相同的数异或之后会是0。所有数字异或之后加和留下的数就是要找的数。
461 Hamming Distance。海明距离是计算两个int都多少个位是不同的。 方法任意两个数异或之后不同的位会变为1。步骤是n(i^j)数n有几个1等同于191。 169 Majority Element. 主元素是指在数组中出现次数超过n/2的元素。前提假设数组不为空主元素总数存在。(这题做过怎么一点印象都没有) 方法1循环计算nums[i]出现次数。时间复杂度O(n2)O(n^2)。 方法2用hashmap保存每个数字出现次数。时间复杂度O(n)O(n)空间复杂度O(n)O(n)。 方法3先排序再找到最长的连续串。时间复杂度O(nlogn)O(nlogn)。 方法4分治法数组一分为2查找第一部分的主元素A第二部分的主元素B。如果A的次数B的次数A和B都是候选主元素。如果不同则选出主元素。时间复杂度O(nlogn)O(nlogn)。 方法5随机选元素不甚理解。平均时间复杂度O(n)O(n)最坏是无穷。随机啊。。。。 方法6Moore Voting algorithm。定义候选元素element和次数count。不断遍历nums如果count0element当前元素count1如果count0当前元素element则count否则count–。留下的element一定是主元素。时间复杂度O(n)O(n)。这个想法太奇妙了。有点像双方交战主元素是一方其他元素是一方。不断增加或者减少count。 方法7位运算。直接上代码吧。有点不会描述了。一个int32位。哪个位置上1的个数n/2那这一位一定是主元素贡献的。所以只要找到1出现次数超过n/2的位其他位置为0就可以找到主元素。
public int majorityElement(int[] nums) {int[] bit new int[32];for (int i 0; i nums.length; i) {for (int j 0; j 32; j) {bit[j] (nums[i] j) 1;}}int majority 0;for (int j 0; j 32; j) {bit[j] bit[j] (nums.length / 2)? 1 : 0;majority bit[j] j;}return majority;}
405 将一个整数用十六进制表示 方法做十进制与十六进制基础元素的映射。做映射有两种方式一种是map一种是数组。当key是数字的时候用数组还是比较方便的。nums[]{0,1,2,….a,b,…f}。数组的下标正好是十六进制对应的十进制。 接着十六进制可以用4位二进制表示。每次将num与0x0f做与操作这样就能只留下最后四位了。
public String toHex(int num) {if(num0) return 0;char[] hexadecimalChar new char[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f };String r ;while (num ! 0) {r hexadecimalChar[num 0x0f] r;num 4;}return r;}
190 给定一个无符号的整数num输出一个整数out这个整数是输入数字的二进制的逆转。如果方法要多次调用可以怎么优化。 方法一变量r为最后结果从num低位开始每次处理1位r1最低位处理的值。循环32次。
public int reverseBits(int n) {int result 0;for (int i 0; i 32; i) {result 1;result n1;n 1;}return result;} 多次调用优化的方法应该是存储字节与结果的映射关系。 方法二可以先看代码。来自网页。每4位当做一个整体处理int32位分为8个部分abcdefgh。处理顺序是abcdefgh - efghabcd - ghefcdab - hgfedcba。代码最后两行是处理4位内部的倒序。 这思路看到后真是震惊。原来分治法还能这么玩。膜拜啊。
public int reverseBits(int n) {n (n 16) | (n 16);n ((n 0xff00ff00) 8) | ((n 0x00ff00ff) 8);n ((n 0xf0f0f0f0) 4) | ((n 0x0f0f0f0f) 4);n ((n 0xcccccccc) 2) | ((n 0x33333333) 2);n ((n 0xaaaaaaaa) 1) | ((n 0x55555555) 1);return n;}
476 Number Complement。一个int的补是指二进制取反。但是高位的0不变。例如5的补是2。因为 5101 取反0102。但是一个int有32位对于5从第4位开始的0都不算。所以需要知道最高位的1在哪个位置即可。 下面是两种解法。
public int findComplement(int num) {return ~num (Integer.highestOneBit(num) - 1);
}public int findComplement2(int num) {int mask Integer.MAX_VALUE;while((num mask) !0){mask 1;}System.out.println(~mask);return ~num (~mask);
}
401 Binary Watch。二进制手表。好酷的手表。这是一个穷举搜索的问题。 时8 4 2 1 。每一个选与不选分别用1和0 表示。这样就形成了一个一个的二进制数。如果说时钟只有一个灯亮那么选择可能有 时8 4 2 1 f1: 0 0 0 1 f2: 0 0 1 0 f3: 0 1 0 0 f4: 1 0 0 0 231 判断一个数是否是2的平方。2的平方的特征是a 大于02 只有一个1。
public boolean isPowerOfTwo(int n) {return n0 (n(n-1))0;}
389 Find the Difference。输入两个字符串s、t。t是s中所有字母随机排列后组成的字符串但是t中有一个字符在s中没有出现。找出在t中没有出现的那个字符。 思路一用map。遍历s中每个字符的出现次数保存在map中。接着遍历t中的字符串将map[key]value值减1。如果在map的key值不存在或者说map[key]的value 0 那这个字符一定不在s中出现。 思路2位操作。用异或可以将相同的字符抵消。s和t两个字符串做异或留下的就是没在s中出现的字符。
public char findTheDifference2(String s, String t) {char ch 0;for(int i0;is.length();i){ch ^ s.charAt(i);ch ^ t.charAt(i);}ch ^ t.charAt(t.length()-1);return ch;
}
268 Missing Number。给一个包含n个不同数值的数组nums数组本应该是0,1,2…n这样的数字但是丢了一个数字。返回丢失的数字。例如输入 nums [0, 1, 3] 返回2。 思路这个题目与上一提很相似。389是查找多出的字符268是查找丢失的数字。都是从两个可比较的对象中查找出多的或者少的部分。 public int missingNumber(int[] nums) {int xor 0,i0;for(i0;inums.length;i){xor xor^i^nums[i];}return xor ^ i;}
371 Sum of Two Integers。不用 - 操作求两个数的和。这个解法就是比较神奇了。处理两个数相同的部分处理两个数相异的部分。两个数相同的部分加和的时候还要向前进一和我们手动计算和相似。
public int getSum(int a, int b) {return b 0 ? a : getSum(a ^ b, (a b) 1);
}
参考资料
1 bit-manipulation 2 网址 3 网址 可能会有落下的网址未列出。谢谢作者们。
