記錄一道使用位操作符的字符串比較算法

QiuyueZhong 發布于2019-08-23 11:47 / 1454人閱讀

摘要：是按位或二進制編碼中，每一位兩者其中一個為，則為，否則，則為，因此就是對每一個字符合并，例如是，是，也是，是，是。

原題目：
給定一個字符串數組，找到長度的最大值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
};

GPU云服務器云服務器字符串加密解密算法16位或者32位字符串比較大小算法字符串比較最快算法字符串相似度比較算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/97479.html

一道有意思的面試算法題

摘要：解決方案異或操作異或運算是對于二進制數字而言的，比如說一個有兩個二進制，如果兩個值不相同，則異或結果為。比如說，本質上其實是和的每一對比特位執行異或操作，等價于下面數字對應的二進制數字對應的二進制數字對應的二進制因此的結果就為啦。新年第一篇文章，先祝大家新年快樂！！那么接下來進入正文。前言前陣子突發奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發現這道題是當時秋招...

maxmin 2019-08-23 14:28 評論0 收藏0
【算法技巧】位運算裝逼指南

摘要：位算法的效率有多快我就不說，不信你可以去用億個數據模擬一下，今天給大家講一講位運算的一些經典例子。不過，最重要的不是看懂了這些例子就好，而是要在以后多去運用位運算這些技巧，當然，采用位運算，也是可以裝逼的，不信，你往下看。位算法的效率有多快我就不說，不信你可以去用 10 億個數據模擬一下，今天給大家講一講位運算的一些經典例子。不過，最重要的不是看懂了這些例子就好，而是要在以后多去運用位運算這...

_ang 2019-05-22 14:28 評論0 收藏0
一道看似簡單的面試題

摘要：二進制本身就是為這個數字而使用的，所以說這道面試題直指二進制的使用是沒錯的。正負在二進制中，第一位為的是負數，是正數。 showImg(https://segmentfault.com/img/bVbd7d0?w=1580&h=732); 前言使用PHP,給定一個數,判斷這個數是否是二的N次方這樣看似簡單的一個面試題, 實際牽出了很多基礎知識,本章在為大家補習基礎知識的情況下來解答...

kid143 2019-07-01 10:21 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

摘要：使用位運算數組只出現一次數字的數組得到最低的有效位，即兩個數不同的那一位看完上面的解法，我腦海中只有問號的存在，啥意思啊下面就讓我們簡單了解一下位運算并解析一下這三道題目。另，負數按補碼形式參加按位與運算。你可做過這幾道題？在面試的準備過程中，刷算法題算是必修課，當然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現一次的數字給定一個非空整數數組，除了某個元素只出現一次以外...

daydream 2019-05-21 11:41 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

摘要：簡單介紹一下位運算異或運算異或邏輯的關系是當不同時，輸出當相同時，輸出。另，負數按補碼形式參加按位與運算。使一個數的最低位為零，可以表示為。，截止到這兒，三道題目中使用的位運算介紹完畢，那么這里我們插入一下的詳細題解。你可做過這幾道題？在面試的準備過程中，刷算法題算是必修課，當然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現一次的數字給定一個非空整數數組，除了某個元素只...

劉明 2019-05-22 14:21 評論0 收藏0