我正在為以下問題尋找偽代碼或 java 或 js 的解決方案：我們需要實現(xiàn)一個有效的位結(jié)構(gòu)來保存 N 位的數(shù)據(jù)（您也可以將這些位視為布爾值，開/關(guān)）。我們需要支持以下方法： init(n) get(index) set(index, True/False) setAll(True/false)現(xiàn)在我得到了一個包含 o(1) 的解決方案，除了 init 是 o(n)。這個想法是創(chuàng)建一個數(shù)組，其中每個索引都保存一點值。為了支持 setAll，我還將使用位 vapue 保存時間戳，以了解是從 tge 數(shù)組中獲取值還是從 tge 最后一個 setAll 值中獲取值。init 中的 o(n) 是因為我們需要遍歷數(shù)組來將它清零，否則它會產(chǎn)生垃圾，可以是任何東西。現(xiàn)在我被要求找到一個 init 也是 o(1) 的解決方案（我們可以創(chuàng)建一個數(shù)組，但我們不能清除垃圾，垃圾甚至可能看起來像有效的數(shù)據(jù)，這是錯誤的并使解決方案變得糟糕，我們需要100% 有效的解決方案）。更新：這是一個算法問題，而不是特定于語言的問題。我在面試問題中遇到過。由于內(nèi)存限制，使用整數(shù)來表示位數(shù)組也不夠好。我被告知它與對數(shù)組中的垃圾數(shù)據(jù)進(jìn)行某種智能處理有關(guān)，而無需在 init 中對其進(jìn)行處理，使用某種機制不落下，因為如果數(shù)組中的垃圾數(shù)據(jù)（但我不是確定如何）。
2 回答
慕田峪4524236
TA貢獻(xiàn)1875條經(jīng)驗 獲得超5個贊
使用 32 位值（8、16、64 個整數(shù)也適用）作為存儲和輔助字段，基于 hashmap制作惰性數(shù)據(jù)結(jié)構(gòu)（而 hashmap 有時可能比 o(1) 的訪問時間更短）InitFlag
要清除所有內(nèi)容，請制作空地圖InitFlag = 0 （刪除舊地圖是 GC 在 Java 中的工作，不是嗎？）
要設(shè)置所有，請制作空地圖 InitFlag = 1
更改某個位時，檢查是否bitnum/32存在對應(yīng)的 int 鍵。如果是，只需更改bitnum&32位，如果不是，則位值不同于InitFlag- 創(chuàng)建具有基于InitFlag（全零或全一）的值的鍵并更改所需的位。
在檢索某個位時，檢查是否存在對應(yīng)的密鑰。如果是，則提取位，如果不是 - 獲取InitFlag值
SetAll(0): ifl = 0, map - {}
SetBit(35): ifl = 0, map - {1 : 0x10}
SetBit(32): ifl = 0, map - {1 : 0x12}
ClearBit(32): ifl = 0, map - {1 : 0x10}
ClearBit(1): do nothing, ifl = 0, map - {1 : 0x10}
GetBit(1): key=0 doesn't exist, return ifl=0
GetBit(35): key=1 exists, return map[1]>>3 =1
SetAll(1): ifl = 1, map = {}
SetBit(35): do nothing
ClearBit(35): ifl = 1, map - {1 : 0xFFFFFFF7 = 0b...11110111}
and so on
一只萌萌小番薯
TA貢獻(xiàn)1795條經(jīng)驗 獲得超7個贊
如果這是大學(xué)/高中計算機科學(xué)測試或家庭作業(yè)問題 - 我懷疑他們試圖讓您使用BOOLEAN BIT-WISE LOGIC - 具體來說，將位保存在 int 或 long 中。我懷疑（但我不是讀心者——我可能是錯的?。┦褂谩皵?shù)組”正是你的老師希望你避免的。
例如 - 這句話是從谷歌的搜索結(jié)果中復(fù)制的：
長：將長的數(shù)據(jù)類型是一個64位的二的補碼整數(shù)。有符號 long 的最小值為 -263，最大值為 263-1。在 Java SE 8 及更高版本中，您可以使用 long 數(shù)據(jù)類型來表示無符號的 64 位 long，其最小值為 0，最大值為 264-1
這意味著 Java 中的單個 long 變量可以存儲 64 個按位值：
long storage;
// To get the first bit-value, use logical-or ('|') and get the bit.
boolean result1 = (boolean) storage | 0b00000001; // Gets the first bit in 'storage'
boolean result2 = (boolean) storage | 0b00000010; // Gets the second
boolean result3 = (boolean) storage | 0b00000100; // Gets the third
...
boolean result8 = (boolean) storage | 0b10000000; // Gets the eighth result.
我可以為您編寫整個內(nèi)容，但我不能 100% 確定您的實際規(guī)格 - 如果您使用 long，則只能存儲 64 個單獨的二進(jìn)制值。如果您想要任意數(shù)量的值，則必須根據(jù)需要使用盡可能多的“長”。
這是關(guān)于二進(jìn)制/布爾值的 SO 帖子： Java 中的二進(jìn)制表示
這是一篇關(guān)于位移位的 SO 帖子： Java - Circular shift using bitwise operations
同樣，這將是一份工作，我不會編寫整個項目。但是，get(int index)和set(int index, boolean val)方法將涉及數(shù)字 1 的逐位移位。
int pos = 1;
pos = pos << 5; // This would function as a 'pointer' to the fifth element of the binary number list.
storage | pos; // This retrieves the value stored as position 5.
添加回答
舉報
0/150
提交
取消