在擴展字符串中查找第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，代碼將幾乎相同，只需稍作更改，我希望您能得到實際的邏輯。