Archive for October 7th, 2013
- In: classic | leetcode
- Leave a Comment
经典题，注意balanced的定义：左右子树都balance，且高度差<=1。所以下面这个也是balanced的，即使a的做右子树都不是完全树。
a / \ b d / \ c e
唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”，直接用height = -1表示不平衡就行。
public boolean isBalanced(TreeNode root) {
return getHeight(root) >= 0;
}
private int getHeight(TreeNode root) {
if (root == null)
return 0;
int leftHeight = getHeight(root.left);
if (leftHeight < 0)
return -1;
int rightHeight = getHeight(root.right);
if (rightHeight < 0)
return -1;
if (Math.abs(leftHeight - rightHeight) > 1)
return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
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 