国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Leetcode[421] Maximum XOR of Two Numbers in an Arr

cocopeak / 1511人閱讀

摘要:復(fù)雜度思路利用的性質(zhì),則有,且所以每次從高位開始,到某一位為止,所能獲得的最大的數(shù)。設(shè)置變量用來表示能形成的值,每一次將和其他的相與得到的值加入,表示在當(dāng)前這一位上,數(shù)組里有這么多。

LeetCode[421] Maximum XOR of Two Numbers in an Array

</>復(fù)制代碼

  1. Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
  2. Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
  3. Could you do this in O(n) runtime?
  4. Example:
  5. Input: [3, 10, 5, 25, 2, 8]
  6. Output: 28
  7. Explanation: The maximum result is 5 ^ 25 = 28.
BitSet+HashSet

復(fù)雜度
O(N), O(N)

思路
利用XOR的性質(zhì),a^b = c, 則有 a^c = b,且 b^c = a;
所以每次從高位開始,到某一位為止,所能獲得的最大的數(shù)。設(shè)置變量mask用來表示能形成的值,每一次將mask和其他的num相與得到的值加入set,表示在當(dāng)前這一位上,數(shù)組里有這么多prefix。

假定在某一位上的任意兩數(shù)xor能得到的最大值是tmp,那么他一定滿足a(xor)b = tmp,其中set.contains(a) && set.contains(b). 所以,我們只需要判斷b(xor)tmp的結(jié)果是不是在當(dāng)前這一位下的set內(nèi),就可以知道這個tmp能不能又這個set中的任意兩個數(shù)組成。

代碼

</>復(fù)制代碼

  1. public int findMaximumXOR(int[] nums) {
  2. int max = 0, mask = 0;
  3. // test each bit pose, 判斷能不能構(gòu)成所需要的值;
  4. for(int i = 31; i >= 0; i --) {
  5. // 每次都在之前的基礎(chǔ)上更新mask
  6. mask = mask | (1 << i);
  7. Set set = new HashSet<>();
  8. for(int num : nums) {
  9. // add the number which has the mask as its prefix;
  10. set.add(num & mask);
  11. }
  12. // 假設(shè)當(dāng)前所能達(dá)到的最大值是這個temp值;
  13. int tmp = max | (1 << i);
  14. for(Integer prefix : set) {
  15. if(set.contains(prefix ^ tmp)) {
  16. // 如果能組成就直接break
  17. max = tmp;
  18. break;
  19. }
  20. }
  21. }
  22. return max;
  23. }

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66227.html

相關(guān)文章

  • 【7 kyu】Sum of two lowest positive integers

    摘要:原題目題目有一個不少于四個元素的數(shù)組,計算其中兩個最小值的和。對比我寫的方法比較常規(guī),中采用了的解構(gòu)賦值和箭頭函數(shù) 原題目 Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. No floats or empty ...

    fjcgreat 評論0 收藏0
  • You need to know curry

    Functions are first-class citizen Functions are first-class citizen in JavaScript, as the same as other types(e.g. number, array, object). They can be used as arguments, as well as return value from o...

    BigNerdCoding 評論0 收藏0
  • 【LC總結(jié)】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

    摘要:找符合條件的總數(shù)。雙指針區(qū)間考慮邊界,長度,為空,等。之后的范圍用雙指針和表示。若三個指針的數(shù)字之和為,加入結(jié)果數(shù)組。不要求,所以不用判斷了。同理,頭部兩個指針向后推移,后面建立左右指針夾逼,找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

    awesome23 評論0 收藏0
  • JavaScript30秒, 從入門到放棄之Array(三)

    摘要:否則,直接循環(huán)去拼接該值返回按照指定的方法對數(shù)組元素進行分組歸類。使用創(chuàng)建一個對象,對象的鍵是生成的結(jié)果,值是符合該鍵的所有數(shù)組元素組成的數(shù)組。微信公眾號秒,從入門到放棄之三 原文鏈接:JavaScript30秒, 從入門到放棄之Array(三)水平有限,歡迎批評指正 flattenDepth Flattens an array up to the specified depth....

    FrancisSoung 評論0 收藏0
  • 一次掌握 JavaScript ES5 到 ES8 數(shù)組內(nèi)容

    摘要:可選到該位置前停止讀取數(shù)據(jù),默認(rèn)等于數(shù)組長度。找出第一個符合條件的數(shù)組元素,參數(shù)是一個回調(diào)函數(shù),所有數(shù)組元素依次執(zhí)行該回調(diào)函數(shù),直到找出第一個返回值為的元素,然后返回該元素?;卣{(diào)函數(shù)可以接受三個參數(shù),依次為當(dāng)前的值當(dāng)前的位置和原數(shù)組。 ECMAScript 5.1 中提供的數(shù)組方法 ECMA-262/5.1 規(guī)范 判斷是否是數(shù)組 Array.isArray ( arg ) // fal...

    baiy 評論0 收藏0
  • JavaScript數(shù)組學(xué)習(xí)記錄_11

    摘要:數(shù)組學(xué)習(xí)記錄是的實例屬性。對數(shù)組元素進行排序,并返回當(dāng)前數(shù)組。返回一個由所有數(shù)組元素組合而成的字符串。為數(shù)組中的每個元素執(zhí)行一次回調(diào)函數(shù)。返回一個數(shù)組迭代器對象,該迭代器會包含所有數(shù)組元素的鍵值對。 JavaScript數(shù)組學(xué)習(xí)記錄 Array.length Array.length 是Array的實例屬性。返回或設(shè)置一個數(shù)組中的元素個數(shù)。該值是一個無符號 32-bit 整數(shù),并且總是...

    TalkingData 評論0 收藏0

發(fā)表評論

0條評論

cocopeak

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<