rust_practice_leetcode_daily_code

fn main(){

}

fn main(){

}

fn main(){

}

fn main(){

}

fn main(){

}

数组

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]


fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，
并且这 n 个数相加和为 0 。



示例 1：
输入：n = 5
输出：[-7,-1,1,3,4]
解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。


示例 2：
输入：n = 3
输出：[-1,0,1]


示例 3：
输入：n = 1
输出：[0]
 

提示：
1 <= n <= 1000
*
*/

impl Solution {
    pub fn sum_zero(n: i32) -> Vec<i32> {
        let mut n = n;
        let mut ans = Vec::new();

        let mod_n = n % 2;
        if mod_n == 1 {
            ans.push(0);
        }
        let mut k = 1;

        while n > 1 {
            ans.push(k);
            ans.push(-k);

            n -= 2;
            k += 1;
        }
        ans
    }
}

PartialOrd	partial_cmp	Option<Ordering>	定义部分排序，允许不可比较的值。

Ord	cmp	Ordering	定义全排序，必须总是可比较。


比较增量：
使用 partial_cmp 比较两个浮点数增量（因为浮点数比较可能失败，如 NaN）。
unwrap_or(Ordering::Equal)：如果比较失败（例如理论上不可能出现的 NaN），默认返回 Equal。

排序方向：
self_inc.partial_cmp(&other_inc) 表示 更大的增量排在前面（因为 BinaryHeap 是最大堆）。
如果 self_inc > other_inc，返回 Greater，self 会排在堆顶。


BinaryHeap 的要求：
BinaryHeap 依赖 Ord 实现来排序元素。
但 Ord 要求先实现 PartialOrd 和 Eq（通过 #[derive(Eq)] 或手动实现）。

self_inc.partial_cmp(&other_inc)： 若 self_inc > other_inc，返回 Greater，self 会被排到后面（但 BinaryHeap 是最大堆，会反转顺序，最终 self 在堆顶）。

self_inc.partial_cmp(&other_inc) 本身的比较方向是“从小到大”，但配合 BinaryHeap（最大堆）使用时，会变成“从大到小”的最终效果！

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

use std::collections::BinaryHeap;


fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。
给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，
表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。
你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。
平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。
与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

 
示例 1：
输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。


示例 2：
输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485
 

提示：
1 <= classes.length <= 10^5
classes[i].length == 2
1 <= passi <= totali <= 10^5
1 <= extraStudents <= 10^5
 *
 */

#[derive(Debug, PartialEq)]
struct Class {
    pass: i32,  // 通过考试的学生人数
    total: i32,  // 班级总学生人数
}

impl Eq for Class{} 

impl PartialOrd for Class {
    // 委托模式：
    // 如果类型总是可比较（如 Class），PartialOrd 可以直接委托给 Ord 的 cmp。
    // 堆排序的核心：
    // Ord 的 cmp 决定了 BinaryHeap 如何排序，这里通过增量计算确保每次选择提升最大的班级。
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}


impl Ord for Class {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let self_inc = (self.pass as f64 + 1.0) / (self.total  as f64 + 1.0) - (self.pass as f64) / (self.total as f64);
        let other_inc = (other.pass as f64 + 1.0) / (other.total  as f64 + 1.0) - (other.pass as f64) / (other.total as f64);

        
        // 降序排列：提升值大的排在前面
        // 我们需要最大的增量排在前面，因此比较 self_inc 和 other_inc
        self_inc.partial_cmp(&other_inc).unwrap_or(std::cmp::Ordering::Equal)
    }
}


impl Solution {

    pub fn max_average_ratio(classes: Vec<Vec<i32>>, extra_students: i32) -> f64 {
        let len = classes.len();

        let mut heap = BinaryHeap::new();

        // 初始化
        for class in classes {
            let pass = class[0];
            let total = class[1];
            
            heap.push(Class { pass, total});
        }

        
        let mut extra = extra_students;

        // 分配所有额外的学生
        while extra > 0 {
            if let Some(mut avg) = heap.pop() {   // 从堆中取出提升最大的班级
                avg.pass += 1;
                avg.total += 1;

                heap.push(avg);

                extra -= 1;
            }
        }

        let mut ans = 0.0;

        while let Some(c) = heap.pop() {
            ans += c.pass as f64 / c.total as f64;
        }

        ans / len as f64
    }
}

根据题意，每回合摘一朵花，摘到最后一朵花的人获胜。 所以当且仅当鲜花个数 x+y 是奇数时，Alice 摘到最后一朵花。

要让 x+y 是奇数：

如果 x 是偶数，那么 y 必须是奇数。 如果 x 是奇数，那么 y 必须是偶数。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 
Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。
环形的草地上有一些鲜花，Alice 到 Bob 之间顺时针有 x 朵鲜花，逆时针有 y 朵鲜花。

游戏过程如下：
Alice 先行动。
每一次行动中，当前玩家必须选择顺时针或者逆时针，然后在这个方向上摘一朵鲜花。

一次行动结束后，如果所有鲜花都被摘完了，那么 当前 玩家抓住对手并赢得游戏的胜利。

给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：


按照上述规则，Alice 必须赢得游戏。
Alice 顺时针方向上的鲜花数目 x 必须在区间 [1,n] 之间。
Alice 逆时针方向上的鲜花数目 y 必须在区间 [1,m] 之间。
请你返回满足题目描述的数对 (x, y) 的数目。
 *
 */

impl Solution {
    pub fn flower_game(n: i32, m: i32) -> i64 {
        // x <= n
        // y <= m 
        //  n*m=总数，要保证 x+y 是奇数，才能稳赢.、
        // 不是奇数 就是 偶数. n*m / 2
        n as i64 + m as i64 / 2
    }
}

这个算法的思路：

左下角三角形：对于每个对角线偏移量 d（0到n-1），收集从 (d, 0) 开始的对角线元素，降序排序后放回

