ARST打卡第327周

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

impl Solution {
    pub fn reordered_power_of2(n: i32) -> bool {
        let s = n.to_string();
        let chars: Vec<char> = s.chars().collect();
        let mut visited = vec![false; chars.len()];
        let mut current = String::new();
        
        Self::generate_permutations(&chars, &mut visited, &mut current)
    }
    
    fn generate_permutations(chars: &[char], visited: &mut Vec<bool>, current: &mut String) -> bool {
        if current.len() == chars.len() {
            // 检查当前排列是否为2的幂
            if let Ok(num) = current.parse::<i32>() {
                if num > 0 && !current.starts_with('0') && Self::is_power_of_two(num) {
                    return true;
                }
            }
            return false;
        }
        
        for i in 0..chars.len() {
            if !visited[i] {
                visited[i] = true;
                current.push(chars[i]);
                
                // 如果找到了一个2的幂，立即返回true
                if Self::generate_permutations(chars, visited, current) {
                    return true;
                }
                
                current.pop();
                visited[i] = false;
            }
        }
        false
    }
    
    fn is_power_of_two(n: i32) -> bool {
        n > 0 && (n & (n - 1)) == 0
    }
}

// 测试用例
#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn test_reordered_power_of2() {
        assert_eq!(Solution::reordered_power_of2(1), true);    // 1 是 2^0
        assert_eq!(Solution::reordered_power_of2(10), false);  // 01, 10 都不是2的幂
        assert_eq!(Solution::reordered_power_of2(16), true);   // 16 是 2^4, 61 不是
        assert_eq!(Solution::reordered_power_of2(24), false);  // 24, 42 都不是2的幂
        assert_eq!(Solution::reordered_power_of2(46), true);   // 64 是 2^6
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

string countDigits(int n) {
    string cnt(10, 0);
    while (n) {
        ++cnt[n % 10];
        n /= 10;
    }
    return cnt;
}

unordered_set<string> powerOf2Digits;

int init = []() {
    for (int n = 1; n <= 1e9; n <<= 1) {
        powerOf2Digits.insert(countDigits(n));
    }
    return 0;
}();

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        return powerOf2Digits.count(countDigits(n));
    }
};