Résolution de l'introduction d'AOJ aux algorithmes et aux structures de données en Python -Partie4-

introduction

Bonjour. C'est moelleux et moelleux. Nous résoudrons l'introduction aux algorithmes et aux structures de données d'AOJ. Il est facile de garder une trace de ce que vous avez appris.

Cela fait moins d'un an et demi que j'ai commencé à toucher la programmation moi-même AtCoder est vert, donc je ne suis pas un homme fort. Travaillons dur ensemble.

Pacho Fasomacho Pasomacho Paso

table des matières

Cette fois PART3: Structure de données de base. Je veux faire de mon mieux et le faire jusqu'au bout.

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

Vérifiez chaque élément de t Le montant du calcul est 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 Vérifiez chaque élément de t Le montant du calcul est 0 (n * q) → 0 (10 ** 9), il est donc impossible de faire une dichotomie, donc 0 (q * ln (n)) Recherche de bisection

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

Fondamentalement calculé avec deque

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 fixe Créer une fonction qui peut être effacée avec une certaine valeur Le reste est le déroulement de la recherche de deux minutes

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)

en conclusion

je ferai de mon mieux