右上角三角形：对于每个对角线偏移量 d（1到n-1），收集从 (0, d) 开始的对角线元素，升序排序后放回

// 左下角对角线：从 (d, 0) 开始
for j in 0..(n-d) {
    let i = d + j;  // 行索引
    let j = j;      // 列索引
}

// 右上角对角线：从 (0, d) 开始  
for i in 0..(n-d) {
    let i = i;      // 行索引
    let j = d + i;  // 列索引
}

对角线遍历技巧 识别和访问矩阵中对角线元素的方法

对于左下角三角形：对角线元素满足 行索引 - 列索引 = 常数

对于右上角三角形：对角线元素满足 行索引 + 列索引 = 常数

AC Code 时间复杂度为 O(n³ log n)，对于 n ≤ 10 的约束来说完全足够。

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}



/**
 
给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
右上角三角形 的对角线按 非递减顺序 排序。
 

示例 1：
输入： grid = [[1,7,3],[9,8,2],[4,5,6]]
输出： [[8,2,3],[9,6,7],[4,5,1]]
解释：

标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：
[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：
[7, 2] 变为 [2, 7]。
[3] 保持不变。



示例 2：
输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解释：
标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。


示例 3：
输入： grid = [[1]]
输出： [[1]]
解释：
只有一个元素的对角线已经符合要求，因此无需修改。
 

提示：
grid.length == grid[i].length == n
1 <= n <= 10
-10^5 <= grid[i][j] <= 10^5

 *
 */


impl Solution {
    pub fn sort_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let row = grid.len();
        let mut ans = grid.clone();

        // 左下角--包括对角线
        for d in 0..row {
            let len = row - d;
            let mut diag: Vec<i32> = (0..len).map(|j| ans[j + d][j]).collect();
            // 逆序
            diag.sort_by(|a, b| b.cmp(a));

            for j in 0..len {
                ans[j + d][j] = diag[j];
            }
        }


        // d 是对角线偏移量
        for d in 1..row {
            let len = row - d;
            let mut diga: Vec<i32> = (0..len).map(|j| ans[j][j + d]).collect();
            // 顺序
            diga.sort();
            
            for j in 0..len {
                ans[j][j + d] = diga[j];
            }
        }

        ans
    }
}

滑动窗口：使用滑动窗口技术来跟踪当前窗口中的1的序列。窗口由left和right指针定义。

zero_count：记录当前窗口中0的个数。因为最多只能有一个0（删除一个元素后全为1），所以当zero_count超过1时需要调整窗口。

窗口调整：当zero_count > 1时，移动left指针，直到窗口内0的个数不超过1。

最大长度计算：每次窗口调整后，计算当前窗口的长度（right - left），并更新max_len。

全1数组处理：如果整个数组都是1，必须删除一个1，因此返回max_len - 1。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
*

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

 

提示 1：
输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。


示例 2：
输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。


示例 3：
输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。
 

提示：
1 <= nums.length <= 10^5
nums[i] 要么是 0 要么是 1 。

*
*/

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let mut ans = 0 as i32;

        // 双指针 滑动
        let mut left = 0;
        let mut zero_cnt = 0; // 记录 0 的个数


        for right in 0..nums.len() {

            if nums[right] == 0 {
                zero_cnt += 1;
            }

            while zero_cnt > 1 {
                // 滑动窗口内只维护一个 0 

                if nums[left] == 0 {
                    zero_cnt -= 1;
                }

                left += 1;
            }

            ans = ans.max((right - left) as i32);
        }


        ans
    }

}

预处理高度==》 从当前行向上连续的1 高度 动态规划 ==》 方便计算出以当前元素的子矩形数量..

单调栈 ==》 用来计算当前列 + 维护的最小高度 ==》 子矩形数量.

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
*

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。


1 0 1
1 1 0
1 1 0

示例 1：
输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。



0 1 1 0
0 1 1 1 
1 1 1 0

示例 2：
输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。


提示：
1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1

*
*/

impl Solution {
    pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
        let row = mat.len();
        let col = mat[0].len();

        let mut heights = vec![vec![0; col]; row];

        let mut ans = 0;

        // 初始化 -- 对于每一列，从上到下累计连续高度.
        for i in 0..row {
            for j in 0..col {
                // 记录高度数组
                if mat[i][j] == 1 {
                    heights[i][j] = if i == 0  {
                        1
                    } else {
                        heights[i - 1][j] + 1
                    }
                }

            }
        }


        // 遍历每一个元素，假设当前元素是子矩形的右下角. 可以组成多少个子矩形
        // 遍历每一行，计算以 (i,j) 为右下角的子矩阵数量
        for i in 0..row {

            // 维护一个最小高度的单调栈 -- value == col
            let mut stack: Vec<usize> = Vec::new();
            let mut dp = vec![0; col];
            for j in 0..col {

                while !stack.is_empty() && heights[i][*stack.last().unwrap()] >= heights[i][j] {
                    stack.pop();
                }

                if stack.is_empty() {
                    //为空，说明当前 列 col 目前就是最小的高度列
                    // 0 - j col 都可以更新一次最小高度的子矩形
                    dp[j] = heights[i][j] * (j - 0 + 1);
                } else {
                    // 以栈顶元素为最小高度
                    // (0 --- 栈顶col --> dp[栈顶col]) + (当前列 -- 栈顶col ---> 新形成的子矩形)
                    let last = *stack.last().unwrap();
                    dp[j] = dp[last] + heights[i][j] * (j - last);
                }

                stack.push(j);

                ans += dp[j];
            }

        }

        ans as i32
    }
}

带注释版

pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
    // 获取矩阵的行数和列数
    let m = mat.len();
    let n = mat[0].len();
    // 初始化高度数组，heights[i][j] 表示从 mat[i][j] 向上连续的1的个数（包括自身）
    let mut heights = vec![vec![0; n]; m];
    let mut result = 0; // 最终结果

    // 预处理阶段：计算每个位置的高度数组
    for i in 0..m {
        for j in 0..n {
            if mat[i][j] == 1 {
                // 如果是第一行，高度为1，否则为上一行同列的高度加1
                heights[i][j] = if i == 0 { 1 } else { heights[i - 1][j] + 1 };
            }
        }
    }

    // 动态规划阶段：计算以每个点为右下角的子矩形数量
    for i in 0..m {
        let mut stack = Vec::new(); // 维护一个单调递增的栈
        let mut dp = vec![0; n];    // dp[j] 表示以 (i,j) 为右下角的子矩形数量
        for j in 0..n {
            // 弹出栈顶元素，直到栈为空或栈顶元素的高度小于当前高度
            while !stack.is_empty() && heights[i][*stack.last().unwrap()] >= heights[i][j] {
                stack.pop();
            }
            // 根据栈是否为空来计算 dp[j]
            if stack.is_empty() {
                // 栈为空，说明当前高度是到目前最小的，可以形成 (j+1) 个新矩形
                dp[j] = heights[i][j] * (j + 1);
            } else {
                // 栈不为空，复用栈顶元素的 dp 值，并加上新形成的矩形数量
                let last = *stack.last().unwrap();
                dp[j] = dp[last] + heights[i][j] * (j - last);
            }
            // 将当前列索引压入栈
            stack.push(j);
            // 累加到结果中
            result += dp[j];
        }
    }

    // 返回结果
    result as i32
}

动态规划阶段变化过程的详细示例
让我们通过一个具体的例子来说明动态规划阶段的变化过程。我们采用示例1中的矩阵：

mat = [
 [1, 0, 1],
 [1, 1, 0],
 [1, 1, 0]
]
预处理后的高度数组 heights
首先，我们预处理得到 heights 数组：

第一行 i=0：

heights[0][0] = 1（mat[0][0] = 1）
heights[0][1] = 0（mat[0][1] = 0）
heights[0][2] = 1（mat[0][2] = 1）
第二行 i=1：

heights[1][0] = 2（mat[1][0] = 1 且 heights[0][0] = 1）
heights[1][1] = 1（mat[1][1] = 1 且 heights[0][1] = 0）
heights[1][2] = 0（mat[1][2] = 0）
第三行 i=2：

heights[2][0] = 3（mat[2][0] = 1 且 heights[1][0] = 2）
heights[2][1] = 2（mat[2][1] = 1 且 heights[1][1] = 1）
heights[2][2] = 0（mat[2][2] = 0）
最终的 heights 数组：

heights = [
 [1, 0, 1],
 [2, 1, 0],
 [3, 2, 0]
]
动态规划阶段
现在，我们逐行进行动态规划计算。

第一行 i=0：
初始化 stack = [] 和 dp = [0, 0, 0]。

j=0：

heights[0][0] = 1
stack 为空，dp[0] = 1 * (0 + 1) = 1
stack = [0]
result += 1（result = 1）
j=1：

heights[0][1] = 0
stack 不为空，heights[0][0] = 1 >= 0，弹出 0，stack = []
stack 为空，dp[1] = 0 * (1 + 1) = 0
stack = [1]
result += 0（result = 1）
j=2：

heights[0][2] = 1
stack 不为空，heights[0][1] = 0 < 1，不弹出
last = 1，dp[2] = dp[1] + 1 * (2 - 1) = 0 + 1 = 1
stack = [1, 2]
result += 1（result = 2）
第二行 i=1：
初始化 stack = [] 和 dp = [0, 0, 0]。

j=0：

heights[1][0] = 2
stack 为空，dp[0] = 2 * (0 + 1) = 2
stack = [0]
result += 2（result = 4）
j=1：

heights[1][1] = 1
stack 不为空，heights[1][0] = 2 >= 1，弹出 0，stack = []
stack 为空，dp[1] = 1 * (1 + 1) = 2
stack = [1]
result += 2（result = 6）
j=2：

heights[1][2] = 0
stack 不为空，heights[1][1] = 1 >= 0，弹出 1，stack = []
stack 为空，dp[2] = 0 * (2 + 1) = 0
stack = [2]
result += 0（result = 6）
第三行 i=2：
初始化 stack = [] 和 dp = [0, 0, 0]。

j=0：

heights[2][0] = 3
stack 为空，dp[0] = 3 * (0 + 1) = 3
stack = [0]
result += 3（result = 9）
j=1：

heights[2][1] = 2
stack 不为空，heights[2][0] = 3 >= 2，弹出 0，stack = []
stack 为空，dp[1] = 2 * (1 + 1) = 4
stack = [1]
result += 4（result = 13）
j=2：

heights[2][2] = 0
stack 不为空，heights[2][1] = 2 >= 0，弹出 1，stack = []
stack 为空，dp[2] = 0 * (2 + 1) = 0
stack = [2]
result += 0（result = 13）
最终结果
累加所有 dp[j] 后，result = 13，与示例1的输出一致。

动态规划阶段的总结
初始化：对于每行 i，初始化栈 stack 和 dp 数组。
遍历列：从左到右遍历每一列 j：
维护单调栈：弹出栈顶元素直到栈顶高度小于当前高度 heights[i][j]。
计算 dp[j]：
如果栈为空，dp[j] = heights[i][j] * (j + 1)。
否则，dp[j] = dp[stack.top()] + heights[i][j] * (j - stack.top())。
压栈和累加：将 j 压入栈，并累加 dp[j] 到 result。
通过这种方式，我们高效地计算了以每个点为右下角的所有全1子矩形的数量，避免了重复计算。

为什么栈为空时，可以形成 (j + 1) 个新矩形？

1. 单调栈的作用 在计算 dp[j] 时，我们需要维护一个单调递增栈，栈中存储的是列索引 k，满足 heights[i][k] < heights[i][j]。这个栈的作用是：

