Linmin's Data
文章 标签 分类
Linmin's Data

Contents

ARST打卡第289周

 included in ARST
   2841 words   6 minutes 

lc825_适龄的朋友 如何瓦解价值数十亿美金的美国监狱行业？【TED演讲】 samba的配置文件/etc/samba/smb.conf CentOS 7.9 编译的程序在 RedHat 7.9 上运行失败分析

Algorithm

lc825_适龄的朋友

硬刚partition_point解题

思路:

看数据范围可以知道，这题肯定要O(nlogn)，所以可以排序后用二分查找满足数据范围的下标数。

其中需要注意不能向自己发好友请求。然后相同的年龄可以一起计算，不用反复计算。

遍历数组x, 满足这三个条件算出y的下标范围，然后计算下标得出好友邀请数。

y > 0.5x + 7, y <= x, y <= 100 || x >= 100

条件二包含了条件三，所以条件三可以省略。

感觉 cursor claude 最近变菜了…一开始 j=i+1 写成了 j=i，导致结果一直不对。 原来是升级cursor之后，默认关掉了claude-3.5-sonnet 20241022。

rust没有lower_bound和upper_bound，所以只能用partition_point来找到下标。但是不熟悉，导致有些地方有问题。导致排查了较久。

最终修改后，还是过不了用例二:

输入 ages = [16,17,18] 输出 3 预期结果 2

反思今天这个中等题做了太久的原因如下:

  1. 好久没练习，变菜了
  2. rust这个partition_point的用法不熟悉，边界问题排查了较久。
  3. 还有奇偶数处理有点麻烦的。
  4. 这个题目真不适合用rust的partition_point, 导致边界联动处理下标 -1 的部分很麻烦。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

struct Solution {

}

impl Solution {
    pub fn num_friend_requests(ages: Vec<i32>) -> i32 {
        let mut ages = ages;
        ages.sort_unstable();
        let n = ages.len();
        let mut ans = 0;

        let mut i = 0;
        while i < n {
            // 1. 注意一开始j=i+1
            let mut j = i + 1;
            while j < n && ages[j] == ages[i] {
                j += 1;
            }

            let age = ages[i];

            // 2. 判断奇偶数去处理 y > 0.5x + 7 的情况，偶数要精确大于，所以加0.1再ceil来大于等于,
            // 奇数ceil之后可以直接大于等于
            // 这里其实不需要判断奇偶数,因为题目要求是严格大于0.5x+7,所以直接ceil就可以了
            // 比如 7.5 取到 8， 然后用 partition_point 找到小于8的下标, 然后后面都是大于7.5的
            let min_age = age as f64 * 0.5 + 7.0;

            // 计算可以发送和接受好友请求的年龄范围
            // 3. 使用partition_point来找到下标
            // 这里 upper_bound 获取大于 min_age 的前一个下标值
            let lower = ages.partition_point(|&x| (x as f64) <= min_age);
            // upper_bound - 1 得到等于的最后一个下标值
            let upper = ages.partition_point(|&x| x < age + 1) - 1;

            // println!("当前年龄: {}, min_age: {}", age, min_age);
            // println!("lower: {}, upper: {}", lower, upper);
            // println!("ages[lower..upper]: {:?}", &ages[lower..upper]);

            // 上面的写法过不了rust编译器，很难受...
            // if upper + 1 > lower {
            if upper + 1 > lower {
                let count = j - i;
                let mut valid = upper - lower + 1;
                // 如果当前年龄在范围内,需要减去自己
                // 导致错误用例二: if i >= lower && i < upper {
                if age >= ages[lower] && age <= ages[upper] {
                    valid -= 1;
                }

                // println!("count: {}, valid: {}, 增加请求数: {}", count, valid, count * valid);
                ans += count * valid;
            }

            i = j;
        }

        ans as i32
    }
}

fn main() {
    let ages = vec![16, 17, 18];
    let result = Solution::num_friend_requests(ages);
    println!("\n最终结果:");
    println!("输出 {}", result);
    println!("预期结果 2");
}

花了比较久，终于用rust partition_point 写出了正确答案 AC 了题目…

partition_point 真有点反直觉，配合rust的严格编译器，真的有点麻烦，感觉cpp还是舒服的。

partition_point详细学习

让我详细讲解一下 partition_point 的实现和用法。

partition_point 的定义

partition_point 是 Rust 标准库中的一个方法，其签名如下：

1
2
3

fn partition_point<P>(&self, pred: P) -> usize 
where
    P: FnMut(&T) -> bool

它返回第一个使得谓词（predicate）返回 false 的元素的索引。要求输入数组对于谓词必须是分段的（partitioned），即所有返回 true 的元素都在返回 false 的元素之前。

实现原理

