1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
# Допълнително упражнение за контролно 1 за специалност информационни системи - 15.11.2024
## Задача първа - https://leetcode.com/problems/remove-nodes-from-linked-list/
Да се напише функция `ListNode* removeNodes(ListNode* node)`, която премахва всеки възел на свързан списък, който има възел с по - голяма стойност вдясно от него, и връща началото на новия списък.
Вход: глава = [5,2,13,3,8]
Изход: [13,8]
## Задача втора
Да се напише функция `node* level_sort(node* root)`, която приема двоично дърво, и връща ново двоично дърво, за което е вярно, че:
* Дървото е пълно - Пълно дърво наричаме дърво, в което всяко ниво (освен евентуално последното) е изцяло запълнено.
* Обхождайки последователно нивата на дървото отляво надясно ще получим елементите на дървото в сортиран вид.
Решението да работи в O(nlog(n)) време и да използва O(n) памет.
## Задача трета
Имаме низ състоящ се от малки латински букви, символа * и символа $. Всеки път, стигайки до символ *, изтриваме най - лявата буква в резултатния низ. Всеки път стигайки до симвой $ добавяме най - лявата буква в резултатния низ.
Да се напише функция `std::string parse(const std::string& str);` която приема низ от този вид и връща низ, който прилага всички символи * и $ върху низа.
Пример:
* abc\*\$\$\*d$a$$zz\* => abbddaaaz
* aaa*** => ""
* aaa$ => aaa
---
---
---
## Задача четвърта
Да се напише функция, която приема сортиран масив, и строи балансирано двоично наредено дърво от него.
## Задача пета
Да се напише функция, която като вход приема масив и връща дърво, в което лявото поддърво на корена съдържа чеслата по - малки от 0, а дясното поддърво тези по - големи от 0. Стойността на корена може да е произволно число от масива.
## Задача шеста
Напишете функция, която получава като аргумент едносвързан списък с елементи цели числа. Функцията трябва да го сортира по следното правило - в началото на списъка трябва да останат четните елементи, подредени в нарастващ ред, след това нечетните елементи, подредени в намаляващ ред.
Бонус: премахнете повтарящите се елементи.
## Задача седма
Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина *k* който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.
|
