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

Contents

ARST打卡第241周

 included in ARST
   2461 words   5 minutes 

Algorithm

lc746_使用最小花费爬楼梯

思路: 这是很常规的爬楼梯题目, 先暴力递归测试数据集大小。

果然 TLE 了: 259 / 283 个通过的测试用例

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

class Solution {
public:
    int sol(const vector<int>& cost, int n) {
        // 递归终止条件
        if (n < 2) {
            return cost[n];
        }
        return cost[n] + min(sol(cost, n - 1), sol(cost, n - 2));
    }
    int minCostClimbingStairs(vector<int>& cost) {
        // 其实就是简单爬楼的dp or 递归
        int n = cost.size();
        int ret = min(sol(cost, n - 1), sol(cost, n - 2));
        return ret;
    }
};

然后通过记忆递归来剪枝可以 AC:

 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 sol(const vector<int>& cost, vector<int>& view, int n) {
        // 递归终止条件
        if (n < 2) {
            return cost[n];
        }
        if (view[n] != -1) {
            return view[n];
        }
        view[n] = cost[n] + min(sol(cost, view, n - 1), sol(cost, view, n - 2));
        return view[n];
    }
    int minCostClimbingStairs(vector<int>& cost) {
        // 其实就是简单爬楼的dp or 递归
        int n = cost.size();
        vector<int> view(n + 1, -1);
        int ret = min(sol(cost, view, n - 1), sol(cost, view, n - 2));
        return ret;
    }
};

最终再优化成 dp 版本的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 其实就是简单爬楼的dp or 递归
        int n = cost.size();
        vector<int> dp(n + 1, 0);
        dp[0] = cost[0]; 
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + min(dp[i-1], dp[i-2]);
        }
        return min(dp[n-1], dp[n-2]);
    }
};

题解则是写到了第n级，更加统一一些，挺好，学习之

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};
// 链接：https://leetcode.cn/problems/min-cost-climbing-stairs/

而且题解还用了滚动变化进一步节省空间:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
};

Review

【TED演讲】如何更快乐

true fun : the playful connected flow.

fake fun : junk food, junk video in your leisure time.

fake fun leaves us feeling disgusting about ourselves.

In fact, fake fun is actually enjoyable. Go for it.

But put the true fun on the top of your priority list.

SPARK method is good to make true fun.

R rebel is really fun. Break the rule in little things.

控制什么能够进入你的大脑打扰你，什么不能进入你的大脑打扰你，以便更好进入心流，获取更多快乐。

不要做一个扫兴的人，选择有趣的人一起玩。

Tips

find *_test -exec ./{} ; 如何剔除一个脚本不运行

如果你想在使用 find 命令时排除某个特定的脚本不运行，可以使用 ! -name 选项排除文件名匹配的文件。以下是一个示例：

1

find *_test ! -name "script_to_exclude.sh" -exec ./{} \;

在这个例子中，! -name "script_to_exclude.sh" 表示排除文件名为 “script_to_exclude.sh” 的文件。你可以根据实际情况替换为你要排除的脚本的文件名。

如果你要排除多个脚本，可以使用 -o 表示逻辑 OR。例如：

1

find *_test ! -name "script_to_exclude1.sh" -o ! -name "script_to_exclude2.sh" -exec ./{} \;

这将排除两个脚本，你可以根据需要添加更多的条件。

make -j 如何控制 Makefile 的依赖顺序

在Makefile中，make -j用于并行构建目标，其中-j选项后面可以指定并行构建的任务数量。然而，并行构建可能会导致一些问题，尤其是在存在复杂的依赖关系时。

如果你想要控制Makefile中目标的依赖顺序，可以使用依赖关系和规则。下面是一些建议：

  1. 上策: 明确定义依赖关系： 确保在Makefile中明确定义了正确的依赖关系。这样，无论是否使用并行构建，Make都会按照正确的顺序构建目标。

    1
