1日1～4(未解決)

7227 ワード
電話番号リスト プログラマ テキストリンク

まず,
  • を実装するためにコードを記述した.
    • def solution(phone_book):
    answer = True
    for i in range(len(phone_book)-1):
        tmp = phone_book[i]
        for j in range(i+1, len(phone_book)):
            if phone_book[j].startswith(phone_book[i]):
                answer = False
                break
    return answer
  • phone bookループで、現在の要素をtmpに指定します.
    以降のすべての要素について、文字列がtmpで始まるとfor文が終了し、responseはfalseで終了します.
  • まずphone bookの要素数は最大100万個です.ドアが2の場合、106∮106=101210^6*10^6=10^12106∮106=1012です.12勝がおかしい...
    要するに、時間的複雑度が上昇するため、この方法の効率は
    • 低下する.
  • さっき習ったhashを利用して
    • を見てみましょう.
  • は各要素が重複していないと言っています!
  • はまず実現していません...100点じゃないから.もちろん効率は0点!
    • def solution(phone_book):
    phone_book = sorted(phone_book, key = lambda x: len(x))
    tmp = set(phone_book)
    answer = True
    for i in phone_book:
        tmp.remove(i)
        for j in tmp:
            if j.startswith(i):
                answer = False
                break
    return answer
  • の実施は正しい...それでも0
    • の効率があります
  • phone bookを文字列サイズで並べ替え、for文でtmpの「i」以外の集合をループします.接頭辞がfalseの場合、break!
  • j forドアが破られ、iが回転し続け、効率はもちろん...
  • だから切れる瞬間iも切るためにもう一つ切る
  • ですが、今回はまた正確ではありません・・・hash表をうまく利用していなかったせいか….
  • リターンボールの真上では、回転が終わっていなくても、所望の条件に達していなくても、forドアを閉じることはできません.
    def solution(phone_book):
    phone_book = sorted(phone_book, key = lambda x: len(x))
    tmp = set(phone_book)
    answer = True
    for i in phone_book:
        tmp.remove(i)
        for j in tmp:
            if j.startswith(i):
                answer = False
                break
        if not answer:
            break
    return answer
  • ifをもう1つ打って、すべての条件が一致するコードを打ってください.
  • はよく実現されていますが、効率は低いです.phone bookの長さは最大100万に達するので、本当なら最大2回、100万*100万の時間複雑度に100万回の比較+100万回を加えると、非常に複雑度が高くなります.
    そのため、効率を向上させるために、異なる方向を考慮する必要があります.
    • 変数を宣言する際の注意点(スキャン)
    ANSI、MBCSとUNICOD