1

对于 google codeJam 资格认证，问题之一是找出两个给定整数之间有多少“回收对”。

这是我的解决方案，但对于大型数据输入集来说还不够快。给定 @a = 10, @b = 200000 之类的东西，它开始变慢。

我认为我的解决方案是 O(2^n) （我还没有对大 O 分析有扎实的了解），这太可怕了。我想知道是否有一种标准方法可以用更快的算法迭代这样的两个循环？

def getPairs
    (@a..@b).each do |n|
      (n..@b).each do |m|
        if (containsSame(n,m)) && (isMatch(@a, n, m, @b))
          @recycledPairs += 1
        end
      end
    end
  end

编辑：来自Google CodeJam 网站：

假设一对不同的正整数 (n, m) 被回收，如果您可以通过将一些数字从 n 的后面移动到前面而不改变它们的顺序来获得 m。例如，(12345, 34512) 是一个循环对，因为您可以通过将 345 从 12345 的末尾移动到前面来获得 34512。请注意，n 和 m 必须具有相同的位数才能成为循环对。n 和 m 都不能有前导零。

4

3 回答 3

3

您可以阅读官方对此问题的分析以获得正确的解决方案。

基本上，解决方案是计算所有大于 的不同旋转n，但不大于B每个n。

于 2012-04-15T12:55:36.430 回答
1

描述说“请注意，n 和 m 必须具有相同的位数才能成为循环对。”

您的内部循环没有考虑到这一点。如果@a = 2 和@b = 20,000，那么你可以切掉整个内循环块。如果n是两位数，那么您只需要测试 的两位数值m。仔细查看内循环的上限。

于 2012-04-15T10:53:30.403 回答
1

从声明中：max b 最多为 2*10^6。与所有代码堵塞问题一样，您需要进行多重测试。

第 1 步：预计算。对于每个数字 n = [1..maxb]，保存所有从它循环的数字，严格小于它（每个不超过 7），例如

10 - 1
321 - 132, 213

第 2 步：针对每个测试。从 A 到 B 遍历每个数字，并计算 A 和 B 之间“循环”的数量。

时间复杂度：步骤 1 对每个数字起作用（位数），即 O(ln n)。你必须做 b 次。总而言之O（b * ln b）。第 2 步也是如此。这在大型测试用例上的工作时间不到一秒。

于 2012-04-15T10:59:35.790 回答