目錄

70. 爬樓梯 Climbing Stairs????

71. 簡(jiǎn)化路徑 Simplify Path??????

72. 編輯距離 Edit Distance????????

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

Rust每日一練 專欄

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

70. 爬樓梯 Climbing Stairs

假設(shè)你正在爬樓梯。需要?n?階你才能到達(dá)樓頂。

每次你可以爬?1?或?2?個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

• 1 <= n <= 45

代碼： 題目本質(zhì)就是斐波那切數(shù)列

fn climb_stairs(n: i32) -> i32 {
    if n <= 1 {
        return 1;
    }
    let mut dp = vec![0; n as usize + 1];
    dp[0] = 1;
    dp[1] = 1;
    for i in 2..=n as usize {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n as usize]
}

fn main() {
    println!("{}", climb_stairs(2));
    println!("{}", climb_stairs(3));
    println!("{}", climb_stairs(5));
}

輸出：

2
3
8

71. 簡(jiǎn)化路徑 Simplify Path

給你一個(gè)字符串?path?，表示指向某一文件或目錄的?Unix 風(fēng)格?絕對(duì)路徑?（以?'/'?開(kāi)頭），請(qǐng)你將其轉(zhuǎn)化為更加簡(jiǎn)潔的規(guī)范路徑。

在 Unix 風(fēng)格的文件系統(tǒng)中，一個(gè)點(diǎn)（.）表示當(dāng)前目錄本身；此外，兩個(gè)點(diǎn) （..）?表示將目錄切換到上一級(jí)（指向父目錄）；兩者都可以是復(fù)雜相對(duì)路徑的組成部分。任意多個(gè)連續(xù)的斜杠（即，'//'）都被視為單個(gè)斜杠?'/'?。 對(duì)于此問(wèn)題，任何其他格式的點(diǎn)（例如，'...'）均被視為文件/目錄名稱。

請(qǐng)注意，返回的?規(guī)范路徑?必須遵循下述格式：

• 始終以斜杠?'/'?開(kāi)頭。
• 兩個(gè)目錄名之間必須只有一個(gè)斜杠?'/'?。
• 最后一個(gè)目錄名（如果存在）不能?以?'/'?結(jié)尾。
• 此外，路徑僅包含從根目錄到目標(biāo)文件或目錄的路徑上的目錄（即，不含?'.'?或?'..'）。

返回簡(jiǎn)化后得到的?規(guī)范路徑?。

示例 1：

輸入：path = "/home/"
輸出："/home"
解釋：注意，最后一個(gè)目錄名后面沒(méi)有斜杠。 

示例 2：

輸入：path = "/../"
輸出："/"
解釋：從根目錄向上一級(jí)是不可行的，因?yàn)楦夸浭悄憧梢缘竭_(dá)的最高級(jí)。

示例 3：

輸入：path = "/home//foo/"
輸出："/home/foo"
解釋：在規(guī)范路徑中，多個(gè)連續(xù)斜杠需要用一個(gè)斜杠替換。

示例 4：

輸入：path = "/a/./b/../../c/"
輸出："/c"

提示：

• 1 <= path.length <= 3000
• path?由英文字母，數(shù)字，'.'，'/'?或?'_'?組成。
• path?是一個(gè)有效的 Unix 風(fēng)格絕對(duì)路徑。

代碼：

fn simplify_path(path: &str) -> String {
    let dirs = path.split("/");
    let mut stack = Vec::new();
    for dir in dirs {
        match dir {
            "" | "." => continue,
            ".." => {
                if stack.len() > 0 {
                    stack.pop();
                }
            },
            _ => stack.push(dir),
        }
    }
    let mut res = String::from("/");
    res.push_str(&stack.join("/"));
    res
}

fn main() {
    println!("{}", simplify_path("/home/"));
    println!("{}", simplify_path("/../"));
    println!("{}", simplify_path("/home//foo/"));
    println!("{}", simplify_path("/a/./b/../../c/"));
}

輸出：

/home
/
/home/foo
/c

72. 編輯距離 Edit Distance

給你兩個(gè)單詞?word1?和?word2，?請(qǐng)返回將?word1?轉(zhuǎn)換成?word2?所使用的最少操作數(shù)??。

你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：

• 插入一個(gè)字符
• 刪除一個(gè)字符
• 替換一個(gè)字符

示例?1：

輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')

示例?2：

輸入：word1 = "intention", word2 = "execution"
輸出：5
解釋：
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1?和?word2?由小寫英文字母組成

代碼：

fn min_distance(word1: String, word2: String) -> i32 {
    let m = word1.len();
    let n = word2.len();
    let mut dp = vec![0; n + 1];
    let word1 = word1.as_bytes();
    let word2 = word2.as_bytes();
    // 初始化第一行
    for j in 1..=n {
        dp[j] = j as i32;
    }
    for i in 1..=m {
        let mut pre = dp[0];
        dp[0] = i as i32;
        for j in 1..=n {
            let temp = dp[j];
            if word1[i - 1] == word2[j - 1] {
                dp[j] = pre;
            } else {
                dp[j] = pre.min(dp[j - 1]).min(dp[j]) + 1;
            }
            pre = temp;
        }
    }
    dp[n]
}

fn main() {
    println!("{}", min_distance("horse".to_string(), "ros".to_string()));
    println!("{}", min_distance("intention".to_string(), "execution".to_string()));
}

輸出：

3
5

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

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

?? 點(diǎn)贊，你的認(rèn)可是我堅(jiān)持的動(dòng)力！?

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

? 評(píng)論，你的意見(jiàn)是我進(jìn)步的財(cái)富！??

??主頁(yè)：https://hannyang.blog.csdn.net/

到了這里，關(guān)于Rust每日一練(Leetday0024) 爬樓梯、簡(jiǎn)化路徑、編輯距離的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！