笔记

leetcode热题与code top题解

二叉树一个节点有两个后驱节点，基本上二叉树的问题可以通过递归解决二叉搜索树左节点

从一个数组里面取元素返回链表，如果数组是空返回空指针，不带头节点的，意味着第一个元素需要放到head指针里面去，然后从第二个元素开始放到链表尾，不断更新链表尾。访问链表，如果链表是空的直接返回，输出当前节点的值，更新当前节点。

启动三个线程分别打印1、2、3，要求按照123123123123……的顺序打印出来，使用互斥锁实现。

启动三个协程分别打印1、2、3，要求按照123123123123……的顺序打印出来，可以使用锁或者通道实现。也可以用通道实现，channel分为有缓冲和无缓冲，内部封装了锁，读写通道是原子性的；有缓冲通道：发送会在缓冲区未满时不阻塞，在缓冲区满时阻塞。无缓冲通道 ：发送和接收都会阻塞，直到被接收或者通道有值。

32位和64位表示的是CPU的架构，32位和64位具体指的是CPU寄存器的大小（bit）、数据总线的长度（bit）、内存地址的长度（bit），由此带来32位的寻址空间只有2^32字节≈4GB。与CPU架构对应的有32位操作系统和64位操作系统，一般64位的操作系统可以运行32位的应用程序，反之则不行。与此对应的数据类型长度问题，32位机器的类型一般是32位的，如普通整型、浮点型。在一些编程语言当中，uint、int的长度是随系统变化的。

适用场景：适合于存储摄影图片和复杂的图像，例如自然风景和人像，通常用于网页、社交媒体和数字摄影。适用场景：主要用于Windows系统的图像处理，适合需要高质量的图像。特点：支持动画和透明背景，采用无损压缩，但颜色限制在256种。特点：支持多种色彩空间，适合高质量图像存储，可以是无损或有损。特点：谷歌开发的格式，支持有损和无损压缩，支持透明度和动画。适用场景：优化网页图像，减小文件大小，同时保持质量。特点：一种新型图像格式，提供更好的压缩比和图像质量。特点：一种无损格式，存储每个像素的数据，不压缩。

用stringstream将字符串变成流，然后用getline从流中读取字符串直到遇到逗号或者回车，再将字符串变成数字即可。假设字符串中数字是以逗号隔开的：1，2，3，4，5，6，7，8。

IO 多路复用是一种同步IO模型，一个线程可以监视多个文件句柄，一旦某个文件句柄就绪，就能够通知应用程序进行相应的读写操作，没有文件句柄就绪就会阻塞应用程序交出CPU无需为每个IO操作创建一个线程或进程，没有线程切换的开销。

此时这两个share指针的引用计数都是2，当node超过生命周期被析构时，node的引用计数变成1，不为0，那么node指向的类实例不会被析构，注意智能指针也是一个类，智能指针的析构和它指向的类实例的析构是两回事，程序中Node实例没有被析构导致p也不会析构。定义一个类，这个类有一个share指针变量，创建一个share指针指向这个类实例，然后将类实例的成员变量share指针也指向这个类实例。用weak指针解决循环引用问题，weak只引用资源不增加资源引用的计数。

实现堆关键在于堆调整，堆有向上调整和向下调整，当pop堆顶元素的时候是弹出数组里面最小的元素，这个时候需要向下调整堆，把堆顶元素的值更新为数组末尾元素的值，然后从堆顶开始向下调整堆。从树根节点开始，找出左右子树中比自己更小的节点，交换值，然后从交换后的节点处继续往下寻找更小的节点，直到堆末尾或者没有更小的。向上调整堆先找出当前节点的父节点，如果父节点是更大的节点，那么交换值后往上走，继续向上寻找更大的节点。push元素的时候先放到数组末尾，然后看看容量是不是满了，增长一下容量，开始从数组末尾向上调整堆。

