Kotlin Leetcode - 1979. Find Greatest Common Divisor of Array

題目連接

class Solution {
    fun findGCD(nums: IntArray): Int {

    }
}

解題思路

這一題考的是對陣列的處理

利用 nums.min() 和 nums.max()

搭配輾轉相除法

可以很簡單的解決這一題

Kotlin 參考解答

點擊展開解答

class Solution {
    fun findGCD(nums: IntArray): Int {
        return gcd(nums.min()!!, nums.max()!!)
    }
    fun gcd(p: Int, q: Int): Int {
        return if (q == 0) p else gcd(q, p % q)
    }
}

這邊的遞迴呼叫僅在最後一行，符合尾遞迴的格式，所以我們可以加上 tailrec 關鍵字

class Solution {
    fun findGCD(nums: IntArray): Int {
        return gcd(nums.min()!!, nums.max()!!)
    }
    tailrec fun gcd(p: Int, q: Int): Int {
        return if (q == 0) p else gcd(q, p % q)
    }
}

另外我們可以使用迴圈來實作輾轉相除法的邏輯

class Solution {
    fun findGCD(nums: IntArray): Int {
        var numList = mutableListOf(nums.max()!!, nums.min()!!)
        while (numList[1] != 0) {
            numList = numList.run { mutableListOf(numList[1], numList[0] % numList[1])}
        }
        return numList[0]
    }
}

使用 Pair 來簡化我們撰寫的邏輯

class Solution {
    fun findGCD(nums: IntArray): Int {
        var numPair = nums.max()!! to nums.min()!!
        while (numPair.second != 0) {
            numPair = numPair.run { second to first % second }
        }
        return numPair.first
    }
}

---

回到 leetcode 列表