Basic Data Structures

Loading...

来自 Saint Petersburg State University 的课程

Competitive Programmer's Core Skills

13 个评分

Saint Petersburg State University

Competitive Programmer's Core Skills

13 个评分

During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Rust, Scala. We assume that you already know how to write simplest programs in one of these.

从本节课中

COMMON STRUGGLES 2

We continue considering common struggles arising in competitive programming. We start by learning how to prove that a natural greedy algorithm is correct. We also discuss programming languages: what features are most helpful on competitions, and what are the advantages and pitfalls of several frequently used languages. Finally, we study an essential and easy-to-implement data structure: the segment tree.

Basic Data Structures5:44

Advanced Data Structures and I/O7:51

Comparing Languages4:54

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov

Hi. In competitive programming,

it's crucial not only invent a solution,

but to also implement it.

And that is done in a programming language.

So in this lesson,

we'll identify the most helpful language features,

so we could study them more closely.

We'll also learn specific features and pitfalls of C++,

Java and Python, so you won't be cold.

And you'll see what advantages and

disadvantages different languages have, so you could just follow them.

In this video, we'll start with a common language tools.

To excel in competitive programming,

you should really learn how to operate them in your language.

First, we'll cover standard data structures.

The most basic is an array,

which is a specific size sequence of values.

In an array, we could set or take an element by its index.

That's basically the only thing we could do, but it's quite useful.

And the cool thing is,

addressing element is really fast,

because an array is just a sequence of values memory.

The natural improvement of arrays are dynamic arrays.

They are also called vectors or lists.

With them, you could do all the same as like the usual array,

but you also could change its size.

So it's quite useful when you don't know how many values you need to store beforehand.

And you also could just appoint values one by one at the end of the dynamic array.

However, that's not for free.

A dynamic array takes up about twice as much space as the usual array of the same size.

And the usually array takes about the sum of space of all the elements in an array.

And now the usual structure is a string.

It's in fact just an array of characters in some especific operations implemented for it,

so you don't have to write them yourself.

The most basic operations just move around string parts.

For example, concatenate or sub to strings,

extract a substring from a string,

or find a given substring in a string.

Another kind those which divides these caracters.

The most used tool just splits a string by white spaces,

like a sentence in a list of words.

Another one, strings white spaces from the end of the string.

If they both start query,

it's often useful to convert a number to this one on the presentation.

A string of digits characters, and vice versa,

from a string to obtain an integer,

which is written as a string by digits.

There is also a powerful tool of regular expressions.

You could not just search for a given substring,

but rather search for a much regular pattern.

Although they aren't frequently used on competitions,

but sometimes they help in some hard implementation problems.

Next, there are other structures built on top of arrays.

A bitset is just a sequence of bits.

But if you take an array of Boolean variables,

each variable will take one byte because one Boolean variable takes one byte.

But in a bitset each bit takes exactly one bit,

so that's eight time less memory.

That's because a bitset is in fact an array of integers.

Each consist on several bits,

and all those bits are enumerated as

if those integers where concatenated in a single long line of bits.

And the useful thing is that it not just takes less space,

it could also do operations on the whole bitset faster.

For example, add into bitsets,

or count in once in a one bitset.

Just in about an hour to do that operations with integers.

If arrays do not fit in standard datatypes it's nice to have big integers,

which could help in arbitrary-size.

And in fact they look similar to bitsets,

because a long integers is just a sequence of bits.

There are also arbitrary-precision floating point numbers.

And then, just in fact,

big integers shifted by some power of two.

And problems often arise in the queue structure,

where you put elements to the back and take away elements from the front.

Of course, it could be implemented by arrays,

but it's as good now to have the structure

implemented language to make the code simpler and easier to understand.

If you take away elements and put elements on the front, it could do the stack structure.

It's also useful, for example,

the active function calls from a stack.

And if you allow to put and take elements from both ends it will be a deque,

standing for a double ending queue.

It's more powerful than both stack and queue,

and so in fact, stack and queue

are implemented through deque in languages you're learning.

So, we have covered simple array-like data structures.

In fact, it will be enough for most of the problems.

But there are more complicated ones and we will cover them in the next video.

We will also cover input and output.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取