baozi's page
0%

发表于 更新于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
server {
        listen 8080;

        location /foo {
            echo "foo = [$foo]";
        }

        location /bar {
            set $foo 32;
            echo "foo = [$foo]";
        }
   }
$ curl 'http://localhost:8080/foo'
foo = []

$ curl 'http://localhost:8080/bar'
foo = [32]

$ curl 'http://localhost:8080/foo'
foo = []

Nginx 变量一旦创建，其变量名的可见范围就是整个 Nginx 配置，甚至可以跨越不同虚拟主机的 server 配置块，但是赋值操作在bar中实现，foo中的foo为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
server {
    listen 80;
    server_name www.example.com;

    location /api/ {
        proxy_pass http://backend_api;
    }

    location /static/ {
        root /var/www/html;
    }

    location /admin {
        return 403;
    }
}
# server的作用是匹配域名和端口号，location的作用是匹配路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
map $args $foo {
        default     0;
        debug       1;
}
# map为映射，args为自变量，foo为因变量，第一列为args的值，第二列卫foo对应的值，default类似于switch case中的default，当其他条件都不满足时，foo为0
# 注意： map不能在server中，与server是并列关系
server {
        listen 8080;

        location /test {
            set $orig_foo $foo;
            set $args debug;

            echo "original foo: $orig_foo";
            echo "foo: $foo";
        }
}
# $ curl 'http://localhost:8080/test'
#   original foo: 0
#   foo: 0
# 原因：$foo 变量在第一次读取时，根据映射规则计算出的值被缓存住了
1
2
3
4
5
6
7
8
9
# nginx有11个阶段 postread -> server_rewrite -> find_config -> rewrite -> post_rewrite -> preaccess -> access -> postaccess -> precontent -> content -> log
location /test {
  set $a 32;
  echo $a;
  set $a 50;
  echo $a;
}
# 输出结果为 50 50 
# set输入rewrite；echo属于content，所有set都在echo之前执行

发表于 更新于 
1
2
print("2" + 8)
-- 输出结果为10， 类型为number，lua中只有number这一种数字类型
1
2
3
-- 字符串连接
str = 123 .. 456
-- 输出结果为123456，类型为string
1
2
3
-- 获取字符串长度
str = "this is a test."
print(type(str))
1
2
local x = 10	-- 局部变量
x = 10 -- 全局变量
1
2
3
4
5
6
7
8
9
10
11
-- lua中的函数可以当作变量
function factorial1(n) 
  if n == 0 then
    return 0
  else 
    return n * factorial1(n - 1)
  end
end
print(factorial1(10))
factorial2 = factorial1;
print(factorial2(10))
1
2
-- if ip is true return ip, if ip is nil return "unknow"
return ip or unknow

lua的八种数据类型

nil：空类型
boolean
number:整数和浮点数都用number表示
string：可以有三种表示方式

1
2
3
4
5
6
7
8
str1 = 'this is test1'
str2 = "this ia test2"
-- 第三种方式可以换行
str3 = [[
    this
    is
    test3
]]

function：function表示lua中的函数，可以接受多个参数，也可以用...表示可变数目的参数，function可以返回多个参数
userdata：用户自定义数据
thread – todo
table 相当于数组，下标从1开始，里面的元素可以是各种类型的，函数也可以作为元素

1
2
3
4
5
tb = { 
        function() return '123' end,
        fucntion() print("abc) end,
        function(a, b) return a + b end,
    }

table还可以当作哈希表

1
2
3
4
5
6
7
8
tb = {
    apple = 3,
    banana = 4,
    ["tt"] = 5,
}
print(tb["apple"])
print(tb.banana)
print(tb.["tt"])

发表于 更新于

1 view c++ as a federation of languages

c

pass by value比pass by reference更高效，c中的引用实质上还是指针

object-oriented c++

有构造函数和析构函数存在，传值会调用拷贝构造函数和析构函数

template c++

pass by reference 更高效，在使用模版时，并不知道是什么类型，使用reference不用拷贝

pass by reference-to-const

STL

2 prefer const enum inline to define

1
2
#define PI 3.14
const pi =3.142

const 比define更好

1
2
3
4
5
class foo{
  private:
  	static const int num = 5;
  	int score[num];
}

num是类中的专属常量，如果在类外取它的地址的话，需要在类外给出定义式

1
const int foo::num;
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>

class foo {
public:
    static const int num;
};
const int foo::num = 5;
int main() {
    const int* p = &foo::num;
    std::cout << *p << std::endl;
}

如果不在类外给出定义式，在类外访问num的地址会出现错误，原因是并没有给num分配内存

1
2
3
4
class foo {
public:
    static const int num = 9;
};

也没分配地址，所以要在外面给出定义式，在类中仅仅只是声明式

1
2
3
4
5
6
7
8
class foo {
public:
    static const int num = 5;
};

int main() {
    std::cout << foo::num << std::endl;
}

像这样，虽然能够输出num的值，但是并没有给num分配内存，仅仅只是替换成5

也可以这样写

1
2
3
4
5
class foo{
  private:
  	enum {num = 5};
  	int score[num];
}

使用inline替换’#define’

3 use const whenever possible

发表于 更新于 分类于

查看当前分支

git branch -- show-current

回退到上一个版本

1
git reset --hard HEAD~1

删除文件

1
git rm filename

删除分支

1
git branch -d branch_name

创建新分支

1
2
git checkout -b branch_name
git switch -c branch_name

回退到clone后的版本

1
git restore .

发表于 更新于 分类于 
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

wsl中出现AddressSanitizer:DEADLYSIGNAL

1
echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

发表于 更新于 分类于

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

const int 必须用const int * p来指向

int* const p必须初始化

顶层const(top-level const)表示指针本身是一个常量，底层const(low-level const)表示指针所指的对象是一个常量，更一般的，顶层const可以表示任意的对象是常量

constexpr修饰指针，constexpr仅对指针有效

函数体外定义的变量存放在固定地址，函数体外的变量则不是，constexpr指针和引用只能用于函数体外的变量

constexpr

常量表达式(const expression)是指值不会改变并且在编译阶段就会得到计算结果的表达式

将变量声明为constexpr类型，由编译器来验证变量的值是否为常量表达式

自定义类、IO库、string类型不能被定义为constexpr

1
2
3
constexpr std::string str = "abc";
std::cout << str << std::endl;
// error: constexpr variable cannot have non-literal type 'const std::string' (aka 'const basic_string<char>')

constexpr指针初值必须是nullptr或0

1
2
3
4
int num = 20;
constexpr int* p = &num;
std::cout << *p << std::endl;
// error: constexpr variable 'p' must be initialized by a constant expression

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
20
21
22
23
24
25
// 声明
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;
}
// 清除特定元素
umap.erase(target);
// 在滑动窗口题目中可以这样使用
if (--cnt[nums[i - k + 1]] == 0) {
	cnt.erase(nums[i - k + 1]);
 }

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[]在栈上分配内存

