Maxw的小站

Maxw学习记录

发表于 分类于

739. 每日温度

维护一个栈来记录未更新的数组值 using xx = xxxx仅可用于为现有变量创建别名，如果数组变量名太长请创建引用 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> out_v(temperatures.size(), 0);
        st.push(0);
        for(int i = 1; i < temperatures.size(); i++){
            if(temperatures[i] <= temperatures[st.top()]){
                st.push(i);
            }else{
                while(!st.empty() && temperatures[i] > temperatures[st.top()]){
                    out_v[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return out_v;
    }
};

496.下一个更大元素 I

和上一题很像的思路，但是需要借助两个数组都没有重复数字的假设构造map，使答案不超时 

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
#include<unordered_map>
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int>mp;
        for(int i = 0; i < nums1.size(); i++){
            mp[nums1[i]] = i;
        }
        vector<int> ng(nums1.size(), -1);
        stack<int> st;
        st.push(0);
        for(int i = 1; i < nums2.size(); i++){
            while(!st.empty() && nums2[i] > nums2[st.top()]){
                int ntop = nums2[st.top()];
                if(mp.find(ntop) != mp.end()){
                    ng[mp[ntop]] = nums2[i];
                }
                // cout<<endl;
                st.pop();
            }
            st.push(i);
        }
        return ng;
    }
};

503.下一个更大元素II

我想的是找到最大的元素，从下一个数开始遍历一遍，不过看题解直接遍历两遍数组即可 

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
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        // int max_n = nums[0];
        // int max_i = 0;
        // for(int i = 0; i < nums.size(); i++){
        //     if(nums[i] > max_n){
        //         max_n = nums[i];
        //         max_i = i;
        //     }
        // }
        stack<int> st;
        st.push(0);
        for(int j = 1; j < nums.size()*2; j++){
            int n_i = j % nums.size();
            while(!st.empty() && nums[n_i] > nums[st.top()]){
                res[st.top()] = nums[n_i];
                st.pop();
            }
            st.push(n_i);
        }
        return res;
    }
};

发表于 分类于

647. 回文子串

首先是找到递推关系，对于字符串中下标i-j的字串，如果s[i] == s[j]则可以由dp[i+1][j-1]推出dp[i][j] 然后是遍历顺序，因为要先知道dp[i+1][j-1]，所以要从下往上，从左至右遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));
        int cnt = 0;
        for(int i = s.size()-1; i >= 0; i--){
            for(int j = i; j < s.size(); j++){
                if(s[i] != s[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i <= 1){
                        dp[i][j] = true;
                        cnt++;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                        if(dp[i][j] == true)cnt++;
                    }
                }
            }
        }
        return cnt;
    }
};

516.最长回文子序列

