Swift | LeetCode - задачи

Задача: 1490. Clone N-ary Tree Сложность: medium Дан корень N-арного дерева, верните глубокую копию (клон) дерева. Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей. class Node { public int val; public List children; } Сериализация входных данных 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,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 👨💻 Алгоритм: 1⃣Базовый случай: Проверить, является ли входной узел null. Если да, вернуть null. 2⃣Копирование узла: Создать новый узел с таким же значением, как у входного узла. 3⃣Рекурсивное клонирование детей: Рекурсивно клонировать каждого ребёнка входного узла и добавить клонированных детей в список детей нового узла. Вернуть клонированный узел. 😎 Решение: class Node { public var val: Int public var children: [Node] public init(_ val: Int) { self.val = val self.children = [] } } class Solution { func cloneTree(_ root: Node?) -> Node? { guard let root = root else { return nil } let nodeCopy = Node(root.val) for child in root.children { nodeCopy.children.append(cloneTree(child)!) } return nodeCopy } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 726. Number of Atoms Сложность: hard Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой. Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами. Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число. Пример: Input: formula = "H2O" Output: "H2O" 👨💻 Алгоритм: 1⃣Используйте стек для отслеживания текущего уровня скобок. 2⃣Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее число, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь. 3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат. 😎 Решение: import Foundation func countOfAtoms(_ formula: String) -> String { var stack = [Dictionary]() stack.append(Dictionary()) let formula = Array(formula) var i = 0 let n = formula.count while i < n { if formula[i] == "(" { stack.append(Dictionary()) i += 1 } else if formula[i] == ")" { let top = stack.removeLast() i += 1 var multiplicity = 0 while i < n && formula[i].isNumber { multiplicity = multiplicity * 10 + Int(String(formula[i]))! i += 1 } multiplicity = multiplicity == 0 ? 1 : multiplicity for (name, count) in top { stack[stack.count - 1][name, default: 0] += count * multiplicity } } else { var start = i i += 1 while i < n && formula[i].isLowercase { i += 1 } let name = String(formula[start.. 1 { result += "\(last[key]!)" } } return result } Ставь 👍 и забирай 📚 Базу знаний

Задача: 561. Array Partition Сложность: easy Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму. Пример: Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are: 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4. 👨💻 Алгоритм: 1⃣Отсортируйте массив nums в неубывающем порядке. 2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого). 3⃣Суммируйте выбранные элементы и верните эту сумму. 😎 Решение: class Solution { func arrayPairSum(_ nums: [Int]) -> Int { let sortedNums = nums.sorted() var sum = 0 for i in stride(from: 0, to: sortedNums.count, by: 2) { sum += sortedNums[i] } return sum } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1273. Delete Tree Nodes Сложность: medium Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве. Пример: Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1] Output: 2 👨💻 Алгоритм: 1⃣Постройте дерево из заданных узлов, значений и родителей. 2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю. 3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов. 😎 Решение: class Solution { func deleteTreeNodes(_ nodes: Int, _ parent: [Int], _ value: [Int]) -> Int { var tree = [Int: [Int]]() for i in 0.. (Int, Int) { var totalSum = value[node] var totalCount = 1 if let children = tree[node] { for child in children { let (childSum, childCount) = dfs(child) totalSum += childSum totalCount += childCount } } return totalSum == 0 ? (0, 0) : (totalSum, totalCount) } return dfs(0).1 } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 640. Solve the Equation Сложность: medium Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом. Пример: Input: s = "*" Output: 9 👨💻 Алгоритм: 1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='. 2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений. 3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'. 😎 Решение: class Solution { func solveEquation(_ equation: String) -> String { func parse(_ s: String) -> (Int, Int) { var coeff = 0 var constPart = 0 var sign = 1 var num = 0 var i = s.startIndex while i < s.endIndex { if s[i] == "+" { sign = 1 i = s.index(after: i) } else if s[i] == "-" { sign = -1 i = s.index(after: i) } else if s[i].isNumber { num = 0 while i < s.endIndex && s[i].isNumber { num = num * 10 + s[i].wholeNumberValue! i = s.index(after: i) } if i < s.endIndex && s[i] == "x" { coeff += sign * num i = s.index(after: i) } else { constPart += sign * num } } else if s[i] == "x" { coeff += sign i = s.index(after: i) } } return (coeff, constPart) } let parts = equation.split(separator: "=") let (leftCoeff, leftConst) = parse(String(parts[0])) let (rightCoeff, rightConst) = parse(String(parts[1])) let coeff = leftCoeff - rightCoeff let constPart = rightConst - leftConst if coeff == 0 { return constPart == 0 ? "Infinite solutions" : "No solution" } return "x=\(constPart / coeff)" } } Ставь 👍 и забирай 📚 Базу знаний