摘要:是按位或二进制编码中,每一位两者其中一个为,则为,否则,则为,因此就是对每一个字符合并,例如是,是,也是,是,是。
原题目:
给定一个字符串数组,找到长度的最大值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<<0,1<<1是什么呢?
1在二进制中(32位)就是00000000000000000000000000000001,<<是左移1位,
那么1<<0还是1,1<<1就是(前面的零省略)10,1<<2就是100,1<<3就是1000,
于是可知
a就是1,
b是10,
c是100...
z是10000000000000000000000000(25个0)。
|是按位或:二进制编码中,每一位两者其中一个为1,则为1,否则,则为0,
因此 val |=就是对每一个字符合并,例如
ab 是 00010|00001=>00011,
f 是 100000,
ffff 也是 100000,
big是 101000010,
axdg是100000000000000001001001。
&,按位与,二进制编码中,每一位两者都为1,则为1,否则,则为0,
例1:axdg和oigd要判断是否有重复:
axdg是:100000000000000001001001 oifd是: 100000100101000 & 后: 000000000000000000001000
因为第4位都为1,所以最后不为0,也可得知重复的就是字母表第4位:d。
例2:axdg和lkmk要判断是否有重复:
结果为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。其中刷到了一道有意思的题目,发现这道题是当时秋招...
摘要:位算法的效率有多快我就不说,不信你可以去用亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去运用位运算这些技巧,当然,采用位运算,也是可以装逼的,不信,你往下看。位算法的效率有多快我就不说,不信你可以去用 10 亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去运用位运算这...
摘要:二进制本身就是为这个数字而使用的,所以说这道面试题直指二进制的使用是没错的。正负在二进制中,第一位为的是负数,是正数。 showImg(https://segmentfault.com/img/bVbd7d0?w=1580&h=732); 前言 使用PHP,给定一个数,判断这个数是否是二的N次方 这样看似简单的一个面试题, 实际牵出了很多基础知识,本章在为大家补习基础知识的情况下来解答...
摘要:使用位运算数组只出现一次数字的数组得到最低的有效位,即两个数不同的那一位看完上面的解法,我脑海中只有问号的存在,啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另,负数按补码形式参加按位与运算。你可做过这几道题? 在面试的准备过程中,刷算法题算是必修课,当然我也不例外。某天,我刷到了一道神奇的题目: # 136. 只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外...
摘要:简单介绍一下位运算异或运算异或逻辑的关系是当不同时,输出当相同时,输出。另,负数按补码形式参加按位与运算。使一个数的最低位为零,可以表示为。,截止到这儿,三道题目中使用的位运算介绍完毕,那么这里我们插入一下的详细题解。你可做过这几道题? 在面试的准备过程中,刷算法题算是必修课,当然我也不例外。某天,我刷到了一道神奇的题目: # 136. 只出现一次的数字 给定一个非空整数数组,除了某个元素只...
阅读 2962·2021-09-22 14:59
阅读 1754·2021-09-22 10:02
阅读 2077·2021-09-04 16:48
阅读 2152·2019-08-30 15:53
阅读 2934·2019-08-30 11:27
阅读 3387·2019-08-29 18:35
阅读 879·2019-08-29 17:07
阅读 2648·2019-08-29 13:27