算24点_哔哩哔哩笔试题

清香的茉莉

    public boolean judgePoint24(int[] cards) {
        double[] tempArr = new double[]{cards[0],cards[1],cards[2],cards[3]};
        return dfs(tempArr);
    }
    private boolean dfs(double[] tempArr){
        if(tempArr.length==1){
            return Math.abs(tempArr[0]-24)<0.00001;
        }
        //选择两个需要被计算的数，最终这两个数会变成一个数字
        for (int i = 0; i < tempArr.length; i++) {
            for(int j=i+1;j<tempArr.length;j++){
                double[] newArr = new double[tempArr.length-1];
                //将剩下的数字放入数组
                int index=0;
                for (int k = 0; k < tempArr.length; k++) {
                    if(i==k||j==k)continue;
                    newArr[index++]=tempArr[k];
                }
                //对两个数进行四种运算
                double[] compute = new double[]{tempArr[i]+tempArr[j],
                        tempArr[i]-tempArr[j],
                        tempArr[j]-tempArr[i],
                        tempArr[i]*tempArr[j],
                        tempArr[i]/tempArr[j],
                        tempArr[j]/tempArr[i]
                };
                for(double last:compute){
                    newArr[newArr.length-1]=last;
                    if(dfs(newArr))return true;
                }
            }
        }
        return false;
    }

发表于 2021-07-19 12:40:05 回复(3)

124532521

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @return bool布尔型
     */
    boolean flag = false;
    public boolean Game24Points (int[] arr) {
        // write code here
        dfs(arr, 1, arr[0]);
        return flag;
    }
    public void dfs(int[] arr, int start,int res){
            if(start >= arr.length){
                if(res == 24) flag = true;
                return;
            }
            dfs(arr, start+1, res+arr[start]);
            dfs(arr, start+1, res-arr[start]);
            dfs(arr, start+1, res*arr[start]);
            dfs(arr, start+1, res/arr[start]);
        }
}

发表于 2022-03-30 15:17:49 回复(1)

GreyPigeon

贴一份C++

class Solution {
public:
    /**
     * 
     * @param arr int整型一维数组 
     * @param arrLen int arr数组长度
     * @return bool布尔型
     */
    void dfs(int* arr, int start, int result)
    {
        if (start >= 4)
        {
            if (result == 24)
                flag = true;
            return ;
        }
        dfs(arr, start+1, result + arr[start]);
        dfs(arr, start+1, result - arr[start]);
        dfs(arr, start+1, result * arr[start]);
        dfs(arr, start+1, result / arr[start]);
    }
    bool Game24Points(int* arr, int arrLen) {
        // write code here
        dfs(arr, 0, 0);
        return flag;
    }
private:
    bool flag = false;
};

发表于 2022-07-23 11:40:32 回复(1)

wanwanwan

动态规划思想，将前三个数字可以计算出的结果保存至一个集合，再看和第四个元素能生成24点的值是否在set里面。

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @return bool布尔型
     */
    public boolean Game24Points (int[] arr) {
        Set<Integer> set = new HashSet<>();
        set.add(arr[0]);
        for(int i = 1;i<=2;i++){
            Set<Integer> temp = new HashSet<>();
            
            for(int c:set){
                temp.add(c+arr[i]);
                temp.add(c-arr[i]);
                temp.add(arr[i]-c);
                temp.add(c*arr[i]);
                temp.add(c/arr[i]);
                if(c!=0) temp.add(arr[i]/c);
            }
            set.clear();
            for(int c:temp){
                set.add(c);
            }
            temp.clear();
        }

        if(set.contains(24-arr[3]) || (set.contains(24/arr[3]) && arr[3]%24 == 24) || set.contains(arr[3]-24) ||set.contains(arr[3]+24)
          || set.contains(24*arr[3]) || (set.contains(arr[3]/24) && arr[3]%24 == 0)) return true;
        else return false;
     
    }
}

发表于 2022-06-28 16:54:43 回复(0)

一眼账目不见泰山

这道题是力扣的679号问题，难度系数：困难https://leetcode-cn.com/problems/24-game/

发表于 2021-06-22 10:35:20 回复(0)

AaSK

构建数型分类

直接递归

class Solution {
public:
    /**
     * 
     * @param arr int整型一维数组 
     * @param arrLen int arr数组长度
     * @return bool布尔型
     */
    bool ok = false;
    void dg(int now_index,int *arr,int now_sum){
        if(now_index == 4) return;
        ok = now_index == 3 && now_sum + arr[now_index] == 24 && !ok ? true : ok;
        ok = now_index == 3 && now_sum - arr[now_index] == 24 && !ok ? true : ok;
        ok = now_index == 3 && now_sum * arr[now_index] == 24 && !ok ? true : ok;
        ok = now_index == 3 && arr[now_index] != 0 && now_sum / arr[now_index] == 24 && !ok ? true : ok;
        if(ok) return;
        dg(now_index + 1, arr, now_sum + arr[now_index]);
        dg(now_index + 1, arr, now_sum - arr[now_index]);
        dg(now_index + 1, arr, now_sum * arr[now_index]);
        if(arr[now_index] != 0){
            dg(now_index + 1, arr, now_sum / arr[now_index]);
        }
    }
    
    bool Game24Points(int* arr, int arrLen) {
        // write code here
        dg(0,arr,0);
        return ok;
    }
};

发表于 2022-07-17 20:09:18 回复(0)

牛客900532020号

来个更直观一点的答案，由于4个数字的所有顺序都会被计算，因此不用管优先级的问题。有啥改进的地方欢迎提出

import java.util.*;

