shihongzhi

//http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
//shihongzhi --2012.3.7

#include <stdio.h>

int M[100];  //相应长度的最长子序列结尾值的下标，且此结尾值为最小值的情况  M[0]没有存东西，在这里没有意义
int P[100];  //最长子序列的index索引

//时间复杂度为O(nlogk)  
int LIS(int *X, int n)

shihongzhi

//http://poj.org/problem?id=1050
//http://poj.org/problem?id=2479
//shihongzhi --2012.3.8

#include <stdio.h>

int maxSubarray(int *A, int n)
{
	int max = 0;
	int sum = 0;

shihongzhi

//http://poj.org/problem?id=1458
//http://poj.org/problem?id=1159  利用了滚动数组，要不然会内存溢出
//http://poj.org/problem?id=2250  需要打印，用一个数组记录path状态
//shihongzhi ---2012.3.8
#include <stdio.h>

int dp[100][100];

int LCS(char *a, char *b, int aLen, int bLen)
{

shihongzhi

//shihongzhi  -- 2012.3.9
#include <stdio.h>
#include <string.h>

void KMP(char *T, char *P, int *pi)
{
	int tLen = strlen(T);
	int pLen = strlen(P);
	int k = 0;
	for (int i=0; i<tLen; ++i)

shihongzhi

#include <sys/time.h>                // for gettimeofday()

class StopWatch {
  timeval     started;
  std::string msg;
  
public:
  StopWatch(const std::string& m): msg(m)
    { gettimeofday(&started, NULL); }

shihongzhi

//google的一道面试题，可以考虑用vector替换deque
#ifndef MIN_STACK_H
#define MIN_STACK_H

#include <vector>       //for vector
#include <utility>     //for pair
#include <functional>  //for std::less<T>
#include <limits>

template<typename T, typename Comparator = std::less<T> >

shihongzhi

//通过minStack.h来实现最小队列，使用两个minStack，来模拟minQueue
//当然可以直接实现minQueue，而非借助minStack
#ifndef MIN_QUEUE_H
#define MIN_QUEUE_H

#include "minStack.h"    //see https://gist.github.com/2213736
#include <functional>

//use two stack: new and old to simulate min_queue
template<typename T, typename Comparator=std::less<T> >

shihongzhi

    template <typename T> 
    class cSingleton
	{
		static T* ms_Singleton;

	public:
		cSingleton( void )
		{
			assert( !ms_Singleton );
			int offset = (int)(T*)1 - (int)(cSingleton <T>*)(T*)1;  //这里的offset主要处理多重继承，及虚继承的情况地址的偏移量

shihongzhi

#ifndef BOUNDED_PRIORITY_QUEUE_H
#define BOUNDED_PRIORITY_QUEUE_H

#include <map>
#include <functional>
#include <limits>
#include <utility>

template<typename T, typename Comparator=std::less<T> >
class BoundedPQueue{

shihongzhi

#ifndef BOUNDED_PRIORITY_QUEUE_H
#define BOUNDED_PRIORITY_QUEUE_H

#include <map>
#include <functional>
#include <limits>
#include <utility>

template<typename T, typename Comparator=std::less<T> >
class BoundedPQueue{