[BOJ-10174]パリンドロン(Python)

10877 ワード
python ps テキストリンク

🤒 質問する


BOJ-10174ファリンドロン

💊 プール1(pop)


ファリンドロン:ファリンドロンは前読み、後ろ読みを指しますが、同じ単語や数字です.
そのため、前後が同じかどうかを順番にチェックすることができます.
前のpop(0)と後ろのpop()が同じかどうかを確認すればいいです.
コアは、文字列が奇数個からなる場合にwhile(case)と同じ方法を使用すると、空のリストにpopが表示され、len(case) > 1にチェックされる.一つだけ残っていれば前後が同じなので、ファリン症候群です.

Dequeを使用する理由

pop(0)の時間的複雑度はO(n)であり、
dequeのpopleft()は,時間的複雑さがO(1)であるためである.
実際には、コミット後にdequeを使用すると、より速く答えられます.
より多くのテストケースがあれば、これより差が大きいので、できるだけdequeを使いましょう.
  • pop(0) 
    • def is_palindrome(case):
    while(len(case) > 1):
        if case.pop(0) is not case.pop():
            return False
        else:
            continue
    return True
  • デックのpopleft()
    • def is_palindrome(case: Deque):
    while(len(case) > 1):
        if case.popleft() is not case.pop():
            return False
        else:
            continue
    return True

    次は完全なソースコードです.

    💊 プール2(ダブルポインタ)


    文字通り、2つのポインタで問題を解決します.
    1.最初は、前のポインタが0番目のインデックスを指し、後のポインタが最後のインデックスを指します.
    2.ドアが前より大きくなったとき、case[front]とcase[back]が一致しなければ、ファリンドロンではないので、Falseに直接反撃します.
    3.一致した場合はfront 1を増やし、back 1を減らす.

    こんな感じで

    ソースコード


    1

    from collections import deque
import collections
from typing import Deque
import sys

def is_palindrome(case: Deque):
    while(len(case) > 1):
        if case.popleft() is not case.pop():
            return False
        else:
            continue
    return True

N = int(input())
for _ in range(N):
    case = collections.deque(sys.stdin.readline().strip().lower())
    if is_palindrome(case):
        print("Yes")
    else:
        print("No")

    2

    import sys

def is_palindrome(case: list):
    front = 0
    back = len(case) - 1

    while(front < back):
        if case[front] is not case[back]:
            return False
        front += 1
        back -= 1
    return True


N = int(input())
for _ in range(N):
    case = sys.stdin.readline().strip().lower()
    if is_palindrome(case):
        print("Yes")
    else:
        print("No")
    開発ログ3週目1日目
    「Protocol Buffer」のPBのgRPCへの応用