Tag Archives: 位运算

剑指 Offer 15. 二进制中1的个数

剑指 Offer 15. 二进制中1的个数

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/


统计无符号int的二进制中1的个数。简单题,n&(n-1)能把最后一个1消掉,直到为0。与LeetCode Number of 1 Bits相同,完整代码如下:

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
        while(n != 0) {
            ++ans;
            n = n & (n - 1);
        }
        return ans;
    }
};

本代码提交AC,用时4MS。

LeetCode XOR Operation in an Array

1486. XOR Operation in an Array

Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7

Example 4:

Input: n = 10, start = 5
Output: 2

Constraints:

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

给定start和n,将所有的start+2i进行异或。简单题,直接照做:

class Solution {
public:
	int xorOperation(int n, int start) {
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans ^= (start + 2 * i);
		}
		return ans;
	}
};

本代码提交AC,用时0MS。

LeetCode Integer Replacement

LeetCode Integer Replacement Given a positive integer n and you can do operations as follow:

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.
What is the minimum number of replacements needed for n to become 1? Example 1:
Input:
8
Output:
3
Explanation:
8 -> 4 -> 2 -> 1
Example 2:
Input:
7
Output:
4
Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

给定一个数n,不断对n进行如下两种操作中的一种
  1. 如果n是偶数,把n变成n/2
  2. 如果n是奇数,把n变成n+1或者n-1
问要把n变为1,需要的最少的变换次数是多少。 为啥我首先想到的是BFS。。。这不就相当于每个点根据情况可以走不同的方向,问走到终点1需要的最少步数吗?很像BFS呀。代码如下: [cpp] class Solution { private: struct P { long long val; int step; P(long long v_, int s_) :val(v_), step(s_) {}; }; public: int integerReplacement(int n) { P p(n, 0); queue<P> qp; qp.push(p); while (!qp.empty()) { P f = qp.front(); qp.pop(); if (f.val == 1)return f.step; else if (f.val & 1) { qp.push(P(f.val + 1, f.step + 1)); qp.push(P(f.val – 1, f.step + 1)); } else { qp.push(P(f.val / 2, f.step + 1)); } } return 0; } }; [/cpp] 本代码提交AC,用时6MS,只击败5%的人。。。 看讨论区,用位运算求解。要想快速的到达1,则n的二进制中0越多越好,因为0越多,后续越有可能用n/2快速的去掉一位。所以如果n是奇数时,我们判断一下n+1和n-1哪个包含的0越多,就走哪步。 但是每次都需要求n+1和n-1中1的个数,复杂度有点高。 其实,我们只需要关注n的最后两个二进制位即可。任何一个数的二进制尾数最后两位可能有四种情况,00、01、10、11,如果n是偶数,即以00或10结尾,则显然n/2能快速的减少一位。但是如果是01或者11呢。如果是01,则减1会变成00,如果加1,会变成10。显然,减1之后多出一个0,而加1之后0的个数没变,所以如果是以01结尾,则减1更优。 如果末尾是11,则减1变成10,加1变成100,显然加1更优。 有一个例外是,如果n就等于3,即二进制为11,则11→10→1比11→100→10→1更优,即当n==3时,减1更好。 完整代码如下: [cpp] class Solution { public: int integerReplacement(int n) { if (n == INT_MAX)return 32; int ans = 0; while (n > 1) { if ((n & 1) == 0) n >>= 1; else if (n == 3 || ((n >> 1) & 1) == 0)–n; else ++n; ++ans; } return ans; } }; [/cpp] 本代码提交AC,用时3MS。]]>

hihoCoder 1496-寻找最大值

hihoCoder 1496-寻找最大值

#1496 : 寻找最大值

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定N个数A1, A2, A3, … AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大。其中AND是按位与操作。 小Ho当然知道怎么做。现在他想把这个问题交给你。

输入

第一行一个数T,表示数据组数。(1 <= T <= 10) 对于每一组数据: 第一行一个整数N(1<=N<=100,000) 第二行N个整数A1, A2, A3, … AN (0 <= Ai <220)

输出

一个数表示答案
样例输入
2
3
1 2 3
4
1 2 4 5
样例输出
12
80

