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
}