和上一题思路类似 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>>dp(s.size(), vector<int>(s.size(),0));
        for(int i = s.size()-1; i >= 0; i--){
            for(int j = i; j < s.size(); j++){
                if(s[i] != s[j]){
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }else{
                    if(i == j){
                        dp[i][j] = 1;
                    }else if(i - j == 1){
                        dp[i][j] = 2;
                    }else{
                        dp[i][j] = dp[i+1][j-1]+2;
                    }
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

发表于 分类于

DNS查询过程

DNS 用来将主机名和域名转换为IP地址, 其查询过程一般通过以下步骤：

本地DNS缓存检查：首先查询本地DNS缓存，如果缓存中有对应的IP地址，则直接返回结果。 如果本地缓存中没有，则会向本地的DNS服务器（通常由你的互联网服务提供商（ISP）提供， 比如中国移动）发送一个DNS查询请求。 如果本地DNS解析器有该域名的ip地址，就会直接返回，如果没有缓存该域名的解析记录，它会向根DNS服务器发出查询请求。根DNS服务器并不负责解析域名，但它能告诉本地DNS解析器应该向哪个顶级域（.com/.net/.org）的DNS服务器继续查询。 本地DNS解析器接着向指定的顶级域名DNS服务器发出查询请求。顶级域DNS服务器也不负责具体的域名解析，但它能告诉本地DNS解析器应该前往哪个权威DNS服务器查询下一步的信息。 本地DNS解析器最后向权威DNS服务器发送查询请求。 权威DNS服务器是负责存储特定域名和IP地址映射的服务器。当权威DNS服务器收到查询请求时，它会查找"example.com"域名对应的IP地址，并将结果返回给本地DNS解析器。 本地DNS解析器将收到的IP地址返回给浏览器，并且还会将域名解析结果缓存在本地，以便下次访问时更快地响应。 浏览器发起连接： 本地DNS解析器已经将IP地址返回给您的计算机，您的浏览器可以使用该IP地址与目标服务器建立连接，开始获取网页内容。

CDN是什么，有什么作用？

CDN是一种分布式网络服务，通过将内容存储在分布式的服务器上，使用户可以从距离较近的服务器获取所需的内容，从而加速互联网上的内容传输。

就近访问：CDN 在全球范围内部署了多个服务器节点，用户的请求会被路由到距离最近的 CDN 节点，提供快速的内容访问。 内容缓存：CDN 节点会缓存静态资源，如图片、样式表、脚本等。当用户请求访问这些资源时，CDN 会首先检查是否已经缓存了该资源。如果有缓存，CDN 节点会直接返回缓存的资源，如果没有缓存所需资源，它会从源服务器（原始服务器）回源获取资源，并将资源缓存到节点中，以便以后的请求。通过缓存内容，减少了对原始服务器的请求，减轻了源站的负载。 可用性：即使某些节点出现问题，用户请求可以被重定向到其他健康的节点。

发表于 分类于

卡码笔试 263.数据重删

题目描述： 输入一串存储的数据，用N表示数据个数，用K表示数据块的大小，设计一个方法判断当前数据块是否和前面的数据块有重复，两个数据块内容完全一样则表示重复，如果重复则将这个数据块删除，并且在第一个出现数据块的后面增加重复数据的计数，输出经过重删之后的数据内容。 输入示例： 

1
2
3
8 
3 
3 4 5 3 4 5 5 4
输出示例： 
1
3 4 5 2 5 4 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
#include <map>
#include <vector>
#include <iostream>
using namespace std;

int main(){
    int total;
    int len;
    int c;
    vector<int> data;
    cin>>total>>len;
    while(cin>>c){
        data.push_back(c);
    }

    map<vector<int>, int> mp;
    vector<vector<int>> uniqueBlock;
    vector<bool> isUnique;
    for(int i = 0; i < data.size(); i+=len){
        int cnt = 0;
        vector<int> block;
        while(cnt < len && (i+cnt) < data.size()){
            block.push_back(data[i+cnt]);
            // cout<<"pushed in block: "<<data[i+cnt]<<endl;
            cnt++;
        }
        // cout<<endl;
        mp[block]++;
        if(mp[block] == 1){
            isUnique.push_back(true);
        }else{
            isUnique.push_back(false);
        }
        uniqueBlock.push_back(block);
    }
    for(int i = 0; i < uniqueBlock.size(); i++){
        if(isUnique[i] == true){
            for(int n: uniqueBlock[i]){
                cout<<n<<' ';
            }
            cout<<mp[uniqueBlock[i]]<<' ';
        }
    }
    // cout<<endl;

    // cout<<"total data: "<<total<<endl;
    // cout<<"len of blocks: "<<len<<endl;
    // for(int i: data){
    //     cout<<i<<' ';
    // }
    // cout<<endl;
}

发表于 更新于 分类于

这回笔试，我选择寄得比算法多（好久没刷八股题了=_=||），某境外电商的算法还是相对简单的

MySQL的默认事务隔离级别

REPEATABLE READ

算法

我ac了：

  • 求杨辉三角指定行指定区间的和（暴力就可以了）
  • 给定一个数组，这个数组的每一项是一个模块的单元测试，每次合并两个模块都需要执行两个模块单元测试数之和，问合并所有模块需要的最小测试数是多少（从小到大sort一下，再相加即可）

考试时发现我忘记了：

sort库函数怎么传递比较参数（比如我不需要默认的从小到大，而是从大到小该怎么办） 怎么构造并使用大/小顶堆

我没有ac:

打包员有m个相同重量上限k的袋子，需要打包weights数组个物品，这些物品一定是从前向后依次打包的，已知物品个数n, 每个物品重量的数组weights,求k的最小值

这个我本来以为需要背包算法，后来发现二分查找就可以了

发表于 分类于

115.不同的子序列

这题我想到要对于t的每个字符，一在s里匹配到，就从两串的下一个字符开始往后匹配。这么一看感觉开始递归了，不太动态规划。

题解的递推公式如下： 这一类问题，基本是要分析两种情况 - s[i - 1] 与 t[j - 1]相等 - s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。 - 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。 - 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]

注意上限长度且所有字符一样的s和t，会使得dp超long long的限制，此时使用uint64_t 

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
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(t.size()+1, vector<uint64_t>(s.size()+1,0));
        // dp[0][0] = 1;
        for(int i=0; i<s.size();i++){
            if(s[i] == t[0])dp[0][i] = 1;
        }
        for(int i=1; i<=t.size(); i++){
            for(int j=1; j<=s.size(); j++){
                if(s[j-1] == t[i-1]){
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    // if(i == 1)dp[i][j] = max(dp[i][j], 1);
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        // for(auto c:dp){
        //     for(int c_i : c){
        //         cout<<c_i<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[t.size()][s.size()];
    }
};

583. 两个字符串的删除操作

和上一题有些类似的思路 

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
        for(int i = 1; i <= word1.size(); i++)dp[i][0] = i;
        for(int j = 1; j <= word2.size(); j++)dp[0][j] = j;
        for(int i = 1; i <= word1.size(); i++){
            for(int j = 1; j <= word2.size(); j++){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+2);
                }
            }
        }
        // for(auto line : dp){
        //     for(auto i : line){
        //         cout<<i<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[word1.size()][word2.size()];
    }
};

