[Разработка под Android, Kotlin] Solving coding problems with Kotlin: Collection functions

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 4 месяца
Сообщений: 27286

news_bot ^® написал(а)
04-Ноя-2020 04:30

Цитировать

(originally published on Medium)I have talked to many Android developers, and most of them are excited about Kotlin. So am I. When I just started learning Koltin, I was solving Kotlin Koans, and along with other great features, I was impressed with the power of functions for performing operations on collections. Since then, I spent three years writing Koltin code but rarely utilised all the potential of the language.During this year, I did more than a hundred coding problems on Leetcode in Java. I didn’t switch to Kotlin because I know the syntax of Java 6 so well, that I could effortlessly write code without autocompletion and syntax highlighting. But I didn’t keep track of new Java features, as Android support of Java SDK lacked many versions behind. I didn’t switch to Kotlin for solving problems right away. Although I was writing Kotlin code for several years, I felt that I need to make an extra cognitive effort to get the syntax and the language constructions right. Solving algorithmic problems, especially under the time pressure, is very different from Android app development. Still, the more I learned about Kotlin, the more I realised how many powerful features I’m missing, and how much boilerplate code I need to write.One day, I have decided that I need to move on, so I started a new session in Leetcode and switched the compiler to Kotlin. I solved just a few easy problems, but I already feel that I have something to share.LoopsLet’s start with loops. Let’s say, you have an IntArray of 10 elements 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and you want to print 123456789.

val array = intArrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for(index in (1 until array.size)) {
print(array[index])
}

(1 until array.size) is an IntRange, a class that represents a range of values of type Int. The first element in this range is 1 and the last one is 9¨C89Cas we used¨C90C¨C8C¨C91Cto exclude the last value. We don’t want to get¨C92C¨C9C¨C93Cright?But what if we want to print all the elements of the array, except the element at index 5? Like this 012346789. Let’s get a bit more Kotliney then writing an if statement in the loop.

val array = intArrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for(index in array.indices - 5) {
print(array[index])
}

array.indices returns the range of valid indices for the array. In this case array.indices represent IntRange of (0..9). Making ¨C16C¨C104Cwill result in¨C105C¨C17C. This is exactly what we need.Koltin also provides an ability to iterate from the greater number down to the smaller number using downTo. The iteration step size can also be changed using step.

val array = intArrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for(index in array.size - 1 downTo 1 step 2) {
print(array[index])
}

The code above with result in 97531.Remove Vowels from a StringIt’s a problem number 1119 on Leetcode.

Given a string S, remove the vowels 'a', 'e', 'i', 'o', and ¨C26C¨C117Cfrom it, and return the new string.

Even in Java there is a 1 line regex solution, but my intuition was the following:

Create a StringBuilder.
Iterate over characters, and if the current character is not a vowel, append it to the StringBuilder.
Return String from the StringBuilder.

public String removeVowels(String S) {
StringBuilder sb = new StringBuilder();
for(char s: S.toCharArray()) {
if(s != 'a' && s != 'e' && s != 'i' && s !='o' && s != 'u') {
sb.append(s);
}
}
return sb.toString();
}

What about Koltin? More idiomatic way is to use filter() or filterNot().

fun removeVowels(S: String): String {
return S.filter { it !in setOf('a', 'e', 'i', 'o', 'u') }
}

filter {predicate: (Char) -> Boolean} returns a string containing only those characters from the original string that match the given predicate.But instead of inverting !in let’s use filterNot()

fun removeVowels(S: String): String {
return S.filterNot { it in setOf('a', 'e', 'i', 'o', 'u') }
}

That was simple even for a beginner. Let’s move on to something a bit more sophisticated.Running Sum of 1d ArrayIt’s another easy problem from Leetcode. Number 1480.

Given an array nums. We define a running sum of an array as runningSum = sum(nums[0]…nums). Return the running sum of <em class="ff" style="box-sizing: inherit; font-style: normal;">nums</em>.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].

So we need to iterate over the array, adding the value at the current index to the running sum, and put it to the same index in the result array.Is there something in Kotlin to help us with the running sum? Well, there’s different variations of fold() and reduce() operations. Here’s a good explanation of those functions. But since Koltin 1.4 there’s even more: runningFold() and¨C140C¨C38C. As we want to start with the first element and return an array, it looks like¨C141C¨C39C¨C142Cis what we need. Let’s check it’s signature.

/**
* Returns a list containing successive accumulation values generated by applying [operation] from left to right
* to each element and current accumulator value that starts with the first element of this array.
*
* @param [operation] function that takes current accumulator value and an element, and calculates the next accumulator value.
*
* @sample samples.collections.Collections.Aggregates.runningReduce
*/
@SinceKotlin("1.4")
@kotlin.internal.InlineOnly
public inline fun IntArray.runningReduce(operation: (acc: Int, Int) -> Int): List<Int>

Sounds a bit too complex, but it will make sense when you’ll see an example.

fun runningSum(nums: IntArray): IntArray {
return nums.runningReduce { sum, element -> sum + element }.toIntArray()
}

