Днешният алгоритъм на 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), тъй като данните са постоянни и не използваме никакви масиви за съхранение.