LeetCode之Bit Manipulation题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

Bitwise AND of Numbers Range

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.

实质：求m和n二进制编码中，相同的前缀

    public int rangeBitwiseAnd(int m, int n) {
        int bit = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            bit++;
        }
        return m << bit;
    }

参考：LeetCode 169 Majority Element

A Linear Time Majority Vote Algorithm 一个典型的算法，可以在一次遍历，时间复杂度是O(1)，空间复杂度是O(1)的情况下完成。

    public int majorityElement(int[] nums) {
        int m = nums[0];
        int c = 1;
        for (int i = 1; i < nums.length; i++) {
            if (m == nums[i]) {
                c++;
            } else if (c > 1) {
                c--;
            } else {
                m = nums[i];
            }
        }
        return m;
    }

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

1. How many majority elements could it possibly have?
2. Do you have a better hint? Suggest it!

参考：LeetCode 229 Majority Element II

因为题目中说是大于⌊ n/3 ⌋次数的元素，这样的元素最多只能有2个。

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> rt = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return rt;
        }
        int m1 = nums[0];
        int m2 = 0;
        int c1 = 1;
        int c2 = 0;
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x == m1) {
                c1++;
            } else if (x == m2) {
                c2++;
            } else if (c1 == 0) {
                m1 = x;
                c1 = 1;
            } else if (c2 == 0) {
                m2 = x;
                c2 = 1;
            } else {
                c1--;
                c2--;
            }
        }
        c1 = 0;
        c2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (m1 == nums[i]) {
                c1++;
            } else if (m2 == nums[i]) {
                c2++;
            }
        }
        if (c1 > nums.length / 3) {
            rt.add(m1);
        }
        if (c2 > nums.length / 3) {
            rt.add(m2);
        }
        return rt;
    }

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?

Credits: 
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

参考：LeetCode 268 Missing Number

既然是0~n只差其中一个数，不如再次加入0~n的序列，这样就和LeetCode 136 Single Number一样了，missing number只出现一次，其余都是出现两次。

    public int missingNumber(int[] nums) {
        int rt = nums.length;
        for (int i = 0; i < nums.length; i++) {
            rt = rt ^ nums[i] ^ i;
        }
        return rt;
    }

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

1. JDK：int bitCount(int i)

效率肯定高，JDK源码+_+

    /**
     * Returns the number of one-bits in the two's complement binary
     * representation of the specified {@code int} value.  This function is
     * sometimes referred to as the <i>population count</i>.
     *
     * @param i the value whose bits are to be counted
     * @return the number of one-bits in the two's complement binary
     *     representation of the specified {@code int} value.
     * @since 1.5
     */
    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

2. 思路

思路一☹：分别判断每一位，有n位就要判断n次。

思路二☺：有几个1就判断几次。参考如何判断一个数是2的n次方？判断i&(i-1)是不是0即可~

    public int hammingWeight(int n) {
        int rt = 0;
        while (n != 0) {
            n = n & (n - 1);
            rt++;
        }
        return rt;
    }

Power of Two

Given an integer, write a function to determine if it is a power of two.

Credits: 
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

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

Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].

考察位图。按位操作，A C G T分别用如下bits表示：

A   00
C   01
G   10
T   11

所以10个连续的字符，只需要20位即可表示，而一个int（32位）就可以表示。定义变量hash，后20位表示字符串序列，其余位数置0 。

定义一个set用来存放已经出现过的hash，计算新hash时，如果已经出现过，就放入结果的set中。

    public List<String> findRepeatedDnaSequences(String s) {
        if (s == null || s.length() < 11) {
            return new ArrayList<String>();
        }
        int hash = 0;
        Set<Integer> appear = new HashSet<Integer>();
        Set<String> set = new HashSet<String>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            hash = (hash << 2) + map.get(c);
            hash &= (1 << 20) - 1;
            if (i >= 9) {
                if (appear.contains(hash)) {
                    set.add(s.substring(i - 9, i + 1));
                } else {
                    appear.add(hash);
                }
            }
        }
        return new ArrayList<String>(set);
    }

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**).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

