[pgsペアリング削除]ストレージスペースではなくDelを使用

2940 ワード
python データ構造 コーディングテスト テキストリンク
プログラマペアリングの削除

Array


私たちが最も簡単に使用したlistはarray資料構造を実現したことです.hashテーブル、linklistなどに比べて、要素は自由で、主要タスク(delete、appendなど)コードは簡単です.
ただし,配列の間に要素を追加/削除したり,ある要素を検索したりする際には,最初からO(n)で要素を検索する必要があるため,時間的複雑度が高い.listスライス(list[3:5])を行うと、3回目の移動が行われ、5回目の移動が行われ、切り取られることがあります.もちろん、メモリ全体の追加/削除(+他のすべての値の場所を移動)は、追加/削除よりも簡単です.

符号化されていないデータ構造配列の説明ビデオ
「すべての配列の値を移動する必要があります」
したがって,探索を必要とするin関数もO(n)からなる.これらのため、in functionが必要な場合は、hashテーブル構造を使用できるかどうかをまず考慮する必要があります.この質問には答えにくいわけではありませんが、strとlistの特性と無効な状況を把握してこそ、効率テストに合格することができます.
3 in [9,8,7,3]
3 in {9:True, 8:True, 7:True, 3:True}
# 아래는 3이라는 key로 접근하기 때문에 O(1), 위는 선형탐색이기 때문에 O(n)

Quesion



Solution


PSEUDO
  • i = 0
  • s = '0' + s
  • while i < len(s)-1:
    if s[i] == s[i+1]:
    sを身につける.(中間の2つの値を削除し、残りの値をsに貼り付けます)
    i-=1#さらに1つのスペースに戻る前に、新しく貼った部分を判断します
    continue
  • len(s)が1の場合、1または024579182が返されます.
    異なるグライダー部分を試すためにsをstr->Listに変形しdelを使用してみます.ソリューション1はstr sleing、2はlist、delはsleingの代わりに、3はスタック(余分なメモリを使用)を使用して、時間を迅速に短縮します.pivonacci数列などの問題では,記憶空間を用いて一度計算したf(x)値は再計算とインポートに類似している.
    結局3人とも正解を返しましたが、3,2,1の順で効率的でした.1、2プログラマーの効率テストに合格するのは難しいです.3合格できます.また,自分の実験でも3>2>1の速度が速いことが示された.(実験結果は下部)
    追加メモリ>DEL>Slicingを使用します.
    def solution1(s):
    if len(s) == 1: return 0

    i = 1
    s = '0' + s # 0을 추가해서 s[-1]이 나오는 것을 방지하기 위함
    while i < len(s)-1:
        if s[i] == s[i+1]: # i == 2
            s = s[:i] + s[i+2:]
            i -= 1
            continue
        i += 1
    return 1 if len(s)==1 else 0

def solution2(s):
    if len(s) == 1: return 0
    list_s = [0] + list(s)
    i = 1
    while i < len(list_s)-1:
        if list_s[i] == list_s[i+1]:
            del list_s[i]
            del list_s[i]
            i -= 1
            continue
        i += 1
    return 1 if len(list_s)==1 else 0

def solution3(s):
    if len(s) == 1: return 0
    stack = list()
    for char in s:
        if not stack:
            stack.append(char)
        else:
            if stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)
    return 1 if not stack else 0
    のケースでは、第3の方法がより速い.正確性はすべて合格したが、3回目は効率テストでも唯一合格できた.1,2のコードはO(n^2)に近づき,3はO(n)である.


    github
    • [開発ログ23日目]マイブログ+
    TIL 2|Javascript var、let、const差異