اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:1 341
مشترکین
-124 ساعت
-107 روز
-2330 روز
آرشیو پست ها
1 341
#medium
Задача: 416. Partition Equal Subset Sum
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: nums = [1,5,11,5] Output: true👨💻 Алгоритм: 1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false. 2⃣Используйте динамическое программирование для определения, можно ли найти подмножество с суммой, равной половине от общей суммы элементов. 3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве. 😎 Решение:
func canPartition(_ nums: [Int]) -> Bool {
let sum = nums.reduce(0, +)
if sum % 2 != 0 { return false }
let target = sum / 2
var dp = [Bool](repeating: false, count: target + 1)
dp[0] = true
for num in nums {
for j in stride(from: target, through: num, by: -1) {
dp[j] = dp[j] || dp[j - num]
}
}
return dp[target]
}1 341
Нужен человек, для сбора вопросов из собеседований на должность iOS разработчик.
Что надо делать:
1. Смотреть записи собеседований (список будет дан)
2. Выписывать вопросы, которые задают кандидату
Ставка: 450 руб. / час
Примерная ЗП: 54 000 руб. / месяц (4 часа в день)
Если интересно и можешь уделять работе от 4 часов / день, то отправь сообщение и сразу напиши какие языки программирования знаешь и какие лучше всего?
1 341
#easy
Задача: 415. Add Strings
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: num1 = "11", num2 = "123" Output: "134"👨💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел. 2⃣Пройдите по массиву nums, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число. 😎 Решение:
func thirdMax(_ nums: [Int]) -> Int {
var first: Int? = nil
var second: Int? = nil
var third: Int? = nil
for num in nums {
if num == first || num == second || num == third {
continue
}
if first == nil || num > first! {
third = second
second = first
first = num
} else if second == nil || num > second! {
third = second
second = num
} else if third == nil || num > third! {
third = num
}
}
return third ?? first!
}1 341
#easy
Задача: 414. Third Maximum Number
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: nums = [3,2,1] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел, используя значения None или аналогичные значения. 2⃣Пройдитесь по массиву, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Если третье максимальное число существует, верните его. В противном случае, верните первое максимальное число. 😎 Решение:
func thirdMax(_ nums: [Int]) -> Int {
var first: Int? = nil
var second: Int? = nil
var third: Int? = nil
for num in nums {
if num == first || num == second || num == third {
continue
}
if first == nil || num > first! {
third = second
second = first
first = num
} else if second == nil || num > second! {
third = second
second = num
} else if third == nil || num > third! {
third = num
}
}
return third ?? first!
}1 341
#medium
Задача: 413. Arithmetic Slices
Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.
Пример:
Input: nums = [1,2,3,4] Output: 3👨💻 Алгоритм: 1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов. 2⃣Для каждой пары элементов проверяйте, сохраняется ли разность между последовательными элементами. Если да, увеличивайте длину текущей арифметической последовательности. Если нет, сбрасывайте начальную позицию и начинайте новую последовательность. 3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2). 😎 Решение:
func numberOfArithmeticSlices(_ nums: [Int]) -> Int {
guard nums.count >= 3 else { return 0 }
var count = 0
var currentLength = 0
for i in 2..<nums.count {
if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] {
currentLength += 1
count += currentLength
} else {
currentLength = 0
}
}
return count
}1 341
#easy
Задача: 412. Fizz Buzz
Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.
Пример:
Input: n = 3
Output: ["1","2","Fizz"]func fizzBuzz(_ n: Int) -> [String] {
var answer = [String]()
for i in 1...n {
if i % 3 == 0 && i % 5 == 0 {
answer.append("FizzBuzz")
} else if i % 3 == 0 {
answer.append("Fizz")
} else if i % 5 == 0 {
answer.append("Buzz")
} else {
answer.append(String(i))
}
}
return answer
}1 341
#hard
Задача: 411. Minimum Unique Word Abbreviation
Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):
"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.
Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.
Пример:
Input: target = "apple", dictionary = ["blade"]
Output: "a4"func generateAbbreviations(_ word: String) -> Set<String> {
var result = Set<String>()
generateAbbreviationsHelper(Array(word), "", 0, 0, &result)
return result
}
func generateAbbreviationsHelper(_ word: [Character], _ current: String, _ pos: Int, _ count: Int, _ result: inout Set<String>) {
if pos == word.count {
result.insert(current + (count > 0 ? String(count) : ""))
return
}
generateAbbreviationsHelper(word, current, pos + 1, count + 1, &result)
generateAbbreviationsHelper(word, current + (count > 0 ? String(count) : "") + String(word[pos]), pos + 1, 0, &result)
}
func minAbbreviation(_ target: String, _ dictionary: [String]) -> String {
let targetAbbrs = generateAbbreviations(target)
var dictAbbrs = Set<String>()
for word in dictionary {
dictAbbrs.formUnion(generateAbbreviations(word))
}
let validAbbrs = targetAbbrs.subtracting(dictAbbrs)
return validAbbrs.sorted(by: { $0.count < $1.count }).first!
}1 341
#easy
Задача: 410. Split Array Largest Sum
Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.
Пример:
Input: nums = [7,2,5,10,8], k = 2 Output: 18👨💻 Алгоритм: 1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива. 2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму. 3⃣Если возможно разбить массив для данной средней суммы, уменьшите верхнюю границу. Если нет, увеличьте нижнюю границу. Повторяйте до тех пор, пока границы не сойдутся. 😎 Решение:
func splitArray(_ nums: [Int], _ k: Int) -> Int {
var left = nums.max()!
var right = nums.reduce(0, +)
while left < right {
let mid = (left + right) / 2
if canSplit(nums, k, mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func canSplit(_ nums: [Int], _ k: Int, _ maxSum: Int) -> Bool {
var currentSum = 0
var subarrays = 1
for num in nums {
if currentSum + num > maxSum {
currentSum = num
subarrays += 1
if subarrays > k {
return false
}
} else {
currentSum += num
}
}
return true
}1 341
Все надоело и пропал интерес, чувствуешь себя амебой и хочется только залипать в телефоне. Бывает?
Психолог взрослого человека - канал для айтишников, у которых периодически опускаются руки и отключается мозг, ибо переработки и постоянная тревожность не приводят к другим исходам.
✔️ Как научиться отвлекаться от работы и отдыхать?
✔️ Как совместить кучу рабочих задач и время с семьей?
✔️ Как справиться с прокрастинацией?
✔️ Как не растерять запал, даже если начальник и коллеги 💩 и кажется, что ничего не выходит?
Подписывайтесь на канал @vadimpetrov_psy и научитесь работать без упахивания, выгорания и ущерба для личной жизни!
👨🏻💻 Псс. Заходите в закреп канала - там много полезного: https://t.me/+5NBjd_Euafg1YTYy
1 341
– Помощь с pet-проектом
– Составление roadmap
– Общая консультация
– Проведение код-ревью и mock-собеседования
– Помощь с трудоустройством
Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT.
🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию
1 341
#easy
Задача: 409. Longest Palindrome
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
Input: s = "abccccdd" Output: 7👨💻 Алгоритм: 1⃣Создайте словарь для подсчета количества каждого символа в строке. 2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома. 3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа. 😎 Решение:
func longestPalindrome(_ s: String) -> Int {
var charCount = [Character: Int]()
for char in s {
charCount[char, default: 0] += 1
}
var length = 0
var oddFound = false
for count in charCount.values {
if count % 2 == 0 {
length += count
} else {
length += count - 1
oddFound = true
}
}
return oddFound ? length + 1 : length
}1 341
#easy
Задача: 408. Valid Word Abbreviation
Строку можно сократить, заменив любое количество не смежных, непустых подстрок их длинами. Длины не должны содержать ведущих нулей.
Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми:
"s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре.
Подстрока - это непрерывная непустая последовательность символов в строке.
Пример:
Input: word = "internationalization", abbr = "i12iz4n" Output: true👨💻 Алгоритм: 1⃣Инициализируйте два указателя: один для строки word и один для аббревиатуры abbr. Начните сравнение символов строки и аббревиатуры с начала. 2⃣Если символ аббревиатуры - это цифра, вычислите полное число и переместите указатель строки word на это количество символов. Если символ аббревиатуры - это буква, убедитесь, что он совпадает с текущим символом строки. 3⃣Повторяйте шаг 2, пока оба указателя не достигнут конца строки и аббревиатуры соответственно. Если это так, верните true, иначе false. 😎 Решение:
func validWordAbbreviation(_ word: String, _ abbr: String) -> Bool {
let wordChars = Array(word)
let abbrChars = Array(abbr)
var i = 0, j = 0
while i < wordChars.count && j < abbrChars.count {
if abbrChars[j].isNumber {
if abbrChars[j] == "0" {
return false
}
var num = 0
while j < abbrChars.count && abbrChars[j].isNumber {
num = num * 10 + abbrChars[j].wholeNumberValue!
j += 1
}
i += num
} else {
if wordChars[i] != abbrChars[j] {
return false
}
i += 1
j += 1
}
}
return i == wordChars.count && j == abbrChars.count
}1 341
#Medium
Задача: 486. Predict the Winner
Дан целочисленный массив nums. Два игрока играют в игру с этим массивом: игрок 1 и игрок 2.
Игрок 1 и игрок 2 ходят по очереди, начиная с игрока 1. Оба игрока начинают игру с нулевым счетом. В каждый ход игрок берет одно из чисел с любого конца массива (то есть nums[0] или nums[nums.length - 1]), что уменьшает размер массива на 1. Игрок добавляет выбранное число к своему счету. Игра заканчивается, когда в массиве не останется элементов.
Верните true, если игрок 1 может выиграть игру. Если счета обоих игроков равны, игрок 1 все равно считается победителем, и вы также должны вернуть true. Вы можете считать, что оба игрока играют оптимально.
Пример:
Input: nums = [1,5,2] Output: false Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return👨💻 Алгоритм: 1⃣Определите maxDiff(left, right) как максимальную разницу в счете, которую текущий игрок может достичь. Если left = right, верните nums[left]. 2⃣В противном случае текущий игрок может выбрать nums[left] или nums[right]. Максимальная разница в счете, которую он может получить, равна большему из значений nums[left] - maxDiff(left + 1, right) и nums[right] - maxDiff(left, right - 1). 3⃣Верните true, если maxDiff(0, n - 1) >= 0. Этот вызов сделан с точки зрения первого игрока, и первый игрок является победителем, если у игроков одинаковый счет (разница 0). 😎 Решение:
class Solution {
private func maxDiff(_ nums: [Int], _ left: Int, _ right: Int) -> Int {
if left == right {
return nums[left]
}
let scoreByLeft = nums[left] - maxDiff(nums, left + 1, right)
let scoreByRight = nums[right] - maxDiff(nums, left, right - 1)
return max(scoreByLeft, scoreByRight)
}
func predictTheWinner(_ nums: [Int]) -> Bool {
return maxDiff(nums, 0, nums.count - 1) >= 0
}
}1 341
#Easy
Задача: 485. Max Consecutive Ones
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве.
Пример:
Input: nums = [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.👨💻 Алгоритм: 1⃣Поддерживайте счетчик для подсчета единиц и увеличивайте его на 1 при встрече единицы. 2⃣Когда встречаете ноль, используйте текущий счетчик единиц для нахождения максимального количества последовательных единиц на данный момент, затем сбросьте счетчик единиц на 0. 3⃣В конце верните максимальное значение. 😎 Решение:
class Solution {
func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
var count = 0
var maxCount = 0
for num in nums {
if num == 1 {
count += 1
} else {
maxCount = max(maxCount, count)
count = 0
}
}
return max(maxCount, count)
}
}1 341
#Medium
Задача: 484. Find Permutation
Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:
s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.
Пример:
Input: s = "I" Output: [1,2] Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.👨💻 Алгоритм: 1⃣Инициализация Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки. 2⃣Для каждого числа i Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result. 3⃣Завершение Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку. 😎 Решение:
class Solution {
func findPermutation(_ s: String) -> [Int] {
var res = [Int](repeating: 0, count: s.count + 1)
var stack = [Int]()
var j = 0
for i in 1...s.count {
if s[s.index(s.startIndex, offsetBy: i - 1)] == "I" {
stack.append(i)
while !stack.isEmpty {
res[j] = stack.removeLast()
j += 1
}
} else {
stack.append(i)
}
}
stack.append(s.count + 1)
while !stack.isEmpty {
res[j] = stack.removeLast()
j += 1
}
return res
}
}1 341
#Easy
Задача: 482. License Key Formatting
Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.
Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.
Верните переформатированный лицензионный ключ.
Пример:
Input: s = "5F3Z-2e-9-w", k = 4 Output: "5F3Z-2E9W" Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.👨💻 Алгоритм: 1⃣Инициализация Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата. 2⃣Итерация по входной строке в обратном порядке Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count. 3⃣Завершение Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её. 😎 Решение:
class Solution {
func licenseKeyFormatting(_ s: String, _ k: Int) -> String {
var count = 0
var ans = ""
for char in s.reversed() {
if char != "-" {
ans.append(char.uppercased())
count += 1
if count == k {
ans.append("-")
count = 0
}
}
}
if ans.last == "-" {
ans.removeLast()
}
return String(ans.reversed())
}
}1 341
#Hard
Задача: 480. Sliding Window Median
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000] Explanation: Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6👨💻 Алгоритм: 1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента. 2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна. 3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления. 😎 Решение:
import Foundation
func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
var medians = [Double]()
for i in 0...(nums.count - k) {
var window = Array(nums[i..<(i + k)])
window.sort()
if k % 2 == 1 {
medians.append(Double(window[k / 2]))
} else {
medians.append((Double(window[k / 2 - 1]) + Double(window[k / 2])) / 2.0)
}
}
return medians
}1 341
#Medium
Задача: 478. Generate Random Point in a Circle
Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.
Реализуйте класс Solution:
- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].
Пример:
Input ["Solution", "randPoint", "randPoint", "randPoint"] [[1.0, 0.0, 0.0], [], [], []] Output [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]] Explanation Solution solution = new Solution(1.0, 0.0, 0.0); solution.randPoint(); // return [-0.02493, -0.38077] solution.randPoint(); // return [0.82314, 0.38945] solution.randPoint(); // return [0.36572, 0.17248]👨💻 Алгоритм: 1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R. 2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния. 3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза. 😎 Решение:
import Foundation
class Solution {
var rad: Double
var xc: Double
var yc: Double
init(_ radius: Double, _ x_center: Double, _ y_center: Double) {
rad = radius
xc = x_center
yc = y_center
}
func randPoint() -> [Double] {
let x0 = xc - rad
let y0 = yc - rad
while true {
let xg = x0 + Double.random(in: 0...(rad * 2))
let yg = y0 + Double.random(in: 0...(rad * 2))
if sqrt(pow(xg - xc, 2) + pow(yg - yc, 2)) <= rad {
return [xg, yg]
}
}
}
}1 341
#easy
Задача: 589. N-ary Tree Preorder Traversal
Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).
Пример:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]👨💻 Алгоритм: 1⃣Инициализация Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack. 2⃣Итеративный обход Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack. 3⃣Возврат результата Верните список output как результат. 😎 Решение:
class Node {
var val: Int
var children: [Node]
init(_ val: Int) {
self.val = val
self.children = []
}
init(_ val: Int, _ children: [Node]) {
self.val = val
self.children = children
}
}
class Solution {
func preorder(_ root: Node?) -> [Int] {
guard let root = root else { return [] }
var stack: [Node] = [root]
var output: [Int] = []
while !stack.isEmpty {
let node = stack.removeLast()
output.append(node.val)
for child in node.children.reversed() {
stack.append(child)
}
}
return output
}
}1 341
#easy
Задача: 326. Power of Three
Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.
Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Проверка начального значения Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны. 2⃣Цикл деления на 3 Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3. 3⃣Проверка конечного значения Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false. 😎 Решение:
class Solution {
func isPowerOfThree(_ n: Int) -> Bool {
if n <= 0 {
return false
}
var num = n
while num % 3 == 0 {
num /= 3
}
return num == 1
}
}