给定一个数组,要求从中选出两个数a和b(它们的下标不能相同),使得乘积a*b*(a&b)最大。 这题的AC之路还挺有意思的,首先我尝试了$$O(n^2)$$的暴力方法,不出所料的TLE了,不过也得了40分。所以$$O(n^2)$$的方法肯定是不行的,我就想各种O(n)的方法。 首先分析一下a*b*(a&b),有两个部分,a*b和a&b。最优的方案当然是求a*b*(a&b)整体的最大值,但是这需要$$O(n^2)$$。次优的方案是求a*b或者a&b的最大值,然后看看整体a*b*(a&b)会不会也是最大呢。 我先考虑了a&b,因为要使a&b越大,则a和b的高位要有很多一致的’1’,这样,a和b本身也就比较大,进而a*b也就比较大。但还是需要$$O(n^2)$$的时间,只不过循环过程中省略了a*b*(a&b)的计算。提交之后WA了,而且是0分,推断这种解法不可行。 后来尝试了求a*b的最大值,想法也和求a&b的最大值类似。如果a*b越大,则a,b本身也比加大,导致a&b也会比较大吧?求a*b的最大值,就好办多了,当然不能暴力两层循环,要不然又TLE。我们只需一次遍历,找到最大和次大的两个数,则他们的乘积肯定是最大的。这次提交之后,虽然也是WA,但是居然得了80分。 所以我就想,可能真的是a,b越大,则a*b*(a&b)也越大。后来一想可能会遇到a很大,二进制是10000;但是b也很大,而且是只比a小1,二进制是01111,这样虽然a*b很大,但是a&b就是0了。导致整体a*b*(a&b)是0。于是我进一步扩大了范围,记录前3大的元素first,second和third,他们之间有3个组合(first,second)、(first,third)、(second,third),只需在这3个对里面求最大就好了。我当时的想法是,虽然first和second会遇到10000和01111的情况,但是second和third可能会不会了。提交之后,居然真的AC了! 代码如下: [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> #include<vector> #include<climits> #include<cfloat> using namespace std; typedef long long LL; vector<LL> nums(100005, 0); int main() { //freopen("input.txt", "r", stdin); int t, n; scanf("%d", &t); while (t–) { scanf("%d", &n); LL first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN; for (int i = 0; i < n; ++i) { scanf("%d", &nums[i]); if (nums[i] > first) { third = second; second = first; first = nums[i]; } else if (nums[i] > second) { third = second; second = nums[i]; } else if (nums[i] > third) { third = nums[i]; } } LL ans = max(first*second*(first&second), first*third*(first&third)); ans = max(ans, second*third*(second&third)); printf("%lld\n", ans); } return 0; } [/cpp] 本代码提交AC,用时85MS。 后来看前几名AC的代码,好多是先对数组排序,然后从大到小求a*b*(a&b)的最大值,这样最坏复杂度还是$$O(n^2)$$,但是好像也能AC。]]>

LeetCode Maximum XOR of Two Numbers in an Array

LeetCode Maximum XOR of Two Numbers in an Array Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231. Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime? Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

给定一个非空数组,从中任意选两个数进行异或操作,问最大的异或结果是多少。 暴力两层循环肯定是不行的,本题需要一些位运算的技巧,解法参考讨论区。 题目限制数值范围在[0,231),所以异或操作最多需要考虑32位。我们从最高位开始考察,判断每一位在数组中异或之后能否得到1的结果。 假设我们已经知道前i-1位的异或最大值为ans,现在要求前i位的异或最大值。我们先把数组中所有数的前i位结果取出来,放到unordered_set<int> hash中。理想情况下,我们希望第i位的异或结果是1,即假设前i位的异或最大值为tmpmax=ans|(1<<i)。我们需要判断hash中是否有两个数异或能得到tmpmax的结果,如果能,说明前i位的异或最大值确实可以达到tmpmax。 也就是说我们需要从hash中选两个数a和b,判断a^b==tmpmax是否成立。常规方法是对hash两层循环判断,但是这样太慢了。利用异或的性质,我们有:如果a^b==tmpmax,则a=b^tmpmax和b=a^tmpmax。比如下面的例子,只是把^和=换了个位置,结果照样成立。
  • 0^0=0 | 0=0^0
  • 0^1=1 | 0=1^1
  • 1^0=1 | 1=0^1
  • 1^1=0 | 1=1^0
所以,我们只需要遍历hash中的数a,和tmpmax异或,如果异或结果b还在hash中,则说明b==a^tmpmax也在hash中,即a^b==tmpmax也成立。说明前i位的异或最大值确实可以达到tmpmax。 代码如下: [cpp] class Solution { public: int findMaximumXOR(vector<int>& nums) { int ans = 0, mask = 0; for (int i = 31; i >= 0; –i) { mask |= (1 << i); unordered_set<int> hash; for (const auto& num : nums) { hash.insert(num & mask); } int tmpmax = ans | (1 << i); for (const auto& prefix : hash) { if (hash.find(prefix ^ tmpmax) != hash.end()) { ans = tmpmax; break; } } } return ans; } }; [/cpp] 本代码提交AC,用时242MS。]]>

