137. Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int x = 0x40000000;
//find the first binary from where m is different from n
int i = 1;
for(i = 1; i < 32; i++){
int a = m & x;
int b = n & x;
if(a != b){
break;
}
x = x >> 1;
}
i--;
//i is the last binary where m is the same as n
int y = 0x80000000;
y = y >> i;
int result = m & y;
return result;
}
}
九章的代码更短
268. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int sum = nums[0];
for (int i = 1; i < n; i++) {
sum = sum ^ nums[i];
}
int sum2 = 0;
for (int i = 1; i <= n; i++) {
sum = sum ^ i;
}
return sum2 ^ sum;
}
}
how to decide if a number is power of 2?
(num&-num) == num