LeetCode679. 24 Game
2024-08-26 18:14:58
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) = 24
Example 2:
Input: [1, 2, 1, 2]
Output: False
Note:
- 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.
思路
有两种解法,其中一种不是很理解。先来说说另一种方法,Backtracking所有可能。对于给定的四个数,首先从中选两个数,然后对这两个数选择加减乘除这四种操作的一个,得出结果后从剩下的3个数中再选两个,执行一种操作。如此这样重复遍历所有可能即可。
class Solution { boolean res = false;
final double eps = 0.001; public boolean judgePoint24(int[] nums) {
List<Double> arr = new ArrayList<>();
for(int n: nums) arr.add((double) n);
helper(arr);
return res;
} private void helper(List<Double> arr){
if(res) return;
if(arr.size() == 1){
if(Math.abs(arr.get(0) - 24.0) < eps) // java中double类型判断是否相等的方法,不能直接用是否等于0判断
res = true;
return;
}
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < i; j++) {
List<Double> next = new ArrayList<>();
Double p1 = arr.get(i), p2 = arr.get(j);
next.addAll(Arrays.asList(p1+p2, p1-p2, p2-p1, p1*p2));
if(Math.abs(p2) > eps) next.add(p1/p2);
if(Math.abs(p1) > eps) next.add(p2/p1); arr.remove(i);
arr.remove(j);
for (Double n: next){
arr.add(n);
helper(arr);
arr.remove(arr.size()-1);
}
arr.add(j, p2);
arr.add(i, p1);
}
}
}
}
注意上面List集合的两个方法:
void add(int index,
E element)
Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
E remove(int index)
Removes the element at the specified position in this list (optional operation). Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the list.
- Parameters:
index
- the index of the element to be removed- Returns:
- the element previously at the specified position
最新文章
- PHP 之道
- 大熊君JavaScript插件化开发------(第二季)
- WinForm开发框架【细化权限至操作按钮】
- java集合-HashMap
- Oracle function real_st_astext,解决ArcSDE中st_astext函数返回字符串结构异常问题
- 使用Atlas实现MySQL读写分离
- iOS 内存管理机制和循环引用处理方法
- Linux下Memcached-1.4.10安装
- pageControl指示器和图片放大-b
- 集合框架工具类--Collections排序
- integer与int区别以及integer.values()方法详解
- SQL Server - Partition by 和 Group by对比
- xpath解析数据
- [转] ADO.NET调用存储过程带输出参数或返回值
- PHP+ajax实现二级联动
- apache环境之困扰,Rewrite导致无法加载多个不同的.html文件
- Zabbix添加Ping外网IP监控
- 【Python编程:从入门到实践】chapter2 变量和简单数据类型
- MS SQL Server数据库在线管理工具
- vSphere下安装Hyper-V