#47. Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
class Solution {
// addition a, b => sum = a ^ b; carry = a & b
public int getSum1(int a, int b) {
int carry;
while (b != 0) {
carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
public int getSum2(int a, int b) {
int carry = (a & b) << 1;
int result = a ^ b;
if (carry == 0) {
return result;
}
return getSum2(carry, result);
}
}
#48. Number of 1 Bit
Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
class Solution {
public int hammingWeight(int num) {
int bits = 0;
while (num != 0) {
boolean is1 = (num & 1) != 0;
if (is1) {
bits++;
}
num = num >> 1;
}
return bits;
}
}
#49. Counting Bits
Given an integer n, return an array of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
class Solution {
public int[] countBits(int n) {
int[] array = new int[n+1];
for (int i=0; i<=n; i++) {
array[i] = hammingWeight(i);
}
return array;
}
}
#50. Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
class Solution {
public int missingNumber2(int[] nums) {
int max = nums.length;
int sum = (max+1) * max / 2;
for (int num : nums) {
sum -= num;
}
return sum;
}
public int missingNumber(int[] nums) {
int xor = nums.length;
// XOR properties:
// a ^ b = b ^ a => we can xor the elements in any order
// x ^ x = 0 => nums[k] ^ i = 0 if nums[k] == i => will eliminate matching elements
// x ^ 0 = x
// the unmatched i will stand out
for (int i=0; i<nums.length; i++) {
xor = xor ^ nums[i] ^ i;
}
return xor;
}
}
Bonus: Reverse bits
Reverse bits of a given 32 bits unsigned integer.
public class Solution {
public int reverseBits(int n) {
int res = 0;
int i = 32; // need to fill all 32 bits
while (i > 0) {
int currentBit = n & 1;
res = res << 1 | currentBit; // res = res * 2 + currentBit;
n = n >> 1;
i--;
}
return res;
}
}
Niciun comentariu:
Trimiteți un comentariu