[Day 22] Map & leetcode 相關練習

今天又要回來繼續講 Collections 的部分啦

Map

Map 一樣分成

  • 只可讀的 Map
  • 可以修改的 Mutable Map

跟 List, Set 用途不同, Map 特性如下

  • Map 是使用 key, value 來儲存資料的一種資料結構,在其他語言中有時候也被稱為 dictionary (字典),因為 map 原理就是像查字典一樣,利用關鍵字(key),找到相對應的資料解釋。
  • Map 的存取主要就是透過 key。

唯讀的 Map

只能讀取,不能修改內容,Kotlin 的 Map 底層是 Java 的 LinkedHashMap,資料是按照加入順序進行排列的有序集合

mapOf()

創造方式如下,使用 mapOf()

第一種方式是 mapOf(key to value,...)

第二種方式是使用 mapOf(Pair(key, value),...)

// to 省略小數點和括號的寫法
val map = mapOf("A" to 10, "B" to 20, "C" to 30) // {A=10, B=20, C=30}

val mapP = mapOf(Pair("A", 10), Pair("B", 20), Pair("C", 30)) // {A=10, B=20, C=30}

其中 to 這樣的寫法是 Kotlin 中一個叫做 infix 的 function 表示法,之後會再提到

可以修改的 Mutable Map

mutableMapOf()

mutableMapOf("A" to 10, "B" to 20, "C" to 30)

讀取 map

可以使用索引取得 [key] 或是用 get(key) 取得

println(muMap["A"])
println(muMap.get("A"))

getValue() - key 不存在時會拋出 NoSuchElementException

println(muMap.getValue("D"))

getValue(key) 取不到時會拋出異常

Exception in thread "main" java.util.NoSuchElementException: Key D is missing in the map.
at kotlin.collections.MapsKt__MapWithDefaultKt.getOrImplicitDefaultNullable(MapWithDefault.kt:24)

getOrElse(), getOrDefault()

這兩個方法都是找不到時,預設回傳某值

只是 getOrElse() 第二個參數會是個 lambda function,所以可以做更多的處理後再回傳預設值。

getOrDefault() 第二個參數則是直接就是找不到就回傳的預設值。

println(muMap.getOrElse("E") {"no value"})
println(muMap.getOrDefault("E", 50))

新增或修改 map

新增或修改可以使用 +=索引[key]put,當然如果 key 一樣的值會被蓋掉喔!

muMap += "D" to 40
muMap["F"] = 100
muMap.put("A", 5)
println("after add or update muMap: $muMap")

結果會是

after add or update muMap: {A=5, B=20, C=30, D=40, F=100}

putIfAbsent()

putIfAbsent(),如果 key 存在就不會做更新!

muMap.putIfAbsent("A", 100) // "A" 存在所以不更新

putAll()

putAll() 能放入的方式就比較多種,以下是一些例子

https://ithelp.ithome.com.tw/upload/images/20201001/20129902xvZKq4JJQc.png

getOrPut()

能取到就直接用取到的值,取不到就會做第二個參數(lambda function )來更新 map

println("getOrPut:" + muMap.getOrPut("G") { 200 })

刪除 map

可以使用 remove(key) 或 -= key 這樣來操作,很有趣吧!

muMap.remove("G")
muMap -= "D"
println(muMap)

loop

如之前的例子差不多,可以這樣走訪 map

muMap.forEach {
    println(it.key + "," + it.value)
}

muMap.forEach { (key, value) -> println("$key , $value") }

for (entry in muMap) {
    println(entry.key + "," + entry.value)
}

還可以使用解構的方式來走訪

// deconstruct
for ((k,v) in muMap) {
    println("$k,$v")
}

HashMap - hashMapOf()

因為 hashMap 底層是 Java 的 HashMap,是無序的

hashMapOf("A" to 10, "B" to 20, "C" to 30)

LinkedHashMap - linkedMapOf()

其實這個跟 mutableMapOf() 一樣,因為底層都一樣是 LinkedHashMap

linkedMapOf("A" to 10, "B" to 20, "C" to 30)

TreeMap - sortedMapOf()

sortedMapOf() 底層是 Java 的 TreeSet,所以會依資料的自然排序做升序排序

sortedMapOf("A" to 10, "B" to 20, "C" to 30)

emptyMap<類型>()

一個空的 map

emptyMap<String, Int>()

當然一些 java 本身就有的方法,還是可以使用

// java
println("compute:" + muMap.compute("H") { _: String, _: Int? -> 200 })
println("computeIfAbsent:" + muMap.computeIfAbsent("J") { 100 })

Leetcode 1. Two Sum

https://leetcode.com/problems/two-sum/

難度: EASY

既然講到 Map 就來看看最老生常談的 2 sum 吧

這題解法就不多解釋了:) 直接來看 kotlin 下怎麼寫吧!

這個寫法跟 Java 的方式差不多

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    nums.forEachIndexed { idx, value ->
        if (map.containsKey(target - value)) {
            return intArrayOf(map.getValue(target - value), idx)
        }
        map.put(value, idx)
    }
    throw RuntimeException("not found")
}

像這個寫法就比較漂亮

用到了 let 如果有找到 key 就回傳結果,沒找到就不會跑 let 的內容了!

fun twoSumSimple(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    nums.forEachIndexed { idx, value ->
        map[target - value]?.let { return intArrayOf(it, idx) }
        map[value] = idx
    }
    throw RuntimeException("not found")
}

以上就是今天的內容!謝謝大家!

今日練習的程式在這: 請點我