Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar02 / README.md
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar02/README.md
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
1 files changed, 0 insertions, 92 deletions
-rw-r--r--Seminar02/README.md92
diff --git a/Seminar02/README.md b/Seminar02/README.md
deleted file mode 100644
index d1779b2..0000000
--- a/Seminar02/README.md
+++ /dev/null
@@ -1,92 +0,0 @@
-# Задачи за стекове 12.10.22
-
-## Задача първа
-Имаме низ състоящ се от английски букви и символа \*. Всеки път когато видим \* трябва да премахнем символът отляво както и самата звезда.
-Пример:
-* aa\* -> "a"
-* erase\*\*\*\*\* -> ""
-* thi\*s i\*s exampl\*e -> "ths s exampe"
-
-Задачата да се реализира за линейно време с линейна памет.
-## Задача втора
-* Вход: Низ състоящ се от отварящи и затварящи скоби.
-* Изход: Дали скобите в този низ са балансирани
-
-Примери:
-* ((())) -> true
-* ))() -> false
-* )( -> false
-* ()()(()) -> true
-
-## Задача трета
-Обратен полски запис наричаме запис, в който операторите "следват" (са след) числата. Примерно изразът 3 + 4 в обратна полска нотация е 3 4 +. Или изразът 1−2+3 би изглеждал 1 2 −3+. Обикновено първо са дадени числата а след това операциите които извършваме върху тях.
-
-А как би изглеждал израза 1−(2+3). Тук първо трябва да извършим събирането и след това изваждането. Тоест израза се записва като 123+−. Предимството от тази нотация е, че нямаме нужда от скоби, което ускорява сметките. Нашата задача е да напишем функция, която приема валиден стринг в обратна полска нотация и връща пресметнатия резултат.
-
-
-# Монотонни стекове
-Монотонен стек наричаме стек, чиито елементи са монотонно растящи или намаляващи. Монотонните стекове имат приложения върхо много различни и интересни задачи върху масиви.
-
-```cpp
-void monotonicStackExample(const std::vector<int>& v) {
- // Нека v = {4, 1, 2, 6, 7, 3}
- // В стека можем да пазим стойности или индекси в зависимост от задачата.
- // По името може да познаете какво пазим и какъв е типа на стека.
- std::stack<int> minMonotonicValues;
-
- for(int i = 0; i < v.size(); i++) {
- while(!minMonotonicValues.empty() && minMonotonicValues.top() < v[i]) {
- minMonotonicValues.pop();
- }
- minMonotonicValues.push(v[i]);
- }
-
- /*
- В края на for цикъла при индекс i стека изглежда така:
- (върха на стека е най - десния елемент)
- i = 0 : [4]
- i = 1 : [4, 1]
- i = 2 : [4, 2]
- i = 3 : [6]
- i = 4 : [7]
- i = 5 : [7, 3]
- */
-}
-```
-Какво можем да забележим от този пример? Примерно, вярно е, че при i = k максимума на подмасива [0..k - 1] е на дъното на стека.
-
-## Задача четвърта
-Искаме да създадем статична структура от данни построена върху масив, която за константно време по индекс ни връща стойността на първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
-
-Пример:
-> [1, 4, 3, 8, 12, 7]
-* getMinLeft(0) -> -1 // няма по - голям елемент от 1 в негово ляво
-* getMinLeft(2) -> 4 // 4 е първия елемент по - голям от arr[2] = 3
-* getMinLeft(5) -> 12 // 12 е първия елемент по - голям от arr[5] = 7
-
-## Обяснение на решението:
-От тази задача можем да си направим извода, че точно преди да вкараме елемента в монотонния стек, върха на стека е първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
-
-Защо това е вярно?
-Нека
-
-$$arr = [a_1 \dots a_k \dots a_m \dots a_n]$$
-
-и нека в цикъла i = m. Твърдя, че ако $a_k$ е първото по - голямо число от $a_m$ то ще бъде задължително на върха на стека след приключване на while цикъла.
-
-
-Ако има други числа на върха на стека, то по предположение те са по - малки от $a_m$ и ще бъдат премахнати.
-
-Ами ако $a_k$ не е в стека? Ако то не е в стека то някое по - голямо от него число, намиращо се между $a_k$ и $a_m$, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво.
-
-## Бонус задачи
-1. Да се сортира стек като използвате само един допълнителен стек.
-
-2. Да се направи задачата със скобите, обаче този път функцията ни казва дали е възможно низът да стане балансиран след най - много едно изтриване на скоба.
-
-Пример:
-* )) -> false
-* ()) -> true
-* () -> true
-* (()()() -> true
-* ())) -> false \ No newline at end of file