Swift | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Ko'proq ko'rsatish
Tarmoq:1 340
Obunachilar
-124 soatlar
-97 kunlar
-2430 kunlar
Postlar arxiv
1 340
Задача: 1052. Grumpy Bookstore Owner
Сложность: medium
Есть владелец книжного магазина, магазин которого открыт в течение n минут. Каждую минуту в магазин заходит некоторое количество покупателей. Вам дан целочисленный массив customers длины n, где customers[i] - это номер покупателя, который заходит в магазин в начале i-й минуты, а все покупатели выходят после окончания этой минуты. В некоторые минуты владелец книжного магазина ворчлив. Вам дан двоичный массив grumpy, в котором grumpy[i] равен 1, если владелец книжного магазина ворчлив в течение i-й минуты, и равен 0 в противном случае. Когда владелец книжного магазина ворчлив, покупатели в эту минуту не удовлетворены, в противном случае они удовлетворены. Владелец книжного магазина знает секретную технику, чтобы не ворчать в течение нескольких минут подряд, но может использовать ее только один раз. Верните максимальное количество покупателей, которое может быть удовлетворено в течение дня.
Пример:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3 Output: 16👨💻 Алгоритм: 1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив. 2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники. 3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд. 😎 Решение:
func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ minutes: Int) -> Int {
var totalSatisfied = 0
var additionalSatisfied = 0
var maxAdditionalSatisfied = 0
for i in 0..<customers.count {
if grumpy[i] == 0 {
totalSatisfied += customers[i]
} else {
additionalSatisfied += customers[i]
}
if i >= minutes {
if grumpy[i - minutes] == 1 {
additionalSatisfied -= customers[i - minutes]
}
}
maxAdditionalSatisfied = max(maxAdditionalSatisfied, additionalSatisfied)
}
return totalSatisfied + maxAdditionalSatisfied
}1 340
Задача: 1370. Increasing Decreasing String
Сложность: easy
Дана строка s. Переставьте символы строки, используя следующий алгоритм:
Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.
Верните результирующую строку после сортировки s с помощью этого алгоритма.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Инициализация и сортировка: Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result. 2⃣Перебор и добавление символов: Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре. 3⃣Проверка завершения: Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result. 😎 Решение:
class Solution {
func sortString(_ s: String) -> String {
var charCount = [Character: Int]()
for char in s {
charCount[char, default: 0] += 1
}
var result = ""
while result.count < s.count {
for char in "abcdefghijklmnopqrstuvwxyz" {
if let count = charCount[char], count > 0 {
result.append(char)
charCount[char]! -= 1
}
}
for char in "zyxwvutsrqponmlkjihgfedcba" {
if let count = charCount[char], count > 0 {
result.append(char)
charCount[char]! -= 1
}
}
}
return result
}
}1 340
Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy
Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.
Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].
Пример:
Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.class Solution {
func findLengthOfLCIS(_ nums: [Int]) -> Int {
var ans = 0, anchor = 0
for i in 0..<nums.count {
if i > 0 && nums[i - 1] >= nums[i] {
anchor = i
}
ans = max(ans, i - anchor + 1)
}
return ans
}
}1 340
Задача: 1325. Delete Leaves With a Given Value
Сложность: medium
Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.
Обратите внимание, что после удаления листового узла со значением target, если его родительский узел становится листовым узлом и имеет значение target, он также должен быть удален (необходимо продолжать делать это, пока это возможно).
Пример:
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left).
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).class Solution {
func removeLeafNodes(_ root: TreeNode?, _ target: Int) -> TreeNode? {
guard let root = root else { return nil }
root.left = removeLeafNodes(root.left, target)
root.right = removeLeafNodes(root.right, target)
if root.left == nil && root.right == nil && root.val == target {
return nil
}
return root
}
}1 340
Задача: 621. Task Scheduler
Сложность: medium
Вам дан массив задач процессора, каждая из которых представлена буквами от A до Z, и время охлаждения, n. Каждый цикл или интервал позволяет завершить одну задачу. Задачи могут быть выполнены в любом порядке, но есть ограничение: одинаковые задачи должны быть разделены не менее чем n интервалами из-за времени охлаждения. Верните минимальное количество интервалов, необходимое для выполнения всех задач.
Пример:
Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8👨💻 Алгоритм: 1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq). 2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq. 3⃣Верните максимум между вычисленным значением и длиной массива задач, поскольку некоторые задачи могут заполнять интервал до n. 😎 Решение:
func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
var taskCounts = [Character: Int]()
for task in tasks {
taskCounts[task, default: 0] += 1
}
let maxFreq = taskCounts.values.max()!
let countMaxFreq = taskCounts.values.filter { $0 == maxFreq }.count
return max(tasks.count, (maxFreq - 1) * (n + 1) + countMaxFreq)
}1 340
Задача: 347. Top K Frequent Elements
Сложность: medium
Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]👨💻 Алгоритм: 1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums. 2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов. 3⃣Возврат результата: Верните k самых частых элементов. 😎 Решение:
class Solution {
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
let count = Dictionary(nums.map { ($0, 1) }, uniquingKeysWith: +)
return Array(count.keys.sorted(by: { count[$0]! > count[$1]! }).prefix(k))
}
}1 340
Задача: 1360. Number of Days Between Two Dates
Сложность: easy
Напишите программу для подсчета количества дней между двумя датами.
Даты даны в виде строк в формате YYYY-MM-DD, как показано в примерах.
Пример:
Input: date1 = "2019-06-29", date2 = "2019-06-30" Output: 1👨💻 Алгоритм: 1⃣Преобразование строк в даты: Используйте встроенные функции для преобразования строковых представлений дат в объекты дат. 2⃣Вычисление разницы в днях: Вычислите разницу между двумя объектами дат в днях. 3⃣Возвращение результата: Верните абсолютное значение разницы в днях для получения положительного числа. 😎 Решение:
import Foundation
class Solution {
func daysBetweenDates(_ date1: String, _ date2: String) -> Int {
let dateFormatter = DateFormatter()
dateFormatter.dateFormat = "yyyy-MM-dd"
let d1 = dateFormatter.date(from: date1)!
let d2 = dateFormatter.date(from: date2)!
return abs(Calendar.current.dateComponents([.day], from: d1, to: d2).day!)
}
}1 340
Задача: 848. Shifting Letters
Сложность: medium
Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины.
Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a').
Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'.
Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз.
Верните итоговую строку после применения всех таких сдвигов к s.
Пример:
Input: s = "abc", shifts = [3,5,9] Output: "rpl" Explanation: We start with "abc". After shifting the first 1 letters of s by 3, we have "dbc". After shifting the first 2 letters of s by 5, we have "igc". After shifting the first 3 letters of s by 9, we have "rpl", the answer.👨💻 Алгоритм: 1⃣Вычислите общее количество сдвигов для всех символов строки, используя массив shifts. 2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге. 3⃣Постройте и верните итоговую строку после всех сдвигов. 😎 Решение:
class Solution {
func shiftingLetters(_ s: String, _ shifts: [Int]) -> String {
var sArray = Array(s)
var totalShifts = shifts.reduce(0, { ($0 + $1) % 26 })
for i in 0..<sArray.count {
let newCharValue = Int(sArray[i].asciiValue!) - 97 + totalShifts
sArray[i] = Character(UnicodeScalar((newCharValue % 26 + 97))!)
totalShifts = (totalShifts - shifts[i]) % 26
}
return String(sArray)
}
}1 340
Задача: 1245. Tree Diameter
Сложность: medium
Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.
Пример:
Input: edges = [[0,1],[0,2]] Output: 2👨💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:
class Solution {
func treeDiameter(_ edges: [[Int]]) -> Int {
if edges.isEmpty { return 0 }
var graph = [Int: [Int]]()
for edge in edges {
graph[edge[0], default: []].append(edge[1])
graph[edge[1], default: []].append(edge[0])
}
var farthestNode = 0
func dfs(_ node: Int, _ parent: Int) -> Int {
var maxDepth = 0
for neighbor in graph[node]! {
if neighbor != parent {
let depth = dfs(neighbor, node)
if depth + 1 > maxDepth {
maxDepth = depth + 1
farthestNode = neighbor
}
}
}
return maxDepth
}
_ = dfs(0, -1)
let startNode = farthestNode
_ = dfs(startNode, -1)
return dfs(farthestNode, -1)
}
}1 340
Задача: 554. Brick Wall
Сложность: medium
Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.
Нарисуйте вертикальную линию от верха до низа, пересекающую наименьшее количество кирпичей. Если ваша линия проходит по краю кирпича, то кирпич не считается пересеченным. Вы не можете нарисовать линию прямо по одному из двух вертикальных краев стены, так как в этом случае линия очевидно не пересечет ни одного кирпича.
Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.
Пример:
Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] Output: 2👨💻 Алгоритм: 1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду. 2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i]. 3⃣Подсчитайте количество кирпичей, которые пересечет вертикальная линия для каждой возможной позиции, обновляя счетчик. Выберите минимальное количество пересеченных кирпичей из всех возможных позиций для вертикальной линии. 😎 Решение:
class Solution {
func leastBricks(_ wall: [[Int]]) -> Int {
var pos = [Int](repeating: 0, count: wall.count)
var res = Int.max
var sum = wall[0].reduce(0, +)
while sum != 0 {
var count = 0
for i in 0..<wall.count {
if wall[i][pos[i]] != 0 {
count += 1
} else {
pos[i] += 1
}
wall[i][pos[i]] -= 1
}
sum -= 1
res = min(res, count)
}
return res
}
}1 340
Задача: 536. Construct Binary Tree from String
Сложность: medium
Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел.
Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой.
Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.
Пример:
Input: s = "4(2(3)(1))(6(5))" Output: [4,2,6,3,1,5]👨💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}
class Solution {
func str2tree(_ s: String) -> TreeNode? {
return str2treeInternal(Array(s), 0).node
}
func getNumber(_ s: [Character], _ index: Int) -> (value: Int, index: Int) {
var idx = index
var isNegative = false
if s[idx] == "-" {
isNegative = true
idx += 1
}
var number = 0
while idx < s.count, let digit = s[idx].wholeNumberValue {
number = number * 10 + digit
idx += 1
}
return (isNegative ? -number : number, idx)
}
func str2treeInternal(_ s: [Character], _ index: Int) -> (node: TreeNode?, nextIndex: Int) {
if index >= s.count {
return (nil, index)
}
let numberData = getNumber(s, index)
let value = numberData.value
var idx = numberData.index
let node = TreeNode(value)
if idx < s.count && s[idx] == "(" {
let leftData = str2treeInternal(s, idx + 1)
node.left = leftData.node
idx = leftData.nextIndex
}
if idx < s.count && s[idx] == "(" {
let rightData = str2treeInternal(s, idx + 1)
node.right = rightData.node
idx = rightData.nextIndex
}
return (node, idx < s.count && s[idx] == ")" ? idx + 1 : idx)
}
}1 340
Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium
Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.
Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.
Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.
Пример:
Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.👨💻 Алгоритм: 1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count. 2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count. 3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s. 😎 Решение:
class Solution {
func minSteps(_ s: String, _ t: String) -> Int {
var count = [Int](repeating: 0, count: 26)
for i in s.indices {
count[Int(t[i].asciiValue! - Character("a").asciiValue!)] += 1
count[Int(s[i].asciiValue! - Character("a").asciiValue!)] -= 1
}
var ans = 0
for i in 0..<26 {
ans += max(0, count[i])
}
return ans
}
}1 340
Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium
Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2class Solution {
func findNumberOfLIS(_ nums: [Int]) -> Int {
let n = nums.count
var length = Array(repeating: 1, count: n)
var count = Array(repeating: 1, count: n)
for i in 0..<n {
for j in 0..<i {
if nums[j] < nums[i] {
if length[j] + 1 > length[i] {
length[i] = length[j] + 1
count[i] = 0
}
if length[j] + 1 == length[i] {
count[i] += count[j]
}
}
}
}
let maxLength = length.max() ?? 0
var result = 0
for i in 0..<n {
if length[i] == maxLength {
result += count[i]
}
}
return result
}
}1 340
Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium
Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.
Пример:
Input: preorder = [5,2,1,3,6] Output: true👨💻 Алгоритм: 1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек. 2⃣Итерируйте по массиву preorder. Для каждого num: Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit. Если num <= minLimit, верните false. Добавьте num в стек. 3⃣Верните true, если удалось пройти весь массив. 😎 Решение:
class Solution {
func verifyPreorder(_ preorder: [Int]) -> Bool {
var minLimit = Int.min
var stack: [Int] = []
for num in preorder {
while !stack.isEmpty && stack.last! < num {
minLimit = stack.removeLast()
}
if num <= minLimit {
return false
}
stack.append(num)
}
return true
}
}1 340
Задача: 609. Find Duplicate File in System
Сложность: medium
Получив список paths информации о каталоге, включающий путь к каталогу и все файлы с содержимым в этом каталоге, верните все дубликаты файлов в файловой системе по их путям. Вы можете вернуть ответ в любом порядке. Группа дубликатов состоит как минимум из двух файлов с одинаковым содержимым. Одна строка информации о каталоге во входном списке имеет следующий формат: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" Это означает, что в каталоге "root/d1/d2/.../dm" имеется n файлов (f1.txt, f2.txt ... fn.txt) с содержимым (f1_content, f2_content ... fn_content) соответственно. Обратите внимание, что n >= 1 и m >= 0. Если m = 0, это означает, что каталог является только корневым. На выходе получается список групп дублирующихся путей к файлам. Для каждой группы он содержит все пути к файлам, которые имеют одинаковое содержимое. Путь к файлу - это строка, имеющая следующий формат: "каталог_путь/имя_файла.txt".
Пример:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"] Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]👨💻 Алгоритм: 1⃣Пройдите по списку путей, разберите каждый путь и соберите информацию о содержимом файлов и соответствующих им путях. 2⃣Используйте словарь для хранения списков путей файлов, сгруппированных по их содержимому. 3⃣Пройдите по словарю и соберите группы дубликатов, содержащие как минимум два пути. 😎 Решение:
func findDuplicate(_ paths: [String]) -> [[String]] {
var contentToFilePaths = [String: [String]]()
for path in paths {
let parts = path.split(separator: " ")
let root = parts[0]
for i in 1..<parts.count {
let fileParts = parts[i].split(separator: "(")
let fileName = String(fileParts[0])
let content = String(fileParts[1].dropLast())
let filePath = "\(root)/\(fileName)"
contentToFilePaths[content, default: []].append(filePath)
}
}
return contentToFilePaths.values.filter { $0.count > 1 }
}1 340
Задача: 272. Closest Binary Search Tree Value II
Сложность: hard
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution {
func closestKValues(_ root: TreeNode?, _ target: Double, _ k: Int) -> [Int] {
var arr = [Int]()
dfs(root, &arr)
arr.sort { abs(Double($0) - target) < abs(Double($1) - target) }
return Array(arr.prefix(k))
}
private func dfs(_ node: TreeNode?, _ arr: inout [Int]) {
guard let node = node else { return }
arr.append(node.val)
dfs(node.left, &arr)
dfs(node.right, &arr)
}
}1 340
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 340
Задача: 771. Jewels and Stones
Сложность: medium
Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.
Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".
Пример:
Input: jewels = "aA", stones = "aAAbbbb"
Output: 3class Solution {
func numJewelsInStones(_ J: String, _ S: String) -> Int {
var ans = 0
for s in S {
for j in J {
if j == s {
ans += 1
break
}
}
}
return ans
}
}1 340
Задача: 1086. High Five
Сложность: easy
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]class Solution {
func highFive(_ items: [[Int]]) -> [[Int]] {
let K = 5
let sortedItems = items.sorted {
if $0[0] != $1[0] {
return $0[0] < $1[0]
}
return $0[1] > $1[1]
}
var solution = [[Int]]()
var i = 0
while i < sortedItems.count {
let id = sortedItems[i][0]
var sum = 0
for k in i..<i+K {
sum += sortedItems[k][1]
}
while i < sortedItems.count && sortedItems[i][0] == id {
i += 1
}
solution.append([id, sum / K])
}
return solution
}
}1 340
Задача: 273. Integer to English Words
Сложность: hard
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution {
private let belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
private let tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
private let thousands = ["", "Thousand", "Million", "Billion"]
func numberToWords(_ num: Int) -> String {
if num == 0 { return "Zero" }
var num = num
var result = ""
var i = 0
while num > 0 {
if num % 1000 != 0 {
result = helper(num % 1000) + thousands[i] + " " + result
}
num /= 1000
i += 1
}
return result.trimmingCharacters(in: .whitespaces)
}
private func helper(_ num: Int) -> String {
if num == 0 { return "" }
else if num < 20 { return belowTwenty[num] + " " }
else if num < 100 { return tens[num / 10] + " " + helper(num % 10) }
else { return belowTwenty[num / 100] + " Hundred " + helper(num % 100) }
}
}