Tag Archives: 位运算

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呀。代码如下:

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

本代码提交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更好。
完整代码如下:

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

本代码提交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了!
代码如下:

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

本代码提交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。
代码如下:

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

本代码提交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表示没有共同字符。
完整代码如下:

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

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

LeetCode Bitwise AND of Numbers Range

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.


求把从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。

LeetCode Repeated DNA Sequences

LeetCode 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"].

题意:给定一个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;
			if (hash == 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。代码如下:

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

注意位运算的优先级小于判等运算,所以一定记得加括号,要不然WA。。。
本代码提交AC,用时16MS。

LeetCode Gray Code

LeetCode 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.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

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

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.


格雷码是这样一种编码:第一个数为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。

LeetCode Convert a Number to Hexadecimal

LeetCode 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.
Note:

  1. All letters in hexadecimal (a-f) must be in lowercase.
  2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
  3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
  4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26
Output:
"1a"

Example 2:

Input:
-1
Output:
"ffffffff"

题意:把一个十进制数转换为十六进制数。如果是负数,则用补码的二进制转换为十六进制。简单题,因为计算机内存存储的就是补码,所以我们只需要取出每4bit,转换为十六进制就好。4bit对应的十六进制字符,可以提前用一个字典(或数组)存储好。
完整代码如下:

class Solution {
public:
	string toHex(int num) {
		if (num == 0)return "0";
		vector<string> dict = { "0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f" };
		int mask = 0xf;
		string ans = "";
		for (int i = 0; i < 8; ++i) {
			if (num == 0)break;
			ans = dict[num&mask] + ans;
			num >>= 4;
		}
		return ans;
	}
};

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

LeetCode Total Hamming Distance

LeetCode Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:

Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

  1. Elements of the given array are in the range of 0 to 10^9
  2. Length of the array will not exceed 10^4.

本题要求数组中所有数两两之间的汉明距离之和,最笨的方法就是两层循环,然后调用LeetCode Hamming Distance的方法计算每两个数之间的汉明距离。
网上还有一种更巧妙的方法,仔细观察下面三个数的二进制表示,我们可以位的角度计算所有汉明距离,而不是每次针对两个完整的数。比如最低位,三个数都是0,则任意两个数之间不会贡献汉明距离;次低位有一个为0,两个为1,要产生汉明距离,必须一个为0,一个为1,也就是(4,14)和(4,2)才能产生次低位的汉明距离,而(14,2)因为都是1没有汉明距离。所以我们可以统计每一位中0和1的个数zero[i]和one[i],在第i位上所有数的两两汉明距离之和为zero[i]*one[i]。所以总的汉明距离就是ans=Σ zero[i]*one[i]。

  • 4:  0100
  • 14:1110
  • 2:  0010

完整代码如下:

class Solution {
public:
	int totalHammingDistance(vector<int>& nums) {
		int bit_len = sizeof(int) * 8;
		vector<int> one(bit_len, 0), zero(bit_len, 0);
		for (int i = 0; i < bit_len; ++i) {
			for (int j = 0; j < nums.size(); ++j) {
				if (nums[j] & 1)++one[i];
				else ++zero[i];
				nums[j] >>= 1;
			}
		}
		int ans = 0;
		for (int i = 0; i < bit_len; ++i) {
			ans += one[i] * zero[i];
		}
		return ans;
	}
};

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