数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 中解密字符串的第 k 个字符 - 集 - 2
概念
对于给定的编码字符串，其中子字符串的重复用子字符串后跟子字符串的计数来表示。例如，如果加密字符串是“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，然后取其与原始子字符串长度的模。这里，所需字符是从第一个指针指向的子字符串开头的第 k 个字符。
示例
// C++ program to find K'th character in
// decrypted string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find K'th character in
// Encoded String
char encodedChar(string str, int k){
int a, b;
int m = str.length();
// Used to store length of substring
int len1;
// Used to store length of substring when
// it is repeated
int num1;
// Used to store frequency of substring
int freq1;
a = 0;
while (a < m) {
b = a;
len1 = 0;
freq1 = 0;
// Determine length of substring by
// traversing the string until
// no digit is found.
while (b < m && isalpha(str[b])) {
b++;
len1++;
}
// Determine frequency of preceding substring.
while (b < m && isdigit(str[b])) {
freq1 = freq1 * 10 + (str[b] - '0');
b++;
}
// Determine length of substring when
// it is repeated.
num1 = freq1 * len1;
// It has been seen that if length of repeated substring is
less than // k then required character is present in next
// substring. Subtract length of repeated
// substring from k to keep account of number of
// characters required to be visited.
if (k > num1) {
k -= num1;
a = b;
}
// It has been seen that if length of repeated substring is
// more or equal to k then required
// character lies in current substring.
else {
k--;
k %= len1;
return str[a + k];
}
}
// This is for the case when there
// are no repetition in string.
// e.g. str="abced".
return str[k - 1];
}
// Driver Code
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
更新于：2020年7月24日
134 次浏览
广告