Car Fleet

关于 853 题 Car Fleet 的 Rust 的代码实现。

Description

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] Output: 3 Explanation: The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The car starting at 0 does not catch up to any other car, so it is a fleet by itself. The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target. Note that no other cars meet these fleets before the destination, so the answer is 3.

Example 2:

Input: target = 10, position = [3], speed = [3] Output: 1 Explanation: There is only one car, hence there is only one fleet.

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1] Output: 1 Explanation: The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2. Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Solutions

rust
1pub fn car_fleet(target: i32, position: Vec<i32>, speed: Vec<i32>) -> i32 {
2    let mut cars: Vec<(i32, f64)> = position
3        .into_iter()
4        .zip(speed.into_iter())
5        .map(|(p, s)| (p, (target - p) as f64 / s as f64))
6        .collect();
7    cars.sort_by(|a, b| b.0.cmp(&a.0));
8    let mut ans = 0;
9    let mut cur = 0.0;
10    for (_, time) in cars {
11        if time > cur {
12            ans += 1;
13            cur = time;
14        }
15    }
16    ans
17}

zip 函数

zip 是 Rust 中的一个函数,它的功能是将两个迭代器(Iterator)的元素配对在一起,返回一个新的迭代器。

当你有两个列表(或者其他可以迭代的容器,例如向量、切片等),并且你想把它们的元素一一对应起来,就可以使用 zip 函数。

假设你有两个向量,一个是 [1, 2, 3],另一个是 ['a', 'b', 'c'],如果你调用 zip 函数,就会得到一个包含元组的新迭代器,每个元组都包含一个来自每个列表的元素,如下所示:[(1, 'a'), (2, 'b'), (3, 'c')]

在你给出的代码中,zip 函数接收两个迭代器 position.into_iter()speed.into_iter(),然后返回一个新的迭代器,这个迭代器的每个元素都是一个元组,元组的第一个元素来自 position 向量,第二个元素来自 speed 向量。

这是一个例子:

rust
1let position = vec![1, 2, 3];
2let speed = vec![4, 5, 6];
3let zipped: Vec<(i32, i32)> = position.into_iter().zip(speed.into_iter()).collect();
4println!("{:?}", zipped);

这段代码的输出会是 [(1, 4), (2, 5), (3, 6)]

RxJS 中的 zip

RxJS(Reactive Extensions for JavaScript)也有类似的操作符,叫做 zipzip 在 RxJS 中被用来组合多个 Observables。当每个输入 Observable 都发出一个新的值,zip 就会发出一个包含所有最新值的数组。

这里有一个简单的例子来演示如何使用 zip

javascript
1const { of, zip } = require('rxjs');
2
3const observable1 = of(1, 2, 3);
4const observable2 = of('a', 'b', 'c');
5
6const zipped = zip(observable1, observable2);
7
8zipped.subscribe(val => console.log(val));

这段代码会输出:

javascript
1[ 1, 'a' ]
2[ 2, 'b' ]
3[ 3, 'c' ]

在这个例子中,我们创建了两个 Observables,一个发出数字,一个发出字符。然后我们使用 zip 将它们组合在一起,创建了一个新的 Observable。当我们订阅这个新的 Observable 时,它会发出包含数字和字符的数组。每个数组都包含从每个输入 Observable 中获得的最新值。

请注意,zip 的行为依赖于输入 Observable。如果输入 Observable 的发出值的频率不一样,zip 会等待每个输入 Observable 都发出新的值再发出数组。如果其中一个 Observable 先完成,zip 就不会再发出新的值。

sort_by 和 sort_unstable_by 区别

Rust 中的 sort_bysort_unstable_by 方法都用于对向量进行排序,不同的是它们在排序过程中的稳定性。

sort_by 方法提供稳定排序。稳定排序保证了相等的元素在排序后保持它们原始的顺序。也就是说,如果有两个元素等价(即,比较函数返回它们相等),它们在排序后的顺序和排序前一样。

sort_unstable_by 方法提供不稳定排序。在不稳定排序中,相等的元素在排序后可能会改变它们的原始顺序。换句话说,如果有两个元素等价(即,比较函数返回它们相等),它们在排序后的顺序可能与排序前不一样。

选择使用哪个函数,取决于你是否需要稳定排序。如果你需要保证相等元素的原始顺序,你应该使用 sort_by。如果你不需要保证顺序,你可以使用 sort_unstable_by,因为它在某些情况下可能会更快。

在你的代码中,sort_unstable_by(|a, b| b.0.cmp(&a.0)) 使用的是不稳定排序。它按照元组的第一个元素(即,车的位置)进行排序,从大到小。如果有两个位置相同的车,它们的顺序在排序后可能会发生变化。