- 这道题体面要求是四个数,填入+、-、*、/和(),来使其结果为24,实际上可以看成一个组合问题,比如从四个数中任意取出2个,算出和,在与剩下的两个数组合到一起,重复这个过程,如果最后能得到24,就返回True,否则返回False,比较简单。代码如下:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
boolean flag = false;
public void search(List<Double> nums) {
if(flag) return;
if (nums.size() == 1) {
if (Math.abs(nums.get(0)-24) < 0.000001) flag = true;
return;
}
int nums_size = nums.size();
for (int i = 0; i < nums_size; i++) {
for (int j = i + 1; j < nums_size; j++) {
double ni = nums.get(i), nj = nums.get(j);
ArrayList<Double> temp_nums = new ArrayList<>();
for (int k = 0; k < nums_size; k++) {
if( k != i && k != j) temp_nums.add(nums.get(k));
}
List<Double> temp_res = new ArrayList<>();
temp_res.addAll(Arrays.asList(ni + nj, ni * nj, ni - nj, nj - ni, ni / nj, nj / ni));
for (double t : temp_res) {
temp_nums.add(temp_nums.size(), t);
search(temp_nums);
temp_nums.remove(temp_nums.size()-1);
}
}
}
}
public boolean judgePoint24(int[] nums) {
List<Double> nums_d = new ArrayList<>();
for (int i = 0; i < nums.length; i++) nums_d.add((double) nums[i]);
search(nums_d);
return flag;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {1, 1, 1, 1};
// int[] nums = {4, 1, 8, 7};
System.out.println(s.judgePoint24(nums));
}
}
- 需要注意的点是List的Remove和Add操作,Remove操作时,一定要是准确的index,不能越界,Add时,Add的Index可以是List Size,表示加在最后一个。