Posts Tagged ‘bit’
- In: leetcode
- 2 Comments
这题上来没法下手，咬牙看了半天用dfs写出了个差不多的，最后卡在两个list merge上。实在看不出规律（后来发现是自己例子都写错了！！），上网一查，大神回复：
假设有n-1的答案为：G0, G1, …, Gn，想得到n的答案，只需要在G0…Gn左边加上一个0，再把G0…Gn颠倒顺序，在左边加上一个1即可。比如n=3（在分界线上倒映）：
000 001 011 010 --- 110 111 101 100
用dfs可以每次求出左边是0，然后求出左边是1的，合一起就是了。两个教训：
- 这种数学题找规律，千万别自己把例子写错了。那样打死也看不出规律的。
- 拿到一题往死里想个10分钟总能想出点眉目的，别放弃。
public ArrayList<Integer> grayCode(int n) {
if (n == 0) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);
return list;
}
return getGrayCode(n - 1);
}
private ArrayList<Integer> getGrayCode(int pos) {
if (pos == 0) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);
list.add(1);
return list;
}
ArrayList<Integer> result = new ArrayList<Integer>();
ArrayList<Integer> startsWithZero = getGrayCode(pos - 1);
ArrayList<Integer> startsWithOne = new ArrayList<Integer>();
for (int i = startsWithZero.size() - 1; i >= 0; i--) {
startsWithOne.add(startsWithZero.get(i) + (1 << pos));
}
result.addAll(startsWithZero);
result.addAll(startsWithOne);
return result;
}
不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的，所以到最后还得不断缩小范围，好能贴近结果。
算法：a / b
- a本来是想一直-b，然后减到<0了，算counter。但是这样慢，所以类似c++ vector的思路，每次发现还没减没，那减数就翻倍（b <<= 1）
- 然后到了一定程度，b实在太大了，大于a剩余的部分了，那么就停止。然后剩下的a再一点点开始减，b回归成最开始的值，重做这两步。
重点是一旦超过，b应该不要一下回到原始值，而是应该一点一点/2这样做。最刁钻的地方是test case全是各种Integer.MINVALUE之类的，搞得各种溢出，然后才发现Math.abs(MIN_VALUE)其实还是-2147483648（坑爹呢吧abs还是负数），而不是2147483648。
下面的解法是能跑过的。因为测试数据出现了-2147483648，还不能把它转成正的(2147483648就溢出了），所以直接全转换成long（64位），跑一遍就过了。
public int divide(int dividend, int divisor) {
if (dividend == 0)
return 0;
if (divisor == 1)
return dividend; //纯粹是为了防止超时
boolean positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
long absDividend = dividend < 0 ? 0 - (long) dividend : (long) dividend;
long absDivisor = divisor < 0 ? 0 - (long) divisor : (long) divisor;
int result = dividePositive(absDividend, absDivisor, absDivisor);
return positive ? result : 0 - result;
}
private int dividePositive(long p, long q, long originalDivisor) { // p / q
if (p < q)
return 0; //这个十分必要，否则会因为p > 0而直接下一层递归，pq永远不变，死循环了就。
int result = 0;
int e = 0;
while (p >= q) { //等于应该也进去。
result += 1 << e;
p -= q;
q = q << 1;
e++;
}
return p > 0 ? result + dividePositive(p, originalDivisor, originalDivisor) : result;
}
bit好久没看真是全尼玛忘了。那些最基本的：
- 显现a的第i位： a & 1 << i
- 把a的第i位置零：a &= ～(1 << i)
- 把result给populate回来：result |= 1 << i
创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。空间复杂度O(1).
public int singleNumber(int[] A) {
int[] bv = new int[32];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < 32; j++) {
bv[j] += (A[i] & (1 << j)) == 0 ? 0 : 1;
}
}
int res = 0;
for (int i = 0; i < 32; i++) {
if (bv[i] % 3 != 0) {
res |= 1 << i;
}
}
return res;
}
Lexi's Leetcode solutions 