superlayone

###利用康托展开求第K个全排列

• 利用康托编码的思路，假设有 n 个不重复的元素，第 k 个排列是 a1,a2,a3,...,an

• 那么我们把 a1 去掉，那么剩下的排列为 a2,a3,...,an,共计 n−1 个元素，n−1 个元素共有 (n−1)! 个排列

• 于是就可以知道

               a1 = k/(n−1)!
               
               
               k2 = k%(n−1)! 
  

superlayone

###Merge sort

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    void merge(vector<int>& array,int left,int pivot,int right){
    	int leftLen = pivot - left + 1;

superlayone

###并查集

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。 假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

    int uset[10001];
    
    int find(int x){
 if (x != uset[x]){

superlayone

###auto_ptr的实现

    
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    template<class T>

superlayone

##Heap sort

• Using template
• Using functional
• Using vector

        #include <iostream>
        #include <vector>
        #include <algorithm>

superlayone

###Return value optimization

我们知道，在函数内如果需要以value方式返回对象，那么需要生成临时匿名对象，然后以这个临时对象去通过copy构造函数生成新的对象，最后调用析构函数销毁对象

    A method(){
        ...
        A temp;
        ...
        return temp;
    }

superlayone

##Struct traits

在《Inside The C++ Object Model》这本书中有一个例子很有趣，就是在struct中放置一个一个元素的char数组,在运行时动态的构造可变长数组，如下：

    struct mumble{
    	/*stuff*/
    	char pc[1];
    };
    typedef struct mumble* mumble_ptr;
 mumble_ptr resize_mum_t(int size){

superlayone

###Pointer to pointer

在删除链表的节点的时候，需要考虑是否删除的是头节点的问题，要保存前驱结点的信息，今天看到了一个巧妙地用法，利用二级指针

Code

    /*
    struct ListNode{
    	int val;
 ListNode* next;

superlayone

概率问题

• 由非等概率Rand生成随机序列

题目：已知随机函数rand(),以p的概率产生0，以1-p的概率产生1，现在要求设计一个新的随机函数Rand(), 使其以1/n的等概率产生1~n之间的任意一个数

1、该问题可以先生成一个等概率0、1生成器。由于以p的概率产生0，以1-p的概率产生1，所以00、01、10、11的生成概率分别是p^2、p(1-p)、p(1-p)和(1-p)^2，我们发现生成01和10的概率是一样的，所以我们可以标记这两个序列构造0、1等概率生成器

    int gen(){
 int i1 = rand();

superlayone

###Reverse list

反转list，使用递归方式

![][1]

如图所示，h为已经经过递归反转过的链表头，在递归之前保存的q指针已经是反转之后的尾指针，修改p指针为新的尾节点，返回h节点

###Code