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

##WeChat Live Coding

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

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

###思路

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

superlayone

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

###思路

递归构造

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

###Code

superlayone

##LIS变种

从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）

###思路

• 双 LIS 问题，用DP可解，目标规划函数 max{ l[i] + r[i]}, 其中

superlayone

##Top K 问题

###Methods

• Top K问题可以维护一个堆，以O(n*logk)的复杂度完成
• Top K问题可以用类似于快排Partition的过程递归的解决
• Top K问题使用STL nth_element解决（大幅缩减代码）

###Complexity

superlayone

##Longest Increasing Subsequence

之前的一篇GIST其实已经解决了这个问题，只不过现在使用STL技术更加优雅地写出来了

这个问题可以用DP解决，如果定义

dp[i] = 以ai为结尾的最长上升子序列的长度

那么转移方程

dp[i] = max{1,dp[j]+1 | j < i and aj < ai}

superlayone

##Longest Common Subsequence

动态规划

设序列X= < x1, x2, …, xm > 和 Y= < y1, y2, …, yn > 的一个最长公共子序列Z= < z1, z2, …, zk >，则：

• 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列
• 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列
• 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列

superlayone

POJ 1664 & HUAWEI 2014-07-06 Test

##Description

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

superlayone

##Combination and Permutation

基于递归的思路

    #include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;