光阴冢

We make choices and life has a way of making us pay for them.

Leetcode

Jul 30, 2020  

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() ,可以加个缓存以便在测试样例中跑得快一点。