baozi's page
0%

发表于 更新于 分类于

查看当前分支

git branch -- show-current

发表于 更新于 分类于 
1
2
3
4
5
#include <stdio.h>
int main() {
  printf("hello world\n");
  return 0;
}

预处理阶段：预处理器根据#开头的命令，读取头文件，并插入到程序中，得到.i文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 1 "hello.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "hello.c"






include <stdio.h>

int main()
{
 printf("hello world\n");
 return 0;

}

编译阶段：编译器将hello.i翻译成文本文件hello.s

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
	.arch armv8-a
	.file	"hello.c"
	.text
	.section	.rodata
	.align	3
.LC0:
	.string	"hello world"
	.text
	.align	2
	.global	main
	.type	main, %function
main:
.LFB0:
	.cfi_startproc
	stp	x29, x30, [sp, -16]!
	.cfi_def_cfa_offset 16
	.cfi_offset 29, -16
	.cfi_offset 30, -8
	mov	x29, sp
	adrp	x0, .LC0
	add	x0, x0, :lo12:.LC0
	bl	puts
	mov	w0, 0
	ldp	x29, x30, [sp], 16
	.cfi_restore 30
	.cfi_restore 29
	.cfi_def_cfa_offset 0
	ret
	.cfi_endproc
.LFE0:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0"
	.section	.note.GNU-stack,"",@progbits

汇编阶段：汇编器将hello.s翻译成机器语言的指令，将结果保存在.o文件中

链接阶段：hello.c文件中调用了printf()函数，printf函数存在于printf.o的程序中，链接器负责处理合并，得到可执行文件

发表于 更新于 分类于

埃氏筛

1
2
3
4
5
6
7
8
9
10
vector<bool> is_prime(n, true);
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; i <= n; i++) {
  if (is_prime[i]) {
    for (int j = 2 * i; j <= n; j += i) {
      is_prime[j] = false;
    }
  }
}

排序算法

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
void bubble_sort(std::vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				std::swap(nums[j], nums[j + 1]);
			}
		}
	}
}

void sellection_sort(std::vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n; i++) {
		int min = i;
		for (int j = i + 1; j < n; j++) {
			if (nums[min] > nums[j]) {
				min = j;
			}
		}
		std::swap(nums[i], nums[min]);
	}
} 

int partition(std::vector<int>& nums, int low, int high) {
	int pivot = nums[low];
	while (low < high) {
		while (low < high && nums[high] > pivot) {
			high--;
		}
		nums[low] = nums[high];
		while (low < high && nums[low] < pivot) {
			low++;
		}
		nums[high] = nums[low];
	}
	nums[low] = pivot;
	return low;
}
void quick_sort(std::vector<int>& nums, int low, int high) {
	if (low < high) {
		int pivot = partition(nums, low, high);
		quick_sort(nums, low, pivot - 1);
		quick_sort(nums, pivot + 1, high);
	}
}

回溯

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

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择 : 本层集合中的元素) {
        处理节点;
        backtracking(路径, 选择列表); // 递归
        撤销处理; // 回溯
    }
}

二叉树的层序遍历

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
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//	使用二维数组保存遍历结果
//	使用队列
vector<vector<int>> level_order(TreeNode* root) {
  vector<int> temp;
  vector<vector<int>> res;
  if (!root) {
  	return res;
  }
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    temp.clear();
    int len = q.size();
    for (int i = 0; i < len; i++) {
      TreeNode* node = q.front();
      q.pop();
      temp.push_back(node->val);
      if (node -> left) {
        q.push(node -> left);
      }
      if (node ->right) {
        q.push(node -> right);
      }
    }
    res.push_back(temp);
  }
  return res;
}

高精度乘法

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> mul(vector<int>&A,int b)
{
    vector<int> C;
    for(int i=0,t=0;i<A.size()||t;i++)
    {
        if(i<A.size())
            t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0)
        C.pop_back();
    return C;
}
int main()
{
    vector<int> A;
    string a;
    int b;
    cin >> a >> b;
    for(int i=int(a.size())-1;i>=0;i--)
        A.push_back(a[i]-'0');
    auto C=mul(A,b);
    for(int i=int(C.size())-1;i>=0;i--)
        cout << C[i];
    return 0;
}

