目錄

84. 柱狀圖中最大的矩形 Largest-rectangle-in-histogram????????

85. 最大矩形 Maximal Rectangle????????

87. 擾亂字符串 Scramble String????????

?? 每日一練刷題專欄???

Rust每日一練 專欄

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

84. 柱狀圖中最大的矩形 Largest-rectangle-in-histogram

給定?n?個非負整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區(qū)域，面積為 10

示例 2：

輸入： heights = [2,4]
輸出： 4

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4?

代碼1：?暴力枚舉

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let n = heights.len();
    let mut max_area = 0;
    for i in 0..n {
        let mut left = i;
        let mut right = i;
        while left > 0 && heights[left - 1] >= heights[i] {
            left -= 1;
        }
        while right < n - 1 && heights[right + 1] >= heights[i] {
            right += 1;
        }
        let area = heights[i] * (right - left + 1) as i32;
        if area > max_area {
            max_area = area;
        }
    }
    max_area
}

fn main() {
    let heights = vec![2, 1, 5, 6, 2, 3];
    println!("{}", largest_rectangle_area(heights)); // 輸出：10

    let heights = vec![2, 4];
    println!("{}", largest_rectangle_area(heights)); // 輸出：4
}

代碼2：?單調(diào)棧

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let n = heights.len();
    let mut stack = Vec::new();
    let mut max_area = 0;
    for i in 0..=n {
        let cur_height = if i == n { 0 } else { heights[i] };
        while !stack.is_empty() && cur_height < heights[*stack.last().unwrap()] {
            let h = heights[stack.pop().unwrap()];
            let w = if stack.is_empty() { i } else { i - stack.last().unwrap() - 1 };
            let area = h * w as i32;
            if area > max_area {
                max_area = area;
            }
        }
        stack.push(i);
    }
    max_area
}

fn main() {
    let heights = vec![2, 1, 5, 6, 2, 3];
    println!("{}", largest_rectangle_area(heights)); // 輸出：10

    let heights = vec![2, 4];
    println!("{}", largest_rectangle_area(heights)); // 輸出：4
}

輸出：

10
4

85. 最大矩形 Maximal Rectangle

給定一個僅包含?0?和?1?、大小為?rows x cols?的二維二進制矩陣，找出只包含?1?的最大矩形，并返回其面積。

示例 1：

輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：6
解釋：最大矩形如上圖所示。

示例 2：

輸入：matrix = []
輸出：0

示例 3：

輸入：matrix = [["0"]]
輸出：0

示例 4：

輸入：matrix = [["1"]]
輸出：1

示例 5：

輸入：matrix = [["0","0"]]
輸出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= row, cols <= 200
• matrix[i][j]?為?'0'?或?'1'

?代碼：

fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
    let rows = matrix.len();
    if rows == 0 {
        return 0;
    }
    let cols = matrix[0].len();
    let mut heights = vec![0; cols];
    let mut max_area = 0;
    for i in 0..rows {
        for j in 0..cols {
            if matrix[i][j] == '1' {
                heights[j] += 1;
            } else {
                heights[j] = 0;
            }
        }
        let area = largest_rectangle_area(&heights);
        if area > max_area {
            max_area = area;
        }
    }
    max_area
}

fn largest_rectangle_area(heights: &Vec<i32>) -> i32 {
    let mut stack = Vec::new();
    let mut max_area = 0;
    let mut i = 0;
    while i <= heights.len() {
        let h = if i == heights.len() { 0 } else { heights[i] };
        while !stack.is_empty() && h < heights[*stack.last().unwrap()] {
            let height = heights[stack.pop().unwrap()];
            let width = if stack.is_empty() { i } else { i - stack.last().unwrap() - 1 };
            let area = height * width as i32;
            if area > max_area {
                max_area = area;
            }
        }
        stack.push(i);
        i += 1;
    }
    max_area
}

fn main() {
    let matrix = vec![
        vec!['1', '0', '1', '0', '0'],
        vec!['1', '0', '1', '1', '1'],
        vec!['1', '1', '1', '1', '1'],
        vec!['1', '0', '0', '1', '0']
    ];
    println!("{}", maximal_rectangle(matrix));
}