确保栈顶元素的高度比当前高度小，这样我们可以利用栈顶信息来计算当前列 j 能形成的新矩形数量。 2. 栈为空时的含义 当 stack.is_empty() 时，表示：

当前列 j 的高度 heights[i][j] 是当前行 i 从 0 到 j 的最小高度。 也就是说，heights[i][j] 比 heights[i][0..j] 的所有高度都要小（或等于）。 3. 如何计算 dp[j]？ 在这种情况下，所有以 (i,j) 为右下角的全1子矩阵的左边边界可以延伸到 0（因为当前高度是最小的）。因此：

子矩阵的宽度可以是 1, 2, …, j + 1。 子矩阵的高度是 heights[i][j]（因为它是当前最小的）。 因此，总共可以形成的子矩阵数量为：

dp[j] = heights[i][j] * (j + 1) heights[i][j]：子矩阵的高度。 j + 1：可能的宽度（从 1 到 j + 1）。

思路： 找到 所有1 的最小行、最大行、最大列、最小列..

动态维护，然后通过 矩形的面积 = (max_row - min_row + 1) * (max_col - min_col + 1) 出结果

边界维护 在遍历过程中，动态维护 1 的边界： min_row：所有 1 的最小行号。 max_row：所有 1 的最大行号。 min_col：所有 1 的最小列号。 max_col：所有 1 的最大列号。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
*

给你一个二维 二进制 数组 grid。
请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。


0 1 0
1 0 1

示例 1：
输入： grid = [[0,1,0],[1,0,1]]
输出： 6
解释：
这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。


0 0 
1 0

示例 2：
输入： grid = [[0,0],[1,0]]
输出： 1
解释：
这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。


提示：
1 <= grid.length, grid[i].length <= 1000
grid[i][j] 是 0 或 1。
输入保证 grid 中至少有一个 1 。

*
*/

impl Solution {
    pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
        let mut min_row = usize::MAX;
        let mut max_row = usize::MIN;
        let mut min_col = usize::MAX;
        let mut max_col = usize::MIN;

        // 二维数组遍历
        for (i, row) in grid.iter().enumerate() {
            for (j, &value) in row.iter().enumerate() {
                
                // 如果是 1 ，更新边界值
                if value == 1 {
                    min_row = min_row.min(i);
                    max_row = max_row.max(i);

                    min_col = min_col.min(j);
                    max_col = max_col.max(j);
                }

            }
        }


        // if min_row == usize::MIN {
            // 表示没有更新过... -- 这道题没有这种情况
        // }

        let hight = max_row - min_row + 1;
        let width = max_col - min_col + 1;

        // 长 * 宽
        hight as i32 * width as i32
    }
}

状态定义：dp[i][j] 表示以 (i, j) 为右下角的最大正方形边长


状态转移:
    对于边界情况（i == 0 或 j == 0），dp[i][j] = 1
    对于其他情况，dp[i][j] = min(左, 上, 左上) + 1
    无论哪种情况，都要将 dp[i][j] 累加到结果中


结果计算：将每个 dp[i][j] 的值累加，因为 dp[i][j] 表示以 (i, j) 为右下角的所有正方形数量

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 *

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，
请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。


示例 1：
输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.



示例 2：
输入：matrix =
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.


提示：
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

 *
 */

/// 如果matrix[i][j]是0，那么dp[i][j] = 0，因为无法形成任何正方形
///
///
/// 如果matrix[i][j]是1，那么dp[i][j]的值由其上方、左方和左上方的值决定。
/// 具体来说，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
/// 这是因为要形成一个边长为k的正方形，需要其上方、左方和左上方的位置都能形成边长为k-1的正方形。
impl Solution {
    pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
        let row = matrix.len();
        let col = matrix[0].len();

        let mut ans = 0;
        let mut dp = vec![vec![0; col]; row];

        for i in 0..row {
            for j in 0..col {
                if matrix[i][j] == 1 {

                    if i == 0 || j == 0 {
                        // 边界 --- 只能组成 长度为 1 的正方形.
                        dp[i][j] = 1;
                    } else {
                        // dp[i][j] 表示以(i, j)为右下角的正方形的最大边长
                        // 同时，这个值也表示以(i, j)为右下角的正方形的数量\
                        //（例如，如果最大边长为3，那么有3个正方形：边长为1、2和3的正方形）

                        // 左 --- dp[i][j-1]   上 --- dp[i -1][j]   左上角 dp[i-1][j-1]  -- 这三个的最小连续 1 -- 决定这个正方形的大小.
                        let length = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]);

                        dp[i][j] = length + 1;
                    }

                    ans += dp[i][j];
                }
            }
        }

        ans
    }
}

需要统计数组中所有全为0的子数组的数量。 关键在于识别连续的0序列，并计算这些序列中所有可能的子数组数目。

连续的0序列长度为k时，可以形成k*(k+1)/2个子数组 （即长度为1到k的子数组之和）

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {

    println!("Hello, world!");
}

struct Solution {}

/**
 *

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

 

示例 1：
输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。


示例 2：
输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。


示例 3：
输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。
 

提示：
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

 *
 */

impl Solution {
    // 公式： 求一个连续序列的子组合 数量，那么就是 1+2+3+....+k
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut cur_len = 0;

        for num in nums {

            if num == 0 {
                cur_len += 1;   // 如果当前元素是0，增加当前连续0的长度

                ans += cur_len; // 当前连续0的长度即为新增的全0子数组数目（包括长度为1到current_length的所有子数组）
            } else {
                cur_len = 0;
            }

        }

        ans 
    }
}

通过尽可能多地使用 3 来拆分 n，可以最大化乘积。
对于剩余的部分（4、3 或 2），直接乘以其自身可以得到更大的乘积。
这种方法简单高效，适用于给定的约束条件。

