推 oz5566: 選c 10/25 15:26
推 scmono: 大師 10/25 15:31
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 個數字是多少。
思路：
一開始直接暴力解果然timeout
思路是k是由k/2產生，從規則可以看出如果k%2為0則不變，k%2為1則取反，
簡化過後變成找k-1二進制出現過1的次數，如果是奇數則輸出1，偶數輸出0
用一行就解完真的蠻爽的
我愛rust
impl Solution {
pub fn kth_grammar(n: i32, k: i32) -> i32 {
format!("{:b}", k - 1)
.chars()
.into_iter()
.filter(|&x| x == '1')
.count() as i32
% 2
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.169.2 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698218719.A.EC4.html