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

Question

给定表格AB2C3和int k的字符串。展开字符串作为ABABC3，然后ABABCABABCABABC。任务是找到第th个元素。你的内存有限，所以你不能展开整个字符串。你只需要找到第012个元素。

我不知道如何去做。有人在编码采访中问我的朋友，我已经给了很多想法，但我没有得到一个有效的解决方案。

Answer 1

更新：一个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<k-k/2，因此k%n<k/2。

因此，当我们重新启动时，k的新值至多是旧值的一半。所以在最坏的情况下，我们会重新启动log2k次。

---

尽管上述解决方案很容易理解，但我们实际上可以做得更好。一旦我们扫描过k（展开后）的字符，我们就可以向后扫描而不是重新开始扫描。在向后扫描，我们需要总是正确k通过采取其模量基础段长度在当前段的范围内：

/* 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)，时间复杂度不会改变。

Answer 2

在第一种情况下，字符串为'AB2C3'，其中'2'从'AB2C3'中删除，'AB2C3'中的'2'（'AB'）的左侧重复'2'次。它变成'ABABC3'。

在第二种情况下，字符串是'ABABC3'，其中'3'从'ABABC3'中被删除，并且字符串'ABABC3'中'3'（'ABABC'）的左侧被重复'3'次。它变成'ABABCABABCABABC'。

算法会是这样的：

所有的

1) READ ONE CHAR AT A TIME UNTIL END OF STRING 
    IF CHAR IS AN INT THEN k := k - CHAR + 1 
2) RETURN STRING[k] 

Answer 3

首先，看一看的字符串。你的字符串由两部分组成：数据部分和信息部分。数据部分包含要重复的实际字符串，信息部分包含重复的实际数目。

如果你明白这一点，你已经了解数据的模式。

下一步是处理特殊情况，如负数重复数，实数重复数而不是整数。你实际上可以说重复是在最后找到的字符串的子字符串，并且由规则定义它只能包含数字。如果你这样想，那么你会有两种情况：字符串以数字结尾，或者字符串不以数字结尾。在第一种情况下，我们有一个有效的重复号码，在第二种情况下，我们必须抛出异常。

如果我们仍然有一个有效的重复编号，那么它可能有多个数字，所以，您必须探索您的字符串以找到最后一个与数字无关的索引。该索引之后的子字符串是信息部分，即rp（重复号码）。另外，这个索引实际上等于你的数据部分的长度 - 1，我们称之为长度L.如果你有一个有效的rp，那么结果字符串的实际长度是L * rp。

现在，如果k是一个整数，那么如果它是负数，您仍然必须抛出异常，并且另一个重要的验证规则是L * rp。

如果一切是有效的，那么实际值的指数的计算方法是：

ķ％L

你不必去实际计算结果字符串来确定第k个字符，因为你可以使用你有重复模式的事实。

Answer 4

我想这个问题的关键是要弄清楚你需要扩展多少，直到你能够获得第k个元素。

在这个例子中，假设第一个字符是索引1，你根本不需要展开。

对于2 < k <= 5您只需要展开第一部分。

对于5 < k <= 10您需要扩大unil ABABCABABC和10 < k <= 15您需要做全面的扩展。

Answer 5

这实际上是一个有趣的益智程序来编写。

这是用C＃编写的答案。这是一个练习转换为C++！有两个递归函数，一个用于计算扩展字符串的长度，另一个用于查找给定字符串的第n个字符。它从右向左反向工作，一次剥离一个角色。

using System; 
using System.Collections.Generic; 
using System.Text; 

namespace expander 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      string y = "AB2C3"; 
      Console.WriteLine("length of expanded = {0} {1}", y, length(y)); 
      for(uint k=0;k<length(y);k++) 
      { 
       Console.WriteLine("found {0} = {1}",k,find(k,y)); 
      } 
     } 

     static char find(uint k, string s) 
     { 
      string left = s.Substring(0, s.Length - 1); 
      char last = s[s.Length - 1]; 
      uint len = length(left); 
      if (last >= '0' && last <= '9') 
      { 
       if (k > Convert.ToInt32(last -'0') * len) throw new Exception("k out of range"); 
       uint r = k % len; 
       return find(r, left); 
      } 
      if (k < len) return find(k, left); 
      else if (k == len) return last; 
      else throw new Exception("k out of range"); 
     } 
     static uint length(string s) 
     { 
      if (s.Length == 0) return 0; 
      char x = s[s.Length - 1]; 
      uint len = length(s.Substring(0, s.Length - 1)); 
      if (x >= '0' && x <= '9') 
      { 
       return Convert.ToUInt32(x - '0') * len; 
      } 
      else 
      { 
       return 1 + len; 
      } 
     } 
    } 
} 

下面是示例输出，其示出了find功能复制膨胀如果迭代k的所有有效值（0为len-1）。

length of expanded AB2C3 is 15 
if k=0, the character is A 
if k=1, the character is B 
if k=2, the character is A 
if k=3, the character is B 
if k=4, the character is C 
if k=5, the character is A 
if k=6, the character is B 
if k=7, the character is A 
if k=8, the character is B 
if k=9, the character is C 
if k=10, the character is A 
if k=11, the character is B 
if k=12, the character is A 
if k=13, the character is B 
if k=14, the character is C 

此程序的内存使用量仅限于堆栈使用情况。堆栈深度将等于字符串的长度。在这个C＃程序中，我一遍又一遍地复制字符串，以至于浪费内存。但即使在这种糟糕的管理下，它也应该使用O（N^2）内存，其中N是字符串的长度。实际扩展的字符串可能会更长，更长。例如，“AB2C999999”只有N = 10，因此应使用O（100）个内存元素，但扩展后的字符串长度超过200万个字符。

Answer 6

给出这个问题的代码。

public String repeater(String i_string, int k){ 
    String temp = ""; 
    for (int i=0; i < k; ++i) 
     temp = temp + i_string.substring(0,k); 
    temp = temp + i_string.substring(k, i_string.length()); 
    return temp; 
} 

我没有考虑到有限的内存问题，因为没有任何明确的信息提及相同。

你不需要任何额外的内存。您可以根据用户要求将数据打印到控制台。如果你只是显示，那么方法的返回类型也可以被排除:)你只需要一个临时字符串来保存处理过的数据。

public void repeater2(String i_string, int k){ 
    String temp = i_string.substring(0,k); 
    // Repeat and Print the first half as per requirements. 
    for (int i=0; i < k; ++i) 
     System.out.print(temp); 
    // Print the second half of the string AS - IS. 
    System.out.print(i_string.substring(k, i_string.length())); 
} 

如果K值为1，则字符串将被打印一次。根据要求。我们需要两次迭代。 对于C++或Java，代码将几乎相同，只需稍作更改，我希望您能得到实际的逻辑。