举例
只要 num > 4，就不断减去 3 并将 3 乘入 product。
这样做的目的是尽可能多地使用 3，因为 3 的乘积贡献最大。
当 num <= 4 时，退出循环，因为此时直接乘 num 可以得到更大的乘积：
    4 可以拆分成 2 + 2，乘积为 4（比 3 + 1 的 3 更大）。
    3 可以直接乘 3。
    2 可以直接乘 2。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

use std::vec;

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 *

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

 

示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。


示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 

提示:
2 <= n <= 58

 *
 */

impl Solution {
    pub fn integer_break(n: i32) -> i32 {

        if n == 2 {
            return 1;
        }
        if n == 3 {
            return 2;
        }


        let mut ans = 1;
        let mut num = n;

        // 尽可能多地减去 3，并将 3 乘入 product
        // 当 num > 4 时继续循环
        // 因为当 num <= 4 时，直接乘 num 可以得到更大的乘积
        // 例如：
        // - 4 可以拆成 2 + 2，乘积为 4
        // - 3 可以直接乘 3
        // - 2 可以直接乘 2
        while num > 4 {
            ans *= 3;
            num -= 3;
        }

        // num = 4 或者 num = 2  
        ans = ans * num;

        ans
    }


    /// dp 解法
    pub fn integer_break_dp(n: i32) -> i32 {
        if n == 2 {
            return 1;
        }
        if n == 3 {
            return 2;
        }

        let len = n as usize;

        // i 的最大乘积
        let mut dp = vec![0 as i32; len + 1];

        dp[1] = 0; // 无法拆分..
        dp[2] = 1;

        for i in 3..=len {
            for j in 1..i {
                // 不继续拆分 -- j * (i - j)
                // 继续拆分 -- j * dp[i - j]
                let max: i32 = (j as i32 * (i - j) as i32).max(j as i32 * dp[i - j]);
                dp[i] = dp[i].max(max);
            }
        }

        dp[len]
    }

    // dp[6] 的可能拆分：
    // 1 + 5 → max(1*5, 1*dp[5]) → max(5,6) = 6
    // 2 + 4 → max(2*4, 2*dp[4]) → max(8,8) = 8
    // 3 + 3 → max(3*3, 3*dp[3]) → max(9,6) = 9
    // ...
    // 最终 dp[6] = max(6,8,9,...) = 9
}

超级丑数是指其 所有质因数 都出现在给定的质数数组中的正整数

说人话就是 ==> 从 第0个丑数 1 开始, 不断和质因数组里的数相乘. --- 得到第 n 小的丑数..

然后第 i 小的丑数 存入 dp[i] 中，然后再从 dp[i] 中 和 质因数组里的数相乘

带注释版

pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
    let n = n as usize; // 将输入的n转换为usize类型，方便数组索引
    let k = primes.len(); // 获取质数数组的长度
    let mut dp = vec![1; n]; // 初始化动态规划数组，dp[0] = 1
    let mut pointers = vec![0; k]; // 初始化指针数组，每个质数的初始指针都指向0
    
    for i in 1..n { // 从第二个位置开始填充dp数组
        let mut min_val = i32::MAX; // 初始化当前最小值为最大整数
        for j in 0..k { // 遍历每个质数
            let candidate = dp[pointers[j]] * primes[j]; // 计算当前质数乘以对应dp值的候选值
            if candidate < min_val { // 更新最小值
                min_val = candidate;
            }
        }
        dp[i] = min_val; // 将最小值赋给dp[i]
        for j in 0..k { // 遍历每个质数，移动指针
            if dp[pointers[j]] * primes[j] == min_val { // 如果当前质数的候选值等于最小值
                pointers[j] += 1; // 移动指针到下一个位置
            }
        }
    }
    dp[n - 1] // 返回第n个超级丑数
}

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

use std::vec;

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 *

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

 

示例 1：
输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。


示例 2：
输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
 
提示：
1 <= n <= 10^5
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列

 *
 */

impl Solution {
    pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
        let n = n as usize;
        let len = primes.len();
        
        let mut dp = vec![1 as i64; n];
        // 一开始 points[j] 都是 == 0 
        let mut points = vec![0; len];
        

        // dp[0] = 1;
        // 从第二个质数计算开始
        for i in 1..n {
            let mut min_val = i64::MAX;

            // 遍历给的质数数组
            for j in 0..len {
                // 计算质数 * dp[j] 的值. --- 取最小的. 
                let candidate = dp[points[j]] * primes[j] as i64;

                if candidate < min_val {
                    min_val = candidate;
                }
            }


            dp[i] = min_val;  // 当前第 i 个超级丑数.

            // 更新 当前计算出来的最小 min_val 对应的  points[j]，即 points[j] + 1;
            // 将所有得到最小值的质数的指针向前移动一位，确保下次计算时不会重复使用相同的dp值。
            for idx in 0..len {
                // 已经计算过的 --- 跳过. 进行下一个idx的计算.
                // 本来dp[0] * 2 = 2  dp[1] = 2
                // 下次就是 dp[1] * 2 = 4  ---- points[idx] <= i 的
                if dp[points[idx]] * primes[idx] as i64 == min_val {
                    points[idx] += 1;
                }
            }

        }


        dp[n - 1] as i32
    }
}

选择两块巧克力，使得它们的总价格最小，同时不超过初始的钱数 money

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 *

给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。
同时给你一个整数 money ，表示你一开始拥有的钱数。

你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。
同时你想最小化购买两块巧克力的总花费。

请你返回在购买两块巧克力后，最多能剩下多少钱。
如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。

 

示例 1：
输入：prices = [1,2,2], money = 3
输出：0
解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。



示例 2：
输入：prices = [3,2,3], money = 3
输出：3
解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。
 

提示：
2 <= prices.length <= 50
1 <= prices[i] <= 100
1 <= money <= 100

 *
 */

impl Solution {
    pub fn buy_choco(prices: Vec<i32>, money: i32) -> i32 {
        let mut sort_prices = prices;

        sort_prices.sort(); // 升序排序

        // 最小的两个 cost
        let need_cost = sort_prices[0] + sort_prices[1];

        if need_cost <= money {
            money - need_cost // 返回剩余的价钱
        } else {
            money // 无法购买，返回初始的价钱
        }
    }
}

