class Solution {
public:
string decodeAtIndex(string s, int k) {
}
};
880. 索引处的解码字符串
给定一个编码字符串 S。请你找出 解码字符串 并将其写入磁带。解码时，从编码字符串中 每次读取一个字符 ，并采取以下步骤：
d），则整个当前磁带总共会被重复写 d-1 次。现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。
示例 1：
输入：S = "leet2code3", K = 10 输出："o" 解释： 解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。 字符串中的第 10 个字母是 "o"。
示例 2：
输入：S = "ha22", K = 5 输出："h" 解释： 解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
示例 3：
输入：S = "a2345678999999999999999", K = 1 输出："a" 解释： 解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。
提示：
2 <= S.length <= 100S 只包含小写字母与数字 2 到 9 。S 以字母开头。1 <= K <= 10^9K 小于或等于解码字符串的长度。2^63 个字母。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-29 10:54:15
func decodeAtIndex(S string, K int) string {
count := 0
for i := 0; i < len(S); i++ {
c1 := 0
if isAlpha(S[i]) {
c1 = count + 1
} else {
c1 = count * int(S[i] - '0')
}
if c1 == K && isAlpha(S[i]) {
return string(S[i])
}
if c1 >= K {
if c1 == i + 1 && isAlpha(S[i]) {
return string(S[K-1])
}
K = K % count
if K == 0 {
K = count
}
return decodeAtIndex(S[:i], K) // 计算被加倍前的那一段
}
count = c1
}
return ""
}
func isAlpha(s byte) bool {
if s >= 'a' && s <= 'z' {
return true
}
return false
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-29 10:53:01
func decodeAtIndex(S string, K int) string {
var cur int
var last string
for k, v := range S {
if v > '1' && v <= '9' {
num := int(v - '0')
//超过k
if num*cur >= K {
if K%cur == 0 {
return last
}
return decodeAtIndex(S[:k], K%cur)
}
cur *= num
continue
}
last = string(v)
cur++
if cur == K {
return last
}
}
return ""
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2023-06-29 10:52:18
class Solution {
public:
string decodeAtIndex(string S, int K) {
long size = 0;
int N = S.size();
// Find size = length of decoded string
for (int i = 0; i < N; ++i) {
if (isdigit(S[i]))
size *= S[i] - '0';
else
size++;
}
for (int i = N-1; i >=0; --i) {
K %= size;
if (K == 0 && isalpha(S[i]))
return (string) "" + S[i];
if (isdigit(S[i]))
size /= S[i] - '0';
else
size--;
}
return "";
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.4 MB, 提交时间: 2023-06-29 10:51:56
class Solution {
public String decodeAtIndex(String S, int K) {
long size = 0;
int N = S.length();
// Find size = length of decoded string
for (int i = 0; i < N; ++i) {
char c = S.charAt(i);
if (Character.isDigit(c))
size *= c - '0';
else
size++;
}
for (int i = N-1; i >= 0; --i) {
char c = S.charAt(i);
K %= size;
if (K == 0 && Character.isLetter(c))
return Character.toString(c);
if (Character.isDigit(c))
size /= c - '0';
else
size--;
}
throw null;
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-06-29 10:51:36
'''
逆向工作法
首先，找出解码字符串的长度。之后，我们将逆向工作，跟踪 size：解析符号 S[0], S[1], ..., S[i] 后解码字符串的长度。
如果我们看到一个数字 S [i]，则表示在解析 S [0]，S [1]，...，S [i-1] 之后解码字符串的大小将是 size / Integer(S[i])。
否则，将是 size - 1。
'''
class Solution:
def decodeAtIndex(self, s: str, k: int) -> str:
size = 0
# Find size = length of decoded string
for c in s:
if c.isdigit():
size *= int(c)
else:
size += 1
for c in reversed(s):
k %= size
if k == 0 and c.isalpha():
return c
if c.isdigit():
size /= int(c)
else:
size -= 1