Pythonで制限未満でXORが最大である要素のリストを見つけるプログラム

数値のリストnumsと、各クエリに[x、limit]が含まれるクエリのリストがあるとします。各クエリ[x、limit]について、e≤limitおよびeXORxが最大化されるようなnumsの要素eを見つけるようなリストを見つける必要があります。そのような要素がない場合は、-1を返します。

したがって、入力がnums =[3、5、9] querys =[[4、6]、[2、0]]の場合、最初のクエリと同様に、出力は[3、-1]になります。 numsで2または4を使用できます。 3 ^ 4 =7、5 ^ 4 =3なので、XORが大きくなる3を選択します。 2番目のクエリでは、0以下の数値はないため、-1に設定します。

これを解決するには、次の手順に従います-

• trie：=新しいマップ

• 関数bits（）を定義します。これには私がかかります

• iの32ビットバイナリ表現を返す

• 関数の挿入を定義します。これには私がかかります

• ノード：=トライ

• ビット（i）の各cについて、実行

  • node：=cがノードにない場合は、その中に空のマップを挿入します

• node [2]：=i

• 関数query（）を定義します。これには私がかかります

• ノード：=トライ

• ビット（i）の各cについて、実行

  • rc：=c XOR 1

  • node：=node[rc]存在する場合はnode[c]

• リターンノード[2]

• メインの方法から、次のようにします-

• リストを並べ替えるA

• B：=各クエリインデックスiおよびクエリ値xとlimitの形式（i、x、limit）の要素のリスト。次に、制限に基づいて並べ替えます

• （j、n、ans）：=（0、Aのサイズ、クエリと同じサイズのリスト、-1で埋める）

• 各インデックスiと値xおよびBの制限について、実行します

  • j

    • insert（A [j]）

    • j：=j + 1

  • jがゼロ以外の場合、

    • ans [i]：=query（x）

• ansを返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, A, queries):
      trie = {}
      def bits(i):
         return map(int, bin(i)[2:].zfill(32))
      def insert(i):
         node = trie
         for c in bits(i):
            node = node.setdefault(c, {})
         node[2] = i
      def query(i):
         node = trie
         for c in bits(i):
            rc = c ^ 1
            node = node.get(rc, node.get(c))
         return node[2]
      A.sort()
      B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2])
j, n, ans = 0, len(A), [-1] * len(queries)
      for i, x, limit in B:
         while j < n and A[j] <= limit:
            insert(A[j])
            j += 1
         if j:
            ans[i] = query(x)
      return ans
ob = Solution()
nums = [3, 5, 9]
queries = [
   [4, 6],
   [2, 0]
]
print(ob.solve(nums, queries))

入力

[3, 5, 9], [[4, 6],[2, 0]]

出力

[3, -1]