2197. Replace Non-Coprime Numbers in Array | LeetCode

題目

https://leetcode.com/problems/replace-non-coprime-numbers-in-array/?envType=daily-question&envId=2025-09-16

日期

2025/09/16

想法

資料結構：Stack

根據題意，操作 Array 會有連鎖反應 (chain reaction) ，所以宜用 stack 儲存運算結果。每一次的核心演算法結束後，就把結果推進這個 stack 。

條件：相鄰兩元素

根據題意需要針對相鄰兩元素運算。所以不只要對下一個元素進行 GCD （最大公因數）判斷以及 LCM （最小公倍數）運算，也要對前一個元素進行運算。

這邊的「前一個元素」就是指 stack 的 top 元素。

核心演算法的地方就可以簡化成一率和 stack top 比對，比對直到沒有元素可以 pop 出來或是兩者最大公因數為 1 。

程式碼

class Solution {
    func replaceNonCoprimes(_ nums: [Int]) -> [Int] {
        var stack = [Int]()
        
        for num in nums {
            var current = num
            
						// 核心處理
            while let last = stack.last,
                  getGcd(current, last) > 1 {
                let top = stack.removeLast()
                current = getLcm(current, top)
            }
            
            stack.append(current)
        }
        
        return stack
    }
    
    private func getGcd(_ a: Int, _ b: Int) -> Int {
        var a = a
        var b = b
        while b != 0 {
            let temp = b
            b = a % b
            a = temp
        }
        return a
    }
    
    private func getLcm(_ a: Int, _ b: Int) -> Int {
    	  a * b / getGcd(a, b)
    }
}