LC377. Combination Sum IV Med
类似于一个完全背包方案数吧。DP
给定一系列数字a[i]，求用它们组合为 target 的方案数，a[i]可以重复使用
状态：dp[i]表示目前已经加和到 i 的方案数
转移: dp[i] = sum(dp[i-a[j]])
边界条件：dp[0] = 1, ans = dp[target]
impl Solution {
pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
let mut dp = vec![0; target as usize + 1];
dp[0] = 1;
for i in 0..target {
for j in &nums {
if i+j > target {
continue;
}
dp[(i+j)as usize] += dp[i as usize];
}
}
dp[target as usize]
}
}LC621. Task Scheduler Med
题目一眼贪心，目的转化为使等待时间最少，考虑一种策略： 把任务 A-Z 按出现的次数排序，并从最多的任务（假设为 M，出现 m 次）开始排列
排列必为 M...M...M...M 这类的情况，其中.的数量为 n
只要在空缺中插入其他任务，且保证每个空缺不会出现两个相同任务，可知这类的排列必是满足题意的。
考虑有任务 X、Y、Z 在这种插入后分别剩 x、y、z 次（显然，任务 X、Y、Z 的总数量都要小于 m）
只需要扩充 每两个 M 之间的间隔，直到能插下即可，也必然符合题意，且不会使得等待时间更多。
因此问题转化为 (m-1)n > len(tasks)-m ? (m-1)(n+1) : len(tasks)
但是这个式子少考虑了如果有任务 K, k = m的情况，只要计数，并在最后累加一下即可（假设有 cnt 个任务都达到了最大值，我们先假设其中 cnt-1 个都只有最大值-1，然后按刚刚的逻辑贪心，最后补 cnt-1 即可）
所以我们要做的就是统计每个字母出现的数量并进行排序。我们同过 Rust 的 HashMap 实现该能力。
use std::collections::HashMap;
impl Solution {
pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
let mut char_count = HashMap::new();
let mut maxn = 0;
let mut maxn_cnt = 0;
for c in &tasks {
let cnt = char_count.entry(*c).or_insert(0);
*cnt += 1;
maxn = std::cmp::max(*cnt, maxn)
}
for (_, &v) in &char_count {
if v == maxn {
maxn_cnt += 1;
}
}
let lhs = (maxn-1) * n;
let rhs = tasks.len() as i32 - maxn - maxn_cnt + 1;
println!(" {} {} ", maxn, maxn_cnt);
if lhs > rhs {
return (maxn-1) * (n+1) + maxn_cnt;
} else {
return tasks.len() as i32;
}
}
}LC442. Find All Duplicates in an Array Med
裸的解法：直接扔进桶里，那就开个 Hashmap
use std::collections::HashMap;
impl Solution {
pub fn find_duplicates(nums: Vec<i32>) -> Vec<i32> {
let mut num_count = HashMap::new();
let mut res = Vec::new();
for num in nums {
let cnt = num_count.entry(num).or_insert(0);
*cnt += 1;
if *cnt == 2 {
res.push(num);
}
}
res
}
}但是显然这也太没意思了，就算是面试也不会考你 Map 的使用。其实给了数据范围，开个普通的桶就行，不知道这题为啥也能算中等。。
LC1696. Jump Game VI Med
一眼 DP，先考虑最朴素的， 状态：f[i]表示已经跳到 i 的最大价值， 转移：f[i]从f[[i-k, i-1]]里更新即可，f[i] = max{f[max(i-k, 0)....i-1]} + nums[i]
边界条件：f[0] = nums[0]，ans = f[nums.len()-1]
但是这东西是O(nk)的，肯定超时，考虑优化。
分析不下去了，这显然是维护前 k 个里最大的，维护一个单调线性结构即可。此结构中的f 的值需要单调减（每次用最左侧的最大值，如果右侧有一个更大的，左侧的值一定没用）。左边出右边进，单调队列即可。
use std::collections::VecDeque;
struct Node {
cur: i32,
val: i32,
}
impl Solution {
pub fn max_result(nums: Vec<i32>, k: i32) -> i32 {
let mut f = vec![0; nums.len()];
let mut q = VecDeque::new();
q.push_back(Node { cur: 0, val: nums[0] });
f[0] = nums[0];
for i in 1..nums.len() {
while !q.is_empty() && q.front().unwrap().cur < i as i32 - k {
q.pop_front();
}
f[i] = nums[i] + q.front().unwrap().val;
while !q.is_empty() && q.back().unwrap().val < f[i] {
q.pop_back();
}
q.push_back(Node { cur: i as i32, val: f[i] })
}
f[nums.len()-1]
}
}学语法中这块有个小点，就是 q.back() 这类的方法，返回的应该是个Option，我们直接 unwrap() 把 OK 中的值拿回来，如果拿不回来就直接 panic。
Option类型是Rust的一个枚举类型，它有两个值：Some(T)和None。Option类型常常用于表示可能存在也可能不存在的值。
q.back()和q.front()的返回值类型都是Option<&T>，其中T是队列中元素的类型。这是因为当队列为空时，back()和front()方法没有元素可以返回，所以它们返回的是None。当队列不为空时，back()和front()方法可以返回队列的尾部和头部元素，所以它们返回的是Some(&T)。
在处理Option类型时，除了模式匹配和unwrap()方法，还有很多其他的方法，比如unwrap_or()、unwrap_or_else()、map()、and_then()等等。
LC387 First Unique Character in a String Ez
impl Solution {
pub fn first_uniq_char(s: String) -> i32 {
let mut v = vec![0; 26];
let s_chars: Vec<char> = s.chars().collect();
for &ch in s_chars.iter() {
v[(ch as i32 - 'a' as i32)as usize] += 1;
}
for (i, &ch) in s_chars.iter().enumerate() {
if v[(ch as u32 - 'a' as u32) as usize] == 1 {
return i as i32;
}
}
-1
}
}
评论 (0)