想问一下有没有能实现`windows_mut`的函数

Neutron3529 发表于 2021-03-02 00:45

leetcode刷题时候遇到的

struct NumMatrix (Vec<Vec<i32>>);
impl NumMatrix {

    fn new(mut matrix: Vec<Vec<i32>>) -> Self {
        if matrix.len()==0{Self(vec![vec![0]])}else{
        matrix.iter_mut().for_each(|i|{i.iter_mut().fold(0,|s,x|{*x+=s;*x});});
        let s=vec![0;matrix[0].len()];/*这里，以及下面的一行*/
        matrix.iter_mut().fold(s,|s,x|{s.iter().zip(x.iter_mut()).for_each(|(s,x)|*x+=s);x.clone()});
        /*这两行其实可以转化成类似`matrix.windows_mut(2).for_each(|[s,x]|s.iter().copied().zip(x.iter_mut()).for_each(|(s,x)|*x+=s))`的句子，可惜并没有类似的windows_mut，如果用其他方法，总觉得会触发若干次边界检查，大家有比较好的办法/函数吗？*/
        Self(matrix)}
    }
    
    fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
        self.0[row2 as usize][col2 as usize] - if col1>0{self.0[row2 as usize][(col1-1)as usize]}else{0} - if row1>0{self.0[(row1-1)as usize][col2 as usize]}else{0} +if col1*row1>0{self.0[(row1-1)as usize][(col1-1)as usize]}else{0}
    }
}

评论区

写评论

eweca-d 2021-03-02 01:33

这不是今天的每日一题么。

且不说你要求的这个函数用到的地方可能不会很多，比起若干次边界检查什么的，直接下标运算生成dp数组不香么？你这个太炫技了，我看着真是头疼。

直接:

impl NumMatrix {
    fn new(matrix: Vec<Vec<i32>>) -> Self {
        let m = matrix.len();
        if m == 0 {
            return NumMatrix{ pre_sum: vec![] };
        }
        let n = matrix[0].len();
        let mut pre_sum = vec![vec![0; n + 1]; m + 1];

        for i in 0..m {
            for j in 0..n {
                pre_sum[i + 1][j + 1] += pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + matrix[i][j];
            }
        }

        NumMatrix{ pre_sum }
    }
    
    fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
        let row1 = row1 as usize;
        let col1 = col1 as usize;
        let row2 = row2 as usize;
        let col2 = col2 as usize;
        self.pre_sum[row2 + 1][col2 + 1] - self.pre_sum[row2 + 1][col1] - self.pre_sum[row1][col2 + 1] + self.pre_sum[row1][col1]
    }
}

不就完事了。

个人觉得，在这个例子中，使用迭代器避免的一点点边界检查开销，完全不值得牺牲代码可读性。

另外dp多加一行一列，可以避免手动检查边界，还是很划算的。

1 共 1 条评论, 1 页