partition_point 实际上是二分查找的一种变体。下面是其基本实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize 
where
    P: FnMut(&T) -> bool
{
    let mut left = 0;
    let mut right = slice.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if pred(&slice[mid]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    left
}

使用示例

让我们通过几个例子来理解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

fn main() {
    // 示例1：找到第一个大于3的位置
    let nums = vec![1, 2, 3, 4, 5, 6];
    let pos = nums.partition_point(|&x| x <= 3);
    println!("第一个大于3的位置: {}", pos); // 输出: 3
    
    // 示例2：找到第一个大于等于3的位置
    let pos = nums.partition_point(|&x| x < 3);
    println!("第一个大于等于3的位置: {}", pos); // 输出: 2
    
    // 示例3：在你的题目中的用法
    let ages = vec![16, 17, 18];
    let min_age = 15.5;
    // 这里 upper_bound 获取大于 min_age 的前一个下标值
    let lower = ages.partition_point(|&x| (x as f64) <= min_age);
    println!("第一个大于{}的位置: {}", min_age, lower); // 输出: 0
    
    let age = 17;
    let upper = ages.partition_point(|&x| x < age + 1);
    println!("第一个大于{}的位置: {}", age, upper); // 输出: 2

    // upper_bound - 1 得到等于的最后一个下标值
    let upper = ages.partition_point(|&x| x < age + 1) - 1;
    println!("最后一个大于等于{}的位置: {}", age, upper); // 输出: 1
}
// 第一个大于3的位置: 3
// 第一个大于等于3的位置: 2
// 第一个大于15.5的位置: 0
// 第一个大于17的位置: 2
// 最后一个大于等于17的位置: 1

在题目中的应用

在你的题目中，我们用 partition_point 来找到满足年龄条件的范围：

  1. lower = ages.partition_point(|&x| x < min_age)

    • 找到第一个大于等于 min_age 的位置
    • 所有小于 min_age 的元素都在左边
    • 所有大于等于 min_age 的元素都在右边

  2. upper = ages.partition_point(|&x| x < age + 1)

    • 找到第一个大于 age 的位置
    • 所有小于等于 age 的元素都在左边
    • 所有大于 age 的元素都在右边

注意事项

  1. 输入数组必须是有序的，否则结果不可预测
  2. 谓词函数必须保证分段性质（前面全是true，后面全是false）
  3. 返回的是第一个使谓词为 false 的位置
  4. 如果所有元素都满足谓词，返回数组长度
  5. 如果没有元素满足谓词，返回0

与其他二分查找函数的对比

  • lower_bound（C++）等价于 partition_point(|&x| x < target)
  • upper_bound（C++）等价于 partition_point(|&x| x <= target)

这就是为什么在你的代码中：

1
2

let lower = ages.partition_point(|&x| x < min_age);  // 找到 >= min_age 的第一个位置
let upper = ages.partition_point(|&x| x < age + 1);  // 找到 > age 的第一个位置

这样就能得到一个左闭右开的区间 [lower, upper)，包含了所有满足条件的年龄。

题解

这里题解用的双指针，比lower和upper的partition_point更安全，而且综合来看也只有O(n)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int n = ages.size();
        sort(ages.begin(), ages.end());
        int left = 0, right = 0, ans = 0;
        for (int age: ages) {
            if (age < 15) {
                continue;
            }
            while (ages[left] <= 0.5 * age + 7) {
                ++left;
            }
            while (right + 1 < n && ages[right + 1] <= age) {
                ++right;
            }
            ans += right - left;
        }
        return ans;
    }
};

计数排序+前缀和获取区间值的思路更是直接不用排序，可以直接O(n)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> cnt(121);
        for (int age: ages) {
            ++cnt[age];
        }
        vector<int> pre(121);
        for (int i = 1; i <= 120; ++i) {
            pre[i] = pre[i - 1] + cnt[i];
        }
        int ans = 0;
        for (int i = 15; i <= 120; ++i) {
            if (cnt[i]) {
                int bound = i * 0.5 + 8;
                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return ans;
    }
};

Review

如何瓦解价值数十亿美金的美国监狱行业？【TED演讲】

恶意获取监狱行业的暴利，只会让更多的人被迫持久坐牢。

就像如果卖伞的人有了下雨的权利，那天永远不会晴。

因此投诉很多不合理的暴利，从而瓦解这种恶性循环。

Tips

samba的配置文件/etc/samba/smb.conf

Share

CentOS 7.9 编译的程序在 RedHat 7.9 上运行失败分析:

实际根本原因是 RedHat 的一些依赖动态库和 CentOS 不一样。

所以 RedHat 7.9 要运行 CentOS 7.9 相似的程序，需要在 RedHat 7.9 上重新编译一次。

Updated on 2024-11-17
Read Markdown
 ARST
Back | Home