320. Generalized Abbreviation
思路和上一题一样，多了个count过程而已。
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> res=new ArrayList<String>();
int size=1<<word.length();
for(int i=0;i<size;i++){
int count=0;
StringBuilder sb=new StringBuilder();
for(int j=0;j<=word.length();j++){
if((i&(1<<j))!=0){
count++;
}
else{
if(count!=0){
sb.append(count);
count=0;
}
if(j<word.length())
sb.append(word.charAt(j));
}
}
res.add(sb.toString());
}
return res;
}
}
136. Single Number
考点是XOR。才发现关于位运算，好多知识盲点啊，主要平常用的太少了，好好补一补知识。
N^N=0。
0^N=N。
N1^N1^N2^N2^....Nn^Nn^Ni=Ni。
也就是一堆数异或，返回的是单独的那个数，对于成双成对的数，异或都是0，由此可见单身的多伤。
解法就很显而易见了。
public class Solution {
public int singleNumber(int[] nums) {
int res=nums[0];
for(int i=1;i<nums.length;i++)
res^=nums[i];
return res;
}
}
137. Single Number II
正常情况下，对于每一位，数组里要么是3个1，要么是3个0，就是说3的倍数的1和3的倍数的0。这样我们对3取余的话，如果还多出了一个1，那么该位上的1就是那个单身数的。以此我们构造出那个单身数。此方法可找k次数里的单身数。
public class Solution {
public int singleNumber(int[] nums) {
int res=0;
for(int i=0;i<32;i++){
int bits=0;
for(int j=0;j<nums.length;j++){
if(((nums[j]>>i)&1)==1){
bits+=1;
bits%=3;
}
}
if(bits!=0)
res|=1<<i;
}
return res;
}
}
260. Single Number III
这次为2个number只出现一次。
先全部异或一次，那么实际上所得就是那2个number异或一次。因为这两个number不相等，我们就取他俩异或出来结果是1的任何一位，比如说i位，他俩在i位上一个为0一个为1。根据i位可以将所有数分为2组，i=1或i=0。这样对于每组都异或一次，得到的即为所求。相当于拆成2个136题。常用操作：(a&(a-1))^a 来取得a中任何一个为1的位，其余位为0。(真tm不好解释)
public class Solution {
public int[] singleNumber(int[] nums) {
int[] res=new int[2];
res[0]=res[1]=0;
int xor=0;
for(int i=0;i<nums.length;i++)
xor^=nums[i];
xor=(xor&(xor-1)^xor);
for(int i=0;i<nums.length;i++){
if((nums[i]&xor)>0)
res[0]^=nums[i];
else res[1]^=nums[i];
}
return res;
}
}
191. Number of 1 Bits
其实原理一开始就想到了，不断的余2再除2，直到等于0。后来一做才发现细节。位运算的话&1来判断是否是odd，就和余2操作一样，然后用非符号移位>>>来实现除2操作。这里注意，>>是符号移位，碰到负数时，会在最前面补1来表示负号，这样的话，当碰到integer.MAX_VALUE时，which is 1000000...0000，进行移位操作，前面的1会当成负号处理，然后一直移0位，就会TLE。所以我们用>>>，无符号移位的话最前面会添0，就没问题了。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res=0;
while(n!=0){
res+=n&1;
n>>=1;
}
return res;
}
}
405. Convert a Number to Hexadecimal
上一题的灵感，对每4位取余，然后移4位。注意取余是least significant bits操作，所以结果要reverse。
public class Solution {
public String toHex(int num) {
char[] map=new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
if(num==0)
return "0";
StringBuilder sb=new StringBuilder();
while(num!=0){
sb.append(map[num&15]);
num>>>=4;
}
return sb.reverse().toString();
}
}
169. Majority Element
通过位运算来构造出那个大数。从LSB开始，一位一位的比较所有数，如果所有数在该位上的1的数目大于0的数目，说明大数在该位上也是1，所以该位上我们就应该构造个1出来。反之，大数在该位就是0，不需要操作。比较完所有位，大数也就出来了。比较的判断还是取余操作&，因为Integer是32bits，所以循环32次位比较。
public class Solution {
public int majorityElement(int[] nums) {
int res=0;
for(int i=0;i<32;i++){
int ones=0, zeros=0;
for(int j=0;j<nums.length;j++){
if((nums[j]&(1<<i))!=0)
ones++;
else zeros++;
}
if(ones>zeros)
res|=(1<<i);
}
return res;
}
}
268. Missing Number
再一次看到了XOR定理的神奇。
对于整个数组，只要把所有数和各自的index异或一遍，就能找出缺失的那个数。因为缺了个数，index会少1，最后记得再异或一个index。
public class Solution {
public int missingNumber(int[] nums) {
int res=0;
for(int i=0;i<nums.length;i++)
res=res^i^nums[i];
return res^nums.length;
}
}
476. Number Complement
因为是补位的数，那么他俩相加，会得到每位都是1的数，因此我们只需要找到最小的大于num的数，一减就行。
诡异的是，求2的立方操作中，不能用2^bits，算出来是0，而必须用Math.pow(2, bits)。原来^操作看成了异或操作。
public class Solution {
public int findComplement(int num) {
int bits=0;
int res=0;
while(res<num){
res+=Math.pow(2, bits);
bits++;
}
return res-num;
}
}
461. Hamming Distance
先异或，然后数1。
public class Solution {
public int hammingDistance(int x, int y) {
int res=0;
int xor=x^y;
for(int i=0;i<32;i++){
res+=(xor>>i)&1;
}
return res;
}
}
477. Total Hamming Distance
brute force就是 O(n^2)。如果我们这么想，对于每一位，要么是0，要么是1，假设这一位上是1的有i个，那么两两异或的话，不就有i*(n-i)个1吗？把所有位异或的加起来，就是所需的结果。
public class Solution {
public int totalHammingDistance(int[] nums) {
int res=0;
for(int i=0;i<32;i++){
int ones=0, zeros=0;
for(int j=0;j<nums.length;j++){
int diff=(nums[j]>>i)&1;
if(diff==1)
ones++;
else zeros++;
}
res+=ones*zeros;
}
return res;
}
}
231. Power of Two
只能有一位是1。所以一位位查。
public class Solution {
public boolean isPowerOfTwo(int n) {
int count=0;
if(n<=0)
return false;
for(int i=0;i<32;i++){
if(((n>>i)&1)!=0)
count++;
if(count>1)
return false;
}
return true;
}
}
另外一个解法就是，只能有一位是1，那么小他的数在1的那位之后全是1，而1的那位是0，也就是说n&n-1==0。
public class Solution {
public boolean isPowerOfTwo(int n) {
return (n>0)&&((n&(n-1))==0);
}
}
389. Find the Difference
又是神奇的异或。将每个都异或起来，就出来了。单身的总是最伤的。
public class Solution {
public char findTheDifference(String s, String t) {
int n=t.length()-1;
char c=t.charAt(n);
for(int i=0;i<n;i++){
c^=s.charAt(i);
c^=t.charAt(i);
}
return c;
}
}
371. Sum of Two Integers
首先&操作获得需要进位的carry，然后^操作获得不为0的位也就是可能需要加carry的位。然后carry左移一位，即为移到要加的位，重复操作。直到carry为0不再需要进位。
public class Solution {
public int getSum(int a, int b) {
if(a==0)
return b;
if(b==0)
return a;
int carry=0;
while(b!=0){
carry=a&b;
a=a^b;
b=carry<<1;
}
return a;
}
}
318. Maximum Product of Word Lengths
因为要不相交的word，所以我们用个map来存每个单词里出现了哪些字母。字母出现几次无所谓，只要出现就可以。这里我们可以通过移位操作来代替hashmap提高速度。map[ i ] |= 1 << ( c - 'a' )，这个用的非常巧，从左到右26位当做26个字母的hash，相应字母出现过就在相应位上填1。
处理过之后，对于每两个字母只需要&他们相应的map就能判断是否相交。
public class Solution {
public int maxProduct(String[] words) {
int res=0;
int[] map=new int[words.length];
for(int i=0;i<words.length;i++){
for(char c:words[i].toCharArray())
map[i]|=1<<(c-'a');
}
for(int i=0;i<words.length;i++){
for(int j=i+1;j<words.length;j++){
if((map[i]&map[j])==0)
res=Math.max(words[i].length()*words[j].length(), res);
}
}
return res;
}
}
201. Bitwise AND of Numbers Rang
因为是&所有区间的数，如果m！=n，那中间必定有一个odd一个even，他俩&的LSB必为0，其他所有数在该位的&操作也一定是0。利用这个性质，我们一直往右移位，找到相同的位即可。当m=n了，所有的位都相等，这时所有位上&都是1，而所有移过的位都是0。
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int bits=1;
while(m!=n){
m>>=1;
n>>=1;
bits<<=1;
}
return m*bits;
}
}
187. Repeated DNA Sequences
位运算的做题思想适合这种固定个数的，固定选项的。在这里因为长度为10，只有4个种类，我们就可以用2位来表示它们，00,01,10,11。然后长度10，只需每次移2位，就能读入新的字母。然后对于不是第一次碰到，我们把它加入到第二次碰到，并加入结果，对于第三次碰到，就属于重复了。
最初的做法是创造4位，A是第一位为1，C是第二位为1，以此类推，然后每次移4位。但是这就需要2^40来表示，就越界了。然后用long的话就会遭遇TLE。很伤。
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> res=new ArrayList<String>();
Set<Integer> first=new HashSet<Integer>();
Set<Integer> repeated=new HashSet<Integer>();
int[] map=new int[26];
map['A'-'A']=0;
map['C'-'A']=1;
map['G'-'A']=2;
map['T'-'A']=3;
for(int i=0;i+9<s.length();i++){
int bits=0;
for(int j=i;j<i+10;j++){
char c=s.charAt(j);
bits<<=2;
bits|=map[c-'A'];
}
if(!first.add(bits)&&repeated.add(bits))
res.add(s.substring(i, i+10));
}
return res;
}
}
338. Counting Bits
先上图。
对于2，4，8，16这种2的次方数，1的数目为1。对于在他们之间的数，可以表示为2^n+x。所以这些数的1的个数为1加上x的1的个数。
public class Solution {
public int[] countBits(int num) {
int[] res=new int[num+1];
res[0]=0;
int bit=1;
int count=0;
for(int i=1;i<=num;i++){
if(i==bit){
res[i]=1;
bit<<=1;
count=1;
}
else {
res[i]=res[count]+1;
count++;
}
}
return res;
}
}
397. Integer Replacement
碰到even肯定除2，关键在于odd的操作，是取n-1还是n+1。不管+1还是-1，影响的最多是后两位。因此我们就从后两位判断。
生成的1越少，所需步数就越少，因此，当n后两位是01时，-1的话就是00，+1的话就是10，当然-1。后两位是11时，当然+1。于是这道题就出来了。另外对于3，只能取-1。
有个corner case是Integer.MAX_VALUE。根据判断，我们会+1，于是就变成负数了，前面也提到过，会无限循环。解决方法是用无符号位移>>>。
public class Solution {
public int integerReplacement(int n) {
int count=0;
while(n!=1){
if((n&1)==0)
n>>>=1;
else {
if(((n>>>1)&1)==0)
n--;
else if(n==3)
n--;
else
n++;
}
count++;
}
return count;
}
}