superlayone

##++前置和++后置

在对操作符++进行重载的时候有两个

    //前置
    Object operator ++();
    //后置
    Object operator ++(int);

其实，前置和后置是有着效率上的差别的，STL中类类型迭代中有很多的前置操作

superlayone

##赋值运算操作符

为如下类型添加赋值运算。

    class MyString
    {
    public:
        MyString(char* pData = NULL);
        MyString(const MyString str);
        ~MyString();

superlayone

##strcpy & memcpy

这两个库函数的实现应该算是比较简单的，但是竟然看到了很多不正确的版本，其实只要注意以下几点就OK了

1. 参数判断
2. 返回指针临时保存
3. 地址重叠判断
4. '\0'复制

 char* MemCpy(char* dst, const char* src, int len){

superlayone

#N Queens

##DFS

N皇后非常经典，传统的DFS在N非常大的时候会TLE，DFS代码如下：

    void placeQueens(int currentRow, int n, vector<int>& place, int& result)
    {
    	if(currentRow == n)
 {

superlayone

##Combination and Permutation

基于递归的思路

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

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

##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

##Longest Increasing Subsequence

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

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

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

那么转移方程

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

superlayone

##Top K 问题

###Methods

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

###Complexity

superlayone

##LIS变种

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

###思路

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