Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part3-

Introduction

Hello. It's chewy and chewy. We will solve the introduction to AOJ's algorithms and data structures. It's easy to keep a record of what you've learned.

It's been less than half a year since I started programming myself AtCoder is green, so I'm not a strong man. Let's work hard together.

make it possible with Pai-chan

table of contents

This time PART3: Basic data structure. I want to do my best and do it to the end.

ALDS1_3_A: Stack ALDS1_3_B: Queue ALDS1_3_C: Bidirectional linked list ALDS1_3_D : Areas on the Cross-Section Diagram

ALDS1_3_A: Stack

stack~

a = list(map(str,input().split()))
l = []
for i in a:
    if i=="+":
        a1 = l.pop()
        a2 = l.pop()
        a3 = a1+a2
        l.append(a3)

    elif i=="-":
        a1 = l.pop()
        a2 = l.pop()
        a3 = a2-a1
        l.append(a3)

    elif i=="*":
        a1 = l.pop()
        a2 = l.pop()
        a3 = a1*a2
        l.append(a3)

    else:
        l.append(int(i))

print(l[0])

ALDS1_3_B: Queue

Let's use deque

from collections import deque
n,q = map(int,input().split())
l = [list(map(str,input().split())) for _ in range(n)]
time = 0
dq = deque(l)
while dq:
    a,b = dq.popleft()
    if int(b)<= q:
        time += int(b)
        print(a,time)

    else:
        time += q
        b = int(b) - q
        dq.append([a,b])

ALDS1_3_C: Bidirectional linked list

Basically calculated with deque In Python, if you do not do the following two points, it will be TLE ・ It is faster to define input by yourself ・ If you don't need index, for a in d: is faster


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
d = deque([])
for _ in range(n):
    a = list(map(str,input().split()))
    if a[0]=="insert":
        d.appendleft(a[1])


    elif a[0]=="delete":
        if a[1] in d:
            d.remove(a[1])

    elif a[0]=="deleteFirst":
        s = d.popleft()


    elif a[0]=="deleteLast":
        s = d.pop()

print(*d)

ALDS1_3_D : Areas on the Cross-Section Diagram

It hasn't melted yet ... Pien




in conclusion

I will update it when D melts. I will not smoke

Recommended Posts

Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part1-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part2-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part4-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part3-
[Introduction to cx_Oracle] (Part 9) DB and Python data type mapping (version 8 or later)
[Introduction to Udemy Python 3 + Application] 36. How to use In and Not
[Introduction to Data Scientists] Basics of Python ♬ Functions and classes
Introduction to Effectiveness Verification Chapters 4 and 5 are written in Python
Introduction to Python scikit-learn, matplotlib, single-layer algorithm (~ towards B3 ~ part3)
[Introduction to Python] Combine Nikkei 225 and NY Dow csv data
[Introduction to Python3 Day 1] Programming and Python
An introduction to statistical modeling for data analysis (Midorimoto) reading notes (in Python and Stan)
processing to use notMNIST data in Python (and tried to classify it)
[Introduction to Data Scientists] Basics of Python ♬ Conditional branching and loops
[Introduction to Data Scientists] Basics of Python ♬ Functions and anonymous functions, etc.
[Introduction to Python] How to use class in Python?
AM modulation and demodulation in Python Part 2
[Introduction to Python3, Day 17] Chapter 8 Data Destinations (8.1-8.2.5)
Ant book in python: Sec. 2-4, data structures
[Introduction to Python3, Day 17] Chapter 8 Data Destinations (8.3-8.3.6.1)
Web-WF Python Tornado Part 3 (Introduction to Openpyexcel)
[Introduction to Python3 Day 19] Chapter 8 Data Destinations (8.4-8.5)
Easily graph data in shell and Python
How to use is and == in Python
"Introduction to data analysis by Bayesian statistical modeling starting with R and Stan" implemented in Python
Introduction to Vectors: Linear Algebra in Python <1>
Introduction to Effectiveness Verification Chapter 1 in Python
[Introduction to Data Scientists] Basics of Python ♬
[Python] [Supplement] Chapter 04-09 Various data structures (set theory and operations in sets)
[What is an algorithm? Introduction to Search Algorithm] ~ Python ~
How to generate permutations in Python and C ++
Introduction to effectiveness verification Chapter 3 written in Python
Python variables and data types learned in chemoinformatics
Receive and display HTML form data in Python
tse --Introduction to Text Stream Editor in Python
[Python] Swapping rows and columns in Numpy data
[Python] How to read data from CIFAR-10 and CIFAR-100
[Introduction to Python3 Day 22] Chapter 11 Concurrency and Networking (11.1 to 11.3)
Send messages to Skype and Chatwork in Python
[Introduction to Python] How to handle JSON format data
[Introduction to Udemy Python3 + Application] 64. Namespace and Scope
[Introduction to Python3 Day 11] Chapter 6 Objects and Classes (6.1-6.2)
[Introduction to Algorithm] Find the shortest path [Python3]
Introduction to Effectiveness Verification Chapter 2 Written in Python
To represent date, time, time, and seconds in Python
How to plot autocorrelation and partial autocorrelation in python
[Python] How to name table data and output it in csv (to_csv method)
Introduction to Time Series Analysis ~ Seasonal Adjustment Model ~ Implemented in R and Python
[Introduction to Udemy Python3 + Application] 35. Comparison operators and logical operators
Convert timezoned date and time to Unixtime in Python2.7
Summary of tools needed to analyze data in Python
Full-width and half-width processing of CSV data in Python
[Introduction to Reinforcement Learning] part.1-Epsilon-Greedy Algorithm in Bandit Game
[Introduction to element decomposition] Let's arrange time series analysis methods in R and python ♬
Genetic algorithm in python
Reading Note: An Introduction to Data Analysis with Python
Introduction to Python language
Introduction to OpenCV (python)-(2)
I tried to implement GA (genetic algorithm) in Python
[Introduction to Python] Summary of functions and methods that frequently appear in Python [Problem format]
Write tests in Python to profile and check coverage