[leetcode]题型整理之用bit统计个数

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?

记录32个bit每个bit出现的次数不能被3整除的几位加起来。

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

巴特西

[leetcode]题型整理之用bit统计个数

最新文章

热门文章