Rust算法练习-LCWeekly 385 & 一系列Ez Bits题

一系列Ez Bits题

LC231. Power of Two

impl Solution {
    pub fn is_power_of_two(mut n: i32) -> bool {
        let mut cnt = 0;
        if n <= 0 {
            return false;
        }
        while n > 0 {
            cnt += n & 1;
            n >>= 1;
        }
        return cnt == 1;
    }
}

LC191. Number of 1 Bits

impl Solution {
    pub fn hammingWeight (mut n: u32) -> i32 {
        let mut cnt = 0;
        while n > 0 {
            cnt += n & 1;
            n >>= 1;
        }
        return cnt as i32;
    }
}

LC338. Counting Bits

递推

impl Solution {
    pub fn count_bits(n: i32) -> Vec<i32> {
        let n = n as usize;
        let mut dp = vec![0; n+2];
        dp[1] = 1;
        for i in 1..=n >> 1 {
            let to = i << 1;
            dp[to] = dp[i];
            dp[to + 1] = dp[i] + 1;
        }
        dp[..n+1].to_vec()
    }
}

还没直接暴力来得快

impl Solution {
    pub fn count_bits(n: i32) -> Vec<i32> {
        (0..=n).map(|i| i.count_ones() as i32).collect()
    }
}

LC190. Reverse Bits

Rust标准里有这玩意。。

impl Solution {
    pub fn reverse_bits(x: u32) -> u32 {
        x.reverse_bits()
    }
}

LCWeekly Contest 385

Count Prefix and Suffix Pairs I&II Ez & Hard

impl Solution {
    pub fn count_prefix_suffix_pairs(words: Vec<String>) -> i32 {
        let mut res = 0;
        for i in 0..words.len() {
            for j in i+1..words.len() {
                if words[j].starts_with(&words[i]) && words[j].ends_with(&words[i]) {
                    res += 1;
                }
            }
        }
        res
    }
}

Hard的数据比较水，用Map维护一下相同值就行。。。就算正解也比较简单，用个Trie即可，只不过子节点索引不是字符，是(ch[x], ch[len-x-1])

Find the Length of the Longest Common Prefix Med

感觉是个字典树，按A建树，B往里跑，跑到哪算哪

struct Trie {
    root: TrieNode,
}
struct TrieNode {
    children: std::collections::HashMap<String, TrieNode>,
    count: i32,
}
impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode {
                children: std::collections::HashMap::new(),
                count: 0,
            },
        }
    }
    fn insert(&mut self, s: String) {
        let mut node = &mut self.root;
        for c in s.chars() {
            node = node.children.entry(c.to_string()).or_insert(TrieNode {
                children: std::collections::HashMap::new(),
                count: 0,
            });
            node.count += 1;
        }
    }
}
impl Solution {
    pub fn longest_common_prefix(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        let mut trie = Trie::new();
        for i in 0..arr1.len() {
            trie.insert(arr1[i].to_string());
        }
        let mut res = 0;
        for i in 0..arr2.len() {
            let mut node = &trie.root;
            let mut now = 0;
            for j in arr2[i].to_string().chars() {
                if let Some(n) = node.children.get(&j.to_string()) {
                    node = n;
                    now += 1;
                } else {
                    break;
                }
            }
            res = res.max(now);
        }
        res as i32
    }
}

Most Frequent Prime Med

妈的，一开始在小点上T，我脑子没转过来，埃筛和线筛都还给老师了。。比赛打完也没过，不知道为啥T了

Upd: 统计不用vec，用HashMap就过了。。。比赛实在来不及了

use super::Solution;
impl Solution {
    pub fn most_frequent_prime(mat: Vec<Vec<i32>>) -> i32 {
        let dirs = vec![
            (0, 1),
            (0, -1),
            (1, 0),
            (-1, 0),
            (1, 1),
            (1, -1),
            (-1, 1),
            (-1, -1),
        ];
        let (m, n) = (mat.len(), mat[0].len());

        let mut is_prime = vec![true; 1000000 + 1];
        is_prime[0] = false;
        is_prime[1] = false;

        let mut p = 2;
        while p * p <= 1000000 {
            if is_prime[p] {
                let mut i = p * p;
                while i <= 1000000 {
                    is_prime[i] = false;
                    i += p;
                }
            }
            p += 1;
        }


        let mut res = vec![0; 1000001];
        for i in 0..m {
            for j in 0..n {
                for dir in &dirs {
                    let (mut x, mut y) = (i as i32, j as i32);
                    let mut num = 0;
                    while x >= 0 && x < m as i32 && y >= 0 && y < n as i32 {
                        num = num * 10 + mat[x as usize][y as usize];
                        if is_prime[num as usize] {
                            res[num as usize] += 1;
                        }
                        x += dir.0;
                        y += dir.1;
                    }
                }
            }
        }


        let mut max = 0;
        let mut ans = 0;
        for i in 10..=1000000 {
            if is_prime[i] && res[i] >= max {
                max = res[i];
                ans = i;
            }
        }
        if max == 0 {
            return -1;
        }
        ans as i32
    }
}