Re: [閒聊] 每日leetcode
2197. Replace Non-Coprime Numbers in Array
這hard?
思路:
先手搓求最大公因數跟最小公倍數的function
再來就照題目去寫
用一個stack紀錄準備回傳數字
當stack的長度=0, 就直接把目前的nums[i]塞到stack裡面
如果stack的長度不等於0, 就求nums[i]跟stack最後一個數字的最大公因數
如果最大公因數=1, 就直接把nums[i]塞到stack裡面
如果最大公因數不等於1, 就把stack最後的數字pop出來
並求nums[i]和該數字的最小公倍數,
一直重複到stack長度=0或是最大公因數=1
golang code :
func replaceNonCoprimes(nums []int) []int {
n := len(nums)
ans := make([]int, 0, n)
for i := 0; i < n; i++ {
num := nums[i]
for len(ans) > 0 {
tmp := ans[len(ans)-1]
g := gcd(tmp, num)
if g == 1 {
break
}
ans = ans[:len(ans)-1]
num = lcm(num, tmp, g)
}
ans = append(ans, num)
}
return ans
}
func gcd(a, b int) int {
if b == 1 {
return 1
}
n := a % b
if n == 0 {
return b
} else {
return gcd(b, n)
}
}
func lcm(a, b, g int) int {
return a * b / g
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1758027235.A.A81.html
討論串 (同標題文章)
完整討論串 (本文為第 1522 之 1549 篇)：