JDK ：int reverse(int i)

    /**
     * Returns the value obtained by reversing the order of the bits in the
     * two's complement binary representation of the specified {@code int}
     * value.
     *
     * @param i the value to be reversed
     * @return the value obtained by reversing order of the bits in the
     *     specified {@code int} value.
     * @since 1.5
     */
    public static int reverse(int i) {
        // HD, Figure 7-1
        i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
        i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
        i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
        i = (i << 24) | ((i & 0xff00) << 8) |
            ((i >>> 8) & 0xff00) | (i >>> 24);
        return i;
    }

思路

把第i位取出，放到结果的第31-i位上。

    public int reverseBits(int n) {
        int rt = 0;
        for (int i = 0; i < 32; i++) {
            rt |= ((n >> i) & 1) << (31 - i);
        }
        return rt;
    }

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: 
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

对于出现2次的数字，用异或。因为“相异为1”，所以一个数字异或本身为0，而0异或0仍为0， 一个数字异或0仍为这个数字。

0 ^ 0 = 0 
n ^ 0 = n 
n ^ n = 0

    public int singleNumber(int[] nums) {
        int n = 0;
        for (int i : nums) {
            n ^= i;
        }
        return n;
    }

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?

对于数组{1,1,1,2}来说，分析每一位：

0 0 0 1  
0 0 0 1  
0 0 0 1  
0 0 1 0  
……………  
0 0 1 3 (位数)

可以分析，分别计算每一位1的出现次数n，如果n%3==1，那么结果中这一位就应该是1。

    public int singleNumber(int[] nums) {
        int rt = 0, bit = 1;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int v : nums) {
                if ((v & bit) != 0) {
                    count++;
                }
            }
            bit <<= 1;
            rt |= (count % 3) << i;
        }
        return rt;
    }

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

参考：LeetCode 136 Single Number 
参考：LeetCode 137 Single Number II

“相异为1”，所以一个数字异或本身为0，而0异或0仍为0， 一个数字异或0仍为这个数字。

0 ^ 0 = 0 
n ^ 0 = n 
n ^ n = 0

1. 只有两个数a、b分别出现了一次，其余的数都是出现了两次
2. 把整个数组异或，结果等于a^b，而a与b是不相等的，所以a^b必不为0
3. 按照a^b结果其中一位，把数组分成两个，一组包含a，一组包含b，即问题变成LeetCode 136 Single Number

    public int[] singleNumber(int[] nums) {
        int[] rt = new int[2];
        int n = 0;
        for (int v : nums) {
            n ^= v;
        }
        int m = n & (~(n - 1));
        for (int v : nums) {
            if ((m & v) == 0) {
                rt[0] ^= v;
            } else {
                rt[1] ^= v;
            }
        }
        return rt;
    }

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,  
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

使用二进制，不需要递归。对于二进制中的每一位，0表示不选择，1表示选择。则有2^n种情况。

使用HashSet，能够直接过滤重复情况（先对数组排序，题目中也要求每个list非降序排列）。

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length == 0) {
            return new ArrayList<List<Integer>>();
        }
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        // 题目中要求每个list是非降序，所以要先从小到大排序
        Arrays.sort(nums);
        // 对于n位，有2^n种情况
        for (int i = 0; i < Math.pow(2, nums.length); i++) {
            List<Integer> list = new ArrayList<Integer>();
            int tmp = i;
            // 对于每种情况，分别求得二进制中1的个数
            // 0代表不选择，1代表选择
            for (int j = 0; j < nums.length; j++) {
                int bit = tmp & 1;
                tmp >>= 1;
                if (bit == 1) {
                    list.add(nums[j]);
                }
            }
            set.add(list);
        }
        return new ArrayList<List<Integer>>(set);
    }