高效地选择箱子，使得它们的总容量至少等于所有苹果的总数，同时使用的箱子数量最少

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 *

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。
一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。
同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。
请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。


示例 1：
输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。


示例 2：
输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。
 

提示：
1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
输入数据保证可以将包裹中的苹果重新分装到箱子中。

 *
 */

impl Solution {
    pub fn minimum_boxes(apple: Vec<i32>, capacity: Vec<i32>) -> i32 {
        // 苹果总数
        let total_apples = apple.iter().sum();

        let mut sort_cap = capacity.clone();

        // 降序
        sort_cap.sort_by(|a, b| b.cmp(&a));


        let mut ans = 0;
        let mut sum = 0;


        // 从大到小遍历箱子容量
        for &cap in &sort_cap {

            sum += cap;
            ans += 1;

            // 累加大于苹果数量后，退出.
            if sum >= total_apples {
                break;
            }

        }

        ans
    }
}

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

fn main() {
    println!("Hello, world!");
}

struct Solution {}

/**
 *

给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。


示例 1：
输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。


示例 2：
输入：num = 9996
输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。


示例 3：
输入：num = 9999
输出：9999
解释：无需改变就已经是最大的数字了。


提示：
1 <= num <= 10^4
num 每一位上的数字都是 6 或者 9 。

 *
 */

impl Solution {
    pub fn maximum69_number(num: i32) -> i32 {
        // 转成 string
        let mut num_str = num.to_string().chars().collect::<Vec<char>>();

        for i in 0..num_str.len() {
            if num_str[i] == '6' {
                num_str[i] = '9';
                break;
            }
        }

        
        // ! into_iter 生成迭代器 --- 遍历列表元素，会消耗原列表元素的所有权。
        // ! collect 收集成 String 类型，然后 通过 parse 转换成 i32 数字.
        num_str.into_iter().collect::<String>().parse::<i32>().unwrap()
    }
}

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

/*

给定一个整数，写一个函数来判断它是否是 4 的幂次方。
如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x


示例 1：
输入：n = 16
输出：true


示例 2：
输入：n = 5
输出：false


示例 3：
输入：n = 1
输出：true
 

提示：
-2^31 <= n <= 2^31 - 1

进阶：你能不使用循环或者递归来完成本题吗？

*/

struct Solution {}

impl Solution {
    pub fn is_power_of_four(n: i32) -> bool {
        let mut n = n;

        while n > 0 {
            if n % 4 == 0 {
                n /= 4;
            } else {
                break;
            }
        }        

        n == 1
    }
}

这个问题的解法基于 三进制（Base-3）表示法 的数学性质，属于 数位分解（Digit Decomposition） 算法的一种变体。其核心思想是：

如果一个数 n 的三进制表示中，每一位只能是 0 或 1（不能有 2），那么 n 可以表示为若干个不同的三的幂之和。

任何整数 n 都可以用 三进制（Base-3） 表示，每一位只能是 0、1 或 2。例如：

5 的三进制是 12（即 1×3¹ + 2×3⁰ = 3 + 2 = 5）。 (2x3^0 ==== 3^0 +3^0) --- 不符合题目要求.

12 的三进制是 110（即 1×3² + 1×3¹ + 0×3⁰ = 9 + 3 + 0 = 12）。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

/*

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，
请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3^x ，我们称这个整数 y 是三的幂。

 
示例 1：
输入：n = 12
输出：true
解释：12 = 3^1 + 3^2


示例 2：
输入：n = 91
输出：true
解释：91 = 3^0 + 3^2 + 3^4


示例 3：
输入：n = 21
输出：false
 

提示：
1 <= n <= 10^7
*/

struct Solution {}


// 在 5 进制（Base-5） 中，一个数的每一位代表的是 5 的幂次方的系数。
// 具体来说，13 的 5 进制表示 是 23，这意味着：
// 2*5^1 + 3*5^0
impl Solution {
    pub fn check_powers_of_three(n: i32) -> bool {
        let mut n = n;
        
        while n > 0 {
            if n % 3 == 2 {  // 如果某一位是 2，说明需要重复使用 3^x，直接返回 false
                return false;
            }
            
            n /= 3;
        }

        true
    }
}

法 1

循环迭代法：通过循环不断地将数字除以3，检查是否能最终得到1。如果在过程中无法被3整除，则不是3的幂次方。

法 2

数学性质利用：在32位整数范围内，最大的3的幂次方是3^19=1162261467。如果n是3的幂次方，那么1162261467一定能被n整除。

条件检查：确保n是正数，并且1162261467能被n整除。同时满足这两个条件时，n就是3的幂次方。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

/*

给定一个整数，写一个函数来判断它是否是 3 的幂次方。
如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x


示例 1：
输入：n = 27
输出：true

示例 2：
输入：n = 0
输出：false


示例 3：
输入：n = 9
输出：true


示例 4：
输入：n = 45
输出：false


提示：
-2^31 <= n <= 2^31 - 1

进阶：你能不使用循环或者递归来完成本题吗？

*/

struct Solution {}

const MOD: i64 = 1_000_000_007;

impl Solution {
    pub fn is_power_of_three(n: i32) -> bool {
        if n <= 0 {
            return false;
        }

        let mut n = n;
        while n % 3 == 0 {
            n = n / 3;
        }

        n == 1
    }


    // ! 计算出i32 内，最大的 3 次幂 数
    fn main() {
        let mut x = 0;
        let mut power = 1; // 3^0 = 1
        while power <= i32::MAX / 3 {
            // 防止溢出
            power *= 3;
            x += 1;
        }
        println!("最大的 3 的幂次方是 3^{} = {}", x, power);
    }

