Ещё пара интересных задачек с литкода и решением на Swift
🐬 Valid Parentheses: дана строка s, содержащая только символы
'(', ')', '{', '}', '[', ']'. Определи, является ли строка валидной: все открытые скобки должны закрываться в правильном порядке и соответствующими типами
// Примеры
Input: s = "()" → true
Input: s = "()[]{}" → true
Input: s = "(]" → false
Input: s = "([)]" → false
Input: s = "{[]}" → true
Объяснение и решение:
• Используем стек: открывающие скобки кладём, закрывающие проверяем и убираем. • Если в какой-то момент не совпадает или стек не пуст в конце false
class Solution {
func isValid(_ s: String) -> Bool {
var stack: [Character] = []
for char in s {
switch char {
case "(", "{", "[":
stack.append(char) // открывающую скобку кладём в стек
case ")":
if stack.last != "(" { return false }
stack.removeLast()
case "}":
if stack.last != "{" { return false }
stack.removeLast()
case "]":
if stack.last != "[" { return false }
stack.removeLast()
default:
return false
}
}
return stack.isEmpty // в конце стек должен быть пустым
}
}
🐬 Best Time to Buy and Sell Stock: дан массив prices, где
prices[i] это цена акции в i-й день. Нужно найти максимальную прибыль, которую можно получить, купив акцию в один день и продав в другой (можно не покупать вообще)
// Примеры
Input: prices = [7,1,5,3,6,4] → 5 (купить в 1, продать в 4)
Input: prices = [7,6,4,3,1] → 0
Input: prices = [2,4,1] → 2
Объяснение и решение:
• Проходим по массиву один раз.
• Запоминаем самую низкую цену слева.
• На каждой итерации считаем потенциальную прибыль и сохраняем максимум
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var minPrice = Int.max // самая низкая цена, которую мы видели
var maxProfit = 0
for price in prices {
if price < minPrice {
minPrice = price // обновляем минимальную цену
} else {
let profit = price - minPrice
if profit > maxProfit {
maxProfit = profit
}
}
}
return maxProfit
}
}
Эти две задачи отлично дополняют предыдущие (Two Sum + Palindrome Number). Они тоже решаются за 10–20 минут, но уже требуют чуть больше размышлений
🥰
@SnowBallCode😍
