s0089_gray_code.rs

#![allow(unused)]
pub struct Solution {}

impl Solution {
    // O(2^n) O(2^n)
    //
    // 格雷码能避免讯号传送错误的原理:
    //
    // 传统的二进制系统例如数字3的表示法为011，
    // 要切换为邻近的数字4，也就是100时，装置中的三个位元都得要转换，因此于未完全转换的过程时装置
    // 会经历短暂的，010,001,101,110,111等其中数种状态，也就是代表着2、1、5、6、7，
    // 因此此种数字编码方法于邻近数字转换时有比较大的误差可能范围。格雷码的发明即是用来将误差之可能性
    // 缩减至最小，编码的方式定义为每个邻近数字都只相差一个位元，因此也称为最小差异码，
    // 可以使装置做数字步进时只更动最少的位元数以提高稳定性。 数字0～7的编码比较如下：
    // 十进制　格雷码 二进制
    //    0  　　 000    000
    //    1  　　 001    001
    //    2   　　011    010
    //    3   　　010    011
    //    4   　　110    100
    //    5   　　111    101
    //    6   　　101    110
    //    7   　　100    111
    pub fn gray_code(n: i32) -> Vec<i32> {
        let mut ans = vec![];
        for i in 0..1 << n {
            ans.push(i ^ i >> 1);
        }

        ans
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_89() {
        assert_eq!(Solution::gray_code(2), vec![0, 1, 3, 2]);
        assert_eq!(Solution::gray_code(0), vec![0]);
    }
}