首页 > 试题广场 > 算24点
[编程题]算24点
  • 热度指数:53 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出41-10的数字,通过加减乘除,得到数字为24就算胜利。
示例1

输入

[7,2,1,10]

输出

true

说明

7*2+1*10
package main

import "math"
/**
 * 
 * @param arr int整型一维数组 
 * @return bool布尔型
*/
func Game24Points( arr []int ) bool {
    // write code here
    floatNums := make([]float64, len(arr))
    for i := range floatNums {
        floatNums[i] = float64(arr[i])
    }
    return dfs(floatNums)
}

func dfs(nums []float64) bool {
    if len(nums) == 1 {
        return math.Abs(nums[0]-24) < 1e-9
    }
    flag := false
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            n1, n2 := nums[i], nums[j]
            newNums := make([]float64, 0, len(nums))
            for k := 0; k < len(nums); k++ {
                if k != i && k != j {
                    newNums = append(newNums, nums[k])
                }
            }
            flag = flag || dfs(append(newNums, n1+n2))
            flag = flag || dfs(append(newNums, n1-n2))
            flag = flag || dfs(append(newNums, n2-n1))
            flag = flag || dfs(append(newNums, n1*n2))
            if n1 != 0 {
                flag = flag || dfs(append(newNums, n2/n1))
            }
            if n2 != 0 {
                flag = flag || dfs(append(newNums, n1/n2))
            }
            if flag {
                return true
            }
        }
    }
    return false
}
发表于 2021-05-04 10:15:46 回复(0)