72. 编辑距离

跟上两题差不多的思路，差点就写对了 

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        for(int i = 0; i < word1.size(); i++)dp[i+1][0] = (i+1);
        for(int i = 0; i < word2.size(); i++)dp[0][i+1] = (i+1);
        // dp[0][0] = 1;
        for(int i = 1; i <= word1.size(); i++){
            for(int j = 1; j <= word2.size(); j++){
                if(word1[i-1] != word2[j-1]){
                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
                }else{
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }

        // for(auto line : dp){
        //     for(int i : line){
        //         cout << i << ' ';
        //     }
        //     cout << endl;
        // }
        return dp[word1.size()][word2.size()];
    }
};

发表于 更新于 分类于

1143.最长公共子序列

按照动态规划，每次比较成功就加一，取所有值最大的思路是错的，这种会把乱序但是相同的字符也算进去。 于是我想了半天怎么先循环以i,j为右下角的正方形，本来想的是记忆化将i,j赋值为比较后相等的值，看了题解发现得在递推公式上作更改 因为字符中间可能会插入别的字符，所以ac,ace的比较结果和ac,aced的比较结果是一样的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1, vector<int> (text2.size()+1, 0));
        for(int i = 1; i <= text1.size();i++){
            for(int j = 1; j <= text2.size(); j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

1035.不相交的线

既然一个数只能连一根线，那么其实和上一题是一个意思了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1, vector<int> (nums2.size()+1, 0));
        for(int i = 1; i <= nums1.size(); i++){
            for(int j = 1; j <= nums2.size(); j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

53. 最大子序和

我想的是，dp[i]由dp[i-1],dp[i-1]+nums[i],nums[i]中的最大值决定，但是这样解会算出不连续的最大值

题解的推算法是这样的： dp[i]只有两个方向可以推出来： - dp[i-1] + nums[i]，即：nums[i]加入当前连续子序列和 - nums[i]，即：从头开始计算当前连续子序列和 再找每个的dp[i]最大值 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            if(dp[i] > res)res = dp[i];
        }
        return res;
    }
};

392.判断子序列

常规做的话双指针法即可，按照动态规划来做是和第一题是差不多的思路 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
        for(int i = 1; i <= s.size(); i++){
            for(int j = 1; j <= t.size(); j++){
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[s.size()][t.size()] == s.size() ? true : false;
    }
};

发表于 分类于

TCP连接三次握手的过程，为什么是三次，可以是两次或者更多吗？

  1. 三次握手的过程

第一次握手：客户端向服务器发送一个SYN （同步序列编号）报文，请求建立连接，客户端进入SYN_SENT 状态。 第二次握手：服务器收到SYN 报文后，如果同意建立连接，则会发送一个SYN-ACK （同步确认）报文作为响应，同时进入SYN_RCVD 状态。 第三次握手：客户端收到服务器的SYN-ACK 报文后，会发送一个ACK （确认）报文作为最终响应，之后客户端和服务器都进入ESTABLISHED 状态，连接建立成功。

(2)为什么需要三次握手 因为TCP需要简历双向的数据连接。通过三次握手，客户端和服务器都能够确认对方的接收和发送能力。第一次握手确认了客户端到服务器的通道是开放的；第二次握手确认了服务器到客户端的通道是开放的；第三次握手则确认了客户端接收到服务器的确认，从而确保了双方的通道都是可用的。