LeetCode Maximum Product of Word Lengths

LeetCode Maximum Product of Word Lengths Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0. Example 1: Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] Return 16 The two words can be "abcw", "xtfn". Example 2: Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"] Return 4 The two words can be "ab", "cd". Example 3: Given ["a", "aa", "aaa", "aaaa"] Return 0 No such pair of words.


给定一个字符串数组,问两个没有共同字母的字符串的长度之积最大是多少,如果不存在这样两个字符串,则返回0。 常规思路是两层循环,判断两个字符串是否有共同字符,没有就把它俩的长度乘起来,更新最大值。 问题的关键就是如果快速的判断两个字符串是否有共同字符,常规思路是把一个字符串Hash,然后对另一个字符串的每个字符,看是否在前一个字符串中出现。快速方法是,因为题目说明字符串中只有小写字母,也就是只有26种情况,所以我们可以对这26个字母编码成一个26长的bit位,用一个int存储足够。这样判断两个字符串是否有共同字符,只需要把两个int相与,等于0表示没有共同字符。 完整代码如下: [cpp] class Solution { public: int maxProduct(vector<string>& words) { int ans = 0; vector<int> mask(words.size(), 0); for (int i = 0; i < words.size(); ++i) { for (int j = 0; j < words[i].size(); ++j) { mask[i] |= 1 << (words[i][j] – ‘a’); } for (int k = 0; k < i; ++k) { if ((mask[i] & mask[k]) == 0) // 注意 == 的优先级高于 & ans = max(ans, int(words[i].size()*words[k].size())); } } return ans; } }; [/cpp] 本代码提交AC,用时69MS。]]>

LeetCode Bitwise AND of Numbers Range

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.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

求把从m~n的所有整数相与的结果。
暴力方法就是从m到n遍历一遍,把所有数都相与一下。但是TLE。
这题明显是个数学题或者找规律题。网上的解法大多数是这样的,把m~n的所有数相与的结果等于m和n这两个数的二进制的最长公共前缀。比如题目中的[5,7],5和7的二进制分别为101和111,最长公共前缀就是100=4,后两位不一样也要补0。再比如[26,30],26和30的二进制分别为11010和11110,最长公共前缀为11000=24。
知道这个规律就好办了,因为m和n都是正数,不断同时把m和n往右移,直到他们相等,最后再把m往左移回去就是最终结果。代码如下:

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

本代码提交AC,用时69MS。

二刷。看下面的图,m和n最长公共前缀后面的二进制位,在[m,n]范围内都在不停的变化,也就是有0也有1,所以全与之后肯定都是0,只有公共前缀的1相与不会变0,所以要找公共前缀。

LeetCode Repeated DNA Sequences

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

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

题意:给定一个DNA序列,问有哪些长度为10的子串出现过至少两次。 解法:遍历字符串,用Hash表记录所有长度为10的子串的出现频率,如果频率等于2,则把该子串加入到结果数组中。时间复杂度为O(n),空间复杂度为Hash表占用的空间。 完整代码如下:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s)
    {
        vector<string> ans;
        unordered_map<string, int> hash;
        for (size_t i = 0; i + 10 <= s.size(); ++i) {
            string seq = s.substr(i, 10);
            ++hash[seq];
            if (hash[seq] == 2)
                ans.push_back(seq);
        }
        return ans;
    }
};

本代码提交AC,用时73MS。
优化思路:
因为碱基只有4个:A,T,G,C,所以可以用两个bit表示所有碱基,子串的长度为10,所以可以用20bits表示一个子串,也就是用一个int就可以表示一个子串了。所以我们在将长度为10的子串插入Hash表时,可以先将其编码成一个int。这样Hash表的key就变成一个int了,Hash存储空间应该会更小,而且int也更利于Hash的查找。
完整代码如下:

class Solution {
private:
    unsigned int encode(const string& s)
    {
        unsigned int code = 0;
        for (size_t i = 0; i < s.size(); ++i) {
            code <<= 2;
            switch (s[i]) {
            case ‘A’:
                code += 0;
                break;
            case ‘T’:
                code += 1;
                break;
            case ‘C’:
                code += 2;
                break;
            case ‘G’:
                code += 3;
                break;
            }
        }
        return code;
    }
public:
    vector<string> findRepeatedDnaSequences(string s)
    {
        vector<string> ans;
        unordered_map<unsigned int, int> hash;
        for (size_t i = 0; i + 10 <= s.size(); ++i) {
            string seq = s.substr(i, 10);
            unsigned int code = encode(seq);
            ++hash[code];
            if (hash[code] == 2)
                ans.push_back(seq);
        }
        return ans;
    }
};

本代码提交AC,用时59MS,快了一点。

LeetCode UTF-8 Validation

LeetCode UTF-8 Validation A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

  1. For 1-byte character, the first bit is a 0, followed by its unicode code.
  2. For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:
   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Given an array of integers representing the data, return whether it is a valid utf-8 encoding. Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data. Example 1:
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

给定一个数组,问这个数组是否能表示正确的UTF8字符。UTF8格式在题目中有详细的说明,字节数为1-4个字节,1字节的UTF8第一个bit为0,n字节的UTF8,前n-bits为1,后面跟一个0bit,后面n-1字节前两个bit为10。 解法为我们依次取出字节的前1,3,4,5bits,看是否是1-4字节的UTF8,检查完第一个字节后,根据字节数检查后面的n-1字节。 注意UTF8字节数只可能是1-4,如果发现第一个字节的前5个及以上的bit都是1,直接返回false。代码如下: [cpp] class Solution { public: bool validUtf8(vector<int>& data) { vector<int> mask1 = { 0x80,0xe0,0xf0,0xf8 }; vector<int> first = { 0x0,0xc0,0xe0,0xf0 }; int mask2 = 0xc0, second = 0x80; int i = 0, j = 0; while (i < data.size()) { for (j = 0; j < 4; ++j) { if ((data[i] & mask1[j]) == first[j]) { while (j–) { if (++i >= data.size())return false; if ((data[i] & mask2) != second)return false; } break; } } if (j >= 4)return false; ++i; } return true; } }; [/cpp] 注意位运算的优先级小于判等运算,所以一定记得加括号,要不然WA。。。 本代码提交AC,用时16MS。]]>

