Created Thursday 19 September 2019
近来同学在刷 Leetcode。虽然没有太多时间，不过分享到有趣的题目的时候会稍微看一下，顺便用 rust 实现一下。
121: Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
最开始仗着 rust 的快速，不管复杂度写了一遍：
1
2
3
4
5
6
7
8
9
10
11
|
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
(2..prices.len() + 1)
.map(|n|
prices.windows(n)
.map(|slice| slice[n-1] - slice[0])
.max()
.unwrap_or(0)
).max().unwrap_or(0).max(0)
}
}
|
果然不行，写了另外一个动规的版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
profit(std::i32::MAX, &prices)
}
}
pub fn profit(current: i32, prices: &[i32]) -> i32 {
match prices.len() {
0 => 0,
1 => (prices[0] - current).max(0),
_ => (prices.iter().max().unwrap() - current)
.max(profit(prices[0], &prices[1..]))
.max(0)
}
}
|
发现效率和之前一样。仔细看了看，果然应该一样啊。在找最小的时候仍然是每次都看了一遍。
然后是修正后的递归版本（只写了那个被递归的函数）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
pub fn profit(current: i32, prices: &[i32]) -> i32 {
match prices.len() {
0 => 0,
1 => prices[0] - current,
_ => {
if prices[0] < current {
profit(prices[0], &prices[0..])
} else {
profit(current, &prices[1..]).max(prices[0] - current)
}
}
}
.max(0)
}
|
终于 100% 了。
PS: 不过同样的算法在 Python 3 中不可行，将会 Memory Limit Exceeded。
136: Single Number
https://leetcode.com/problems/single-number/
这道题以前就有同学分享过，很不幸地最好的方法被剧透过了，没有亲自想出来。
不过随着后来接触到的密码攻击方法也很多了，想到这个异或的思路还是非常自然的。相信现在的我能够自己想出来。
1
2
3
4
5
|
impl Solution {
pub fn single_number(nums: Vec<i32>) -> i32 {
nums.iter().fold(0, |res, &i| res ^ i)
}
}
|
155: Min Stack
https://leetcode.com/problems/min-stack/
很简单。但是坑点比较奇特。因为只有一个 get_min() ，可以加个缓存以便在测试样例中跑得快一点。