而如果仅使用两次握手，服务器可能无法确定客户端的接收能力是否正常，比如客户端可能已经关闭了连接，但之前发送的连接请求报文在网络上延迟到达了服务器，服务器就会主动去建立一个连接，但是客户端接收不到，导致资源的浪费。而四次握手可以优化为三次。

TCP连接四次挥手的过程，为什么是四次？

（1）四次挥手的过程

第一次挥手：客户端发送一个FIN报文给服务端，表示自己要断开数据传送，报文中会指定一个序列号 (seq=x)。然后,客户端进入FIN-WAIT-1 状态。 第二次挥手：服务端收到FIN报文后，回复ACK报文给客户端，且把客户端的序列号值+1，作为ACK报文的序列号(seq=x+1)。然后，服务端进入CLOSE-WAIT(seq=x+1)状态，客户端进入FIN-WAIT-2状态。 第三次挥手：服务端也要断开连接时，发送FIN报文给客户端，且指定一个序列号(seq=y+1)，随后服务端进入LAST-ACK状态。 第四次挥手：客户端收到FIN报文后，发出ACK报文进行应答，并把服务端的序列号值+1作为ACK报文序列号(seq=y+2)。此时客户端进入TIME-WAIT状态。服务端在收到客户端的ACK 报文后进入CLOSE 状态。如果客户端等待2MSL没有收到回复，才关闭连接。

（2）为什么需要四次挥手

TCP是全双工通信，可以双向传输数据。任何一方都可以在数据传送结束后发出连接释放的通知，待对方确认后进入半关闭状态。 当另一方也没有数据再发送的时候，则发出连接释放通知，对方确认后才会完全关闭 TCP 连接。因此两次挥手可以释放一端到另一端的TCP连接，完全释放连接一共需要四次挥手。

只有通过四次挥手，才可以确保双方都能接收到对方的最后一个数据段的确认，主动关闭方在发送完最后一个ACK后进入TIME-WAIT 状态，这是为了确保被动关闭方接收到最终的ACK ，如果被动关闭方没有接收到，它可以重发FIN 报文，主动关闭方可以再次发送ACK 。

而如果使用三次挥手，被动关闭方可能在发送最后一个数据段后立即关闭连接，而主动关闭方可能还没有接收到这个数据段的确认。

HTTP的Keep-Alive是什么？TCP 的 Keepalive 和 HTTP 的 Keep-Alive 是一个东西吗？

HTTP 的 Keep-Alive，是由应用层实现的，称为 HTTP 长连接 每次请求都要经历这样的过程：建立 TCP连接 -> HTTP请求资源 -> 响应资源 -> 释放连接，这就是HTTP短连接，但是这样每次建立连接都只能请求一次资源，所以HTTP 的 Keep-Alive实现了使用同一个 TCP 连接来发送和接收多个 HTTP 请求/应答，避免了连接建立和释放的开销，就就是 HTTP 长连接。通过设置HTTP头Connection: keep-alive来实现。

TCP 的 Keepalive，是由TCP 层（内核态）实现的，称为 TCP 保活机制，是一种用于在 TCP 连接上检测空闲连接状态的机制 当TCP连接建立后，如果一段时间内没有任何数据传输，TCP Keepalive会发送探测包来检查连接是否仍然有效。

补充说明：

其实这里tcp的keepalive，不只是支持http，还可以支持ftp和smtp的，他是一个能力，类似于gc。

http的这个keepalive感觉更是一种策略吧，比如你有一个http用了keepalive，然后过了一会，你不传输数据了，这个时候没有通知对方close，这个时候tcp的keepalive就会起到用处去关闭这次链接。

发表于 更新于 分类于 ，

