Днешният алгоритъм на LeetCode се нарича Plus One, нека разгледаме инструкциите: Ще ни бъде дадено голямо цяло число, което е цяло число със стойност, равна на или по-голяма от 10. Това цяло число ще бъде представено като масив. Така че числото 4568
ще бъде представено така: [4,5,6,8]
. Цифрите са подредени отляво надясно от най-значимата към най-малко значимата и няма да очакваме масив с водещи нули. Предвид всичко това, единствената ни задача е да увеличим голямото цяло число с 1 и да върнем получения масив.
На пръв поглед този проблем може да изглежда много прост. Определено си паднах по простотата на този въпрос. Ето моето първоначално решение:
Много просто решение, което всъщност не прави нищо. Хванах последния индекс на дадения масив, увеличих го с единица и върнах резултата. Твърде лесно, нали? Подозирах, че това не може да е правилният отговор, тъй като е твърде прост. Оказа се, че съм забравил да взема предвид някои крайни случаи.
Какво се случва, ако числото ни завършва на 9? Какво ще кажете, ако номерът ни е само 9? Ако предадем това [1, 1, 9]
в горната функция, няма да преминем тестовете. Грабването на последния индекс на този масив и увеличаването ще ни даде неправилен резултат от [1, 1, 10]
. Трябва да носим единицата, както всички научихме в математиката в началното училище, за да върнем [1, 2, 0]
. За да върнем правилния резултат, когато е дадено произволно число, и особено ако присъства числото 9, ще трябва да преминем през масива и да използваме условно условие. Нека опитаме това:
Тази функция ще върне правилен резултат. Нека да разгледаме как работи:
- Преминаваме през масива отдясно наляво, започвайки с последния индекс.
- След това използваме условно условие, като първоначално проверяваме дали елементът с индекс 9 е по-малък от 9.
- Ако елементът е по-малък от 9, ние просто увеличаваме с 1 и връщаме резултата. Голямо цяло число, представено като
[1, 1, 1]
, ще се увеличи и ще се върне като[1, 1, 2]
, завършвайки нашия цикъл. - Ако елементът с индекс
i
е9
, задаваме елемента на0
и се връщаме в цикъла, за да итерираме отново.[1, 1, 9]
става[1, 1, 0]
за кратък момент, докато цикълът проверява следващия индекс вляво, който е по-малък от9
. Този индекс се увеличава и нашият масив се връща като:[1, 2, 0]
. - Последната част от кода се грижи за последния крайен случай: всеки елемент в масива е числото
9
. Ако даденият масив беше[9, 9, 9]
, for цикълът в крайна сметка щеше да завърши и да ни даде[0, 0, 0]
. За да отчетем това, използваме метода.unshift()
с аргумент1
. Това ще добави числото1
към индекса нула, което ще направи нашия масив[1, 0, 0, 0]
. - След това връщаме нашия масив, като успешно решаваме алгоритъма.
Времевата сложност на този алгоритъм е O(n), където n е равно на броя на елементите в дадения масив, а нашата пространствена сложност е O(1), тъй като данните са постоянни и не използваме никакви масиви за съхранение.