This is the whole solution to the running sum problem using Kotlin runningReduce() function. sum starts with the first element in the array, element represens the current element. In lambda, we calculate the value of the next sum. Oh… I guess my explanation isn’t making it more clear that a doc. Let’s just print out the values of the¨C150C¨C44C¨C151Cand the¨C152C¨C45C¨C153Cat each step:sum: 1; element: 2; sum + element: 3sum: 3; element: 3; sum + element: 6sum: 6; element: 4; sum + element: 10sum: 10; element: 5; sum + element: 15And the array we return is [1, 3, 6, 10, 15]. There is no sum + element: 1, I didn’t miss the line. The thing is that runningReduce, as we see in the doc, takes the first value as the initial accumulator.Unfortunately, Leetcode doesn’t support Kotlin 1.4 yet, so the code above might not compile.Most Common WordEasy Leetcode problem, number 819.

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.Input:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"

What are the steps to solve it?

Convert string to lower case and split by words.

[bob, hit, a, ball, the, hit, ball, flew, far, after, it, was, hit]2. Create a set of banned words.[hit]3. Create a map of words to their occurrence, excluding the banned words.{bob=1, a=1, ball=2, the=1, flew=1, far=1, after=1, it=1, was=1}4. Return word with the highest number of occurrences from the map.ballLet’s implement those 4 steps in Java.

public String mostCommonWord(String paragraph, String[] banned) {
// 1. Covert string to lower case and split by words.
String[] words = paragraph.replaceAll("[^a-zA-Z0-9 ]", " ").toLowerCase().split("\\s+");
// 2. Create a set of banned words.
Set<String> bannedWords = new HashSet();
for (String word : banned)
bannedWords.add(word);
// 3. Create a map of words to their occurrence, excluding the banned words
Map<String, Integer> wordCount = new HashMap();
for (String word : words) {
if (!bannedWords.contains(word))
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
// 4. Return word with the highest number of occurrences from the map.
return Collections.max(wordCount.entrySet(), Map.Entry.comparingByValue()).getKey();
}

And the same 4 steps in Kotlin.

fun mostCommonWord(paragraph: String, banned: Array<String>): String {
// 1. Covert string to lower case and split by words.
val words = paragraph.toLowerCase().split("\\W+|\\s+".toRegex())
// 2. Create a set of banned words. Not needed in Kotlin
// 3. Create a map of words to their occurrence, excluding the banned words
val wordToCount = words.filterNot { it in banned }.groupingBy { it }.eachCount()
// 4. Return word with the highest number of occurrences from the map.
return wordToCount.maxBy { it.value }!!.key
}

Now let’s go through the functions to see what is happening here.

We split the string into words: List<String>. The type is inferred.
No need to create a set as we can perform in check on the array in Kotlin.
In this step, we chain 3 function calls. First, we use filterNot() to filter out banned words.¨C166C¨C58C¨C167Cwill return a¨C168C¨C59C¨C169Cthat contains only those strings that are not in the¨C170C¨C60C¨C171Carray. Unlike¨C172C¨C61C¨C173Cthat returns a map,¨C174C¨C62C¨C175Creturns an object of¨C176C¨C63C¨C177Ctype, that could be used later with one of group-and-fold operations. We use¨C178C¨C64C¨C179Cin¨C180C¨C65C¨C181Clambda. This means that we are grouping by the current element (word) in the collection. In other words — we create a map, where the key is a word, and the value is a count of occurrences of the word. To get the number of occurrences we use¨C182C¨C66C¨C183Con the¨C184C¨C67C
We use¨C185C¨C68C¨C186Cfunction to get the first largest element in the map, by¨C187C¨C69C. This returns us an object of¨C188C¨C70C, e.g.¨C189C¨C71C. And we return a key, which is the most common word in the sentence.

Order of elementsWhen you create a set setOf(“a”, “b”, “c”) or converting array to set using arrayOf(“a”, “b”, “c”).toSet() the returned set is LinkedHashSet and therefore element iteration order is preserved.The same is true about mapsmapOf(Pair(“a”, 1), Pair(“b”, 2))arrayOf</em>(Pair(“a”, 1), Pair(“b”, 2)).toMap()Both functions will return an instance of LinkedHashMap that keeps preserves the original element order. Knowing it might be helpful when solving problems.I have covered just a few of all available collection functions in Koltin. There’s map, flatMap, count, find, sum and much more!
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_razrabotka_pod_android (Разработка под Android), #_kotlin, #_kotlin, #_android, #_kotlin_vs_java, #_collections, #_kotlin_lessons, #_programming, #_razrabotka_pod_android (
Разработка под Android
), #_kotlin

Профиль ЛС

codeblogging

Стаж: 3 года 4 месяца
Сообщений: 1
Откуда: United kingdom

codeblogging написал(а)
03-Мар-2021 23:07 (спустя 3 месяца 29 дней)

Цитировать

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 03-Июл 23:35
Часовой пояс: UTC + 5