作者：siukwan

主要原因是加入了中文注释，需要在文件第一行加入：

#encoding: utf-8

pi = new (ptr) int; //placement new

括号里的参数ptr是一个指针，它指向一个内存缓冲器，placement new将在这个缓冲器上分配一个对象。Placement new的返回值是这个被构造对象的地址(比如括号中的传递参数)。placement new主要适用于：在对时间要求非常高的应用程序中，因为这些程序分配的时间是确定的；长时间运行而不被打断的程序；以及执行一个垃圾收集器 (garbage collector)。

简单来说，placement new是创建对象（即调用对象的构造函数），但是不分配内存，使用了现有的内存。

1.如果对象是无析构函数，或者类型是基本的数据类型，new出来的一个数组，使用delete p和delete[]p没有区别。

2.如果new出来的对象具有析构哈书，使用delete p只会调用p[0]的析构函数，而其余的均不会调用，可能会造成内存泄漏。

之前的快排采用了一个指针和for循环，这次使用的是双指针，相对比较正规，不过这次是使用快排来实现寻找第k小的数，去掉quickSort里面的判断，可以实现快排。

原来的代码：快排（一）

int partition(vector<int>&arr, int l, int r)
{
	int pivot = arr[l];
	int i = l + 1;
	int j = r;

	while (i <= j)
	{
		while (i <= j&&arr[i] <= pivot)
			i++;
		while (i <= j&&arr[j] >= pivot)
			j--;
		if (i <= j)
			swap(arr[i], arr[j]);
	}
	swap(arr[j], arr[l]);
	return j;
}

void quickSort(vector<int>&arr, int l, int r,int idx,int&target)
{
	if (l > r) return;
	int k = partition(arr, l, r);
	if (k == idx)
	{
		target = arr[k];
		return;
	}
	else if (k < idx)
		quickSort(arr, k + 1, r, idx, target);
	else
		quickSort(arr, l, k - 1, idx, target);
}

 

非递归方法参考：206. Reverse Linked List（只需新建两个指针，借用传入的head指针，共使用三个指针）

递归实现代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        
        ListNode* tmp=reverseList(head->next);//把head->next后面的链表翻转
        head->next->next=head;//翻转后的链表，head->next是尾节点，把head连接到尾部
        head->next=NULL;//因为head是尾部，所以指向NULL
        return tmp;
    }
};

 

1.内核中使用双向循环链表来组织进程描述符（task_struct），进程描述符即我们操作系统中学习的进程控制块PCB，进程描述符里面包含进程的基本信息（thread_info），所接收的信号（signal_struct），进程号，父进程指针等。

2.由于在某些情况下，内核必须能从进程的PID到处对应的进程描述符指针，如kill系统调用从P1进程向P2发送信号，需要从P2的进程描述符中取出记录挂起信号的数据结构指针。所以引入了4个散列表，分别是PIDTYPE_PID（进程的PID），PIDTYPE_TGID（线程组领头进程），PIDTYPE_PGID（进程组领头进程的PID），PIDTYPE_SID（会话领头进程的PID），使用双向链表来解决冲突。

3.进程调度：采用CFS：完全公平调度算法。该算法有两个特点：（1）设有最小时间颗粒，即最低的CPU占用时间（如1ms），避免频繁的切换进程造成上下文切换的浪费；（2）按照nice的相对值来分配时间，而不是绝对值，如nice值为20和0的两个进程分配的时间为5ms和15ms，而nice值为1和0的两个进程分配的时间仍为5ms和15ms。

4.信号在内核中是如何发送传递的？

向某个进程a发送信号，会在a的进程描述符中信号相关变量设置，相关的有共享挂起信号队列，有私有挂起信号队列，向某个进程组发送的信号，会挂在共享挂起信号队列中，向单独一个进行发送的信号，会挂在私有挂起信号队列中。相应的进程在从内核态转到用户态时，会先处理可以处理的信号（没有阻塞的信号），然后再回到用户态。

5.init进程的pid号为1，内核中有pid为0的swapper进程，它只有在CPU不能执行其他进程时才执行。

6.Linux下如何进行进程调度？

对于普通进程，采用CFS(完全公平调度)算法，CFS使用红黑树组织可运行进程队列。

对于实时进程，有两种调度方法，分别是SCHED_FIFO和SCHED_RR，FIFO是简单的先入先出调度算法，不适用时间片。而SCHED_RR则是带有时间片的SCHED_FIFO，任务好紧它的时间片时，同一优先级的其他实时进程被轮流调度。

方法一：相当于头插法，不断地把后面的节点插入到头部的next位置，思路是先反转头结点后面的节点，最后再把头结点添加到末尾。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        
        ListNode* first=head->next;//第一个翻转的节点
        ListNode* tmp;//过度节点
        
        while(first->next)
        {
            tmp=first->next;
            first->next=tmp->next;
            tmp->next=head->next;
            head->next=tmp;
        }
        
        //这个时候first为现在最后的节点，head->next为元链表最后的节点
        tmp=head->next;
        head->next=NULL;
        first->next=head;
        return tmp;
    }
};

方法二：就地翻转

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //就地反转
        if(head==NULL || head->next==NULL) return head;
        
        ListNode* pre=NULL;
        ListNode* next=NULL;
        
        while(head)
        {
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        
        return pre;
    }
};