小编LTi*_*Tim的帖子

最近,我在接受采访时被问到以下问题.

给定字符串S,我需要找到另一个字符串S2,使得S2是S的子序列,并且S是S2 +反向的子序列(S2).这里'+'表示连接.我需要为给定的S输出最小可能的S2长度.

我被告知这是一个动态编程问题,但我无法解决它.有人可以帮我解决这个问题吗？

编辑-

有没有办法在O(N ²)或更少的情况下执行此操作.

给定数字X,计算该数字的素因子乘积的最有效方法是什么？有没有办法在没有实际分解的情况下做到这一点？注意 - 需要素数因子的乘积(全部是功率统一).

给定一个'n'整数数组，我需要为该数组的每个元素查找以该元素为最大元素的连续子数组的数量。

元素可以重复。

有没有办法做到小于O（n ^ 2）。

O（nlogn）还是O（n）？

Example-
If array is {1,2,3}. Then-
For '1': 1 Such subarray {1}.
For '2': 2 Such subarrays {2},{1,2}
For '3': 3 Such subarrays {3},{2,3},{1,2,3}

我们给了N个对象，其中一个对象恰好具有不同的权重（可以更少或更多）。此外，我们还提供了以下3种类型的M个比较-

1. 重量（A组）<重量（B组）
2. 重量（A组）>重量（B组）
3. 重量（A组）=重量（B组）

其中集合A和集合B（都具有相同数量的对象）是从最初的N个对象开始的对象列表。

给定M这样的比较，如果可能的话，我需要找到重量不同的物体。否则，请说明给定的M个比较列表不足以检测权重不同的列表。

有人可以提出解决这个问题的算法吗？

有没有办法在O(NlogN)时间内找到两个序列中最长的公共子序列？

我在某处读到有一种方法可以使用二进制搜索来实现这一点.

我知道需要O(N ²)时间的dp方法.