给定一个形式为AB2C3的字符串,并且int k.Expand将字符串作为ABABC3,然后ABABCABABCABABC.任务是找到第k个元素.内存有限,因此无法扩展整个字符串.你只需要找到第k个元素.
我不知道如何去做.在编码面试中被问到我的朋友,我已经给了很多想法,但我没有得到一个有效的解决方案.
解决方法
更新：以下是O(1)空格和O(N)时间版本.见下文.
原始解决方案使用O(1)空间和O(N log k)时间,其中n是未扩展字符串的大小：
char find_kth_expanded(const char* s,unsigned long k) {
/* n is the number of characters in the expanded string which we've
* moved over.
*/
unsigned long n = 0;
const char *p = s;
for (;;) {
char ch = *p++;
if (isdigit(ch)) {
int reps = ch - '0';
if (n * reps <= k)
n *= reps;
else {
/* Restart the loop. See below. */
k = k % n;
p = s;
n = 0;
}
}
else if (ch == 0 || n++ == k)
return ch;
}
}
该函数简单地从字符串向左到右移动,跟踪已经遍历的扩展字符串中有多少个字符.如果该值达到k,那么我们在扩展的字符串中找到了第k个字符.如果重复将跳过字符k,则我们将k减少到重复中的索引,然后重新启动扫描.
很明显,它使用O(1)空间.为了证明它在O(N log k)中运行,我们需要计算循环重新启动的次数.如果我们重新启动,那么k≥n,否则我们以前会在n处返回字符.如果k≥2n则n≤k/ 2,所以k％n≤k/ 2.如果k <2n则k％n = k-n.但是n> k / 2,所以k-n
/* Unlike the above version,this one returns the point in the input
* string corresponding to the kth expanded character.
*/
const char* find_kth_expanded(const char* s,unsigned long k) {
unsigned long n = 0;
while (*s && k >= n) {
if (isdigit(*s))
n *= *s - '0';
else
++n;
++s;
}
while (k < n) {
--s;
if (isdigit(*s)) {
n /= *s - '0';
k %= n;
}
else
--n;
}
return s;
}
上述功能都不能正确处理乘数为0且k小于段长度乘以0的情况.如果0是合法乘数,则简单的解决方案是反转扫描最后0个字符串,在以下字符处开始find_kth_expanded.由于反向扫描为O(N),所以时间复杂度不变.
