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]); } }
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; }
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; };
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; } }
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; } };
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,面向结果编程
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; }
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]); } }
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]; };
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; } }
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 }