LeetCode Bit题目汇总整理

136. Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
思路:利用异或的性质,相同位异或为0,不同异或为1.

public class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }
}

371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
思路:位运算加法。
1.先检查edge case,如果有一个给定为0,就返回另一个的值.
2. 对于输入的a,b 如果不考虑进位的话,做加法求和等同于a XOR b, 例如1+0=1,1+1=0;1+0=1.
3. 对于进位运算,当相加两数都为1才进位,进位可以表示为carry = (a and b) << 1. 进位,就左移1位。
4. 最后 a + b可以表示为: (a XOR b) + (a AND b) << 1, 由于可能产生进位,所以要递归调用处理进位。

public class Solution {
    public int getSum(int a, int b) {
        if (b == 0) return a;
        int sum = a ^ b;
        int carry = (a & b) << 1;
        return getSum(sum, carry);
    }
}

231. Power of Two
Given an integer, write a function to determine if it is a power of two.
思路: 2次幂的特征就是数字中只有一个1. k次幂就是相当于向左移动了k位, 那么这个数N-1后,第k位变为0,从第k-1位到最后一位都是1. 那么N & (N-1) == 0。 我们可以用这个性质来判断这个数是否是2的次幂.
思路2:我们还可以连续对2做除法,直到判断最后是否为1.

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }
}

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 0) return false;
        if (n == 1) return true;
        while( n % 2 == 0) {
            n = n / 2;
            if (n == 1){
                return true;
            }
        }
        return false;
    }
}

231. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
思路: 直接方法就是不停的跟4整除, 看最后是否为1.
bit方法,4次方就是1向左移动两位,4次幂中1只出现在奇数位,也就是二进制数从右边起开始,1,3,5,…奇数位都为1. 其16进制表示为0x55555555, 那么如果(num & 0x55555555! != 0,肯定不是4次幂,这里我们先去除不是2次幂的,然后去除不是4次幂的。

public class Solution {
    public boolean isPowerOfFour(int num) {
       if (num <= 0) return false;
       return ((num&(num-1)) == 0) && ((num & 0x55555555) != 0 );
    }
}

191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.
思路: 求给定的无符号的二进制整数中有多少个1. 我们可以从低位开始,挨个判断是否为1, 如果为1,就累加,然后整个数字右移1位(注意要用无符号右移>>>). 直到最后为0,循环停止。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if (n == 0) return 0;
        int count = 0;
        while (n != 0) {
            count += 1 & n;
            n = n >>> 1;
        }
        return count;
    }
}

190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

思路: 32位无符号二进制翻转,大概思路就是对于给定数,从低位i开始,翻转后就是我们把i对应的数字放到31-i位上面。 大概分几步:1. 将翻转的数n跟1做&运算,取最低位的数. 2.将这个数左移到31-i位置上面. 3. 将翻转的结果放到result变量 4. n 无符号右移1位,取下一个数

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int reverse = 0;
        for (int i = 0; i < 32; i++) {
            int tmp = n & 1;
            int reverseTmp = tmp << (31 - i);
            reverse = reverse | reverseTmp;
            n = n >>> 1;
        }
        return reverse;
    }
}

169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路: 投票算法,用一个count表示出现次数,candidate表示这个众数,如果candidate跟当前数相同,则count加1,否则count减一。如果count为0情况,那么candidate就选当前数。最后返回的candidate就为众数。

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int ret = 0;
        for (int num : nums) {
            if (count == 0) {
                ret = num;
            } 
            if (ret == num) {
                count++;
            } else {
                count--;
            }
        }
        return ret;
    }
}

389. Find the Difference
Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

思路: 利用XOR性质,把s中所有字符代表的char数值XOR,跟t中所有字符代表的char数值XOR, 那么结果就是不同的那个字母的char值。

public class Solution {
    public char findTheDifference(String s, String t) {
        char res = 0;
        for (int i = 0; i < s.length(); i++) {
            res = (char)(res ^ s.charAt(i));
        }
        for (int j = 0; j < t.length(); j++) {
            res = (char)(res ^ t.charAt(j));
        }
        return res;
    }
}

405. Convert a Number to Hexadecimal
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
思路: 十进制转十六进制。 可以借鉴十进制转二进制方法,对2做mod,求得的余数反向输出。 这里我们可以将输入数字的每4个bit作为一个单位进行转换。

public class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        while( num != 0) {
            sb.append(hex[num & 15]);
            num = num >>> 4;
        } 
        sb.reverse();
        return sb.toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s