队列用链表实现很简单，记住链表头和链表尾就行了，每次push就往头插入，每次pop就删掉尾巴。我们这里用数组实现一下队列，基本思想是一个循环滑动的窗口，用两个变量记录队首和队尾索引。这里比较难的是队列容量的动态增长，申请两倍的容量后，从队首索引开始拷贝。push放到队尾，pop放到队首，队尾索引和队首索引都需要循环。

为了栈容量动态增长，写一个成长函数，将容量翻倍，即申请一块新内存，将原来元素拷贝过去，释放掉原来的空间。这里用数组实现，需要三个成员变量，分别记录栈容量、栈顶索引（栈元素数量）、数组首地址。push的时候直接放到栈顶位置，然后栈顶移动，判断元素是否满了，满了就增长栈容量。pop的时候先看看栈是不是空的，不是空的就移动栈顶，返回栈顶元素。链表实现的话，push就往头节点插入，pop就删除头节点。如此一来top实际上是栈元素的个数。栈的实现可以用链表或者数组实现。

设置两个全局变量当作线程共享资源，为了让两个线程分别持有一个资源让它们抢到一个资源后睡一会让另一个抢。最简单的死锁，线程x持有资源a请求资源b，线程y持有资源b请求资源a，死锁了。等同于这个代码，刚刚的代码相当于实现了一个自旋锁，下面这个是互斥锁。死锁就是多个进程或者线程竞争临界资源所造成的僵局。只需要把它们请求资源的顺序改成相同就不会死锁了。

dd可以删除整行，把整个配置文件的内容全部删掉，你也可以在删除之前备份一下，然后把刚刚copy的配置内容复制到这里来。根据发行版本找到对应的配置文件copy起来。查看发行版本，记下来。

定位到xv6目录下的kernel.ld的第25行。.stab:{ 修改成。

使用两个循环指针用来实现环形队列，头指针和尾指针在队列为空的时候是相同的，起始为0，当头指针快追上尾指针的时候代表队列已满，也就是head=tail-1的时候，这意味着我们使用了一个元素的位置来表示队列是否满，环形buffer实际容量为数组长度减去一个单位。环形缓冲区由一个固定大小的数组构成，生产者将数据写入缓冲区的尾部，而消费者则从缓冲区的头部读取数据，当缓冲区被填满时，生产者会等待，直到有空间可用；生产即入队，元素安排在头指针处，之后头指针移动，消费即出队，取尾指针处元素后移动尾指针。

快速排序基本思想是寻找一个元素作为基准，将其他元素划分为两部分，其中一部分比基准元素小，另一部分比基准元素大，然后如此继续对这两部分操作下去快速排序最简单的实现就是通过简单的递归，实现方式之一是使用双指针，两个指针同时走，左指针找到大的，右指针找到小的，然后交换这两个元素的位置，问题在于枢纽元素和谁交换，让右指针先走，两个指针走到相同位置的时候必然是右指针走到左指针的地方了，而左指针指向的元素是刚刚交换完比枢纽元素小的，而枢纽元素选的是第一个，因此它们进行位置交换就是正确的这里给出C版本，C++版本一般是将

括号离不开栈，栈可以消除有效的括号，先用栈将左括号装起来，遇到右括号并且栈非空就弹栈，如果遇到右括号栈空就计数，说明需要插入左括号，完事之后栈里面的元素就都是左括号，都计数，因为都需要加上右括号。对于一个只有（）组合的括号字符串，如果想要这个字符串是有效的括号对，找出最少需要插入多少个括号。

先关闭所有wsl终端，远程连接开发的IDE也需要关闭，因为工具链开着给你wsl没有完全关闭，在Windows的power shell终端命令行窗口可以实验以下命令检查是否wsl已经关闭。然后文件内容复制下面信息，CPU核数为processors，修改即可，在确认所有Linux子系统已经关闭的情况下，保存文件重启wsl即可。创建文件C:\Users\\.wslconfig，目录必须对，例如C:\Users\Yezi。查看LinuxCPU核数。