前言

距离建站已经大半个月了, 却一直没有发一篇博客, 一直想着写一点什么, 可以又实在没有什么好写的, 纯粹为了写博客而写博客也没有必要.

最近主要做的工作大概有三块

断断续续地复现论文
学习rust
刷leetcode

关于复现论文等到复现完毕倒是可以写一篇博客, 学习rust的话自己记一记笔记就好了, 不值得写一篇博客. 不过今天做的一道 leetcode 题目感觉倒是值得记录一下.

正文

最近在跟着这个网站刷动态规划的题目就, 按照这个网站上的分类, 这是一道动态规划的题目, 但是看到题目之后并无法按照常用的解动态规划题目的套路来解决这个题目, 后来看了一下这个题解发现好像也确实不能算动态规划吧.

这虽然是一道hard题目, 但是看完题解之后感觉并没有特别难理解的思维过程. 而且和直接做的一道矩阵相关的题目(最大矩形)有一部分思想是类似的, 都是分行/分列考虑. 每一行/列内的处理过程也和之前一道题目(和为K的子数组)相似.

我参考的题解里面还用了python的 BiSect 数据结构, rust的stdlib没有提供这个数据结构, 于是只好自己造轮子. 感觉二分搜索啥的真的都是基本技能, 随处都可能用到. 还有找左边界, 右边界的变体啥的.

题目定义

题目定义如下: 给定一个非空矩阵matrix 和一个整数 k, 找到matrix内部不大于k的最大子矩阵和. 此处矩阵和的定义就是矩阵中所有元素的和.

示例如下:

输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2
解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

详情可以参考leetcode

解题思路

我们先考虑这样一个问题. 给定一个非空数组 arr 和一个数 k. 找到其中数组和不大于k的最大子数组和.

示例如下:

输入: arr = [1, 0, -1, 3], k = 2
输出: 2
解释: 子数组[-1, 3]数组和是 2，且 2 是不超过 k 的最大数字（k = 2）。

首先我们考虑”不大于k“这个条件.

设 f(i, j) = arr[i] + arr[i+1] + .. + arr[j-1] + arr[j]

则有 f(i, j) = f(0, j) - f(0, i-1)

可以得出若 f(i, j) <= k, 则有 f(0, j) - f(0, i-1) <= k, 即f(0, j) - k <= f(0, i-1)

其次我们考虑第二个条件”最大子数组和”. 则我们需要在满足f(0, j) - k <= f(0, i-1)的条件下使得 f(0, i-1) 尽可能地小. 当 f(0, i-1)取得最小值地时候, 即 f(0, j) - k = f(0, i-1), 此时 f(0, j) - f(0, i-1) = k. 我可以直接返回了.

我们用一个变量acc记录每个元素的累计和, 一个有序(升序)数组bs保存每个位置的累计和. 可以得到如下伪代码

acc = 0
res = INT_MIN
bs.insort(0) # !!! 一个数都没有的时候和为0
for val in arr:
    acc += val # f(0, j)
    pre = acc - k
    lower_bound 为bs中大于等于pre的最小值 # f(0, i-1)
    res = max(res, acc - lower_bound)
    将acc插入到bs中的某一位置, 使得bs依然保持升序
return res

由此我们可以得到计算一个数组arr中不大于k的最大子数组和了. 这儿如果用python写的话可以用BiSect这个数据结构, 但是rust的stdlib中并没有这个数据结构, 所以选择自己造了个轮子, 不是很复杂, 就一个Vec和一个二分查找.

对于这道矩阵题我们可以对其进行分解, 将其转化成计算多个数组中不大于k的最大子数组的情况. 具体划分方法有分行和分列两种方法, 我们以分列计算为例.

设最终得到的矩阵占据的列范围为(col1, col2). 那么我们通过如下遍历肯定可以枚举出该列.

for j1 in 0..n{
    for j2 in j1..n{
        // do sth
    }
}

我们再用一个列向量col_sum记录列范围为 (j1, j2) 的每一行的所有元素和: col_sum[i] = matrix[i][j1] + matrix[i][j1+1] + .. + matrix[i][j2-1] + matrix[i][j2], i in 0..m (说的可能不太清楚, 可以看这个视频)

然后对于每一个col_sum求其不大于k的最大子数组和即可. 成功转化为了数组题. 贴一下代码吧

struct BiSect<T>{
    pub data: Vec<T>,
}

/// https://docs.python.org/3/library/bisect.html
impl BiSect<i32>{
    pub fn new() -> BiSect::<i32>{
        BiSect::<i32>{
            data: Vec::new(),
        }
    }

    pub fn wit_vec(vec: Vec<i32>) -> BiSect::<i32>{
        BiSect::<i32>{
            data: vec,
        }
    }

    /// BiSec 中不小于val的第一个(索引最小)数的索引
    pub fn bisect_left(&self, val: i32) -> usize{
        let mut lo: usize = 0;
        let mut hi: usize = self.data.len();
        while lo < hi {
            let mid = lo + (hi - lo) / 2;
            if self.data[mid] < val {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        lo
    }

    /// BiSec所有大于等于val的数中最小的数 or None
    pub fn no_less_than(&self, val: i32) -> Option<i32>{
        let idx = self.bisect_left(val);
        if (idx >= self.data.len()){
            return None;
        } else {
            return Some(self.data[idx]);
        }
    }

    /// 将 val 插入数组中, 保证数组的升序性
    pub fn insort(&mut self, val: i32){
        self.data.insert(self.bisect_left(val), val);
    }
}

pub fn max_sum_submatrix(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = matrix.len();
    if (m == 0) {return 0;}
    let n = matrix[0].len();
    if (n == 0) {return 0;}

    let mut max = i32::MIN;

    for col_start in 0..n {
        let mut col_acc = vec![0; m];
        for col_end in col_start..n {
            for row_idx in 0..m {
                col_acc[row_idx] += matrix[row_idx][col_end];
            }
            println!("cols : ({}, {})", col_start, col_end);
            println!("{:?}", col_acc);
            let mut bs = BiSect::new();
            bs.insort(0); // 表示没有数的时候和为0
            let mut acc = 0;
            for val in col_acc.iter() {
                acc += val;
                let v1 = acc - k;
                if let Some(v2) = bs.no_less_than(v1) {
                    max = i32::max(max, acc - v2);
                }
                if (max == k){return max;}
                bs.insort(acc);
            }
        }
        
    }
    max
}

fn main(){
    let vv1 = vec![
        vec![2, 2, -1], 
    ];
    let res = max_sum_submatrix2(vv1, 0);
    println!("res is {:?}", res);
}

结语

刷leetcode的时候遇到过挺多有意思的题目的. 但是往往都懒得记录了… 希望这个博客可以经常更新吧.

写rust真是一种快乐的事情(二叉树除外2333). 环境配置十分简单, 直接cargo new就可以了. 编译器的报错信息十分直观. 需多语法的设计非常符合我的使用逻辑, 用起来非常舒服. 比如 if let, match这些(语法糖?). 不过对于太底层的东西(比如操作内存)用起来就感觉太繁琐了. 比如下面这个二叉树的定义, 每当这个时候就会怀念c语言朴实无华的指针2333.

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

不过刚才和秋豪聊天得知rust的 Foreign Function Interface (FFI) 挺好用的. 所以底层的东西可以用c写.

当时第一次知道rust这个语言貌似是N1ctf的一道堆题, 自此就对rust的印象就是用的dlmalloc, 内存安全做的好, 逆向难度大. 经过一段时间的学习之后现在对这门语言的印象大为改观, 写rust使我快乐 :P