Re: [閒聊] 每日leetcode
679. 24 Game
滿無聊的題目
思路 :
題目限制可能數應該就 4! * 5 * 4^3 = 7680
就backtracking下去找就好了
沒什麼營養
再來就是注意不要除0跟浮點數的精度判斷, 不要直接拿 == 24.0去判斷
golang code :
func judgePoint24(cards []int) bool {
return bk(cards, []float64{}, [4]bool{})
}
func bk(cards []int, cur []float64, visited [4]bool) bool {
if len(cur) == 4 {
return test(cur)
}
for i := 0; i < 4; i++ {
if !visited[i] {
visited[i] = true
if bk(cards, append(cur, float64(cards[i])), visited) {
return true
}
visited[i] = false
}
}
return false
}
func test(tmp []float64) bool {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
for k := 0; k < 4; k++ {
if chk(i, j, k, tmp) {
return true
}
}
}
}
return false
}
func chk(i, j, k int, cards []float64) bool {
a := cal(cal(cal(cards[0], cards[1], i), cards[2], j), cards[3], k)
b := cal(cal(cards[0], cards[1], i), cal(cards[2], cards[3], k), j)
c := cal(cal(cards[0], cal(cards[1], cards[2], j), i), cards[3], k)
d := cal(cards[0], cal(cards[1], cal(cards[2], cards[3], k), j), i)
e := cal(cards[0], cal(cal(cards[1], cards[2], j), cards[3], k), i)
return is24(a)|| is24(b) || is24(c) || is24(d) || is24(e)
}
func cal(a, b float64, symbol int) float64 {
switch symbol {
case 0:
return a + b
case 1:
return a - b
case 2:
return a * b
case 3:
if math.Abs(b) < 1e-9 {
return 1e10
}
return a / b
default:
return 0
}
}
func is24(x float64) bool {
return math.Abs(x-24.0) < 1e-6
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1755516352.A.A4B.html
討論串 (同標題文章)
完整討論串 (本文為第 1503 之 1548 篇)：