Re: [閒聊] 每日leetcode
https://leetcode.com/problems/find-the-k-th-character-in-string-game-ii/
3307. Find the K-th Character in String Game II
給定一個數組operations與整數k，
原先有一個字串word = "a"，
依照operations的順序執行以下操作：
如果operations[i] == 0，
則將word複製一份並接在word後面；
如果operations[i] == 1，
則將word的所有字元更改為英文字母的下一個字母（"z"改為"a"），
並接在word後面。
返回執行後word的第k個字元
--
思路：
依照變換規則，
每一個字元都有其前身，
且不論操作為何，
word的長度都會變為原本的兩倍。
假設operations = [1, 1, 1]且k = 7，
那word最後會變成"abbcbccd"，
第7個字元"c"是經由第3次操作從第3個字元"b"而來，
第3個字元"b"又是經由第2次操作從第1個字元"a"而來，
而第1次操作不影響到第7個字元為何。
把與k產生有關的操作次數寫成二進位是110即十進位的6，
剛好等於k-1。
因此只要先把k減去1，
再使用while循環，
如果此時的個位數為1，
表示此次操作會影響到第k個字元，
並且判斷該次操作的種類，
如果為0類操作的不改變字母種類，
若為1類操作則將字母往後一個。
循環判斷下一位數，
直到k變成0為止
--
Python code:
class Solution:
def kthCharacter(self, k: int, operations: List[int]) -> str:
k -= 1
ans = 'a'
while k:
if k & 1 and operations[0]:
ans = chr(ord(ans) + 1) if ans != 'z' else 'a'
operations.pop(0)
k >>= 1
return ans
--
咖啡是一種豆漿，
茶是一種蔬菜湯。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.182.229 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1751615935.A.2FA.html
推
07/04 16:19,
5月前
, 1F
07/04 16:19, 1F
→
07/04 17:50,
5月前
, 2F
07/04 17:50, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1458 之 1548 篇)：