2

    target: dependency1 dependency2
    command

  2. 可能情况: 使用.PHONY目标： 如果你的Makefile包含一些伪目标（例如clean），你可以使用.PHONY目标来确保它们不会干扰并行构建的依赖关系。

    1
2
3
4

    .PHONY: clean

clean:
    rm -rf obj/

  3. 下策: 使用串行构建： 如果你发现并行构建导致问题，可以考虑使用串行构建，即不使用-j选项。这样可以确保每个目标都按照定义的依赖关系顺序构建。

    1

    make

  4. 下下策: 调整任务数量： 如果你仍然想使用并行构建，但发现问题，可以尝试减少并行构建的任务数量，以减少并行导致的问题。

    1

    make -j2  # 仅使用两个并行任务

请注意，上述建议是基于Makefile的一般约定。具体的解决方案可能取决于你的具体项目和Makefile结构。

Share-为什么条件变量一定要配合while使用理解

GPT帮忙说明背景

pthread_cond_wait 是 POSIX 线程库中用于等待条件变量的函数。为了理解为什么在使用条件变量时通常要结合 while 而不是 if，我们需要理解条件变量的基本工作原理。

首先，让我们回顾一下条件变量的基本用途和结构。条件变量用于在多线程环境中实现线程之间的协调和同步。它通常与互斥锁一起使用，以确保线程在满足某个条件之前等待，而在条件满足时被唤醒。

pthread_cond_wait 的基本用法如下：

1
2
3
4
5
6

pthread_mutex_lock(&mutex);  // 先获取互斥锁
while (!condition) {
    pthread_cond_wait(&cond, &mutex);  // 等待条件变量，并释放互斥锁
}
// 在条件满足后执行相应操作
pthread_mutex_unlock(&mutex);  // 操作完成后释放互斥锁

现在让我们来看看 pthread_cond_wait 的实现原理，以便理解为什么要使用 while。

  1. 释放互斥锁： pthread_cond_wait 在等待条件时会释放关联的互斥锁。这是为了让其他线程有机会在条件满足时修改共享数据。当线程调用 pthread_cond_wait 时，它会释放互斥锁，并将线程置于阻塞状态等待条件变量的信号。

  2. 竞争条件： 当一个线程被唤醒并重新获得互斥锁时，它需要重新检查等待的条件，因为在等待的过程中，其他线程可能已经修改了共享数据。这是为了防止竞争条件，即在释放互斥锁和等待条件变量信号之间，其他线程可能已经修改了条件的情况。

因此，使用 while 而不是 if 是为了防止虚假唤醒（spurious wakeups）和确保在条件变量被满足之前继续等待。如果使用 if，在唤醒时线程可能会错误地假设条件已满足，而实际上其他线程可能已经修改了共享数据。

使用 while 语句，线程会在被唤醒后重新检查条件，如果条件仍然不满足，线程将继续等待。这样可以避免虚假唤醒，提高程序的正确性和健壮性。

个人重点总结

if是只判断一次！！！只要被唤醒，就不会再判断，所以虚假唤醒就完蛋了。而且真实唤醒被抢断也完蛋。

假唤醒产生的可能情况

  1. 暴力实现: 直接用的广播唤醒多个线程，会有很多假唤醒。
  2. 实现细节问题，一个信号唤醒了2个线程–唤醒竞态，导致了假唤醒。–详细见《操作系统导论》书中第30章的L11引用文章。

别的线程抢占

假设没有假唤醒，但是在多线程环境下，可能if去唤醒了某个线程a，但是这个线程还在就绪，

被其他线程b抢先if判断通过了(while判断别人也是抢先执行。NOTICE:判断通过了就不用等待了),

然后线程b就执行了，然后本身的线程a开始执行是就没有while的double-check (按理来说应该double-check去校验，这样就发现别人先执行过了),

就导致二次访问临界区(critical area)然后可能导致数据错误或者coredump.

Updated on 2023-12-17
Read Markdown
 ARST
Back | Home