C++ 中范围 [l, r] 内的对称数字数量（对称数字 III）

Strobogrammatic 数是指将数字旋转180度后看起来相同的数字，所以它们上下颠倒后看起来是一样的。例如，69、88和818是strobogrammatic的，因为即使我们将它们翻转，它们看起来仍然是一样的。

然而，如果我们取一个像123或45这样的数字并将其翻转，它看起来会不同。因此，像这样的数字不是strobogrammatic的。如果我们得到任意两个数字l和r（包括边界），我们就必须找出l和r之间（包括l和r）有多少个strobogrammatic数。为了解决这个问题，我们需要生成所有可能的strobogrammatic数，然后在验证每个数字是否是strobogrammatic后进行计数。

在解决问题之前，了解strobogrammatic数很重要。回文数（palindromes）是指正反读都相同的数字，而strobogrammatic数有特定的旋转规则。我们不是检查一个数字反转后是否相同，而是检查一个数字旋转180度后是否看起来相同。

我们的任务是高效地查找和计数strobogrammatic数，而不是逐个检查。如果我们采用暴力方法，我们就必须遍历每个数字并查看它是否是strobogrammatic。这将非常慢，尤其是当'n'的值很大时。为了优化这一点，我们可以使用递归和一些智能过滤。

大多数时候，这类问题都涉及某些约束；在这种情况下，约束涉及到处理大数。在C++中，如果一个数字太大，它将无法正确表示。因此，此问题中的输入n实际上是一个数字的字符串表示，它可以任意大。这样做是为了避免数值溢出。

理解Strobogrammatic数

为了以最佳方式解决此问题，我们首先必须知道什么是strobogrammatic数。如果一个数字的每个数字都被翻转，我们得到的数字仍然是原来的顺序，那么它就是strobogrammatic数。

如果一个数字包含除0、1、8之外的任何其他数字（例如2、3、4、5或7），那么它就不能是strobogrammatic数，因为有些数字在 upside down 翻转时没有有效的数字，或者翻转后会使数字看起来不同。

例如，如果我们取23，2和3在翻转时都没有有效的数字。

• 在创建strobogrammatic数时，我们必须确保从中间向两侧（对称地）进行。
• 这意味着第一个和最后一个数字应该是可以翻转后看起来仍然是数字的（例如6和9这样的组合）。
• 之后，第二个数字和倒数第二个数字应该是同一类的组合。

需要注意的一个重要事项是，如果我们已经有了较少位数的strobogrammatic数，我们就可以创建更多位数的strobogrammatic数。我们只需要在这些较小的strobogrammatic数两边添加一对有效的数字即可。让我们说我们已经知道的较小的数字在这里被称为基本情况，它们就是个位数的strobogrammatic数，即0、1和8。现在，使用这些基本情况，我们可以形成两位数的strobogrammatic数，如11、69、88、96等。同样，使用递归方法，我们可以生成任何strobogrammatic数。

我们还需要检查生成的strobogrammatic数是否在给定的边界[l,r]之间。边界l和r是以字符串形式给出的，所以我们可以将字符串l和r转换为数字，而不是将strobogrammatic数转换为字符串，这样比较起来就容易简单了。

此外，除非数字本身是零，否则不允许数字有多余的前导零。例如，即使0是一个有效的strobogrammatic数，我们也无法有06或08。总而言之，如果数字有多于一位，我们就不应该在开头包含零。

计数递归方法

在给定范围[l,r]内查找strobogrammatic数的最优方法之一是使用递归。我们不是生成所有数字然后查看哪些是正确的，而是逐位构建有效的strobogrammatic数。这样可以避免做很多得不到答案的额外工作，从而使事情更快。

为了做到这一点，我们的递归函数采用自顶向下的方法。我们一开始没有任何数字。之后，我们添加两个构成有效strobogrammatic数的数字。关键是我们知道数字应该是什么样子，因为我们知道它必须有多长（数字的位数由n给出）以及n是奇数还是偶数。

递归步骤

• 检查我们已构建的数字是否在l和r之间（包括边界）。如果是，则增加计数。
• 在数字的两端添加一对匹配的strobogrammatic数字。一直这样做，直到我们的数字达到正确的长度或更长。

导致我们停止生成新分支的因素

• 除非我们的数字只有一位，否则不要在开头添加0。
• 如果我们的数字已经比目标值大，我们就不能再添加任何东西了。
• 必须遵循的规则：我们放置的每一对都必须是以下组合之一：00、11、88、69或96。

实现方法

我们可以创建一个递归函数。它将接收到目前为止的数字、其长度以及我们想要达到的长度。在每一步，我们将添加一对有效的数字并递归调用函数。如果长度是奇数，我们只能有1、0或8。

• 假设我们要创建一个长度为4的数字。最初，我们可以从空字符串开始，然后在每一步，我们可以采取下面提到的数字。
• “1001”、“6009”、“8888”、“9696”等。
• 每当我们取一个有效的数字时，我们都会检查它是否在给定的范围内。

通过这种方法，我们可以有效地计数strobogrammatic数，而无需实际生成所有这些数。时间复杂度为O(5^(n/2))，因为递归的每个级别最多会扩展到五个其他级别，因为有五个有效的数字对。即使r的值很大，由于剪枝技术，该解决方案也能很好地工作。

代码实现

输出

Strobogrammatic numbers in the range [50, 1000]:
69 88 96 101 111 181 609 619 689 808 818 888 906 916 986  
Total count: 14   

结论

总之，在给定范围[l, r]内计数strobogrammatic数是一个有趣的计算挑战，它结合了数字属性、递归和字符串操作。Strobogrammatic数在旋转180度后保持不变，它们由特定的数字对构成，如(0,0)、(1,1)、(6,9)、(8,8)和(9,6)。理解这些约束有助于高效地生成有效数字，而无需检查范围内的每个数字。

递归方法利用了对称性，通过从两端向中心构建数字，从而确保只使用有效的数字对。诸如避免前导零和确保字典序比较之类的剪枝技术有助于优化性能。该算法不是通过蛮力检查每个数字，而是构建不同长度的strobogrammatic数，并验证它们在给定范围内的有效性。

总体时间复杂度为O(5^(n/2))，该解决方案对于中等大小的输入来说是高效的。该实现有效地生成和计数strobogrammatic数，同时处理诸如个位数、前导零和不同字符串长度等边缘情况。

这个问题展示了递归在生成组合方面的强大功能。它可以应用于各种领域，包括数字表示、检查对称性以及研究数字模式。学习这些有组织的数值特征可以提高解决编程算法问题的专业知识。