资讯专栏INFORMATION COLUMN

记录一道使用位操作符的字符串比较算法

QiuyueZhong / 1343人阅读

摘要:是按位或二进制编码中,每一位两者其中一个为,则为,否则,则为,因此就是对每一个字符合并,例如是,是,也是,是,是。

原题目:
给定一个字符串数组,找到长度的最大值length(word[i]) * length(word[j]),其中两个单词中的字母无相同。您可以假定每个单词只包含小写字母。如果没有这两个词,返回0。

例:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".

解析:
这题肯定要进行交叉对比(2个for循环),但最关键的就是对比过程,也就是判断2个字符串是否存在相同的字符。

如果使用indexOf或者数组下标记录都会造成时间复杂度大幅提升,看了他人的答案发现使用的是位操作符<<|&,而且是在交叉对比之前进行预处理,交叉对比的时候只需要简单的判断pretreate[i] & pretreate[j]===0便可,

因为使用后效率提升太多,解析并且记录一下。

先解释val |= (1 << (word.charCodeAt(i)-aCode))

word.charCodeAt(i)-aCode这个很好懂,也就是a对应0,b对应1...这里的0,1数字代表的是
二进制1后面的位数。

1<<01<<1是什么呢?

1在二进制中(32位)就是00000000000000000000000000000001<<是左移1位,

那么1<<0还是11<<1就是(前面的零省略)101<<2就是1001<<3就是1000

于是可知

a就是1

b10

c100...

z10000000000000000000000000(25个0)。

|是按位或:二进制编码中,每一位两者其中一个为1,则为1,否则,则为0,

因此 val |=就是对每一个字符合并,例如

ab00010|00001=>00011

f100000

ffff 也是 100000

big101000010

axdg100000000000000001001001

&,按位与,二进制编码中,每一位两者都为1,则为1,否则,则为0,

例1:axdgoigd要判断是否有重复:

axdg是:100000000000000001001001

oifd是:         100000100101000

& 后:  000000000000000000001000  

因为第4位都为1,所以最后不为0,也可得知重复的就是字母表第4位:d
 
例2:axdglkmk要判断是否有重复:

结果为0,说明无重复。

axdg是:100000000000000001001001

lkmk是:           1110000000000

& 后:  000000000000000000000000  

总结:这种方法使用了二进制数字的位数作为保存字符的手段,相比起数组,散列表等,速度更快,在保存量较小(<=32)优势非常明显。

代码:

/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function(words) {
    let aCode="a".charCodeAt(0)
    function compute(word){
        let val=0
        for(let i=0;imaxSum && (pretreatment[i] & pretreatment[j])===0){
                 maxSum=len1*len2
            }
        }
    }
    return maxSum
};

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/97479.html

相关文章

  • 一道有意思面试算法

    摘要:解决方案异或操作异或运算是对于二进制数字而言的,比如说一个有两个二进制,如果两个值不相同,则异或结果为。比如说,本质上其实是和的每一对比特位执行异或操作,等价于下面数字对应的二进制数字对应的二进制数字对应的二进制因此的结果就为啦。 新年第一篇文章,先祝大家新年快乐!!那么接下来进入正文。 前言 前阵子突发奇想,突然开始刷leetcode。其中刷到了一道有意思的题目,发现这道题是当时秋招...

    maxmin 评论0 收藏0
  • 算法技巧】运算装逼指南

    摘要:位算法的效率有多快我就不说,不信你可以去用亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去运用位运算这些技巧,当然,采用位运算,也是可以装逼的,不信,你往下看。位算法的效率有多快我就不说,不信你可以去用 10 亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去运用位运算这...

    _ang 评论0 收藏0
  • 一道看似简单面试题

    摘要:二进制本身就是为这个数字而使用的,所以说这道面试题直指二进制的使用是没错的。正负在二进制中,第一位为的是负数,是正数。 showImg(https://segmentfault.com/img/bVbd7d0?w=1580&h=732); 前言 使用PHP,给定一个数,判断这个数是否是二的N次方 这样看似简单的一个面试题, 实际牵出了很多基础知识,本章在为大家补习基础知识的情况下来解答...

    kid143 评论0 收藏0
  • 由三道 LeetCode 题目简单了解一下运算

    摘要:使用位运算数组只出现一次数字的数组得到最低的有效位,即两个数不同的那一位看完上面的解法,我脑海中只有问号的存在,啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另,负数按补码形式参加按位与运算。你可做过这几道题? 在面试的准备过程中,刷算法题算是必修课,当然我也不例外。某天,我刷到了一道神奇的题目: # 136. 只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外...

    daydream 评论0 收藏0
  • 由三道 LeetCode 题目简单了解一下运算

    摘要:简单介绍一下位运算异或运算异或逻辑的关系是当不同时,输出当相同时,输出。另,负数按补码形式参加按位与运算。使一个数的最低位为零,可以表示为。,截止到这儿,三道题目中使用的位运算介绍完毕,那么这里我们插入一下的详细题解。你可做过这几道题? 在面试的准备过程中,刷算法题算是必修课,当然我也不例外。某天,我刷到了一道神奇的题目: # 136. 只出现一次的数字 给定一个非空整数数组,除了某个元素只...

    刘明 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<