[Day 9] 數字 ＆ 位運算 ＆ leetcode 相關練習
今天來講數字， Kotlin 的數字運算跟 Java 很類似，但多了很多有用的內建 API
字串轉數字
這裡把字串 3.14 轉成 Double，這很簡單
val numStr = "3.14"
val num0 = numStr.toDouble()
println(num0) // 3.14
但如果要把 "3.14" 字串直接轉 Int 會發生 NumberFormatException
這時候可以使用 toIntOrNull() 當無法成功轉型時會回傳 null，這裡還用了貓王運算子 ?:，當 null 的時候預設給 0，所以結果會是 0
// val num10 = numStr.toInt() // 會發生 NumberFormatException
val num1 = numStr.toIntOrNull() ?: 0
println(num1) // 0
像這樣無法轉型的狀況下，也是預設 0
val numStr2 = "abc"
val num2 = numStr2.toIntOrNull() ?: 0
val num3 = numStr2.toBigDecimalOrNull() ?: 0
println(num2) // 0
println(num3) // 0
浮點數處理
像下面的例子，如果是 Double 相減的狀況下，會發現結果不如預期，會變成 4.569999999999999
val x = 10.1
val y = 5.53
val result = x - y
println(result) // 4.569999999999999
如果希望維持小數點兩位的結果的話，可以使用 format() 來達成
println("%.2f".format(result)) // 4.57
roundToInt() 則可以四捨五入取到整數
println(result.roundToInt()) // 5
BigDecimal
那當然更好處理浮點數的方式是使用 BigDecimal，尤其是處理金額的時候
這裡可以看到結果處理得很好，在 Kotlin 裡面 BigDecimal 甚至可以直接用 - 或 ＋ 號來做運算！不用呼叫方法了！
println("BigDecimal demo...")
println(BigDecimal.valueOf(x).minus(BigDecimal.valueOf(y))) // 4.57
println(BigDecimal.valueOf(x) - BigDecimal.valueOf(y)) // 4.57
println(BigDecimal.valueOf(x).plus(BigDecimal.valueOf(y))) // 15.63
println(BigDecimal.valueOf(x) + BigDecimal.valueOf(y)) // 15.63
連比較值也是！可以直接用 大於小於等於 符號！超方便的！
println(BigDecimal.valueOf(100.123).compareTo(BigDecimal.ZERO) > 0) // true
println(BigDecimal.valueOf(100.123) > BigDecimal.ZERO) // true
最後再來提一下，BigDecimal.valueOf() 和 BigDecimal() 的結果是不一樣的
println(BigDecimal(x) - BigDecimal(y)) //4.56999999999999939603867460391484200954437255859375
來看原始碼，會發現 BigDecimal.valueOf() 會先把輸入值轉成字串在傳入 BigDecimal()，所以能夠保持原本的輸入值得小數點精度
但 BigDecimal() 預設是不特別保留精度
所以如果要維持原本的輸入值的小數點精度，建議使用 BigDecimal().valueOf()
可以參考官網更多的 BigDecimal API
位元運算子 (bit operator)
最後來談談位運算，說真的以前覺得這好像沒啥用，後來才發現這東西很神啊！
舉例子來說在 Java 裡面 PriorityQueue 的原始碼，裡面就大量用到了位運算
像是
Java 中 右移運算子是 >>，左移運算子是 <<
為什麼要用位運算呢？
下面用 Kotlin 的寫法來看，
shl(1) 代表左移一位，也就是乘 2
shr(1) 代表右移一位，也就是除2
// bit operator
println(42.shl(1)) // var43 = 42 << 1; // 84
println(42.shr(1)) // var43 = 42 >> 1; // 21
println(42 shr 1) // var43 = 42 >> 1; // 21
因為位運算就是把數值都化為 2 進制，也就是 0 跟 1，所以移動一位就是 2的倍數 或 1/2，移動2位就是 2*2 的倍數 或 1/4。
位運算的方式是最有效率的，而且在面對大數字的時候，能夠避免數字的 overflow
這裡用一題 leetcode 的 binary search 來解釋
Leetcode 153. Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
難度： MEDIUM
原題是在說在原本有一個排序過的 array 在旋轉後，在這旋轉過的 arrya 中，找到其中最小的數字
解題概念: 因為這個 array 在排序後卻被旋轉了，以 [3, 4, 5, 1, 2] 這例子，在原本有順序的狀況下，左邊都小於右邊的數字，但是到 5 和 1 的時候，卻變成左邊大於右邊了，所以這題可以用 binary search 的方式，找到 nums[mid] > nums[right] (5 > 2)的狀況，最小的結果就會是 nums[mid+1] (也就是 1)
fun findMin(nums: IntArray): Int {
var left = 0
var right = nums.size - 1
while (left < right) {
var mid = (left + right).shr(1)
if (nums[mid] > nums[right]) {
left = mid + 1
} else {
right = mid
}
}
return nums[left]
}
var mid = (left + right).shr(1) 這裡取中間的 index 就使用了位運算
一般來說怕數字太大 overflow 的話，不使用位運算，就得寫成 var mid = left + (right - left)/2 但這樣的寫法比較不直觀。
再舉另一個位運算的題目
Leetcode 136. Single Number
https://leetcode.com/problems/single-number/
難度: EASY
這題要在 array 中找出只出現一次的數字(其他數字會出現 2次)，這時候可能會想到要用 map 跑一個 for 去存，在判斷哪個數字是一個？這樣會是 O(n) 的時間複雜度和 O(n) 的空間複雜度(用了map)
用位運算可以不用額外的空間！
這裡跑了一個 for 針對每個元素做 xor，因為只有一個數字會出現一次，其他都是出現兩次，所以做 xor，出現 2次的數字的位元會抵消，最後只留下出現一次的數字的位元組！
以 [2, 2, 5] 為例子， xor 定義是同樣的數字會變 0，不同會變 1
2 xor 2 會變成 0010 xor 0010 = 0000 (因為 2 和 2 都一樣）
0 xor 5 會變成 0000 xor 0101 = 0101 結果還是 5
fun singleNumber(nums: IntArray): Int {
var result = 0;
nums.forEach {
result = result.xor(it); //do xor
}
return result;
}
更多的 bit API 可以參考官網 https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-int/ 搜尋 bit 關鍵字
數字的部分就講到這裡啦！謝謝大家，我們明天見！
今日練習的程式在這: 請點我