高精度加法

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int>&a,vector<int>&b)
{
    vector<int> A,B;
    if(a.size()<b.size())
    {
        A=b;
        B=a;
    }
    else
    {
        A=a;
        B=b;
    }
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size())
            t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)
        C.push_back(t);
    return C;
}
int main()
{
    vector<int> A,B;
    string a,b;
    cin >> a >> b;
    for(int i=int(a.size())-1;i>=0;i--)
        A.push_back(a[i]-'0');
    for(int i=int(b.size())-1;i>=0;i--)
        B.push_back(b[i]-'0');
    auto C=add(A,B);
    for(int i=int(C.size())-1;i>=0;i--)
        cout << C[i];
}

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
// 不使用+-来计算两数之和
int add (int a, int b) {
  while (b) {
    int carry = (a & b) << 1;	//进位
    a = a ^ b;	// 无进位结果
    b = carry;
  }
  return a;
}
// 奇数的最低位总是1，偶数的最低位总是0
if (num & 1) {
  cout << "奇数" << endl;
}

01背包

问题描述：给定 n 个物品，第 i 个物品的重量为 wgt[i−1]、价值为 val[i−1] ，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

定义状态：[i, c],物品编号i和背包容量c

对于当前物品，有两种方案

​ 不放入背包：[i, c] = [i - 1, c]

​ 放入背包：[i, c] = [i - 1, c - weight[i - 1]],价值增加val[i];

dp[i,c]=max(dp[i−1,c],dp[i−1,c−wgt[i−1]]+val[i−1]

滑动数组

定长滑动数组

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

例如s = "abciiidef", k = 3

从左到右遍历 s。
首先统计前 k−1=2 个字母的元音个数，这有 1 个。
s[2]=c 进入窗口，此时找到了第一个长为 k 的子串 abc，现在元音个数有 1 个，更新答案最大值。然后 s[0]=a 离开窗口，现在元音个数有 0 个。
s[3]=i 进入窗口，此时找到了第二个长为 k 的子串 bci，现在元音个数有 1 个，更新答案最大值。然后 s[1]=b 离开窗口，现在元音个数有 1 个。
s[4]=i 进入窗口，此时找到了第三个长为 k 的子串 cii，现在元音个数有 2 个，更新答案最大值。然后 s[2]=c 离开窗口，现在元音个数有 2 个。
s[5]=i 进入窗口，此时找到了第四个长为 k 的子串 iii，现在元音个数有 3 个，更新答案最大值。然后 s[3]=i 离开窗口，现在元音个数有 2 个。
s[6]=d 进入窗口，此时找到了第五个长为 k 的子串 iid，现在元音个数有 2 个，更新答案最大值。然后 s[4]=i 离开窗口，现在元音个数有 1 个。
s[7]=e 进入窗口，此时找到了第六个长为 k 的子串 ide，现在元音个数有 2 个，更新答案最大值。然后 s[5]=i 离开窗口，现在元音个数有 1 个。
s[8]=f 进入窗口，此时找到了第七个长为 k 的子串 def，现在元音个数有 1 个，更新答案最大值。遍历结束。

步骤：

入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。

代码：

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 maxVowels(string s, int k) {
        unordered_set<char> vowles = {'a', 'e', 'i', 'o', 'u'};
        int ans = 0;
        int cur = 0;
        for (int i = 0; i < s.size(); i++) {
            if (vowles.count(s[i]) > 0) {
                cur++;
            }
            if (i < k - 1) {
                continue;
            }
            ans = max(ans, cur);
            if (vowles.count(s[i - k + 1]) > 0) {
                cur--;
            }
        }
        return ans;
    }
};

