資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告