推 devilkool: 幹 看題目直覺用stack或字串結果都不行... 09/28 01:13
推 NTHUlagka: 還想說怎沒人發今天每日 本來寫完要發的 就看到你這篇 09/28 01:52
→ NTHUlagka: 今天的每日寫起來小麻煩 09/28 01:52
https://leetcode.com/problems/decoded-string-at-index/description
880. Decoded String at Index
給你一個被編碼過後的字串，找出他解碼之後的第 k 個字元是什麼，解碼規則如下：
當前字串假設為 s：
如果 s[i] 是字母，s += s[i]
如果 s[i] 是數字，假設數字為 d，s = d個s拼接
思路：
1.最簡單的寫法就是按照規則組出字串然後訪問指定位置的字元，但是解碼後的字元可
能長度是 2^63，會吃 MLE，只能改從解碼字串找出一些關係，我們可以從解碼字串的
長度下手。
2.首先，我們只需找到第 k 個字元，所以解碼的字串長度大於等於 k 的時候我們可以
提前跳出不必繼續解碼，並從當前索引往前去判斷，關鍵是要怎麼找到前面的字元。
3.對於字串 appleappleappleappleapple 來說，k = 4 和 k = 14 都是一樣的，觀察發
現規律，若重複的字串為 word，s[k] = s[k % word.size]。
4.開始往前判斷，利用(3)的關係式，我們對 size 取餘數以確定 k 在當前解碼字串的
位置，可以有三種情況：
如果 k % size == 0 且 s[i] 是字母，表示 s[i] 就是第 i 個字元（size == k），
直接返回 s[i] 作為解。
如果 k % size == 0 但是 s[i] 是數字，表示 k 比當前 size 還小，透過反向操作
size = size / s[i] 我們可以得到解碼前的字串，回到第四步。
如果 k % size != 0 表示 k 在更前面的位置，所以縮減 size，size = size - 1，
回到第四步。
Java Code：
--------------------------------------------------
class Solution {
public String decodeAtIndex(String S, int K) {
char[] chs = S.toCharArray();
long size = 0;
int index = -1;
for (char ch : chs) {
if (size >= K) break;
if (Character.isDigit(ch)) {
size *= (ch - '0');
} else {
size++;
}
index++;
}
for (int i = index; i >= 0; i--) {
K %= size;
char ch = chs[i];
if (K == 0 && Character.isLetter(ch)) {
return String.valueOf(ch);
}
if (Character.isDigit(ch)){
size = size / (ch - '0');
} else {
size--;
}
}
return "";
}
}
--------------------------------------------------
好難想:( 不看題解想不到 躺平
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1695826368.A.401.html