不定长滑动数组

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLongestSubstring(string s) {
        int res = 0;
        int left = 0;
        unordered_map<char, int> cnt;
        for (int right = 0; right < s.size(); right++) {
            cnt[s[right]]++;
            while (cnt[s[right]] > 1) {
                cnt[s[left]]--;
                left++;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }

越长越合法

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numberOfSubstrings(string s) {
        int left = 0;
        unordered_map<char, int> cnt;
        int ans = 0;
        for (int right = 0; right < s.size(); right++) {
            cnt[s[right]]++;
            while (cnt['a'] && cnt['b'] && cnt['c']) {
                cnt[s[left]]--;
                left++;
            }
            ans += left;
        }
        return ans;
    }

现在的已经满足了，更长的子串就满足，+left

越短越合法

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int cur = 1;
        int res = 0;
        int left = 0;
        if (k <= 1) {
            return 0;
        }
        for (int right = 0; right < nums.size(); right++) {
            cur *= nums[right];
            while (cur >= k) {
                cur /= nums[left];
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }

长的合法，长的所有子串都合法，+ right - left + 1

恰好

例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

计算有多少个元素和 ≥k 的子数组。
计算有多少个元素和 >k，也就是 ≥k+1 的子数组。
答案就是元素和 ≥k 的子数组个数，减去元素和 ≥k+1 的子数组个数。这里把 > 转换成 ≥，从而可以把滑窗逻辑封装成一个函数 f，然后用 f(k) - f(k + 1) 计算，无需编写两份滑窗代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int my_fun(vector<int>& nums, int goal) {
        int left = 0;
        int res = 0;
        int cur = 0;
        for (int right = 0; right < nums.size(); right++) {
            cur += nums[right];
            while (cur >= goal && left <= right) {
                cur -= nums[left];
                left++;
            }
            res += left;
        }
        return res;
    }
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return my_fun(nums, goal) - my_fun(nums, goal + 1);
    }

二分

1
mid = left + (right - left) / 2; //避免溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// lower_bound,指向第一个 ≥ value 的元素的迭代器。
int binarySearch(vector<int>& nums,int target) {
  int left = 0;
  int right = nums.size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}
1
auto it = lower_bound(nums, target);	//二分，返回的是迭代器，值为*it
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// upper_bound,指向第一个 > value 的元素的迭代器。
int binarySearch(vector<int>& nums,int target) {
  int left = 0;
  int right = nums.size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

发表于 分类于

Lab1

1 Sleep

首先判断sleep是否有参数，将argv[1]转换为int类型，使用系统调用sleep实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 #include "kernel/types.h"
 2 #include "kernel/stat.h"
 3 #include "user/user.h"
 4
 5 int main(int argc, char* argv[]) {
 6   if (argc != 2) {
 7    fprintf(2, "usage: sleep 10");
 8    exit(1);
 9   }
10   int time = atoi(argv[1]);
11   sleep(time);
12
13   exit(0);
14
15 }

2 pingpong

建立两个管道，fd1, fd2，通过read和write实现父进程和子进程之间的通信 

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
 1 #include "kernel/types.h"
 2 #include "kernel/stat.h"
 3 #include "user/user.h"
 4
 5 int main(int argc, char* argv[]) {
 6     int fd1[2];
 7     int fd2[2];
 8     int ret1 = pipe(fd1);
 9     int ret2 = pipe(fd2);
10     char buffer[] = {'a'};
11     if (ret1 == -1) {
12         fprintf(2, "pipe error");
13         exit(1);
14     }
15     if (ret2 == -1) {
16         fprintf(2, "pipe error");
17         exit(1);
18     }
19     int pid = fork();
20     if (pid == -1) {
21         fprintf(2, "fork error");
22         exit(1);
23     } else if (pid == 0) {
24         //child
25         read(fd1[0], buffer, 1);
26         printf("%d: received ping\n", getpid);
27         write(fd2[1], buffer, 1);
28     } else {
29         //parent
30         write(fd1[1], buffer, 1);
31         read(fd2[0], buffer, 1);
32         printf("%d: received pong\n", getpid);
33
34     }
35     exit(0);
36 }

3 primes

在main函数中的父进程中输入2～35，在main函数的子进程中递归调用filter函数

在filter函数中，首先读的一定是质数，直接输出，通过这个prime判断其他数是否读入到下一个进程中

每个父进程都要写wait，否则会超时

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
68
69
 1 #include "kernel/types.h"
 2 #include "kernel/stat.h"
 3 #include "user/user.h"
 4
 5 #define INT_LENGTH 4
 6
 7 void filter(int fd[2]) {
 8     int prime;
 9     read(fd[0], &prime, INT_LENGTH);
10     printf("prime %d\n", prime);
11     int num;
12     int flag;
13     flag = read(fd[0], &num, INT_LENGTH);
14     if (flag == 0) {
15         exit(0);
16     }
17     int new_fd[2];
18     int ret = pipe(new_fd);
19     if (ret == -1) {
20         fprintf(2, "pipe error");
21         exit(1);
22     }
23
24     int pid = fork();
25     if (pid == -1) {
26         fprintf(2, "fork error");
27     } else if (pid == 0) {
28         close(new_fd[1]);
29         filter(new_fd);
30     } else {
31         close(new_fd[0]);
32         if (num % prime != 0) {
33             write(new_fd[1], &num, INT_LENGTH);
34         }
35         while (read(fd[0], &num, INT_LENGTH) > 0) {
36             if (num % prime != 0) {
37                 write(new_fd[1], &num, INT_LENGTH);
38             }
39         }
40             close(new_fd[1]);
41             close(fd[0]);
42     }
43     wait(0);
44
45
46 }
47
48 int main(int argc, char* argv[]) {
49     int fd[2];
50     int ret = pipe(fd);
51     if (ret == -1) {
52         fprintf(2, "pipe error");
53     }
54     int pid = fork();
55     if (pid == -1) {
56         fprintf(2, "fork error");
57     } else if (pid == 0) {
58         close(fd[1]);
59         filter(fd);
60     } else {
61         close(fd[0]);
62         for (int i = 2; i <= 35; ++i) {
63             write(fd[1], &i, INT_LENGTH);
64         }
65         close(fd[1]);
66         wait(0);
67     }
68     exit(0);
69 }

4 find

find用法：find current_path target

fmtname作用：根据当前路径返回最后一个/后的内容

通过st.type判断是文件还是目录

文件，与target进行比对，相同输出当前路径

目录，递归使用find，构造路径

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

#define MAX_PATH 512

void find(char *curr_path, char *target);

char* fmtname(char *path)
{
    static char buf[DIRSIZ+1];
    char *p;

    // Find first character after last slash.
    for(p=path+strlen(path); p >= path && *p != '/'; p--)
        ;
    p++;

    // Return blank-padded name.
    if(strlen(p) >= DIRSIZ)
        return p;
    memmove(buf, p, strlen(p));
    buf[strlen(p)] = 0;
    return buf;
}

void find(char *curr_path, char *target) {
    char buf[MAX_PATH], *p;
    int fd;
    struct dirent de;
    struct stat st;

    if ((fd = open(curr_path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", curr_path);
        return;
    }

    if (fstat(fd, &st) < 0) {
        fprintf(2, "find: cannot stat %s\n", curr_path);
        close(fd);
        return;
    }

    switch (st.type) {
    case T_FILE: {
        // Check if the current file matches the target filename
        char *f_name = fmtname(curr_path);
        if (strcmp(f_name, target) == 0)
            printf("%s\n", curr_path);
        close(fd);
        break;
    }

    case T_DIR:
        // Traverse each entry in the directory
        memset(buf, 0, sizeof(buf));
        int curr_path_len = strlen(curr_path);
        memcpy(buf, curr_path, curr_path_len);
        buf[curr_path_len] = '/';
        p = buf + curr_path_len + 1;
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            if (de.inum == 0 || strcmp(de.name, ".") == 0 ||
                strcmp(de.name, "..") == 0)
                continue;
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            find(buf, target); // Recurse into subdirectories
        }
        close(fd);
        break;
    }
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(2, "usage: find [directory] [target filename]\n");
        exit(1);
    }
    find(argv[1], argv[2]);
    exit(0);
}

5 xargs

xargs的用法：echo a | xargs echo b,输入 b a，将前一个命令的输出作为后一个命令的参数

注意：下面代码中argv[0]是xargs

使用fork和exec使得新的进程得到执行

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"

void xargs(char* argv[], char* args[]) {
    int fd[2];
    int ret = pipe(fd);
    if (ret == -1) {
        fprintf(2, "pipe error");
        exit(1);
    }

    int pid = fork();
    if(pid == -1) {
        fprintf(2, "fork error");
    } else if (pid == 0) {
        //child
        close(fd[0]);
        close(fd[1]);
        exec(argv[1], args);
        exit(1);
    } else {
        wait(0);
    }
}

int main(int argc, char* argv[]) {
    if (argc < 3) {
        fprintf(2, "usage error");
    }

    char buf[512];
    char* args[MAXARG];
    args[0] = argv[1];
    // printf("argv[0]:%s\n", argv[0]);

    while (1) {
        gets(buf, 512);
        if (buf[0] == '\0') {
            break;
        }
        // printf("buf:%s\n", buf);

        buf[strlen(buf) - 1] = '\0';
        
        for (int i = 2; i < argc; i++) {
            args[i - 1] = argv[i];
        }

        args[argc - 1] = buf;
        args[argc] = 0;
        /*
        for (int i = 0; i < argc; i++) {
            printf("args:%s\n", args[i]);
        }
        */
        
        xargs(argv, args);
    }
    exit(0);
}

发表于 更新于 分类于

报错信息

kex_exchange_identification: read: Connection reset by peer Connection reset by ::1 port 3316

使用vscode链接docker后在终端输入以下命令

1
sudo service ssh restart

发表于 更新于 分类于

const

const位于星号左侧，const用于修饰指针指向的变量；const位于星号右侧，const修饰指针本身

1
2
3
4
5
int b = 500;
const int* a = &b; [1]
int const *a = &b; [2]
int* const a = &b; [3]
const int* const a = &b; [4]

1和2是等价的，都表示指向常量的指针，3表示指针本身不可变，但是指向的内容可变

1
2
3
4
5
int a = 10;
int* const p = &a;
*p = 20; //合法
int b = 20;
p = &b;	//不合法，Cannot assign to readonly type int * const
1
int a

static

被static修饰的变量只能在当前文件访问，函数同理

1
2
3
4
5
6
7
8
9
10
11
12
// a.cpp 文件
static int a = 10;  // static 修饰全局变量
int main() {
    a++;  // 合法，可以在当前文件中访问 a
    return 0;
}

// b.cpp 文件
extern int a;  // 声明 a
void foo() {
    a++;  // 非法，会报链接错误，其他文件无法访问 a
}

修饰局部变量

1
2
3
4
5
6
7
8
9
10
11
12
void foo() {
    static int count = 0;  // static 修饰局部变量
    count++;
    cout << count << endl;
}

int main() {
    foo();  // 输出 1
    foo();  // 输出 2
    foo();  // 输出 3
    return 0;
}

extern

用于声明外部变量

File1.c

1
2
3
4
5
6
7
8
#include <stdio.h>

int globalVar = 42;  // 定义全局变量

void printVar() {
    printf("globalVar = %d\n", globalVar);
}

file2.c

1
2
3
4
5
6
7
8
#include <stdio.h>

extern int globalVar;  // 声明外部变量

void modifyVar() {
    globalVar = 100;  // 修改外部变量
}

函数同理，extern还可以链接c和c++，用extern声明一个函数是c语言，则该函数可以在c++文件中使用

c

1
2
3
4
5
6
#include <stdio.h>

void hello() {
    printf("Hello from C!\n");
}

c++

1
2
3
4
5
6
7
8
9
#include <iostream>

extern "C" void hello();  // 告诉编译器这个函数是 C 语言的

int main() {
    hello();  // 调用 C 代码中的 hello() 函数
    return 0;
}

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
28
29
30
31
32
33
34
35
#include<vector>

// 声明
vector<int> vec1; //声明空的vector
vector<int> vec2(5); // 声明大小为5的vector
vector<int> vec3(5, 10); //声明大小为5且值都为10的vector
vector<int> vec4{1, 2, 3, 4, 5}; //初始化
vector<int> vec5(vec4); // 用另一个vecotr初始化

// 用法
vec.push_back(x); //在末尾添加元素
vec.emplace_back(x);	//在末尾添加元素，比push_back更快，push_back需要先构造，再复制，emplace_back直接在容器内构造，不需要复制
vec.pop_back(); //删除最后一个元素
int num = vec.back(); //获取最后一个元素
vec.erase(vec.begin() + 1); //删除指定位置的元素
vec.erase(vec.begin() + 1, vec.edn() - 1); // 删除指定范围的元素
vec.clear(); // 清空vector
int n = vec.size(); // 获取vec的大小
vec.resize(x); //动态调整大小，x比n大补0， x比n小，超出的部分移除
sort(vec.begin(), vec.end()); // 升序
sort(vec.begin(), vec.end(), greater<int>()); // 降序
int it = find(vec.begin(), vec.end(), 3); //查找值为3的元素
vec.remove(vec.begin(), vec.end(), 5); // 将值为5的元素移动到容器末尾
if (!vec.empty())；	//判空
int sum = accumulate(vec.begin(), vec.end(), 0)	//求和，初始值为0
int max_num = *max_element(vec.begin(), vec.end())//数组中的最大值
vec.insert(vec.end(), vec.begin(), vec.end())	//在vec的后面添加vec例如123->123123z
//在一个vector的后面添加另一个vector
vector<int> vec1 = {1, 2, 3};
vector<int> vec2 = {4, 5, 6};
vec1.insert(vec1.end(), vec2.begin(), vec2.end());
// 二维数组
int row = 3;
int col = 4;
vector<vector<int>> nums(row, vector<int>(4));

atoi stoi

1
2
3
4
5
6
7
8
9
10
11
12
const char* str = "abc";

// atoi
int result = atoi(str); //将字符串转换为数字

// stoi
try {
  std::string str = "abc";
  int result = std::stoi(str);
} catch (const std::invalid_argument& e) {
  std::cout << "Invalid argument:" << e.what() << std::endl;
}

stoi提供了更安全的方式

tolower, toupper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cctype>
string str = "Hello World";
string res;
for (char ch : str) {
  res += tolower(ch); //转为小写
}
for (char ch : str) {
  res += toupper(ch); //转为大写
}

// 更简单的方法
for (char ch : str) {
  ch ^= 32;
}
// 'A'(65) ⊕ 32 = 'a'(97)
// 'a'(97) ⊕ 32 = 'A'(65)

unordered_map

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 声明
unordered_map<char ch, int n> my_map;
my_map.insert({'a', 2}); 	// 插入元素
my_map[b] = 1; // 如果键不存在会创建并初始化
// 遍历
for (const auto& pair: my_map) {
  cout << pair.first << pait.second << endl;
}
// find的用法
auto it = umap.find("a");
if (it != umap.end()) {
    std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
} else {
    std::cout << "Not found!" << std::endl;
}
// count,返回键是否存在（0 或 1）
if (umap.count("a") > 0) {
    std::cout << "Key exists!" << std::endl;
}

sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//基础用法
vector<int> nums = {2, 3, 1, 0, 4};
sort(nums.begin(), nums.end());	// 默认升序
sort(nums.begin(), nums.end(), std::greater());	//降序排列
// 自定义排序
struct Student {
    std::string name;
    int score;
};

// 自定义排序规则
bool compareStudents(const Student& a, const Student& b) {
    if (a.score == b.score)  // 分数相同，按姓名排序
        return a.name < b.name;
    return a.score > b.score; // 分数降序
}

引用和指针

1
2
3
4
int a = 10;
int &b = a;
b = 20;
cout << a << endl;	// 20

b是a的引用，就是给a起个别名，对b进行操作实际上就是对a进行操作

1
2
int* a = null;
int& b;	//error

指针可以指向空，但是引用不能为空

1
2
3
4
int a = 10;
int &b = a;
int c = 30;
int &b = c;	//error

指针可以随意改变（除const修饰外），引用一旦绑定就不可以再改变

静态链接和动态链接

.cpp文件经过预处理成为.i文件，.i文件经过编译后成为.s文件，.s文件经过汇编后成为目标文件，即.o，静态链接将该.o文件和其他目标文件以及库文件链接起来，这个过程称为静态链接。

而动态链接将这个过程推迟到了运行时，由操作系统装载程序加载库

静态链接的代码装载速度快，但是文件体积大

动态链接的速度慢，但是文件体积小

c和c++的区别

  1. c只支持基本数据类型，还有结构体、枚举、联合；c++支持类和对象
  2. c++有封装的特性、有构造函数和析构函数、c++支持函数重载，可以定义同名但是参数列表不同的函数；c都做不到
  3. c++有异常处理机制；c没有
  4. c没有引用&

delete

释放new申请的空间，会调用析构函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

class MyClass {
public:
    MyClass() {
        std::cout << "构造函数" << std::endl;
    }
    ~MyClass() {
        std::cout << "析构函数" << std::endl;
    }
};

int main() {
    MyClass* obj = new MyClass();
    delete obj;
    return 0;
}

作用域解析操作符

访问全局变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

int num = 20;

void test() {
    int num = 10;
    std::cout << "test1:" << num << std::endl;
    std::cout << "test2" << ::num << std::endl;
}

int main() {
    int num = 30;
    test();
    std::cout << "test3:" << num << std::endl;
    std::cout << "test4:" << ::num << std::endl;
    return 0;
}

访问命名空间中的标识符

1
2
3
4
5
6
7
8
9
10
#include <iostream>

namespace MyNamespace {
    int val = 20;
}

int main() {
    std::cout << MyNamespace::val << std::endl;
    return 0;
}

访问修饰符

public:可以在任何函数中访问

protected:只能在类中或者类的子类中访问

private：只能在类中访问

strlen 和sizeof

1
2
3
4
5
char ch[] = "Hello World";
std::string str = "Hello World";
std::cout << sizeof(ch) << std::endl;	//12
std::cout << strlen(ch) << std::endl;	//11
std::cout << sizeof(str) << std::endl;	//24(windows|macos) 32(linux)

对于char ch[]类型，是c风格的字符串，在末尾会自动加\0

sizeof会统计末尾的\0

strlen不统计

string 和char ch[]

string在堆上分配内存，sizeof获取的是string类的大小

char ch[]在栈上分配内存

发表于 更新于 分类于

自然语言

通常是指一种自然地随文化演化的语言。自然语言是人类交流和思维的主要工具，是人类智慧的结晶

自然语言处理

是计算机科学领域与人工智能领域中一个重要的方向。它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法

自然语言处理的层次

  1. 输入层
  2. 文档层
  3. 句法分析
  4. 语义分析与篇章分析
  5. 其他高级任务

自然语言处理的流派

  1. 基于规则
  2. 基于统计
  3. 深度学习

机器学习

机器学习指的是计算机通过某项任务的经验数据提高了在这项任务上的能力

机器学习是让机器学会算法的算法

语料库

语料库是指经科学取样和加工的大规模电子文本库

语料库的分类

中文分词语料库

由人工正确切分后的句子集合

词性标注语料库

切分并为每个词语制定一个磁性的语料

命名实体识别语料库

人工标注了文本内部制作者关心的实体名词以及实体类别

句法分析语料库

文本分类语料库

语料库建设

构建一份语料库的过程

语言模型（Language Model）

语言模型是用来计算一个句子的概率的概率模型

语言模型的作用

  1. 决定哪一个词序列的可能性更大
  2. 已知若干个词，预测下一个词

语言库模型的应用

  1. 语音识别
  2. 机器翻译
  3. 上下文敏感的拼写检查

大语言模型

定义

是一种人工智能模型，旨在理解和生成人类语言。它们在大量的文本数据上进行训练，可以执行广泛的任务，包括文本总结、翻译、情感分析等。

序列标注问题

序列标注指的是给定一个序列x= x1 x2 x3 x4… 找出序列中每个元素对应的标签y = y1 y2 y3 y4 ….的问题

y所有可能的取值集合称为标注集

常见的序列标注方法

隐马尔可夫模型、条件随机场、深度学习模型

分类

指的是预测样本所属类别的问题

应用

  1. 文本分类
  2. 关键词提取时，对文章中每个单词判断是否属于关键词
  3. 在指代消解问题中，对每个代词和每个实体判断是否存在指代关系
  4. 预测天气、照片对应哪种事物、声波是否由哪个人发出

聚类

什么是聚类

指的是将给定对象的集合划分为不同子集的过程

应用

数据预处理

排重

大众化推荐

人工抽查

N-gram语言模型

更大的n：对下一个词出现的约束信息更多，更大的辨别力

更小的n：在训练语料库中出现的次数更多，更可靠的统计结果，更高的可靠性

Transformer

定义

Transformer是一种用于自然语言处理（NLP）和其他序列到序列（sequence-to-sequence）任务的深度学习模型架构。

Transformer模型是一种基于自注意力机制的神经网络模型

Transformer模型主要由两个部分组成：编码器和解码器

序列到序列任务

序列到序列是指将一个序列转换为另一个序列到任务

发表于 更新于 分类于

exit

执行exit系统调用后，进程会从运行状态转为僵尸状态(zombie),操作系统会销毁当前进程，释放资源

exit是c标准库的函数，_exit是系统调用，直接终止进程，不进行清理工作

僵尸进程: 进程已经终止，但是父进程还未回收其状态信息

exec

将当前进程的地址空间替换为新的程序，但保留当前进程的pid

与fork配合使用，可以在子进程中运行一个新的程序

fork

fork的作用是在当前进程下，创建一个新的进程，通常把这两个进程称为父进程和子进程，子进程的内存是复制父进程的，它们有独立的内存空间，fork在父进程中返回的值为子进程的pid，在子进程中返回的值为0,这就是为什么pid == 0可以判断它是子进程

1
2
3
4
5
6
7
int pid;
pid = fork();
if (pid == 0) {
  std::cout << "this is child process" << std::endl;
} else {
  std::cout << "this is parent process" << std::endl;
}

通过fork实现父子进程之间的读和写

read(fd[0], buf, sizeof(buf));

write(fd[1], buf, sizeof(buf));

注意：默认情况下读用0，写用1，管道是单方向的，要实现两端的读和写需要两个管道，buf是指向缓冲区的指针

wait

用于让父进程等待子进程结束的系统调用

xargs

xargs的作用是读取标准输入，将其作为后面命令的参数

1
echo hello |xargs echo bye

上述命令的输出为bye hello

发表于 更新于 分类于

进入insert模式

1
2
3
4
i: 在光标的位置插入
a: 在光标后的位置插入
o: 在当前的下一行插入 
O：在当前的上一行插入

在insert模式下

1
2
3
ctrl + h: 删除光标前面的字符 
ctrl + w: 删除光标前面的单词
ctrl + u: 删除光标前面的本行所有内容

在normal模式下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
w: 移动到下一个单词的开头
e: 移动到下一个单词的结尾
b: 移动到上一个单词的开头
f{char}: 移动到char上
0: 移动到行首
$: 移动到行尾
gg: 移动到文件开头
G: 移动到文件结尾
ctrl + o: 快速返回
ngg: 跳转到第n行
x: 删除光标后的第一个字符
daw: 删除光标所在的单词
dw: 删除光标后面的单词
diw: 删除光标所在的单词
dt{char}: 删除从光标到char的所有内容
1
2
3
gt：在vim不同标签之间切换
ctrl + shift + t：新建终端标签页
alt + 1/2/3/4：切换标签页

发表于 更新于 分类于

概述

host

1
与网络相连的计算机常成为主机，也叫端系统

互联网的组成

1
1、边缘部分：由所有连接在互联网上的主机组成，这部分是用户直接使用，用来进行通信（传送数据、音ping）