輸出：

6

87. 擾亂字符串 Scramble String

使用下面描述的算法可以擾亂字符串?s?得到字符串?t?：

1. 如果字符串的長度為 1 ，算法停止
2. 如果字符串的長度 > 1 ，執(zhí)行下述步驟：
   • 在一個隨機下標處將字符串分割成兩個非空的子字符串。即，如果已知字符串?s?，則可以將其分成兩個子字符串?x?和?y?，且滿足?s = x + y?。
   • 隨機?決定是要「交換兩個子字符串」還是要「保持這兩個子字符串的順序不變」。即，在執(zhí)行這一步驟之后，s?可能是?s = x + y?或者?s = y + x?。
   • 在?x?和?y?這兩個子字符串上繼續(xù)從步驟 1 開始遞歸執(zhí)行此算法。

給你兩個?長度相等?的字符串?s1?和?s2，判斷?s2?是否是?s1?的擾亂字符串。如果是，返回?true?；否則，返回?false?。

示例 1：

輸入：s1 = "great", s2 = "rgeat"
輸出：true
解釋：s1 上可能發(fā)生的一種情形是：
"great" --> "gr/eat" // 在一個隨機下標處分割得到兩個子字符串
"gr/eat" --> "gr/eat" // 隨機決定：「保持這兩個子字符串的順序不變」
"gr/eat" --> "g/r / e/at" // 在子字符串上遞歸執(zhí)行此算法。兩個子字符串分別在隨機下標處進行一輪分割
"g/r / e/at" --> "r/g / e/at" // 隨機決定：第一組「交換兩個子字符串」，第二組「保持這兩個子字符串的順序不變」
"r/g / e/at" --> "r/g / e/ a/t" // 繼續(xù)遞歸執(zhí)行此算法，將 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 隨機決定：「保持這兩個子字符串的順序不變」
算法終止，結(jié)果字符串和 s2 相同，都是 "rgeat"
這是一種能夠擾亂 s1 得到 s2 的情形，可以認為 s2 是 s1 的擾亂字符串，返回 true

示例 2：

輸入：s1 = "abcde", s2 = "caebd"
輸出：false

示例 3：

輸入：s1 = "a", s2 = "a"
輸出：true

提示：

• s1.length == s2.length
• 1 <= s1.length <= 30
• s1?和?s2?由小寫英文字母組成

代碼：

fn is_scramble(s1: String, s2: String) -> bool {
    let s1 = s1.as_bytes();
    let s2 = s2.as_bytes();
    let n = s1.len();
    if s1 == s2 {
        return true;
    }
    if n != s2.len() {
        return false;
    }
    let mut dp = vec![vec![vec![false; n + 1]; n]; n];
    for i in 0..n {
        for j in 0..n {
            dp[i][j][1] = s1[i] == s2[j];
        }
    }
    for l in 2..=n {
        for i in 0..=n-l {
            for j in 0..=n-l {
                for k in 1..l {
                    if (dp[i][j][k] && dp[i+k][j+k][l-k]) || (dp[i][j+l-k][k] && dp[i+k][j][l-k]) {
                        dp[i][j][l] = true;
                        break;
                    }
                }
            }
        }
    }
    dp[0][0][n]
}

fn main() {
    let s1 = String::from("abcde");
    let s2 = String::from("caebd");
    println!("{}", is_scramble(s1, s2));
    let s1 = String::from("a");
    let s2 = String::from("a");
    println!("{}", is_scramble(s1, s2));
}

輸出：

false
true

?? 每日一練刷題專欄???

? 持續(xù)，努力奮斗做強刷題搬運工！

?? 點贊，你的認可是我堅持的動力！?

???收藏，你的青睞是我努力的方向！?

? 評論，你的意見是我進步的財富！??

??主頁：https://hannyang.blog.csdn.net/

6.13 生日快樂文章來源地址http://www.zghlxwxcb.cn/news/detail-483321.html

到了這里，關(guān)于Rust每日一練(Leetday0029) 柱狀圖、最大矩形、擾亂字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！