逻辑运算（位运算）

LeetCode日志 位操作 位运算

题目：

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.

1.思路

（明显思路来自网上）

这里用位操作来处理极为简便。26个不同的英文字符。我用int类型的二进制来求同存异。

上次遇到的这样的处理还是在分析一个数的二进制数中1的个数，当时是与一个全为1的数与。

分步解决，先来解决怎么把一个字符串预处理为我们后面比较方便使用的形式：

public int preSolve(String string){
    int n=0;
    for(int i=0;i<string.length();i++){
        n|=1<<(string.charAt(i)-'a');
    }
    return n;
}

2.简单回顾位运算(逻辑运算）

位运算符主要针对二进制，它包括了：“与”、“非”、“或”、“异或”。从表面上看似乎有点像逻辑运算符，但逻辑运算符是针对两个关系运算符来进行逻辑运算，而位运算符主要针对两个二进制数的位进行逻辑运算。下面详细介绍每个位运算符。

1.与运算符

一般也叫做逻辑与运算，与运算符用符号“&”表示，其使用规律如下：
两个操作数中位都为1，结果才为1，否则结果为0

与运算经常用于求解某一个数的二进制1的个数。
比如对于正整数10。我们的做法是用1左移32位的形式，每左移一次就与10做一个与运算，结果为0表示该为不为1，

2.或运算符

2．或运算符
或运算符用符号“|”表示，其运算规律如下：
两个位只要有一个为1，那么结果就是1，否则就为0

或运算经常用来求某个整数的二进制0的个数。

3.非运算符

非运算符用符号“~”表示，其运算规律如下：
如果位为0，结果是1，如果位为1，结果是0

4.异或运算符

异或运算符是用符号“^”表示的，其运算规律是：
两个操作数的位中，相同则结果为0，不同则结果为1

3.题解

不知道为什么把这种做法叫做mask.我也这么叫吧

public int makeProduct(String []words){
    int []mask=new int[words.length];//mask数组元素就是每个字符串预处理后的值
    for(int i=0;i<words.length;i++}{
        for(int j=0;j<words[i].length();j++){
            mask[i]|=1<<(words[i].charAt(j)-'a');//预处理核心语句。之前一直把1<<step看错了，这是把1往左移step位
        }
    }
    int max=0;
    for(int i=0;i<words.length;i++){
        for(int j=i+1;j<words.length;j++){
        //这两个字符串之间没有出现相同的字符
            if(mask[i]&mask[j]==0){
                if(words[i].length()*words[j].length()>max){
                    max=words[i].length()*words.length();
                }
            }
        }
    }
    return max;
}