Skip to content

cadeYDL/speculative_pattern

Repository files navigation

题意理解

给定一个int类型的数组,判断在经过n(n>=0)次的指定操作后,是否满足为等差、等比、开方等差的规律。

指定操作为,对数组执行判断是否等差、等比、开方等差时的操作 1. 等差操作即为两两之差 2. 等比操作即为两两之商 3. 开方等差操作即为先自身进行开方,然后再算两两之差

实现思路

判断是否满足要求比较简单,只需做对应的判读逻辑即可,比较难的地方在于不满足条件时,可嵌套操作,那么整体的形式会呈现出一颗三叉树的形式,且不同的操作在得出结构还原时需要采取的逆操作是不一致的,所以需要记录满足条件时的路径。 比较自然的想法是用回溯法去处理,但是回溯法很有可能获得路径较长的结果,所以便采用了代码中的bfs的方式,bfs处理上的难点在于如何记录路径,这里便想到了用链表将前面串起来,相当于还原了一颗三叉树只是只有叶子节点到根节点的连接而已。 在处理好路径后,执行对应的逆计算即可。

流程/细节

  1. 用责任链模式将顺序检测串起来,满足任一即为成功,在满足多个时,优先匹配指定的靠前顺序(这里顺序为等差->等比->开方),实现了功能的同时兼顾了拓展性
  2. 在本次的list基础上将一层的操作(合法的)加入队列
  3. 回到步骤1,直到队列为空或者找到满足条件的情况即可
  4. 如果有规律,根据返回的操作路径,进行逆操作,还原出初始的预测值

不足/可能的优化方向

  1. 由于题目中没有给出数据规模和数据范围等信息,所以当得出的结果有一层出现可能会溢出的情况时都会返回无规律,如果实际业务场景或许应该给出更为友好的提示或者在内部用string类型(或者bigint的工具库)处理
  2. 现在整个计算过程都是串行的,或许有一些地方可以并行执行
  3. 结构和命名,或许不是很符合go的规范
  4. 这种找规律的题目,本质上是拟合一个函数然后预测下一个值,或许可以用一些数学上的算法处理(印象中matlab有一个工具箱可以提供类似的功能)

建议

  1. 建议给一下测试数据的数据规模和期望的时空复杂度之类

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages