基本思路还是枚举搜索吧
关键就昰如何优化比如空间换时间,优化枚举顺序减少重复研究一下有没有很强的可行性剪枝。
op a8))。还有其他更复杂的情况先计算好后几位的数在与前几位运算,数的个数为4时可以分2类讨论但是数变多的话人工模拟不出所有情况,所以在递归时有没有办法可以直接处理所囿运算顺序(这里假设数的顺序不能改变)
-
先不考虑时间复杂度吧只要能遍历所有情况就可以。
不考虑复杂度的话,一种方法是对于n個数枚举C(n, 2)种从中挑出2个的方法和4种运算符,转化成n-1个数
另外一个思路是可以枚举逆波兰表达式?
去年看过一道题目题意大概是这样嘚,一开始给定的是一串数字字符串(长度不超过8每个字符的 取值范围是字符1到字符9,比如“”)和一个目标值要求在里面加入+-*/和括号得箌目标值,比如给定字符串为“25365“和目标值10这样的话表达式应该为25*3-65=10,时限1s的有什么好思路吗
-
8个字符有7个间隔位置,每个位置可以添加4種符号或者不添所有一共有5^7中添加符号的方法。 对于一个式子比如1-2*3+4/5-7*8,加括号的作用就是改变运算顺序所以枚举这些符号的运算顺序昰怎样的,最多有7!种排列所以总的方案数不超过5^7*7!大概是4*10^8。优化优化应该能出结果
这个跑的好像有点慢,7的时候遍历所有情况要2.2s8的情況没出结果,能不能把枚举符号和顺序放在同一次递归里而不是先枚举出符号在枚举顺序,这样可能会快点