pfx/
lib.rs

1//! # Rust :: Prefix Sum
2
3/// 363h Max Sum of Rectangle No Larger Than K
4struct Sol363 {}
5
6impl Sol363 {
7    pub fn max_sum_submatrix(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
8        let mut pfxsum = vec![vec![0; matrix[0].len() + 1]; matrix.len()];
9        let mut xsum = i32::MIN;
10
11        for r in 0..matrix.len() {
12            println!("-> {pfxsum:?}");
13
14            for c in 0..matrix[r].len() {
15                pfxsum[r][c + 1] = pfxsum[r][c] + matrix[r][c];
16                xsum = xsum.max(pfxsum[r][c + 1]).min(k);
17            }
18        }
19
20        xsum
21    }
22}
23
24/// 1352m Product of the Last K Numbers
25#[derive(Debug)]
26struct ProductOfNumbers {
27    pds: Vec<i32>,
28}
29
30impl ProductOfNumbers {
31    fn new() -> Self {
32        ProductOfNumbers { pds: vec![1] }
33    }
34
35    fn add(&mut self, num: i32) {
36        match num {
37            0 => {
38                self.pds = vec![1];
39            }
40            _ => {
41                self.pds.push(num * self.pds[self.pds.len() - 1]);
42            }
43        }
44
45        println!("-> {} {:?}", num, self);
46    }
47
48    fn get_product(&self, k: i32) -> i32 {
49        match self.pds.len() <= k as usize {
50            true => 0,
51            _ => self.pds[self.pds.len() - 1] / self.pds[self.pds.len() - 1 - k as usize],
52        }
53    }
54}
55
56/// 2845m Count of Interesting Subarrays
57struct Sol2845;
58
59impl Sol2845 {
60    pub fn count_interesting_subarrays(nums: Vec<i32>, modulo: i32, k: i32) -> i64 {
61        use std::collections::HashMap;
62
63        let mut counts = HashMap::new();
64        counts.entry(0).or_insert(1);
65
66        let mut psum = 0;
67        nums.iter().fold(0, |mut count, n| {
68            if n % modulo == k {
69                psum += 1;
70            }
71
72            match counts.get(&((psum - k + modulo) % modulo)) {
73                Some(v) => count += v,
74                _ => (),
75            }
76
77            counts
78                .entry(psum % modulo)
79                .and_modify(|f| *f += 1)
80                .or_insert(1);
81
82            println!("-> {:?}", counts);
83
84            count
85        })
86    }
87}
88
89#[cfg(test)]
90mod tests;
pfx/lib.rs

pfx/
lib.rs
