Lösen der Einführung von AOJ in Algorithmen und Datenstrukturen in Python -Part4-

Einführung

Hallo. Es ist zäh und zäh. Wir werden die Einführung in die Algorithmen und Datenstrukturen von AOJ lösen. Es ist einfach, aufzuzeichnen, was Sie gelernt haben.

Es ist weniger als ein halbes Jahr her, seit ich anfing, mich selbst mit dem Programmieren zu beschäftigen AtCoder ist grün, also bin ich kein starker Mann. Lass uns hart zusammenarbeiten.

Pacho Fasomacho Pasomacho Paso

Inhaltsverzeichnis

Diesmal TEIL 3: Grundlegende Datenstruktur. Ich möchte mein Bestes geben und es bis zum Ende tun.

ALDS1_4_A: Linear Search ALDS1_4_B: Binary Search ALDS1_4_C: Dictionary ALDS1_4_D : Areas on the Cross-Section Diagram

ALDS1_4_A: Linear Search

Überprüfen Sie jedes Element von t Berechnungsbetrag ist 0 (n * q)

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))
ans = 0
for t1 in t:
    if t1 in s:
        ans += 1

print(ans)

ALDS1_4_B: Binary Search Überprüfen Sie jedes Element von t Der Berechnungsbetrag beträgt 0 (n * q) → 0 (10 ** 9), daher ist eine Dichotomie nicht möglich, also 0 (q * ln (n)). Halbierungssuche

def b_search(x, target):
    found = False
    min = 0
    max = len(x)
    mid = (min + max) // 2
    while min <= max:
        if target == x[mid]:
            found = True
            break
        elif target > x[mid]:
            min = mid + 1
        else:
            max = mid - 1
        mid = (min + max) // 2
    if found:
        return True
    else:
        return False


n = int(input())
s = sorted(list(set(map(int,input().split()))))
q = int(input())
t = list(map(int,input().split()))
ans = 0
for i in t:
    if  b_search(s, i):
        ans += 1
print(ans)

ALDS1_4_C: Dictionary

Grundsätzlich mit deque berechnet

n = int(input())
d = {}

for i in range(n):
    demand, str_list = map(str,input().split())
    if demand == "insert":
        d[str_list] = True

    else:
        if str_list in d:
            print("yes")
        else:
            print("no")

ALDS1_3_D : Areas on the Cross-Section Diagram

Dichotomie behoben Erstellen Sie eine Funktion, die mit einem bestimmten Wert gelöscht werden kann Der Rest ist der Ablauf der zweiminütigen Suche

n,k = map(int,input().split())
w = list(int(input())for i  in range(n))
def amount(p):
    e_amount = 0
    track = 1
    for i in w:
        if i > p:
            return False
        elif e_amount + i > p:
            e_amount = i
            track += 1
        else:
            e_amount += i

    if track <= k:
        return True
    else:
        return False


ng = 0
ok = 10**10
while ng + 1 < ok :
    mid = (ok+ng)//2
    if amount(mid) :
        ok = mid
    else:
        ng = mid

print(ok)

abschließend

Ich werde mein Bestes geben