进程家族树 (Process Family Tree)

  1. 实验报告：准备好实验报告

  2. simple_fork.c：编写一个名为 simple_fork.c 的简短程序，使用 fork() 函数从父进程生成一个子进程。父进程应在 fork 之前打印一条语句，并在 fork 之后打印出子进程的 PID。子进程应在被生成后打印一条语句，使用 getpid() 和 getppid() 函数打印出其自身的 PID 及其父进程的 PID。在您的树莓派上编译并运行您的程序，并将程序的输出作为此问题的答案。 提示：gcc编译gcc [source] -o [destination]

  3. tree_fork.c：编写第二个名为 tree_fork.c 的程序，该程序将一个整数作为命令行参数，并在最多 10 代的固定限制内，生成一个具有指定代数的“二进制家族树”进程。这将创建 2^n - 1 个进程，其中 n 是代数。对于 n=1，程序将创建 1 个进程；对于 n=5，将创建 31 个进程；对于 n=10，将创建 1023 个进程，依此类推。我们将代数限制为最多 10，因为更大的数字会运行很长时间，甚至可能冻结您的树莓派！

    • 如果未提供命令行参数，程序应输出有用的用法消息并退出。
    • 否则，它应将命令行参数转换为整数并存储在 generations 变量中。
    • 如果 generations 变量小于 1 或大于 10，程序应输出有用的用法消息并退出。
    • 否则，它（以及它生成的任何子进程）应执行以下操作（原始程序为第一代）：
      • 打印一行，说明它属于哪一代及其自身的 PID；
      • 增加当前代数计数器；
      • 如果已达到最后一代（根据 generations 变量），则直接返回 0；否则，生成两个子进程；
      • 使用 wait(0) 等待任何成功生成的子进程完成；
      • 如果两个子进程都成功生成，则返回 0；如果任一生成（或两者都）失败，则返回 -1。
    • 提示：仔细检查每次调用 fork()（或您用于生成每个子进程的任何调用）返回的 pid_t 值非常重要，因为 (1) 这些调用可能失败（由负返回值指示），(2) 0 表示子进程正在运行，(3) 正数表示父进程正在运行。
    • 提示：基于此，使用递归，或使用带有几个 pid_t 变量（每个子进程一个）的 while 循环并明智地在子进程中运行的代码分支使用 continue 语句，可以很直接地实现本练习的逻辑。
    • 作为此练习的答案，请展示您的程序在运行 4 代时（如果正确实现，应总共生成 15 个进程）的输出。

  4. 修改 kobject 示例模块：现在我们将回到使用这些思想进行内核模块设计。首先，从您的 linux 源码目录中，找到并将文件 samples/kobject/kobject-example.c 复制到您保存内核模块代码的目录中。这是一个使用称为 kobjects 的功能的内核模块，它提供了一个在内核和用户空间之间交换数据的接口。每个数据项称为一个属性（attribute），对于每个属性，您需要提供一个 show 和 store 函数，分别在用户空间读取和写入这些值时被调用。

    • 该特定模块提供三个属性：foo、baz 和 bar。加载后，您可以在 sysfs 文件系统中的 /sys/kernel/kobject_example/ 目录下找到它们。
    • 修改此文件，以便（通过使用 printk）在更新 foo、baz 或 bar 中的任何一个时打印一条系统日志消息，并在消息中显示被更新变量的旧值和新值。
    • 现在我们可以像以前一样构建您修改后的模块。首先，更新您的 Makefile，使其包含新模块的相应 .o 文件目标，然后为您的模块生成 .ko 文件，如下所示： 
      1
      2
      3
      module add arm-rpi
      LINUX_SOURCE=您的Linux内核源代码路径
      make -C $LINUX_SOURCE ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- M=$PWD modules
    • 然后，使用 sftp 将生成的 .ko 文件复制到您的树莓派上，并使用 sudo insmod 加载该模块。
    • 在具有 root 权限的终端中，您可以使用 cat 命令读取这些属性的值，并使用 echo 命令将值写入这些属性，例如： 
      1
      2
      3
      4
      5
      sudo bash
      cd /sys/kernel/kobject_example/
      cat foo          # 显示 foo 属性的当前（原始）值
      echo 42 > foo    # 将值 42 写入属性 foo
      cat foo          # 显示属性 foo 的新值
      注意：您必须有一个 root 终端（sudo bash 可以给您）才能写入这些命令（即 sudo echo 不起作用）。
    • 作为此练习的答案，请展示使用这些命令成功更改 foo、bar 和 baz 值的输出演示。

  5. family_reader.c 模块：现在我们将编写一个内核模块，通过 sysfs 接口读取一个 PID，并在系统日志中打印该进程的祖先谱系。

    • 创建一个基于您修改后的 kobject-example.c 文件的新内核模块文件 family_reader.c（即，首先请复制它）。该模块应在 /sys/kernel/fam_reader/ 下创建单个系统属性（像上一个练习一样是整数值）。当您向此属性写入一个整数时，您的模块应尝试打印出该 PID 的祖先谱系（即，它的父进程，然后是父进程的父进程，依此类推，一直追溯到 init 任务）。涉及几个步骤：
      • 旁注：现代 Linux 内核为了便于在不同虚拟主机之间迁移进程，区分了“真实”PID 和“虚拟”PID。虚拟 PID 是进程从用户空间看到的 PID。
      • 您需要将整数输入转换为合适的内核 PID。使用函数 find_vpid()（请参阅 include/linux/pid.h 和 kernel/pid.c），它返回一个 struct pid *。此函数可能失败，因此在解引用指针之前务必检查其返回值。
      • 接下来，您可以通过将 struct pid * 和标志 PIDTYPE_PID 传递给函数 get_pid_task()（请参阅 include/linux/pid.h 和 kernel/pid.c）来将其转换为 struct task_struct *。此函数可能失败，因此在解引用指针之前务必检查其返回值。
      • 一旦您有了 struct task_struct *，就可以访问它存储的任何数据。特别是，real_parent 字段存储了生成它的进程的 struct task_struct * 指针，comm 字段是给出命令名称的字符串。
        • 注意：有一个单独的字段叫做 parent，这不是我们本练习想要的。parent 是共享进程组信号并允许父子进程之间等待的逻辑父进程。
      • 回溯家族树，打印出每个任务的 PID 和命令名称，一直回溯到 PID 为 1 的 init 任务。
    • 像上一个模块一样编译您的新内核模块，然后使用 sftp 将生成的 .ko 文件复制到您的树莓派上。在您的树莓派上，安装该模块，然后使用 sudo bash 为您的终端会话提供 root 访问权限。在该模块的目录下（将在 /sys/kernel/ 下），使用 cat 和 echo 读取和写入该模块属性的值，然后使用 dmesg 确认系统日志显示您的模块工作正常。
    • 使用 ps 命令查找在您当前终端窗口中运行的 sudo 进程的 PID，使用 echo 将您的模块属性设置为该 PID，然后使用 dmesg 查看该进程的祖先谱系。作为此练习的答案，请展示显示 sudo 进程祖先谱系的系统日志消息。

