@Yano 2015-12-30T11:27:03.000000Z 字数 8364 阅读 7011

# LeetCode之Bit Manipulation题目汇总

LeetCode

LeetCode 题目汇总

# 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.

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

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!

    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.

    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)

    /**     * 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. 思路

    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   00C   01G   10T   11

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

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;    }

    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?

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?

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

    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.

“相异为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],
[]
]


    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);    }

• 私有
• 公开
• 删除