c – 在扩展字符串中查找第k个元素

概述给定一个形式为AB2C3的字符串,并且int k.Expand将字符串作为ABABC3,然后ABABCABABCABABC.任务是找到第k个元素.内存有限,因此无法扩展整个字符串.你只需要找到第k个元素. 我不知道如何去做.在编码面试中被问到我的朋友,我已经给了很多想法,但我没有得到一个有效的解决方案. 更新：以下是O(1)空格和O(N)时间版本.见下文. 原始解决方案使用O(1)空间和O(N l 给定一个形式为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),所以时间复杂度不变.

总结

以上是内存溢出为你收集整理的c – 在扩展字符串中查找第k个元素全部内容，希望文章能够帮你解决c – 在扩展字符串中查找第k个元素所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。