Go 代码
- 总共
4
个数,每次从中挑2
个数进行4
种运算,这部分时间复杂度是4*3*4
,
- 一轮只会,会变成
3
个数,继续从中挑2
个数进行4
种运算,这部分的时间复杂度是3*2*4
,
- 直到最后剩下
1
个数
- 总时间复杂度=
4x3*4 * 3*2*4 * 2*1*4 = 9216
,因此可以dfs
- ps: 浮点数要考虑精度,判断浮点数相等
double x == a
等价于 x
和a
的差的绝对值要小于一个很小的数1e-8
func judgePoint24(nums []int) bool {
tmp := []float64{}
for i := 0; i < len(nums); i ++ {
tmp = append(tmp, float64(nums[i]))
}
return dfs(tmp)
}
func fabs(x float64) float64 {
if x < 0 {
return -x
}
return x
}
func get(nums[]float64, x, y int, combine float64) []float64 {
res := []float64{}
for i := 0; i < len(nums); i ++ {
if i == x || i == y {
continue
}
res = append(res, nums[i])
}
res = append(res, combine) // 这里不用考虑插入的顺序,是因为暴搜可以不重不漏得搜完所有的
return res
}
func dfs(nums[]float64) bool {
n := len(nums)
if (n == 1) {
return fabs(nums[0] - 24.0) < 1e-8
} else {
for i := 0; i < n; i ++ {
for j := 0; j < n; j ++ {
if i != j {
a := nums[i]
b := nums[j]
if dfs(get(nums, i, j, a + b)) {
return true
}
if dfs(get(nums, i, j, a - b)) {
return true
}
if dfs(get(nums, i, j, a * b)) {
return true
}
if b > 0 && dfs(get(nums, i, j, a / b)) {
return true
}
}
}
}
return false
}
}
C ++ 代码
class Solution {
public:
bool judgePoint24(vector<int>& nums) {
vector<double> a(nums.begin(), nums.end());
return dfs(a);
}
vector<double> get(vector<double> nums, int i, int j, double t) {
vector<double> res;
for (int u = 0; u < nums.size(); u ++)
if (u != i && u != j) res.push_back(nums[u]);
res.push_back(t);
return res;
}
bool dfs(vector<double> nums) {
int n = nums.size();
if (n == 1) {
return fabs(nums[0] - 24) < 1e-8;
} else {
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (i != j) {
double a = nums[i];
double b = nums[j];
if (dfs(get(nums, i, j, a + b))) return true;
if (dfs(get(nums, i, j, a - b))) return true;
if (dfs(get(nums, i, j, a * b))) return true;
if (b && dfs(get(nums, i, j, a / b))) return true;
}
return false;
}
}
};