The 24 Game Algorithm using Depth First Search
- 时间:2020-09-23 15:11:59
- 分类:网络文摘
- 阅读:94 次
You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.
Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24Example 2:
Input: [1, 2, 1, 2]
Output: FalseNote:
The division operator / represents real division, not integer division. For example, 4 / (1 – 2/3) = 12.
Every operation done is between two numbers. In particular, we cannot use – as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 – 1 – 1 – 1 is not allowed.You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.
In 24 Point Poker Game Calculator, the complete list of the 24-game solutions has been implemented using PHP, via the bruteforce algorithm by iterating all possible solutions (which might contain duplicates such as communitive laws a+b=b+a).
Simple Depth First Search Algorithm to Check if 4 cards can make up to 24
As there are only four numbers, and four operators which are addition, subtraction, multiplication and divisor, the total solution space is constant.
The Depth First Search Algorithm will operate on a vector. The algorithm will bruteforce all pairs of the numbers in the vector, and apply four operators on these two numbers, push the result to the vector, and recursively calling itself until there is only 1 number in the vector – which we can easily check if it is 24 – remember, the types in the vector should be double i.e. converting the input integers to the doubles first.
As multiplication and additions are communitive so that we can slightly speed the process up by ignoring the pairs by comparing the indices.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | class Solution { public: bool judgePoint24(vector<int>& nums) { vector<double> arr; for (const auto &n: nums) { arr.push_back(n); } return search(arr); } private: bool search(vector<double>& nums) { if (nums.empty()) return false; if (nums.size() == 1) return abs(nums[0] - 24) < 1e-6; for (int i = 0; i < nums.size(); ++ i) { for (int j = 0; j < nums.size(); ++ j) { if (i == j) continue; vector<double> nums2; for (int k = 0; k < nums.size(); ++ k) { if (k != i && k != j) { nums2.push_back(nums[k]); } } for (int k = 0; k < 4; ++ k) { if ((k < 2) && (j > i)) continue; // ignoring communitive additions and multiplication switch (k) { case 0: nums2.push_back(nums[i] + nums[j]); break; case 1: nums2.push_back(nums[i] * nums[j]); break; case 2: nums2.push_back(nums[i] - nums[j]); break; case 3: if (nums[j] != 0) { nums2.push_back(nums[i] / nums[j]); } else { continue; } break; } if (search(nums2)) return true; nums2.pop_back(); } } } return false; } }; |
class Solution { public: bool judgePoint24(vector<int>& nums) { vector<double> arr; for (const auto &n: nums) { arr.push_back(n); } return search(arr); } private: bool search(vector<double>& nums) { if (nums.empty()) return false; if (nums.size() == 1) return abs(nums[0] - 24) < 1e-6; for (int i = 0; i < nums.size(); ++ i) { for (int j = 0; j < nums.size(); ++ j) { if (i == j) continue; vector<double> nums2; for (int k = 0; k < nums.size(); ++ k) { if (k != i && k != j) { nums2.push_back(nums[k]); } } for (int k = 0; k < 4; ++ k) { if ((k < 2) && (j > i)) continue; // ignoring communitive additions and multiplication switch (k) { case 0: nums2.push_back(nums[i] + nums[j]); break; case 1: nums2.push_back(nums[i] * nums[j]); break; case 2: nums2.push_back(nums[i] - nums[j]); break; case 3: if (nums[j] != 0) { nums2.push_back(nums[i] / nums[j]); } else { continue; } break; } if (search(nums2)) return true; nums2.pop_back(); } } } return false; } };
Special case has to be handled when checking the divisor being zero. The complexity of the algorithm is O(1) an the space complexity is also O(1) as they both do not grow as the size of the problem grows.
Remember to play at: 24 Point Poker Game Calculator
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:小羊小鹿和小熊共同修建一个小水池 wordpress 文章发布出现“定时发布失败”的原因及解决方法 wordpress 数据库表前缀修改方法 wordpress技巧:为标签链接添加rel=”nofollow”属性 wordpress 4.0 新增自定义图标插件安装 WordPress在线文件管理插件:FileBrowser 设置wordpress文章标题高亮的代码 免插件实现WordPress文章置顶的方法 让新浪微博变身外链图床的wordpress插件:微博图床 三款自动翻译文章标题为英文的wordpress插件介绍与比较
- 评论列表
-
- 添加评论