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