python - 使用「按位或x和y」求解計數算法

Question

我正在分析Codility計數練習的解決方案（Frog_river_one）。
我所看到的大多數解決方案都是基於循環給定數組的位置和值。我遇到的其中一個解決方案似乎以不同的方式處理這個問題。

我認識到「按位或x和y」在那裏使用，但我不明白解決方案的邏輯。尤其是checker=checker| 1<<(A[x]-1)
請問有人可以解釋一下嗎？

小青蛙想獲得到河的另一邊的問題。青蛙是 目前位於位置0，並希望到達位置X. 葉從樹上落到河面上。給你一個 非零空索引數組A由N個整數組成，代表 落葉。 A [K]表示在時間K，一片葉子落在 處的位置，以分鐘計。目標是找到最早的時間 當青蛙可以跳到河的另一邊。青蛙可以 交叉只有當葉出現在河對岸每個位置從 1至X.

The solution

A= [1,3,1,4,2,3,5,4] 

def solution(X, A): 
    checker=0 
    final_val=pow(2,5)-1 
    for x in range(len(A)): 
     checker=checker| 1<<(A[x]-1) 

     if(checker==final_val): 
      return x 
    return -1 

Answer 1

其實方法solution應稍微更改爲：

def solution(X,A): 
    checker = 0 
    final_val = pow(2,X) - 1 
    for x in range(len(A)): 
     checker = checker | 1 << (A[x] - 1) 

     if(checker == final_val): 
      return x 
    return -1 

A = [1,3,1,4,2,3,5,4] 

print(solution(5,A)) 

這個算法背後的基本思想是確保所有的葉子落在河邊，包括posi通過使用葉子位置的按位運算和二進制表示來生成X。

爲了使這項工作，你定義final_val這等於2^X -1。在X是5,final_val是2^5 - 1 = 31的情況下。然後你遍歷列表A。

這是最有趣的部分。

checker = checker | 1 << (A[x] - 1) 

您初始化checker爲等於0。

然後讓我們分解上面的表達式：

1 << (A[x] - 1)相同2 ^（A [X] - 1）。該操作將二進制1向左移位01​​A [x]`。

然後去|運營商（OR）。在這種情況下，這是某種plus運算符，但它不會添加重複的術語。

讓我們通過給出的例子來說明它是如何工作的。

x = 0: 

1 << A[0] - 1 which is 1 << 1 - 1 
         1 << 0 

無變化。 1保持1.

checker = 0 | 1 

按位|給出1.

所以checker現在1。這意味着有在1位置的葉。

x = 1: 

1 << A[1] - 1 which is 1 << 3 - 1 
         1 << 2 

所以現在1變爲二進制100。這意味着在位置3處有一片葉子。

然後：

checker = 1 | 100 

其實這是001 | 100這給101。

x = 2: 

checker = 101 | 1 << 0 
     = 101 

注意，這裏位置1已經出現，所以它不會改變checker變量。

x = 3: 

checker = 101 | 1 << 3 
     = 101 | 1000 
     = 0101 | 1000 
     = 1101 

現在checker是1101。這意味着在位置4有一片葉子。

x = 4: 

checker = 1101 | 1 << 1 
     = 1101 | 10 
     = 1101 | 0010 
     = 1111 

這意味着在位置2有一片葉子。

x = 5:    

checker = 1111 | 1 << 4 
     = 1111 | 10000 
     = 01111 | 10000 
     = 11111 

這意味着在位置5有一片葉子。

但這是青蛙需要得到的位置。

這就是爲什麼有一個檢查條件，比較checker和final_val每次迭代。

所以我們看到​​等於final_val（31是11111的二進制），算法返回5的位置，其中6。

請注意，如果某些位置沒有出現在5之前，例如而不是2有1，那麼算法將返回-1，因爲青蛙無法到達位置5。