Решать задачиРешения для задач с собеседований по Swift
Алгоритм бинарного поиска
Бинарный поиск (Binary Search) - это эффективный алгоритм для поиска значения в отсортированном массиве.
Принцип алгоритма очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым.
Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится.
Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую.
Если же элемент совпадает с искомым, мы выходим из цикла.
func binarySearch(array: [T], key: T) -> Int? {
var lowerBound = 0
var upperBound = array.count - 1
while lowerBound <= upperBound {
let mid = (lowerBound + upperBound) / 2
if array[mid] == key {
return mid
} else if array[mid] < key {
lowerBound = mid + 1
} else {
upperBound = mid - 1
}
}
return nil
}
Термины:
target - искомое значение
index - индекс искомого значения.
left, right - левый и правый индексы, определяющие область нахождения.
mid - индекс элемента в центре текущего поля поиска, который будет сравниваться с целевым значением.
Эта реализация основана на использовании цикла и позволяет найти индекс искомого фрагмента в отсортированном массиве или вернуть nil, если искомое значение не найдено.
Реализуйте оператор возведения в степень (^^)
Постановка:
У Swift есть набор предопределенных операторов для арифметических и логических действий. Он также позволяет создавать свои собственные операторы, как унарные, так и бинарные.
Определите и реализуйте собственный оператор возведения в степень ^^ по следующим требованиям:
- принимает в качестве параметров два Int
- возвращает результат возведения первого параметра в степень второго
- корректно обрабатывает порядок алгебраических операций
- игнорирует возможные ошибки переполнения
Решение:
Создание нового оператора происходит в два этапа: объявление и реализация.
Объявление использует ключевое слово operator для задания типа (унарный или бинарный), для задания последовательности символов нового оператора, его ассоциативности и старшинства выполнения.
Здесь оператор — это ^^ и его тип infix (бинарный). Ассоциативность правая.
В Swift нет предопределенного старшинства для возведения в степень. В алгебре возведение в степень должно вычисляться перед умножением/делением. Таким образом, мы создаем пользовательский порядок выполнения, помещая возведение в степень выше умножения.
Это объявление:
precedencegroup ExponentPrecedence {
higherThan: MultiplicationPrecedence
associativity: right
}
infix operator ^^: ExponentPrecedence
Это реализация:
func ^^(base: Int, exponent: Int) -> Int {
let l = Double(base)
let r = Double(exponent)
let p = pow(l, r)
return Int(p)
}
Расширение Array для подсчёта количества уникальных значений
Вариант 1:
extension Array where Element: Comparable {
func countUniques() -> Int {
let sortedValues = sorted()
let initial: (Element?, Int) = (.none, 0)
let reduced = sortedValues.reduce(initial) {
($1, $0.0 == $1 ? $0.1 : $0.1 + 1)
}
return reduced.1
}
}
Вариант 2:
func countUniques<T: Hashable>(_ array: Array<T>) -> Int {
return Set(array).count
}
Максимально упростите замыкание
Постановка:
Этот код сортирует массив по алфавиту. Максимально упростите замыкание.
var animals = ["fish", "cat", "chicken", "dog"]
animals.sort { (one: String, two: String) -> Bool in
return one < two
}
print(animals)
Решение:
Swift автоматически определяет тип параметров замыкания и возвращаемый тип, так что вы можете убрать их:
animals.sort { (one, two) in return one < two }
Вы можете заменить имена параметров использованием нотации $i:
animals.sort { return $0 < $1 }
Замыкания, состоящие из одного оператора, могут не содержать ключевое слово return. Значение последнего выполненного оператора становится возвращаемым результатом замыкания:
animals.sort { $0 < $1 }
Наконец, так как Swift знает, что элементы массива соответствуют протоколу Equatable, вы можете просто написать:
animals.sort(by: <)
Есть и более короткий вариант:
animals.sort()
Он сортирует по возрастанию, работает для типов, реализующих Comparable.
Авторизуйтесь, чтобы просматривать следующий контентПоменяйте местами две переменные без третьей
Авторизуйтесь, чтобы получить доступПерепишите функцию divide
Авторизуйтесь, чтобы получить доступРеализуйте инициализацию при помощи литералов
Авторизуйтесь, чтобы получить доступСконвертируйте отрицательное целое в UInt с сохранением его представления в памяти
Авторизуйтесь, чтобы получить доступНайдите дубликат без дополнительной переменной
Авторизуйтесь, чтобы получить доступОпределите тип бинарного дерева
Авторизуйтесь, чтобы получить доступНайдите целое число, которое встречается больше 50% раз
Авторизуйтесь, чтобы получить доступРеализуйте простейший Singleton
Авторизуйтесь, чтобы получить доступРеализуйте паттерн "Абстрактная фабрика"
Авторизуйтесь, чтобы получить доступРеализуйте паттерн "Строитель"
Авторизуйтесь, чтобы получить доступРеализуйте паттерн "Фабричный метод"
Авторизуйтесь, чтобы получить доступРеализуйте паттерн "Прототип"
Авторизуйтесь, чтобы получить доступТакже в этой категории
Топ тредов
: Задача в JavaScript "Поиск пары чисел по сумме"
: Задача в JavaScript "Форматирование текста"
: Задача в JavaScript "Числовая спираль"
