Я потратил большую часть мая и июня на подготовку к собеседованию, и под подготовкой к собеседованию я имею в виду много работы с Leetcode. Я решил решить большинство проблем в Kotlin, так как я подал заявку на должности Android, и заметил, что Kotlin, который я писал, сильно отличался от Kotlin, который я использую на работе. Я решил скомпилировать обзор фрагментов кода, которые часто возникали во время подготовки к собеседованию, в шпаргалку, а затем глубоко погрузиться в фрагменты кода в серии из 5 сообщений Medium. Шпаргалку можно найти здесь.
В части 1 я расскажу о нескольких общих типах данных, которые часто встречаются в вопросах алгоритмов и структур данных - как их инициализировать, как выполнять с ними некоторые общие операции и некоторые варианты использования. Мы перейдем к следующему:
Вы можете найти Часть 2 здесь, Часть 3 здесь, 4 - здесь и Часть 5 - здесь.
MutableList
Это структура данных, которую я использовал чаще всего, и вы, вероятно, уже знакомы с ней. Я хочу отметить, что вы можете легко использовать его как стек или очередь, если столкнетесь с проблемой, которая требует этого; Обычно я использую MutableList для представления очереди при поиске в ширину.
// Create an empty MutableList val list1 = mutableListOf<Int>() // Create a MutableList with elements [0, 1, 2, 3, 4] val list2 = mutableListOf(0, 1, 2, 3, 4)
Использование MutableList в качестве стека
add()добавляет элемент в конец списка и может использоваться какpushremoveLast()удаляет последний элемент из списка и возвращает его, может использоваться какpoplast()возвращает последний элемент, не удаляя его, и может использоваться какpeek
val stack: MutableList<Int> = mutableListOf() // push stack.add(1) stack.add(2) // peek stack.last() // returns 2 // pop stack.removeLast() // returns 2 stack.removeLast() // returns 1
Использование MutableList в качестве очереди
add()можно использовать какenqueueremoveAt(0)удаляет первый элемент из списка и возвращает его, может использоваться какdequeueget(0)возвращает первый элемент и может использоваться какpeek
val queue: MutableList<Int> = mutableListOf() // enqueue queue.add(1) queue.add(2) // peek queue[0] // returns 1 // dequeue queue.removeAt(0) // returns 1 queue.removeAt(0) // returns 2
Множество
Массивы кажутся простыми, но когда я начал готовиться к собеседованию, я понял, что не очень хорошо их знаю, потому что вместо этого использую списки. Когда проблема Leetcode имела ввод массива или ожидал вывода массива, мне приходилось искать в Google.
В Kotlin массивы имеют фиксированный размер и поддерживают get(), set() и size, а также большинство функций сбора Kotlin. Вы можете использовать [], также известный как оператор индексации, для более лаконичного получения и установки. Вы не можете изменять размер или удалять элементы. Я считаю массивы полезными для задач, когда вы хотите отслеживать фиксированное количество счетчиков или флагов.
Есть два способа инициализировать массивы. Вы можете использовать arrayOf<T>():
// Create an array with elements [0, 1, 2, 3, 4] val array1 = arrayOf<Int>(0, 1, 2, 3, 4)
Или используйте Array<T>(n) { initFunction }. Это создаст массив размером n, где каждый элемент создается с использованием initFunction. initFunction может быть просто значением по умолчанию, например -1 для массива Ints или блока кода.
// Create an array with elements [0, 0, 0, 0, 0]
val array2 = Array<Int>(5) { 0 }
// Create an array with elements [0, 2, 4, 6, 8]
// The initFunction block can access the index as a parameter.
// Here, each element is initialized by taking its index and multiplying it by 2.
val array3 = Array<Int>(5) { index -> 2 * index }
Также существуют специальные методы arrayOf для следующих примитивных типов: double , float , long , int , char , short , byte , boolean, которые обеспечивают лучшую производительность, избегая накладных расходов на бокс Kotlin:
// Create an array with elements [0, 1, 2, 3, 4]
val intArray1 = intArrayOf(0, 1, 2, 3, 4)
// Create an array with elements [0, 0, 0, 0, 0]
val intArray2 = IntArray(5) { 0 }
// Create an array with elements [true, true, false, true, true]
val booleanArray1 = booleanArrayOf(true, true, false, true, true)
// Create an array with elements [true, false, true, false, true]
// Each element is initialized by by whether or not its index is even
val booleanArray2 = BooleanArray(5) { index -> index % 2 == 0 }
Текущая сумма 1d массива - это пример простой задачи Leetcode, в которой вы можете использовать IntArray для отслеживания результатов:
/** * Problem description: Given an arraynums. We define a running sum * of an array asrunningSum[i] = sum(nums[0]…nums[i]). Return the * running sum ofnums. * * Example: * Input: nums = [1,2,3,4] * Output: [1,3,6,10] * Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, * 1+2+3+4]. ** / fun runningSum(nums: IntArray): IntArray { val results = IntArray(nums.size) { 0 } results[0] = nums[0] for (i in 1 until nums.size) { results[i] = results[i - 1] + nums[i] } return results }
HashMap
HashMaps представляют собой набор пар ключ-значение, где ключи уникальны, а карта может иметь только одно значение для каждого ключа. Они часто используются в задачах собеседования для хранения информации. Например, HashMap<Node, Boolean> может хранить, какие узлы в графе уже были посещены, а HashMap<String, Int> может хранить количество различных слов, появляющихся в предложении.
Несколько полезных функций:
clear()удаляет все элементы с карты.containsKey(key: K)возвращает истину, если карта содержит указанный ключ.remove(key: K)удаляет указанный ключ и соответствующее ему значение из этой карты.getOrPut(key: K, defaultValue: () -> V)возвращает значение для данного ключа, если он есть на карте. Если это не так, вызовите функциюdefaultValue, поместите ее результат на карту под заданным ключом и верните его.
// Create an empty HashMap
val map1 = hashMapOf<String, Int>()
// Create a HashMap with initial values
val map2 = hashMapOf(
"Never Let Me Go" to 2005,
"A Little Life" to 2015
)
// Two ways to insert a key-value pair
map2.put("The Name of the Wind", 2007)
map2["The Bell Jar"] = 1963
// Two ways to retrieve a value
map2.get("The Name of the Wind") // returns 2007
map2["The Bell Jar"] // returns 1963
// Using getOrPut()
map2.getOrPut("The Name of the wind", 1990) // Returns 2007
map2.getOrPut("1984", 1949) // Inserts new entry and returns 1949
PriorityQueue
PriorityQueues полезны, когда вы хотите, чтобы элементы обрабатывались на основе их приоритета. Этот класс реализован с использованием кучи. Они часто используются в задачах собеседования, которые требуют K-го наибольшего, K-го наименьшего, наиболее частого K и т. Д.
Вы можете инициализировать его с помощью PriorityQueue<T>(), где для определения приоритета будет использоваться естественный порядок типа T, или с помощью пользовательского Comparator, например PriorityQueue<T> { (a: T, b: T) -> Int }, где вы указываете собственный способ определения приоритета.
Несколько полезных функций:
add(element: E)иoffer(element: E)оба вставляют элемент, и вы можете использовать любой из них;PriorityQueueимеет две функции, которые делают одно и то же, потому что он реализует два интерфейса,CollectionиQueue. Коллекции используютadd()для вставок, тогда как очереди используютoffer().peek()возвращает, но не удаляет заголовок очереди.poll()возвращает и удаляет заголовок очереди.
// Create a PriorityQueue pq where the maximum value Int has highest
// priority
val pq = PriorityQueue<Int> {
a, b -> b - a
}
// Add 2, 1, 3 to the pq
pq.offer(2)
pq.add(1)
pq.offer(3)
pq.peek() // returns 3 but does not remove it from pq
// pq will be empty after 3 iterations
while(pq.isNotEmpty()) {
pq.poll() // returns 3, then 2, then 1
}
Компаратор
Интерфейс Comparator<T> предоставляет функцию сравнения для установления общего порядка между экземплярами типа T. Это часто бывает полезно для технических собеседований, требующих сортировки или определения приоритетов, потому что большинство алгоритмов сортировки Kotlin позволяют передавать Comparator.
Вы можете использовать функцию compareBy() Kotlin, чтобы создать Comparator, который использует последовательность переданных вами функций для вычисления результатов сравнения. Последовательность функций оценивается последовательно на парах значений, и как только результаты для двух значений, возвращаемых функцией, не сравниваются как равные, возвращается результат, а остальные функции для этой пары пропускаются.
val customComparator = compareBy<T> {
...
}
Вот пример Comparator, который сравнивает Ints по абсолютному значению:
val absComparator = compareBy<Int>{ Math.abs(it) }
val nums: MutableList<Int> = mutableListOf(-1, 3, 7, -5, 3)
nums.sortWith(absComparator)
// Or if you only need to use the comparator once, you can pass in
// the call to compareBy() directly.
val nums: MutableList<Int> = mutableListOf(-1, 3, 7, -5, 3)
nums.sortWith(compareBy{ Math.abs(it) })
Вот пример Comparator, который сравнивает пользовательский класс Card по свойству цвета, а BLACK карточки «лучше», чем RED карточки. Мы будем использовать свойство number, чтобы разорвать связи:
enum class Color { RED, BLACK }
data class Card(val number: Int, val color: Color)
val cardComparator = compareBy(
// Compare by color first
{ if(it.color == BLACK) 1 else 0 },
// If the results of color comparison are equal, compare by
// number
{ it.number }
)
val cards: MutableList<Card> = mutableListOf(
Card(4, Color.RED),
Card(2, Color.BLACK),
Card(1, Color.RED),
Card(3, Color.BLACK)
)
cards.sortWith(cardComparator)
// cards becomes:
// [Card(1, RED), Card(4, RED), Card(2, BLACK), Card(3, BLACK)]
Если сравнение сложно, вы можете создать объект, который явно реализует интерфейс Comparator и переопределит функцию compare() . Он должен возвращать ноль, если аргументы равны, отрицательное число, если первый аргумент меньше второго, или положительное число, если первый аргумент больше второго.
object CustomComparator: Comparator<T>{
override fun compare(a: T, b: T): Int {
...
return ...
}
}
Вот как будет выглядеть объект Comparator при сравнении карт:
object cardComparator: Comparator<Card>{
override fun compare(a: Card, b: Card): Int {
if (a.color == b.color) {
return a.number - b.number
} else if (a.color == Color.BLACK) {
// Case where a is BLACK and b is RED
return 1
} else {
// Case where a is RED and b is BLACK
return -1
}
}
}
Сопоставимый
Для настраиваемых классов вы также можете сделать так, чтобы ваш класс расширил интерфейс Comparable и переопределил compareTo() для наложения общего порядка, а не для создания отдельного объекта. Вы можете использовать вспомогательную функцию Kotlin compareValuesBy(), которая, как и compareBy(), использует последовательность переданных вами функций для вычисления результатов сравнения. Поэтому вместо того, чтобы использовать sortWith() и передавать свой собственный компаратор, вы можете просто использовать sort(), и функция будет знать, как выполнить полное упорядочение.
enum class Color { RED, BLACK }
data class Card(val number: Int, val color: Color)
: Comparable<Card> {
override operator fun compareTo(other: Card): Int {
compareValuesBy(
this,
other,
// Compare by color first
{ it.color },
// If the results of color comparison are equal,
// compare by number
{ it.number }
)
}
}
val cards: MutableList<Card> = mutableListOf(
Card(4, Color.RED),
Card(2, Color.BLACK),
Card(1, Color.RED),
Card(3, Color.BLACK)
)
cards.sort()
// cards becomes:
// [Card(1, RED), Card(4, RED), Card(2, BLACK), Card(3, BLACK)]
Опять же, у вас есть возможность реализовать compareTo() без помощника compareValuesBy(), если вам будет понятнее:
data class Card(val number: Int, val color: Color)
: Comparable<Card> {
override operator fun compareTo(other: Card): Int {
if (this.color == other.color) {
return this.number - other.number
} else if (this.color == Color.BLACK) {
return 1
} else {
return -1
}
}
}
И это первая часть! В Части 2 я рассмотрю полезные функции коллекции Kotlin. Вот ссылка на шпаргалку, снова охватывающую все 5 частей.
Щелкните 👏, чтобы сказать «спасибо!» и помогите другим найти эту статью.
Чтобы быть в курсе отличных новостей о Kt. Academy, подписывайтесь на рассылку новостей, следите за Twitter и следите за нами на Medium.
Если вам нужна мастерская Kotlin, узнайте, чем мы можем вам помочь: kt.academy.