lambda函数

1
2
[capture list] (parameter list) -> return type { function body }

capture list 表示获取列表用于表示lambda可以访问的外部变量

paramete list表示lambda的参数

return type表示返回类型

`function body 表示函数体

值捕获

1
2
3
4
int x = 10;
auto f  = [x] (int y) -> int {return x + y;};
x = 20;
cout << f(5) << endl;	//15

引用捕获

1
2
3
4
int x = 10;
auto f = [&x] (int y ) -> int {return x + y;};
x = 20;
cout << f(5) << endl;	//25

类型别名

typedef

1
2
typedef double wages;	// wages是double的同义词
typedef wages base, *p;	//base是double的同义词，p是double*的同义词

using

1
using SI = Sales_item;

explicit

防止隐式类型转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MyClass {
  public:
  	MyClass(int x){}
}
void doSomething(MyClass obj) {
  
}
int main() {
  dosomething(5);	// 合法，但是隐式构造了一个MyClass(5);
}

// 有explicit
class MyClass {
  public:
  	explicit MyClass(int x){}
}
void doSomething(MyClass obj) {
  
}
int main() {
  dosomething(5);	// 编译错误
  dosomething(MyClass(5));	// 正确
}

string_view

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

// 它是对字符串的一个视图，指向一段连续的字符序列，但不拥有数据。类似于一个只读的“窗口”
void print(std::string_view sv) {
    std::cout << "String view: " << sv << '\n';
}

类型转换

static_cast

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

using namespace std;

int main() {
	int num = 97;
	char ch = static_cast<char>(num);
	cout << ch << endl;	// a
}

static_cast用法，static_cast<要转换的类型>（变量）

dynamic_cast

  1. 上行转换，从子类转换成父类
  2. 下行转换，从父类转换成子类， 且要求父类中至少有一个虚函数

const_cast

  1. 移除const修饰符
  2. 添加const修饰符

reinterpret_cast

  1. 指针类型的转换
  2. 指针和整数之间的转换
  3. 非相关类型的转换

数组指针 todo，primer6.3

数组不能被拷贝，所以在函数中无法返回数组，但是可以返回数组的指针或引用
在写一个返回数组指针的函数时，可以用别名来声明

1
2
3
4
typedef int arrT[10];   // 为int[10]起一个别名
using arrT = int[10];   // 等价上面
// 有了别名，可以定义返回数组指针的函数了
arrT* function(int n);  //接受一个int类型的参数，返回一个指向包含十个int数组的指针

如果不想使用别名来声明函数，需要了解下面三个的区别

1
2
3
int *arr[5] = {1, 2, 3, 4, 5};  // 声明了一个大小为5的数组
int *p1[5]; // 声明了一个包含5个指针的数组，它是一个指针数组，数组元素是指针
int (*p2)[5] = &arr;    // 声明了一个指针，它指向arr

deep copy and shallow copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Person {
private:
    int age_;
    string name_;
public:
    Person(int age, string name) : age_(age), name_(name);
    // 拷贝构造函数
    Person(const Person& person);
   
}
Person::Person(const Person& person) {
    age_ = person.age_;
    name_ = person.name_;
}

对于基本数据类型，浅复制可以实现，但是当类中有引用或者指针时，就需要用到深复制
在写拷贝构造函数的时候，必须将参数写成引用，一是引用可以避免拷贝，二是c++语法要求，否则，在传参的时候就会调用拷贝构造函数，进入无限循环
而且最好写成const类型，这样非const类型也可以传入

rvalue

int a = 5在这句代码中，a表示左值(lvalue)，5表示右值(rvalue)，左值表示在内存中可以找到它，右值在内存中找不到，
右值是一个立即数(immediate number)，

1
2
3
4
int a = 20; // correct, a is a lvalue
20 = 30;    // incorrect, 20 is a rvalue
int &lref = a; // 左值引用
int &&rref = 20;    //右值引用

在写函数的参数时，最好将参数定义为const引用类型，首先可以保证函数内部不会对参数做出修改，而且引用不会进行拷贝操作；其次，const引用可以传入右值引用，而非const的左值引用只能传入左值。例如，当传入的参数为具体的数字的时候，此时参数为右值，如果函数参数定义为const引用，可以传入，否则会出错