    // O(1)
    // ! 数学性质利用：在32位整数范围内，最大的3的幂次方是3^19=1162261467。
    // ! 如果n是3的幂次方，那么1162261467一定能被n整除。
    // ! 条件检查：确保n是正数，并且1162261467能被n整除。同时满足这两个条件时，n就是3的幂次方
    pub fn is_power_of_three2(n: i32) -> bool {
        n > 0 && 1162261467 % n == 0
    }
}

总方案数 = 不选的方案数 + 选的方案数

dp[i] ==> i 的方案数

直观理解
想象你有一个背包，容量为 j，现在有一个物品 num，你可以选择：
    不选 num：方案数仍然是 dp[j]（和之前一样）。
    选 num：背包剩余容量是 j - num，方案数是 dp[j - num]。
因此，总方案数 = 不选的方案数 + 选的方案数：

dp[j] = dp[j] + dp[j - num]

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

/*
 
给你两个 正 整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。
换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。

由于答案可能非常大，请你将它对 10^9 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。


示例 1：
输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。


示例 2：
输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 4^1 = 4 。
- n = 3^1 + 1^1 = 4 。
 

提示：
1 <= n <= 300
1 <= x <= 5

*/


struct Solution { }

const MOD: i64 = 1_000_000_007;

impl Solution {
    pub fn number_of_ways(n: i32, x: i32) -> i32 {
        //! 记录可组成 n 的数
        let mut nums = Vec::new();
        let mut i: i32 = 1;


        // 存储所有可能的候选数（i^x不超过n的i的x次幂）
        loop {
            let value = i.pow(x as u32);
            if value > n {
                break;
            }

            nums.push(value);
            i = i + 1;
        }
        
        // 动态规划
        // dp 代表 i 的可以组成功的方案数
        let mut dp = vec![0; n as usize + 1];
        dp[0] = 1; // 0 -- 什么都不选 ==> 算一种方案 // 初始化：和为0的方案数为1

        // 遍历组成元素
        for &num in &nums {

            // 倒序--防止重复使用元素
            for item in (num..=n).rev() {
                // 总方案 = 不选 num 的方案 + 选 num 的方案
                dp[item as usize] = (dp[item as usize] + dp[(item - num) as usize]) % MOD;
            }
        }

        dp[n as usize] as i32
    }
}

本题学到的知识点： 1.二进制分解 (n=15, 分解后=1,2,4,8) rust while num > 0 { if num & 1 == 1 { // 二进制数 power } power <<= 1; num >>= 1; }

2.前缀和 let mut prefix = vec![1; len + 1]; prefix[i + 1] = xx * prefix[i]; // prefix[i+1] 是 i 的前缀和

3.模逆元 (除法 取模 ==> 转换成 乘法) 核心思路：在模数 10^9 + 7下，除法等价于乘以模逆元。利用费马小定理，模逆元可以通过快速幂计算。

实现方法：对于 prefix[left] 的模逆元，计算 pow_mod(prefix[left], MOD - 2)。

作用：将除法转换为乘法，避免直接除法在模运算中的问题

举例： (a * b) % MOD ==> (a * b^(MOD-2)) % MOD

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]
#![allow(unused_variables)]

/*
 
给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，
它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。
根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，
其中 queries[i] = [lefti, righti] ，
其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，
其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余 。

 

示例 1：
输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10^9 + 7 取余得到的结果都相同，所以返回 [2,4,64] 。


示例 2：
输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10^9 + 7 取余后结果相同，所以返回 [2] 。
 

提示：
1 <= n <= 10^9
1 <= queries.length <= 10^5
0 <= starti <= endi < powers.length

*/

struct Solution { }

const MOD: i64 = 1_000_000_007;

impl Solution {
    //! 题目的意思
    //! 算出一个 powers 数组，1,2,4,8 二次幂组成的，之和 == n
    //! 然后从 queries 数组中给定的 [lefti, righti] ==> 相乘 powers[lefti] 到 powers[righti] 的所有数，组成 ans 数组返回
    pub fn product_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut powers = Vec::new();
        let mut num  = n as i64;
        let mut power = 1;

        // 计算 power
        while num > 0 {
            // 分解 n 的二次幂组成的关键.. num&1 == 1 才加进去
            // 这段代码通过逐位检查 n 的二进制表示，收集所有为 1 的位对应的 2 的幂，
            // 从而将 n 分解为最少数量的 2 的幂之和，并且这些幂是按非递减顺序排列的。这是解决该问题的关键步骤之一
            if num & 1 == 1 {
                powers.push(power);
            }

            power <<= 1;
            num >>= 1; 
        }

        let len = powers.len();
        // 计算前缀和
        let mut prefix_sum = vec![1i64; len + 1];
        for i in 0..len {
            prefix_sum[i + 1] = (powers[i] * prefix_sum[i]) % MOD;
        }

        let mut ans = Vec::new();
        // 计算 queries 乘积
        for q in queries {
            let left = q[0]; 
            let right = q[1]; // index=0 ==> 1, 所以 index=right 时==> 乘积是 prefix_sum[right+1]
            
            // powers[left]....powers[right] 相乘
            // 用前缀和 ==> (prefix_sum[right] / prefix_sum[left - 1]) % MOD == 正常来讲.... 注意! left 也要加入乘积结果
            // 这里使用 模逆元--费马小定理 (a / b) % MOD ==> (a * b^(MOD - 2)) % MOD
            let value = (prefix_sum[(right+1) as usize] * Self::mod_inverse(prefix_sum[left as usize])) % MOD;
            ans.push(value as i32);
        }
    
        ans
    }


    fn mod_inverse(a: i64) -> i64 {
        Self::power_mod(a, MOD - 2)
    }


    fn power_mod(mut a: i64, mut b: i64) -> i64 {
        let mut ans = 1;
        a = a % MOD;
        
        while b > 0 {
            if b & 1 == 1 {
                ans = (ans * a) % MOD;
            }

            a = (a * a) % MOD;
            b >>= 1;
        }

        ans
    }

}

