Re: [閒聊] 每日LeetCode

[z2147483648 (溢傷了喇)]

: 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 個數字是多少。

思路：一開始想用dp做結果MLE

後來看了答案(哭啊)

可以發現
1. 每一row的前1/2數列 剛好是前一row的數列
2. 每一row的後1/2數列 剛好是前一row的數列 的相反(0 <-> 1)
        - 所以可以利用change_count變數記憶到底翻了幾次
3. 第n==2的row的答案恰為k_index - 1
        - 所以算到 n == 2 就可以得到 答案應該是 k-1


於是可以寫成下面這樣

========== Python

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if (n == 1):
            return 0
        change_count = 0
        while(n > 2):
            if (k <= 2**(n-2)):
                pass
            else:
                k = k - 2**(n-2)
                change_count += 1
            n -= 1
        k = k - 1
        if (change_count % 2 == 1):
            k = self.change(k)
        return k

    def change(self, x):
        if x == 1:
            return 0
        else:
            return 1

========== C++

class Solution {
public:
    int kthGrammar(int n, int k) {
        int change_count = 0;
        while(n > 2)
        {
            if (k <= pow(2, n-2)) {}
            else
            {
                k = k - pow(2, n-2);
                change_count++;
            }
            n--;
        }
        k--;
        if (change_count % 2 == 1) k = change(k);
        return k;
    }
    int change(int x)
    {
        if (x == 1) return 0;
        else return 1;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.12.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698338575.A.92B.html
推 usadapussy: 錢