Rust算法刷題

劃分字符串

題干

輸入: S = "ababcbaca defegde hijhklij" 輸出: [9,7,8]

解釋: 劃分結果為 "ababcbaca", "defegde", "hijhklij"。 每個字母最多出現在一個片段中。 像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少。
注意: 1. S的長度在[1, 500]之間。 2. S只包含小寫字母'a'到'z'。

邏輯分析

這道題考查方向為對貪心算法的掌握，貪心算法的核心思想是在每一步都做出局部最優的選擇，以期望最終得到全局最優解。

這道題要求將字符串劃分成一個個段，使得每個字母最多出現在一個片段中。也就是說，每個片段的所有字符在整個字符串中只出現一次或出現在同一個片段中。我們需要找到每個字符最后出現的位置，以便確定每個片段的邊界。

故得到一個合理片段的充分必要條件，用文字表達如下：

• 每個片段中，其最后一個字母，即為在整個字符串中最后一次出現。
• 每個片段中，除最后一個字母外的其他字母，在后面的片段中也不會出現。
  ?所以可以知道，對于這么一個題目，其中字母最后出現的位置?很重要！

量化表達

為了實現成功分片的這個目標，我們可以按照以下步驟來解決問題：

1. ?記錄每個字符最后出現的位置?：首先遍歷字符串，記錄每個字符最后出現的位置。我們將這個map記為last_occurrence

2. ?確定每個片段的邊界?：再遍歷字符串時，通過比較當前字符的最后出現位置和當前片段的結束位置，來決定是否需要結束當前片段并開始一個新片段。可以知道的是，一個成功的分片的充要條件如下：
   每個片段中，其最后一個字母，即為在整個字符串中最后一次出現。
   每個片段中，除最后一個字母外的其他字母，在后面的片段中也不會出現。

   1.分片中最后一個字母的下標等于其?last_occurrence中對應的數
   2.一個片段中的字母的?last_occurrence不能大于其結尾字符的last_occurrence數值

代碼

\*\*使用命令`cargo new test_str_split`，在目錄中創建項目。之后進入項目的main.rs中，將下面的代碼復制粘貼進去后，運行`cargo run`，即運行main方法。

use std::collections::HashMap;
?
fn partition_labels(s: String) -> Vec<i32> {
    // 記錄每個字符最后出現的位置，獲得last_occurrence
    let mut last_occurrence = HashMap::new();
    for (i, c) in s.chars().enumerate() {
        last_occurrence.insert(c, i);
    }
?
    // 初始化
    let mut partitions = Vec::new();
    let (mut start, mut end) = (0, 0);
    
    // 遍歷字符串并劃分片段
    for (i, c) in s.chars().enumerate() {
        // 更新當前片段的結束位置，滿足第二個條件
        end = std::cmp::max(end, *last_occurrence.get(&c).unwrap());
        // 如果當前索引等于當前片段的結束位置，確定一個片段，滿足第一個條件
        if i == end {
            partitions.push((end - start + 1) as i32);
            start = i + 1;
        }
    }
    partitions
}
?
fn main() {
    let s = String::from("ababcbacadefegdehijhklij");
    let result = partition_labels(s);
    println!("{:?}", result);  // 輸出: [9, 7, 8]
}
?

其他

\*\*本題的實際解法為貪心算法。貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優的選擇的算法。它通常用于解決優化問題。貪心算法的核心思想是在每一步都做出局部最優的選擇，以期望最終得到全局最優解。貪心算法的解決步驟通常包括：

1. ?選擇當前最優的選擇?：每一步都選擇當前狀態下最優的操作。

2. ?確定問題的局部結構?：問題能被分解為一系列子問題，每個子問題的解是局部最優解。

3. ?判斷全局最優性?：局部最優解能夠匯總為全局最優解。

    \*\*本算法問題的過程體現了貪心算法的思想：在每一步都做出最優選擇（當前片段的結束位置），以保證最終劃分的片段數最多。