🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 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
}
Ставь 👍 и забирай 📚 Базу знаний
