12

コンテキスト: 私は CS n00b で、「Cracking the Coding Interview」に取り組んでいます。最初の問題は、「文字列に一意の文字がすべて含まれているかどうかを判断するアルゴリズムを実装する」ことです。私の（おそらく素朴な）実装は次のとおりです。

def isUniqueChars2(string):
  uchars = []
  for c in string:
    if c in uchars:
      return False
    else:
      uchars.append(c)
  return True

著者は、次の実装を提案しています。

def isUniqueChars(string):
  checker = 0
  for c in string:
    val = ord(c) - ord('a')
    if (checker & (1 << val) > 0):
      return False
    else:
      checker |= (1 << val)
  return True

著者の実装が私のものよりも優れている理由は何ですか (FWIW、著者のソリューションは Java であり、私はそれを Python に変換しました。私のソリューションは Java で実装することはできません)。または、より一般的に言えば、この問題の解決策として何が望ましいでしょうか? 私が取ったアプローチの何が問題になっていますか？私は、重要であり、この問題に対してどのアプローチをとるかを選択するのに役立ついくつかの基本的な CS 概念 (私がよく知らない) があると想定しています。

4

8 に答える 8

0

あなたの実装は O(n2) かかり、作成者は O(n) かかります。あなたの実装では、「 if c in uchars:」 、この配列に c があるかどうかをチェックするとき、配列全体を通過する必要があり、時間がかかります。つまり、あなたのものは著者のものよりも優れていません...

于 2013-08-06T16:04:30.170 に答える
0

解決策 1:

def is_unique(string):
  if len(string) > 128:
    return False

  unique_tracker = [False] * 128
  for char in string:
    if unique_tracker[ord(char)] == False:
      unique_tracker[ord(char)] = True
    else:
      return False
  return True

解決策 2:

def is_unique_bit(string):
  if len(string) > 128:
  return False

  unique_tracker = 0
  for char in string:
    ascii_val = ord(char)
    if (unique_tracker & (1 << ascii_val)) > 0:
      return False
    unique_tracker |= (1 << ascii_val)
  return True
于 2016-12-18T00:51:33.787 に答える