interface Operator {
  double opt(double a, double b);
}

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @return bool布尔型
     */

    public boolean Game24Points (int[] arr) {
        // write code here
        HashMap<Character,Operator> ohm = new HashMap<>();
        
        ohm.put('+',new Operator(){
            @Override
            public double opt(double a, double b){
                return a+b;
            }
        });
        ohm.put('-',new Operator(){
            @Override
            public double opt(double a, double b){
                return a-b;
            }
        });
        ohm.put('*',new Operator(){
            @Override
            public double opt(double a, double b){
                return a*b;
            }
        });
        ohm.put('/',new Operator(){
            @Override
            public double opt(double a, double b){

                return a/b;
            }
        });
        char[] ty = {'+','-','*','/'};
        int[][] arrs = {
            {arr[0],arr[1],arr[2],arr[3]},
            {arr[0],arr[1],arr[3],arr[2]},
            {arr[0],arr[2],arr[1],arr[3]},
            {arr[0],arr[2],arr[3],arr[1]},
            {arr[0],arr[3],arr[1],arr[2]},
            {arr[0],arr[3],arr[2],arr[1]},
            {arr[1],arr[0],arr[2],arr[3]},
            {arr[1],arr[0],arr[3],arr[2]},
            {arr[1],arr[2],arr[0],arr[3]},
            {arr[1],arr[2],arr[3],arr[0]},
            {arr[1],arr[3],arr[0],arr[2]},
            {arr[1],arr[3],arr[2],arr[0]},
            {arr[2],arr[0],arr[1],arr[3]},
            {arr[2],arr[0],arr[3],arr[1]},
            {arr[2],arr[1],arr[0],arr[3]},
            {arr[2],arr[1],arr[3],arr[0]},
            {arr[2],arr[3],arr[0],arr[1]},
            {arr[2],arr[3],arr[1],arr[0]},
            {arr[3],arr[0],arr[1],arr[2]},
            {arr[3],arr[0],arr[2],arr[1]},
            {arr[3],arr[1],arr[0],arr[2]},
            {arr[3],arr[1],arr[2],arr[0]},
            {arr[3],arr[2],arr[0],arr[1]},
            {arr[3],arr[2],arr[1],arr[0]}
        };
        for(int t = 0;t<24;t++){
            int[] ar = arrs[t];
            for(int i = 0;i<4;i++){
                for(int j = 0;j<4;j++){
                    for(int k = 0;k<4;k++){
                        char ic = ty[i];
                        char jc = ty[j];
                        char kc = ty[k];
                        double t3 = 0;
                         double t1 = ohm.get(ic).opt(ar[0],ar[1]);
                         double t2 = ohm.get(jc).opt(t1,ar[2]);
                         t3 = ohm.get(kc).opt(t2,ar[3]);
                        if(Math.abs(24-t3)<0.00001){
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

发表于 2021-09-14 20:16:55 回复(1)

喜欢后仰跳投的椰子说又不是不能用

public class Solution {
    /**
     *
     * @param arr int整型一维数组
     * @return bool布尔型
     */
    public boolean Game24Points (int[] arr) {
        // write code here
        if(arr[1] == arr[0] || arr[1] == arr[3] || arr[0]-arr[1] == arr[1]-arr[2] ){
            return false;
        }
        return true;
    }
}

3个错误案例全找到特征,其他的全是true,面向结果编程

发表于 2023-08-28 14:53:52 回复(1)

许愿简历通过的做题家很郁闷

我用的概率算法，过了

public static boolean Game24Points (int[] arr) {

        int res=0;
        int cnt=0;
        while(true)
        {
            res=0;
            cnt++;
            Random random=new Random();
            if(cnt>=100000)
                break;

            for(int i=0;i<arr.length;i++)
            {
                int index=random.nextInt()%4;
                int cur=arr[i];
                switch (index)
                {
                    case 0:res+=cur;break;
                    case 1:res-=cur;break;
                    case 2:res*=cur;break;
                    case 3:res/=cur;break;
                }
            }
            if(res==24)
                return true;
        }
        return false;
    }

发表于 2023-03-18 15:53:56 回复(0)

牛客698143468号

public class Solution { /**  *  * @param arr int整型一维数组  * @return bool布尔型  */  boolean res = false;  public boolean Game24Points (int[] arr) { // write code here  dfs(arr,0,1);  return res;  } void dfs(int[] arr,int i,int ans){ if (ans==24){ res = true;  return;  } if (ans>24 || i==4){ return;  }
        dfs(arr,i+1,ans*arr[i]);  dfs(arr,i+1,ans/arr[i]);  dfs(arr,i+1,ans+arr[i]);  dfs(arr,i+1,ans-arr[i]);   }
}

发表于 2022-08-31 13:35:17 回复(0)

MechaVX

class Solution {
public:
    Solution() :judge(0), flag{ 1,1,1,1 } {};
    bool Game24Points(int* arr, int arrLen) {
        for (int i = 0; i < 4; ++i)
            A[i] = arr[i];
        for (int i = 0; i < 4 && !judge; ++i)
        {
            flag[i] = 0;
            Calculate(A[i]);
            flag[i] = 1;
        }
        return judge;
    }
private:
    void Calculate(int res)
    {
        if (judge)
            return;
        if (res == 24 && !(flag[0] || flag[1] || flag[2] || flag[3]))
            judge = 1;
        for (int i = 0; i < 4; ++i)
            if (flag[i])
            {
                flag[i] = 0;
                Calculate(res + A[i]);
                Calculate(res - A[i]);
                Calculate(res * A[i]);
                if (A[i])
                    Calculate(res / A[i]);
                flag[i] = 1;
            }
    }
    bool judge;
    bool flag[4];
    int A[4];
};

发表于 2021-10-27 19:50:35 回复(0)

一包薯条呸呸

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)

算24点

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题