pi 中 4 位序列的上限
Upper bound on 4 digit sequences in pi
如果这不是该问题的正确 SE 站点，请告诉我。
有个朋友在电话里分享了他接到的这个面试题，我自己也试着解决了。我会转述：
The value of pi up to n digits as a string is given.
How can I find all duplicate 4 digit sequences in this string?
这部分看起来相当简单。将 4 个字符序列添加到散列 table，一次递增一个字符。在插入散列table之前检查当前的4字符序列是否已经存在。如果是这样，那么您找到了重复项。将其存储在某处，然后重复该过程。有人告诉我这或多或少是正确的。
我遇到的问题是第二个问题：
What is the upper bound?
n = 10,000,000 就是一个例子。
我的算法背景固然很生疏。我的第一个想法是上限一定与 n 有某种关系，但我被告知不是。
我该如何计算？
编辑：
我也愿意接受忽略上限与 n 无关的限制的解决方案。要么是acceptable.
您的解决方案的上限是您可以装入内存的哈希 table 的大小。
另一种技术是生成所有序列并对它们进行排序。然后重复项将相邻并且易于检测。通常，与散列 table 相比，您可以将更多内容放入线性数据结构中，如果仍然耗尽内存，则可以对 to/from 磁盘进行排序。
编辑：除非"upper bound"表示算法的O(n)，这应该很容易算出来。
四位数的可能序列只有10,000个（0000到9999），所以在某些时候你会发现每个序列都被重复了，不需要进一步处理数字。
如果您假设 pi 是一个完全均匀的随机数生成器，那么处理的每个新数字都会产生一个新序列，并且在大约 20,000 个数字之后，您会发现所有 10,000 个序列都是重复的。鉴于 pi 并不完美，在复制所有序列之前您可能需要更多的数字，但 100,000 是上限的合理猜测。
此外，由于只有 10,000 种可能性，您实际上并不需要散列 table。您可以简单地使用一个包含 10000 个计数器的数组 (int count[10000])，并为您找到的每个序列递增计数。
如果这不是该问题的正确 SE 站点，请告诉我。
有个朋友在电话里分享了他接到的这个面试题，我自己也试着解决了。我会转述：
The value of
piup tondigits as a string is given.How can I find all duplicate 4 digit sequences in this string?
这部分看起来相当简单。将 4 个字符序列添加到散列 table，一次递增一个字符。在插入散列table之前检查当前的4字符序列是否已经存在。如果是这样，那么您找到了重复项。将其存储在某处，然后重复该过程。有人告诉我这或多或少是正确的。
我遇到的问题是第二个问题：
What is the upper bound?
n = 10,000,000 就是一个例子。
我的算法背景固然很生疏。我的第一个想法是上限一定与 n 有某种关系，但我被告知不是。
我该如何计算？
编辑：
我也愿意接受忽略上限与 n 无关的限制的解决方案。要么是acceptable.
您的解决方案的上限是您可以装入内存的哈希 table 的大小。
另一种技术是生成所有序列并对它们进行排序。然后重复项将相邻并且易于检测。通常，与散列 table 相比，您可以将更多内容放入线性数据结构中，如果仍然耗尽内存，则可以对 to/from 磁盘进行排序。
编辑：除非"upper bound"表示算法的O(n)，这应该很容易算出来。
四位数的可能序列只有10,000个（0000到9999），所以在某些时候你会发现每个序列都被重复了，不需要进一步处理数字。
如果您假设 pi 是一个完全均匀的随机数生成器，那么处理的每个新数字都会产生一个新序列，并且在大约 20,000 个数字之后，您会发现所有 10,000 个序列都是重复的。鉴于 pi 并不完美，在复制所有序列之前您可能需要更多的数字，但 100,000 是上限的合理猜测。
此外，由于只有 10,000 种可能性，您实际上并不需要散列 table。您可以简单地使用一个包含 10000 个计数器的数组 (int count[10000])，并为您找到的每个序列递增计数。