无限序列 12345678910111213
Infinite sequence 12345678910111213
给定一个无限的数字序列：
12345678910111213141516.....等等。我必须找到输入字符串的第一个位置。像这样：
1234 gives 1
13 gives 16
111 gives 12
有人已经想出了解决此类问题的算法吗？
提示:
如果您知道输入字符串以整数开头，则可以通过尝试所有前缀来快速验证该假设。例如，取 21521.
2 不能正确，因为它继续为 2 3 4...
21 不能正确，因为它继续为 21 22 23...
215 很好，因为它继续 215 216...
也有可能字符串不是以整数开头，可以试试后缀以整数开头，并检查前面的数字。
2 1521 可以是 152 153...，但是前面有 15 1,
21 512 可以是 512 513...，但是前面有 5 11,
215 12 可以是 1 2 3...，但这之前是...没有，
2151 2 可以是 2 3...，但是前面没有足够的数字。
在您确定匹配项后仍需查找索引。您将必须累计个位数、两位数的计数...
还要检查没有遗漏的可能性。
乍一看，此过程需要时间 O(N³)，其中 N 是字符串的长度，无论其位置如何。
给定一个无限的数字序列：
12345678910111213141516.....等等。我必须找到输入字符串的第一个位置。像这样：
1234 gives 1 13 gives 16 111 gives 12
有人已经想出了解决此类问题的算法吗？
提示:
如果您知道输入字符串以整数开头，则可以通过尝试所有前缀来快速验证该假设。例如，取 21521.
2 不能正确，因为它继续为 2 3 4...
21 不能正确，因为它继续为 21 22 23...
215 很好，因为它继续 215 216...
也有可能字符串不是以整数开头，可以试试后缀以整数开头，并检查前面的数字。
2 1521 可以是 152 153...，但是前面有 15 1,
21 512 可以是 512 513...，但是前面有 5 11,
215 12 可以是 1 2 3...，但这之前是...没有，
2151 2 可以是 2 3...，但是前面没有足够的数字。
在您确定匹配项后仍需查找索引。您将必须累计个位数、两位数的计数...
还要检查没有遗漏的可能性。
乍一看，此过程需要时间 O(N³)，其中 N 是字符串的长度，无论其位置如何。