可选拓展练习 (Optional Enrichment Exercises)

  1. 探索 task_struct：task_struct 包含许多有趣的进程数据和进程记账信息。尝试将其他字段打印到系统日志中，并作为此练习的答案，请简要描述您打印了哪些内容，并展示执行此操作后的一些系统日志消息。
  2. 探索调度程序功能：kernel/sched 和 include/linux/sched 中的文件包含许多用于处理任务的功能，包括修改特定任务或迭代系统中每个任务的能力。例如，include/linux/sched/signal.h 定义了诸如 for_each_process() 之类的宏。尝试使用其中一些功能，并作为此练习的答案，请简要描述您做了什么以及观察到了什么。

发表于 分类于

300.最长递增子序列

这题我一开始想使用回溯找最长子序列，但是我发现需要记录的状态太多，回溯没办法解决；同时对于序列中的相同数字，如何记住遍历前后的状态也是个问题。 题解中这题使用的是动态规划，对于每一个索引求它所在的最长递增子序列，再求所有子序列中最长的那个。

  • 外层循环：遍历序列中每一个索引i
  • 内层循环：求从开头到i之前的数字j中最长的子序列，如果nums[i] > nums[j]，则开头到i所在处最长子序列为j所在处+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int mx = 1;
        for(int i = 1; i<nums.size(); i++){
            for(int j = 0; j<i; j++){
                if(nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);
                // cout<<dp[i]<<' ';
            }
            mx = max(mx, dp[i]);
            // cout<<endl;
        }
        return mx;
    }
};

674. 最长连续递增序列

这题不要想得太复杂了就行 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int lng = 1;
        int max_l = 1;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > nums[i-1]){
                lng++;
            }else{
                lng = 1;
            }
            max_l = max(max_l, lng);
        }
        return max_l;
    }
};

718. 最长重复子数组

这题我想可不可以分别求两个数组的最长相等前后缀表，再找重复子数组。看了动规解法我发现，一个两数组比较表能解决的事情，用前后缀表似乎有点浪费？

动规解法中，dp[i][j]表示两个数组下标i-1，j-1个数进行比较，这样0行和0列默认初始化为0即可。如果表示下标i，j个数，则需要再初始化一下0行和0列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len = 0;
        vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
        for(int i = 1; i < (nums1.size()+1); i++){
            for(int j = 1; j < (nums2.size()+1); j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(dp[i][j] > len)len = dp[i][j];
            }
        }
        // for(auto line:dp){
        //     for(int l:line){
        //         cout<<l<<' ';
        //     }
        //     cout<<endl;
        // }
        return len;
    }
};

0%