NC350. 24点游戏算法
描述
示例1
输入:
[7,2,1,10]
输出:
true
说明:
7*2+1*10C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-07-26
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return bool布尔型
*/
bool is24(vector<int>& n, int num)
{
if(num == 24) return true;
for(int i=0; i<n.size(); ++i){
int tmp = n[i];
n.erase(n.begin() + i);
if(is24(n, tmp)) return true;
if(is24(n, num+tmp)) return true;
if(is24(n, num-tmp)) return true;
if(is24(n, tmp-num)) return true;
if(is24(n, num*tmp)) return true;
if(num!=0 && num%tmp==0 && is24(n, num/tmp)) return true;
if(num!=0 && tmp%num==0 && is24(n, tmp/num)) return true;
n.insert(n.begin() + i, tmp);
}
return false;
}
bool Point24(vector<int>& nums) {
return is24(nums, 0);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-03-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return bool布尔型
*/
double get(double x,double y,int flag)
{
if(flag == 0) return x+y;
else if(flag == 1) return x-y;
else if(flag == 2) return x*y;
return x/y;
}
bool dfs(vector<double>& a)
{
int n = a.size();
if(n==0) return false;
if(n==1) return fabs(a[0]-24.0)<1e-6;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j) continue;
vector<double> temp;//存放剩余数字
for(int k=0;k<n;k++)
{
if(k==i||k==j) continue;
temp.push_back(a[k]);
}
//进行四种运算
for(int k=0;k<4;k++)
{
double result = get(a[i],a[j],k);
temp.push_back(result);
if(dfs(temp)) return true;
temp.pop_back();//回溯
}
}
}
return false;
}
bool Point24(vector<int>& nums) {
// write code here
vector<double> res(nums.begin(),nums.end());
return dfs(res);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 476KB, 提交时间: 2022-07-21
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return bool布尔型
*/
bool dfs(vector<double>& res)
{
int n=res.size();
if(n==0) return false;
if(n==1 && res[0]==24) return true;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j)
{
vector<double> new_res;
for(int k=0;k<n;k++)
{
if(k!=i&&k!=j){
new_res.push_back(res[k]);
}
}
for(int op=0;op<4;++op)
{
if(op==0)
new_res.push_back(res[i]+res[j]);
else if(op==1)
new_res.push_back(res[i]-res[j]);
else if(op==2)
new_res.push_back(res[i]*res[j]);
else if(op==3){
if(res[j]==0) continue;
new_res.push_back(res[i]/res[j]);
}
if(dfs(new_res)) return true;
new_res.pop_back();
}
}
}
}
return false;
}
bool Point24(vector<int>& nums) {
// write code here
vector<double> res(nums.begin(),nums.end());
return dfs(res);
}
};
Go 解法, 执行用时: 3ms, 内存消耗: 1108KB, 提交时间: 2022-06-30
package main
import "math"
func Point24(nums []int) bool {
a := make([]float64, len(nums))
for i := range a {
a[i] = float64(nums[i])
}
return dfs(a)
}
func dfs(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24) < 1e-9
}
f := false
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
x, y := nums[i], nums[j]
b := make([]float64, 0, len(nums))
for k := 0; k < len(nums); k++ {
if k != i && k != j {
b = append(b, nums[k])
}
}
f = f || dfs(append(b, x+y))
f = f || dfs(append(b, x-y))
f = f || dfs(append(b, y-x))
f = f || dfs(append(b, x*y))
if x != 0 {
f = f || dfs(append(b, y/x))
}
if y != 0 {
f = f || dfs(append(b, x/y))
}
if f {
return true
}
}
}
return false
}
Go 解法, 执行用时: 3ms, 内存消耗: 1140KB, 提交时间: 2022-07-26
package main
//import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return bool布尔型
*/
func Point24(nums []int) bool {
// write code here
first := nums[0]
for i := 1; i < len(nums); i++ {
// 两两进行计算
if i == 1 {
res1 := calResult(first, nums[1])
res2 := calResult(nums[2], nums[3])
for _, v1 := range res1 {
for _, v2 := range res2 {
if isTarget(calResult(v1, v2), 24) {
return true
}
}
}
}
if i == 2 {
res1 := calResult(first, nums[2])
res2 := calResult(nums[1], nums[3])
for _, v1 := range res1 {
for _, v2 := range res2 {
if isTarget(calResult(v1, v2), 24) {
return true
}
}
}
}
if i == 3 {
res1 := calResult(first, nums[3])
res2 := calResult(nums[1], nums[2])
for _, v1 := range res1 {
for _, v2 := range res2 {
if isTarget(calResult(v1, v2), 24) {
return true
}
}
}
}
}
return false
}
func calResult(a, b int) []int {
result := make([]int, 0)
result = append(result, a+b)
result = append(result, a-b)
result = append(result, b-a)
result = append(result, b*a)
if b != 0 {
result = append(result, a/b)
}
if a != 0 {
result = append(result, b/a)
}
return result
}
func isTarget(input []int, target int) bool {
for i := 0; i < len(input); i++ {
if input[i] == target {
return true
}
}
return false
}