一天一道LeetCode，沖啊！——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 <= 100

• S

  隻包含小寫字母與數字

  2

  到

  9

  。

• S

  以字母開頭。

• 1 <= K <= 10^9

• 解碼後的字元串保證少于

  2^63

  個字母

分析

（copy的leetcode的閱讀解答）

• 方法：逆向工作法
  • 思路
    • 如果我們有一個像

      appleappleappleappleappleapple

      這樣的解碼字元串和一個像

      K=24

      這樣的索引，那麼如果

      K=4

      ，答案是相同的。
    • 一般來說，當解碼的字元串等于某個長度為 size 的單詞重複某些次數（例如

      apple

      與

      size=5

      組合重複6次）時，索引

      K

      的答案與索引

      K % size

      的答案相同。
    • 我們可以通過逆向工作，跟蹤解碼字元串的大小來使用這種洞察力。每當解碼的字元串等于某些單詞

      word

      重複

      d

      次時，我們就可以将

      k

      減少到

      K % (Word.Length)

      。
  • 算法
    • 首先，找出解碼字元串的長度。之後，我們将逆向工作，跟蹤

      size

      ：解析符号

      S[0], S[1], ..., S[i]

      後解碼字元串的長度。
    • 如果我們看到一個數字

      S [i]

      ，則表示在解析

      S [0]，S [1]，...，S [i-1]

      之後解碼字元串的大小将是

      size / Integer(S[i])

      。 否則，将是

      size - 1

      。

代碼

public class Solution880 {
    public String decodeAtIndex(String S, int K) {
        long size = 0;
        int N = S.length();

        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;
    }
}
           

後記

GitHub — fuyuaaaaa