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

Contents

ARST打卡第242周

 included in ARST
   1913 words   4 minutes 

Algorithm

lc1962_移除石子使总数最小

思路: 先暴力算法就是排序之后，进行k次最大值移除石子操作(奇数的话要加1再除以2)。 这里复杂度就是:

  1. 一开始插入堆中就是 O(nlogn)
  2. 然后后面k次移除再插入O(klog(n))

综合来看也就是 O(nlogn).

这里还是考虑了用堆来维护最大值的移除和剩余石子移除的，但是时间复杂度还是太高。

 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

// #include <concepts>
// #include <functional>
// #include <iostream>
// #include <queue>
// #include <ranges>
// #include <string_view>
// #include <vector>
 
template<typename T>
void print(std::string_view name, T const& q, int& sum)
{
    // std::cout << name << ": \t";
    for (auto const& n : q)
        sum += n;
        // std::cout << n << ' ';
    // std::cout << '\n';
}
 
template<typename Adaptor>
requires (std::ranges::input_range<typename Adaptor::container_type>)
void print(std::string_view name, const Adaptor& adaptor, int& sum)
{
    struct Printer : Adaptor // 用于访问受保护的 Adaptor::Container c;
    {
        void print(std::string_view name, int& sum) const { ::print(name, this->c, sum); }
    };
 
    static_cast<Printer const&>(adaptor).print(name, sum);
}

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        // 最大优先队列
        std::priority_queue<int> q1(piles.begin(), piles.end()); 
        
        for (int i = 1; i <= k; i++) {
            int nxt = q1.top() & 1 ? (q1.top() + 1) >> 1 : q1.top() >> 1;
            q1.pop();
            q1.push(nxt);
        }

        int ans = 0;
        print("sum", q1, ans);
        return ans;
    }
};

一次性AC了，和题解的思路一毛一样。但是对于其中 priority_queue 的遍历却有些波折。

学习了一下 priority_queue.

发现其中的示例可以通过变化使用 for 遍历，然后发现 priority_queue 本身无法直接 for 遍历。

于是研究了一下，正常 priority_queue 遍历是这样的:

正常的遍历

在 C++ 中，priority_queue 是一个适配器，它基于底层容器（默认是 std::vector）来实现优先队列。但是，priority_queue 并没有提供直接支持范围循环（range-based loop）的功能。

范围循环通常要求被遍历的对象支持 begin() 和 end() 成员函数，而 priority_queue 并没有这些成员函数。因此，你不能像 for(auto x : q) 这样直接使用范围循环来遍历 priority_queue。

不过，你仍然可以通过其他方式来遍历 priority_queue，比如使用 while 循环和 top()、pop() 成员函数，或者将 priority_queue 的底层容器拷贝到一个标准容器（如 std::vector）中，然后使用范围循环遍历该容器。以下是使用拷贝的方式：

 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

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);
    pq.push(15);

    // 将 priority_queue 的元素拷贝到 vector 中
    std::vector<int> vec;
    while (!pq.empty()) {
        vec.push_back(pq.top());
        pq.pop();
    }

    // 使用范围循环遍历 vector
    for (auto x : vec) {
        std::cout << x << " ";
    }

    std::cout << std::endl;

    return 0;
}

在这个例子中，首先将 priority_queue 的元素逐个弹出并拷贝到 std::vector 中，然后通过范围循环遍历该 std::vector。这样就能实现类似范围循环的效果。

理解官方的for遍历

官网示例之所以可以使用范围循环 for (auto const& n : q) 遍历， 是因为它定义了一个用于适配 priority_queue 的自定义适配器（Adaptor）， 并在适配器中实现了 input_range 的要求，从而使得范围循环成为可能。

让我们来仔细分析一下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

template<typename Adaptor>
requires (std::ranges::input_range<typename Adaptor::container_type>)
void print(std::string_view name, const Adaptor& adaptor)
{
    struct Printer : Adaptor // 用于访问受保护的 Adaptor::Container c;
    {
        void print(std::string_view name) const { ::print(name, this->c); }
    };

    static_cast<Printer const&>(adaptor).print(name);
}

这是一个模板函数 print，它接受一个模板参数 Adaptor， 该参数必须满足 input_range 的要求（即，具有 begin 和 end 成员函数）。

在函数体内，定义了一个内部结构体 Printer，该结构体继承自 Adaptor， 并通过 static_cast 将传递进来的 Adaptor 强制转换为 Printer。 这样，就可以访问 Adaptor 中的受保护成员 Container c。

接下来，Printer 结构体中定义了一个成员函数 print， 该函数调用了 ::print 函数，将 Adaptor 中的容器 this->c 传递给 ::print 函数。 这个函数就是负责遍历打印容器元素的函数。

在 main 函数中，创建了不同类型的 priority_queue 对象， 然后通过调用 print 函数来打印它们的元素。 由于这些 priority_queue 对象都符合 input_range 的要求，所以可以使用范围循环进行遍历。

这个过程通过定义适配器 Adaptor 实现，使得打印的统一接口对于不同类型的容器都适用。

Review

【TED演讲】如何平息焦虑

有4个方法:

  • 深呼吸: 吸气4个数，屏息4个数，呼气4个数，屏息4个数…
  • Move: 任何身体运动，散步10分钟也是好的.
  • 识别: 识别分析自己的焦虑到底是什么，从而找出应对接纳化解的方法.
  • 帮助焦虑的他人: 识别身边人的焦虑，帮助他人，自己也能获得平静。

Tips

How do I specify a Range including everything in a RocksDB column?

Share_core不出来就打印堆栈到日志

有时候程序可能触发了 abort，但是因为某些原因(信号捕获，或者其他依赖关系)没有 coredump，导致无法知道堆栈信息。

可以通过在代码中把堆栈捕获打印到日志里，从而加速开发问题的排查速度。

 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

--- a/libs/x/xx.cc
+++ b/libs/x/xx.cc
+#include <execinfo.h>
 
+void printSourceInfo(const char* executablePath, const char* address) {
+    char command[256];
+    snprintf(command, sizeof(command), "addr2line -e %s %s", executablePath, address);
+
+    FILE* pipe = popen(command, "r");
+    if (!pipe) {
+        perror("popen");
+        return;
+    }
+
+    char buffer[256];
+    while (fgets(buffer, sizeof(buffer), pipe) != nullptr) {
+        LOGV(LL_FATAL, "lm_debug: TRACE: %s", buffer);
+    }
+
+    pclose(pipe);
+}
+
+void printStackTrace() {
+    const int maxStackTraceSize = 64;
+    void* stackTrace[maxStackTraceSize];
+
+    // Capture the current stack trace
+    int frames = backtrace(stackTrace, maxStackTraceSize);
+
+    // Get symbols
+    char** symbols = backtrace_symbols(stackTrace, frames);
+
+    // Print stack trace
+    for (int i = 0; i < frames; ++i) {
+        // LOGV(LL_FATAL, "# %d %s", i, symbols[i]);
+        // Extract executable path and address
+        char* start = strchr(symbols[i], '[');
+        char* end = strchr(symbols[i], ']');
+        if (start && end) {
+            *end = '\0';  // Terminate the string at ']'
+            char* address = start + 1;
+
+            // Print the addr2line command
+            // std::cout << "addr2line -e your_program " << address << std::endl;
+
+            // Call the function to print source information
+            printSourceInfo("/path/to/your_program", address);
+        }
+
+    }
+
+    // Clean up
+    free(symbols);
+}
Updated on 2023-12-23
Read Markdown
 ARST
Back | Home