查找解密后的字符串的第k个字符-Set – 2 in C ++

概念

对于给定的编码字符串，其中子字符串的重复表示为子字符串，后跟子字符串的计数。因此，例如，如果加密的字符串为“ pq2rs2”且k = 5，则输出为“ r”，因为解密的字符串为“ pqpqrsrs”，而第5个字符为“ r”。

应当注意，加密子串的频率可以大于一位数。因此，例如，在“ pq12r3”中，pq重复12次。在此，子串的频率中不存在前导0。

输入项

"p2q2r3", k = 6

输出结果

r

解密后的字符串为“ ppqqrrr”

输入项

"pq4r2ts3", k = 11

输出结果

t

解密后的字符串是“ pqpqpqpqrrtststs”

方法

在这里，逐步算法是-

• 确定当前子串的长度。实现两个指针。我们必须在子字符串的开头固定一个指针，然后继续处理另一个指针，直到找不到数字为止。

• 通过进一步移动第二个指针直到找不到字母来确定重复的频率。

• 确定子字符串的长度（如果通过将频率与其原始长度相乘来重复）。

• 已经观察到，如果此长度小于k，则所需字符位于后面的子字符串中。我们必须从k中减去此长度，以保持需要覆盖的字符数的计数。

• 可以看出，如果长度小于或等于k，则所需字符位于当前子字符串中。因为k是1索引的，所以将其减少1，然后使用原始子串长度获取其mod。在此，必需字符是从第一个指针所指向的子字符串开始的第k个字符。

示例

// C++ program to find K'th character in
//解密的字符串
#include <bits/stdc++.h>
using namespace std;
//显示查找第K个字符的功能
//编码字符串
char encodedChar(string str, int k){
   int a, b;
   int m = str.length();
   //用于存储子串的长度
   int len1;
   //用于存储子串的长度 when
   //重复
   int num1;
   //用于存储子串的频率
   int freq1;
   a = 0;
   while (a < m) {
      b = a;
      len1 = 0;
      freq1 = 0;
      //确定子字符串的长度
      //遍历字符串，直到
      //找不到数字。
      while (b < m && isalpha(str[b])) {
      b++;
      len1++;
   }
   //确定前一个子字符串的频率。
   while (b < m && isdigit(str[b])) {
      freq1 = freq1 * 10 + (str[b] - '0');
      b++;
   }
   //时子字符串的长度
   //重复.
   num1 = freq1 * len1;
   //已经看到，如果重复子串的长度是
   less than // k then required character is present in next
   //子字符串。减去重复长度
   //的数量
   //需要访问的字符。
   if (k > num1) {
      k -= num1;
      a = b;
   }
   //已经看到，如果重复子串的长度是
   //大于或等于k然后要求
   //字符位于当前子字符串中。
      else {
         k--;
         k %= len1;
         return str[a + k];
      }
   }
   //当
   //字符串中没有重复。
   // e.g. str="abced".
   return str[k - 1];
}
//驱动程式码
int main(){
   string str1 = "pqpqpqpqrrtststs";
   int k1 = 11;
   cout << encodedChar(str1, k1) << endl;
   string str2 = "p2q2r3";
   int k2 = 6;
   cout << encodedChar(str2, k2) << endl;
   return 0;
}

输出结果

t
r