Re: [閒聊] 每日LeetCode已刪文

看板Marginalman作者ZooseWu (動物園公告)時間2年前 (2023/10/27 16:37)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串468/719 (看更多)

※ 引述《wwndbk (snoopy養的狗)》之銘言： : https://leetcode.com/problems/k-th-symbol-in-grammar/description : 779. K-th Symbol in Grammar : 給你一個數字 n 和一個數字 k，n 表示第幾列 k 表示第幾行（列和行從 1 開始） : 第一列的數字固定為 0，第一列之後的數字按照以下規律： : 取代前一列的所有 0 -> 01 取代前一列的所有 1 -> 10 : Example： : n = 3，則 : ROW1=0 : ROW2=01 : ROW3=0110 : 求出第 n 列的第 k 個數字是多少。補課 First thought: DP或是遞迴解不斷從前一個row往後推下一個row。 Approach: 我把數列列出來 // n = 1: 0 // n = 2: 01 // n = 3: 0110 // n = 4: 01101001 // n = 5: 0110100110010110 // k = 1234567890123456 發現每一個row的前半都跟前一個row長的一模一樣後半才是新衍生出來的這代表什麼？代表n根本不重要第n row第3個數字跟第3 row的第3個數字會一樣所以我們根本不用考慮n 反正題目已經限制k < 2^n 再來是我們去觀察數字生成的方式 // n = 4: 01101001 // n = 5: 0110100110010110 // k = 1234567890123456 從黃色的規律跟紅色的規律可以發現兩個現象 1. 第15跟第16個數字只會受到第8個數字影響 2. 奇數會跟前一個數字一樣偶數會反轉例如16->8以及14->7都反轉了然後15->8 13->7都不反轉這樣看下來算式就很簡單：查看是不是偶數，是的話就反轉然後index/2 一直查到1 最後輸出解。 TS code: function kthGrammar (n: number, k: number): number { let result = false for (let i = k; i > 1; i = Math.ceil(i / 2)) { if (i % 2 === 0) result = !result } return result ? 1 : 0 } 結果丟上去速度超慢的被80%的人屌打研究了一下我用到了%以及ceil(i/2) 代表每次運算我都進行了兩次除法非常吃效能所以我把它全部改成用二進制去計算 i / 2 -> i >> 1 i % 2 -> (i & 1) 最後效能達到PR90 TS code: function kthGrammar (n: number, k: number): number { let result = false for (let i = k; i > 1; i = i >> 1) { if ((i & 1) === 0) { result = !result } else { i++ } } return result ? 1 : 0 } -- Zoosewu Yoututbe顯示PTT推文可以在各個網站追實況或Live時使用預覽圖: https://i.imgur.com/ZhtXdAJ.png