главная новое лучшее написать
неделя месяц год вечное
посты пользователи ответы

2 leetcoder 20-03-2025 к записи «🔗 Оптимальный поиск минимальной AND-стоимости пути »

Полезно заметить, что если использовать для разбиения на компоненты связности подход с Disjoint Set Unions, — можно получить решение, работающее на практике в 2 раза быстрее за счёт более эффективных аллокаций памяти (нет необходимости поддерживать списки смежности).

struct UnionFind {
    parent: Vec<usize>,
    size: Vec<usize>,
    min_and: Vec<i32>,
}

impl Solution {
    pub fn minimum_cost(n: i32, edges: Vec<Vec<i32>>, query: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut uf = UnionFind::new(n);

        // Process edges to construct the Union-Find structure
        for edge in &edges {
            let (u, v, w) = (edge[0] as usize, edge[1] as usize, edge[2]);
            uf.union(u, v, w);
        }

        // Process queries efficiently
        query.into_iter().map(|q| {
                let (s, t) = (uf.find(q[0] as usize), uf.find(q[1] as usize));
                if s == t { uf.min_and[s] } else { -1 }
            }).collect()
    }
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),
            size: vec![1; n],
            min_and: vec![-1; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]); // Path compression
        }
        self.parent[x]
    }

    fn union(&mut self, a: usize, b: usize, weight: i32) {
        let mut root_a = self.find(a);
        let mut root_b = self.find(b);

        if root_a != root_b {
            // Union by size: attach the smaller tree under the larger tree
            if self.size[root_a] < self.size[root_b] {
                std::mem::swap(&mut root_a, &mut root_b);
            }
            self.parent[root_b] = root_a;
            self.size[root_a] += self.size[root_b];
            self.min_and[root_a] &= self.min_and[root_b];
        }

        // Update min_and for the new root
        self.min_and[root_a] &= weight;
    }
}
перейти
1 leetcoder 18-03-2025 к записи «🔥 Поиск наибольшего «красивого» подмассива методом скользящего окна в чистом функциональном стиле»

Привычное итеративное решение, конечно, стоит также привести для сравнения

impl Solution {
    pub fn longest_nice_subarray(nums: Vec<i32>) -> i32 {
        let mut current_bitset = 0;
        let mut max_len = 0;
        let mut left = 0;

        for (right, &val) in nums.iter().enumerate() {
            // Shrink the window if nums[right] conflicts with current_bitset
            while current_bitset & val != 0 {
                current_bitset ^= nums[left];
                left += 1;
            }

            // Expand the window by including nums[right]
            current_bitset |= val;
            max_len = max_len.max((right - left + 1) as i32);
        }

        max_len
    }
}
перейти
1 leetcoder 04-03-2025 к записи «🚀 Разбиение массива вокруг опорного элемента с сохранением порядка»

Стоит также обратить внимание на чуть более медленное, зато короткое решение через стабильную сортировку

impl Solution {
    pub fn pivot_array(mut nums: Vec<i32>, pivot: i32) -> Vec<i32> {
        nums.sort_by_key(|&num| num.cmp(&pivot)); nums
    }
}
перейти