ARST打卡第283周

Linmin.Shan included in ARST

2024-10-06 1188 words 3 minutes

Contents

lc134_加油站假如医疗费用变得透明化会如何？【TED演讲】推荐书籍《宝贵的人生建议》凯文凯利 4年理财思考分享

Algorithm

lc134_加油站

思路:

暴力做法就是直接 O(n^2) 遍历所有加油站作为起点，然后每次都加满油，看看能不能回到原点。

但是显然数据范围不支持暴力做法。

所以先贪心把所有加油站的油量减去到下一个加油站的距离，如果小于0，说明无法到达下一个加油站。

然后开始双指针滑动，让区间始终大于等于0，这样当右指针能到达左指针的时候，就说明找到了一个解。

从而把时间复杂度降到 O(n)。

 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


struct Solution {}

impl Solution {
    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
        let mut remGas = vec![0; gas.len()];
        let mut total_gas = 0;
        let mut total_cost = 0;

        for i in 0..gas.len() {
            remGas[i] = gas[i] - cost[i];
            total_gas += gas[i];
            total_cost += cost[i];
        }

        if total_gas < total_cost {
            return -1;
        }

        let mut l = 0;
        let mut r = 0;
        let mut current_gas = 0;
        while r < l + gas.len() {
            current_gas += remGas[r % gas.len()];
            // println!("r: {}, current_gas: {}", r, current_gas);
            // while current_gas < 0 && l < r && l < gas.len() {
            // 此处必须让 l <= r 否则就会导致起始值为负数无法排除掉..即main中用例无法通过
            while current_gas < 0 && l <= r && l < gas.len() {
                current_gas -= remGas[l % gas.len()];
                l += 1;
                // println!("  l: {}, current_gas: {}", l, current_gas);
            }
            r += 1;
        }
        if current_gas >= 0 {
            return l as i32;
        }

        -1
    }
}

fn main() {
    let gas = vec![1,2,3,4,5,5,70];
    let cost = vec![2,3,4,3,9,6,2];
    let result = Solution::can_complete_circuit(gas, cost);
    println!("Result: {}", result);
}

结果题解更简洁，直接利用以下总结跳过中间量。

如果x到达不了y+1，那么x-y之间的点也不可能到达y+1，因为中间任何一点的油都是拥有前面的余量的，所以下次遍历直接从y+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


impl Solution {
    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
        let n = gas.len();
        let mut i = 0;
        while i < n {
            let mut sum_of_gas = 0;
            let mut sum_of_cost = 0;
            let mut cnt = 0;
            while cnt < n {
                let j = (i + cnt) % n;
                sum_of_gas += gas[j];
                sum_of_cost += cost[j];
                if sum_of_cost > sum_of_gas {
                    break;
                }
                cnt += 1;
            }
            if cnt == n {
                return i as i32;
            } else {
                i = i + cnt + 1;
            }
        }
        -1
    }
}

Review

假如医疗费用变得透明化会如何？【TED演讲】

在美国，同样的血检在一个诊所可能只要19美元，但在几个街区外的诊所却要收522美元——而且只有在几周后收到账单时，人们才知道其中的差别。

记者珍妮·平得说道，事情并不一定要这样。她建立了一个平台，通过大众的力量让医疗的真实成本和数据公开化，揭示了医疗保健定价的秘密。

提前知道医疗成本如何能让我们更健康，如何帮我们省下更多的钱——以及如何来修复一个崩溃的系统。

一开始找了一个讲经济财富的TED，语速太快加生词太多，不适合听力练习，就换成这个了

Tips

推荐书籍《宝贵的人生建议》凯文凯利

智者吸收他人经验，强者利用他人经验，愚者重复他人经验。

4年理财思考分享

最近因为A股政策调整，美股做多中概赚了1w，当年失去的年终回来一点。

这次虽然回血一点。但学到了如下教训:

选择优秀市场: 4年定投spy早就40%多收益而不是A股/中概还在等回本(A股不算稳定市场，美股算)
趁早交易,但优先做多工资: 股票在年轻无资产时杠杆效应比较小，应该花大量时间先做多自己的工资
主动尝试,独立思考: 遇到大政策要思考分析尝试，敢活u重仓，听取多方意见，但不要被部分kol迷惑

Contents

ARST打卡第283周

Algorithm

Review

Tips

Share