思考过程： 要计算所有子数组的范围和，即每个子数组的最大值与最小值之差的总和。 直接的方法是枚举所有可能的子数组，计算每个子数组的范围并累加。 这种方法的时间复杂度是 O(n^2)，适用于较小的输入规模。 但对于较大的输入（如 n=1000），这种方法可能不够高效。

另一种思路：可以表示为所有子数组的最大值之和减去所有子数组的最小值之和

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]

/*
给你一个整数数组 nums 。
nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。

 
示例 1：
输入：nums = [1,2,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0 
[2]，范围 = 2 - 2 = 0
[3]，范围 = 3 - 3 = 0
[1,2]，范围 = 2 - 1 = 1
[2,3]，范围 = 3 - 2 = 1
[1,2,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4


示例 2：
输入：nums = [1,3,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[3]，范围 = 3 - 3 = 0
[3]，范围 = 3 - 3 = 0
[1,3]，范围 = 3 - 1 = 2
[3,3]，范围 = 3 - 3 = 0
[1,3,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4


示例 3：
输入：nums = [4,-2,-3,4,1]
输出：59
解释：nums 中所有子数组范围的和是 59
 

提示：
1 <= nums.length <= 1000
-10^9 <= nums[i] <= 10^9
 

进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？
*/
fn main(){
    println!("hello rust.");
}

struct Solution { }

impl Solution {
    pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
        let len = nums.len();

        let mut ans = 0 as i64;
        for i in 0..len {
            let mut min_v = nums[i];
            let mut max_v = nums[i];
            for j in i+1..len {
                min_v = min_v.min(nums[j]);
                max_v = max_v.max(nums[j]);

                ans += (max_v - min_v) as i64;
            }
        }

        ans
    }
}

利用数学性质和单调栈来高效计算所有子数组的最小值和最大值贡献的总和

问题转化：子数组的范围和可以表示为所有子数组的最大值之和减去所有子数组的最小值之和。

单调栈应用：使用单调栈来高效计算每个元素作为最大值或最小值出现在多少个子数组中。

计算最大值之和：使用单调栈找出每个元素作为最大值的子数组范围。

计算最小值之和：类似地，使用单调栈找出每个元素作为最小值的子数组范围。

结果计算：最终结果为所有子数组的最大值之和减去所有子数组的最小值之和。

impl Solution {
    pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
        let len = nums.len();
        let mut sum_max = 0 as i64;
        let mut sum_min = 0 as i64;

        let mut stack = Vec::new();

        // 类 单调递减栈
        for i in 0..=len {

            // 如果当前 栈顶 < nums[i] ，出栈后加入栈顶
            while !stack.is_empty() && (i == len || nums[*stack.last().unwrap() as usize] < nums[i])  {
                // 当前以 nums[current_index] 做最大值. 有多少种 子数组
                let current_index: i64 = stack.pop().unwrap();  

                // 左边界
                let left = if stack.is_empty() { 
                    current_index - (-1) 
                } else {
                    // 当前栈顶 ==> 是左边第一个比 current_index 大的值, 因为小的都被pop了。
                    current_index - stack.last().unwrap()
                };

                // 右边界
                let right = i as i64 - current_index;

                // 组合数量
                sum_max += (nums[current_index as usize] as i64 * left * right) as i64;
            }

            stack.push(i as i64);
        }

        stack.clear();


        for i in 0..=len {
            // 类 单调递增栈
            while !stack.is_empty() && (i == len || nums[*stack.last().unwrap() as usize] > nums[i]) {
                let current_index = stack.pop().unwrap();

                let left = if stack.is_empty() {
                    current_index - (-1) 
                } else {
                    current_index - stack.last().unwrap()
                };

                let right = i as i64 - current_index;

                sum_min += (nums[current_index as usize] as i64 * left * right) as i64;
            }

            stack.push(i as i64);
        }


        sum_max - sum_min
    }
}

栈用来记录 当前嵌套层级的分数。 每遇到一个 (，就压入一个 0，表示新开一层；每遇到一个 )，就计算当前层的分数并合并到外层。

初始化栈：栈初始化为 [0]，用来存储当前层的分数。

遍历字符串：逐个字符处理字符串中的每个括号：

遇到左括号 (：
压入 0 到栈中，表示开始一个新的嵌套层。

遇到右括号 )：
弹出栈顶元素 top，这代表当前层的分数。如果 top 是 0，说明当前是一个 ()，分数为 1；
否则，当前层是 (A) 的形式，分数为 2 * top。然后将该分数加到新的栈顶元素上。

返回结果：最终栈中剩下的唯一元素即为整个字符串的分数。

AC Code

#![allow(dead_code)]
#![allow(unused_attributes)]

/*
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
 

示例 1：
输入： "()"
输出： 1

示例 2：
输入： "(())"
输出： 2

示例 3：
输入： "()()"
输出： 2

示例 4：
输入： "(()(()))"
输出： 6
 

提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
*/
fn main(){
    println!("hello rust.");
}


struct Solution { }

impl Solution {
    pub fn score_of_parentheses(s: String) -> i32 {
        // 栈
        let mut stack = vec![0];

        // 遍历
        for c in s.chars() {
            match c {
                '(' => {
                    stack.push(0);
                }, 
                ')' => {
                    // 计数
                    let new_qiantao_ceng = stack.pop().unwrap(); // 内层的分数
                    let current_qiaotao_ceng = stack.pop().unwrap();  // 外层的分数           

                    // 如果 new_num == 0 表示 是第一层（）嵌套，如果 !== 0，就是里面嵌套了（）, 根据题目意思需要 * 2
                    let num = current_qiaotao_ceng + std::cmp::max(2 * new_qiantao_ceng, 1);
                    stack.push(num);
                }, 
                _ => unreachable!(),
            }

        }

        stack.pop().unwrap()
    }
}