Допълнително упражнение за контролно 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 който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.