Rust算法刷题
划分字符串
题干
输入: S = "ababcbaca defegde hijhklij" 输出: [9,7,8]
解释: 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
注意: 1. S的长度在[1, 500]之间。 2. S只包含小写字母'a'到'z'。
逻辑分析
这道题考查方向为对贪心算法的掌握，贪心算法的核心思想是在每一步都做出局部最优的选择，以期望最终得到全局最优解。
这道题要求将字符串划分成一个个段，使得每个字母最多出现在一个片段中。也就是说，每个片段的所有字符在整个字符串中只出现一次或出现在同一个片段中。我们需要找到每个字符最后出现的位置，以便确定每个片段的边界。
故得到一个合理片段的充分必要条件，用文字表达如下：
- 每个片段中，其最后一个字母，即为在整个字符串中最后一次出现。
- 每个片段中，除最后一个字母外的其他字母，在后面的片段中也不会出现。
所以可以知道，对于这么一个题目，其中字母最后出现的位置很重要！
量化表达
为了实现成功分片的这个目标，我们可以按照以下步骤来解决问题：
-
记录每个字符最后出现的位置：首先遍历字符串，记录每个字符最后出现的位置。我们将这个map记为last_occurrence
-
确定每个片段的边界：再遍历字符串时，通过比较当前字符的最后出现位置和当前片段的结束位置，来决定是否需要结束当前片段并开始一个新片段。可以知道的是，一个成功的分片的充要条件如下：
每个片段中，其最后一个字母，即为在整个字符串中最后一次出现。
每个片段中，除最后一个字母外的其他字母，在后面的片段中也不会出现。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]
}
其他
\*\*本题的实际解法为贪心算法。贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择的算法。它通常用于解决优化问题。贪心算法的核心思想是在每一步都做出局部最优的选择，以期望最终得到全局最优解。贪心算法的解决步骤通常包括：
-
选择当前最优的选择：每一步都选择当前状态下最优的操作。
-
确定问题的局部结构：问题能被分解为一系列子问题，每个子问题的解是局部最优解。
-
判断全局最优性：局部最优解能够汇总为全局最优解。
\*\*本算法问题的过程体现了贪心算法的思想：在每一步都做出最优选择（当前片段的结束位置），以保证最终划分的片段数最多。
