简介
我有一个无限字符串。这个字符串的长度在我们的想象中是无限的,不能被限制。假设我们在String中有这样一个序列:
"123456789..."
数字 9 之后的 点 实际上代表下一个序列。所以,它会是这样的:
"...7891011121314..."
要求
在这一节中,我想解释一下这个要求。要求是找到输入字符串第一次出现的索引(称为 n)。让我举个例子:
例子1
n = "3"
First Index of n = 2
例子2
n = "910"
First Index of n = 8
问题
我编写了算法来查找字符串 n 的索引。但该算法只是一个while循环,用于检查n的索引,如果没有找到n的索引,则逐一添加下一个序号。我想要一个更好的算法,以便在不依赖循环或更少循环的情况下找到 n 第一次出现的索引。至少,如果 n 的值很大(例如:123456790 或 62716855),算法的运行时间不会超过 2 秒。
---编辑---
我的代码片段:
while(!num.contains(s)){
num +=start.toString();
start = start.add(BigInteger.ONE);
}
这是我的完整代码:My Full Code
最佳答案
下面是如何解决此问题的一般说明。将其翻译成 Java 仍然具有挑战性。
您的输入字符串基本上是所有自然数的无限序列 1 2 3 4 5 6 7 8 9 10 11 12 13 ....
我认为练习的重点是识别子字符串 n
所属的输入字符串的第一个自然数子序列,然后计算其索引而不实际构造大 "无限”字符串。
为此,您必须尝试将子字符串 n
拆分为数字尽可能少的递增数字序列。
首先,您必须检查子字符串 n
是否创建了一个单位数字序列。就是这种情况,比如n == 345678(注意n可能同时包含个位数和双位数,比如n == 345678910
,你应该也能识别) .
如果您在该步骤中失败,您应该寻找一个两位数的序列。例如,n == 33343536
就是这种情况。现在,这可能会变得更棘手,因为 n == 2333435363
也是一个两位数序列,但序列的前导和尾随数字(32 和 37)被截断了。
如果您再次失败,您将寻找一个 3 位数字的序列。
如果找不到任何序列,则将整个子字符串 n
视为大字符串中的单个数字。
现在,假设 n
是 199319941995
,并且您在上一步中发现序列中的第一个数字是 1993
。剩下的工作是计算输入字符串中数字 1993
的索引。您知道单个数字采用 1*9 索引。两位数取 2*90 个索引。三位数字取 3*900 个索引。 1000 到 1993 之间的三位数取 4*993 个索引。因此1993的索引为1*9+2*90+3*900+4*993,也就是子串199319941995
的第一个索引。
关于java - 无限字符串中字符串的第一个索引 - Java,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45727821/