【每日算法Day 48】位操作
今天来看一些不太多见的位操作有关的问题。例如异或，人们利用异或的运算特性，在重复数据中去除冗余信息，实现信息增量和数据压缩。（HashMap底层的hash方法就是将hashCode无符号右移16位再和原数做异或，将高16位的信息渗透到低16位中，减少hash碰撞，因为只有低16位参与后面摸桶数的运算）又譬如，使用按位或可以填充掩码，使用按位与可以比较掩码（还记得全排列那题吗）。
# LeetCode 389. 找不同 (opens new window)
# 题目描述
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
# 示例
输入：
s = "abcd"
t = "abcde"
输出：
e
解释：
'e' 是那个被添加的字母。
2
3
4
5
6
7
8
9
# 解题思路
常规的思路可能是使用长度为26的数组或哈希表来统计每个字符出现的次数，然后再进行比较。
不过这里可以考虑使用异或的性质：两个相同元素异或之后的值是0，0和x(任何数)异或等于x，还有一点非常重要：就是不管两个相同的数是在什么时候异或的，最终的结果都会存在0。例如有6个数字：2 3 4 4 3 2， 不管是2^3^4^4^3^2 还是我们经过处理之后组合起来 (2^2)^(3^3)^(4^4)结果都是一样的，不会影响结果。
本题两个字符串中的字符，s和t中相同的字符都存在两份，将他们全部异或之后肯定为0，多出来的那个字符x再异或0就成了0^x=x，这样就得到了结果。
public char findTheDifference(String s, String t) {
char res=0;
for (char c : s.toCharArray()) {
res ^= c;
}
for (char c : t.toCharArray()) {
res ^= c;
}
return res;
}
2
3
4
5
6
7
8
9
10
还看到有人把两个字符串中的所有字符各自相加（强制转整形），相减再转回char类型的，好吧……不过这样做的前提是知道这两部分只有目标字符串是多出来的其他的相同。例如下面这题就没有这种方法了。
# LeetCode 136. 只出现一次的数字 (opens new window)
# 题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
# 示例
输入: [4,1,2,1,2]
输出: 4
2
# 解题思路
同上，使用异或来消除两个相同的数的信息。
public int singleNumber(int[] nums) {
int result=0;
for(int i:nums){
result ^= i;
}
return result;
}
2
3
4
5
6
7
# LeetCode 318. 最大单词长度乘积 (opens new window)
# 题目描述
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
# 示例
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。
2
3
4
5
6
7
# 解题思路
拿到这一题开始想到的可能是两两比较字符串，如果他们的长度乘积大于已知的最大乘积并且经比较它们不含有公共的字母的话就更新这个长度的乘积。假设一共有N个单词，外层这个两两比较的时间复杂度为O(n^2)。
public int maxProduct(String[] words) {
if (words==null||words.length<2) return 0;
int n = words.length;
int maxProduct=0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int product = words[i].length() * words[j].length();
if (product > maxProduct && !containsSameChar(words[i], words[j])) {
maxProduct = product;
}
}
}
return maxProduct;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
现在我们来看内部的containsSameChar(words[i], words[j])这个方法应该怎么写。如果两两比较字符的话时间复杂度为O(L1*L2)，这样内外的总时间复杂度就非常大了，应该寻找更快的方法。我们要快速明确一个单词包含哪些字符可以使用一个26位的掩码，掩码对应位为1表示存在该字符，为0表示不存在。可以通过预处理把计算掩码的过程放在循环外面，并保存掩码。
//你也可以写成一个方法
class Solution {
int[] masks;
public int maxProduct(String[] words) {
if (words==null||words.length<2) return 0;
int n = words.length;
//预处理，计算每个单词的掩码
masks=new int[n];
for (int i = 0; i < n; i++) {
int mask=0;
for (char c : words[i].toCharArray()) {
mask |= (1 << (c - 'a'));
}
masks[i] = mask;
}
//计算不含有重复字符的单词的最大长度乘积
int maxProduct=0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int product = words[i].length() * words[j].length();
if (product > maxProduct && !containsSameChar(i,j)){
maxProduct = product;
}
}
}
return maxProduct;
}
private boolean containsSameChar(int i,int j) {
return (masks[i] & masks[j]) != 0;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
设一共有N个单词，所有单词的字符总长度为L，则该方法的时间复杂度为O(L)+O(N^2)，空间复杂度为O(N)。