superlayone

##构造n对括号的全部有效组合

###思路

递归构造

• 左括号：只要还有左括号，则加入
• 右括号：只要右括号比左括号剩余的还多，则不构成非法，加入

###Code

superlayone

##WeChat Live Coding

实验室人的TST计划——微信面试题，一个小时内做出如下5道题，在collabedit上在线coding

拿来学习一下。。。啦啦啦啦啦啦

###思路

• 1、哈希表
• 2、递归解决，按照中序遍历的反方向查找

superlayone

##Sort

• 算法导论版本

从左开始与pivot比较，左边始终是<=pivot的元素，使用随机化pivot版本

    int partition(int arr[], int begin, int end){
    	int pivot_index = rand() % (end - begin + 1) + begin;
    	swap(arr[pivot_index],arr[end]);
    	int pivot = arr[end];

superlayone

###Reverse list

反转list，使用递归方式

![][1]

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

###Code

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

###Pointer to pointer

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

Code

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

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

###Return value optimization

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

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

superlayone

##Heap sort

• Using template
• Using functional
• Using vector

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

superlayone

###auto_ptr的实现

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