Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-09-27 22:52:45
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:

Links booklink

Contact Us: admin [ a t ] ucptt.com