LeetCode Gray Code

89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

格雷码是这样一种编码:第一个数为0,后面每个数和前一个数在二进制位上只相差一位。现在给定二进制编码为n位,要求输出一串格雷码。
在不了解格雷码的情况下,可以单纯根据上面格雷码的定义来列出这一串格雷码,我们需要尝试依次翻转n位中的每一位,如果翻转之后得到的编码之前没有出现过,则翻转成功,接着进入下一次尝试,直到产生所有格雷码。
假设一个二进制数为x,则翻转其第i位之后的二进制数为(x&(~(1 << i))) | (~x)&(1 << i),还是有点复杂的。
这种思路可以用递归的方法实现,完整代码如下:

class Solution {
public:
    void work(vector<int>& ans, unordered_set<int>& codes, int gray, int n)
    {
        for (int i = 0; i < n; ++i) {
            int new_gray = (gray & (~(1 << i))) | (~gray) & (1 << i); // flip i-th bit
            if (codes.find(new_gray) == codes.end()) {
                codes.insert(new_gray);
                ans.push_back(new_gray);
                work(ans, codes, new_gray, n);
                break;
            }
        }
    }
    vector<int> grayCode(int n)
    {
        vector<int> ans = { 0 };
        if (n == 0)
            return ans;
        unordered_set<int> codes = { 0 };
        work(ans, codes, 0, n);
        return ans;
    }
};


本代码提交AC,用时6MS。
查看格雷码的维基百科,有好多种方法都可以生成格雷码序列,其中一种很有意思,可以根据二进制长度为n-1的格雷码序列生成二进制长度为n的格雷码序列,如下图所示,这种方法叫做镜射排列。

仔细观察会发现,n长的格雷码序列的前一半序列和n-1长的格雷码序列,在十进制数上是完全一样的,二进制数上也只是多了一个前导零;而后半序列是n-1长的格雷码序列镜面对称之后,加上一位前导1得到的。所以很容易可以写出镜射排列的代码:

class Solution {
public:
    vector<int> grayCode(int n)
    {
        vector<int> ans = { 0 };
        if (n == 0)
            return ans;
        ans.push_back(1);
        for (int i = 2; i <= n; ++i) {
            int sz = ans.size();
            while (sz–) {
                ans.push_back(ans[sz] | (1 << (i – 1)));
            }
        }
        return ans;
    }
};

本代码提交AC,用时3MS。