C++的观察者模式

观察者模式主要使用到了函数指针,类似的结构在linux内核中比较常见。

//C++实现观察者模式

#include<vector>
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;

template <class Handler>
class event //模板类,这就决定了这个委托可以委托任何类型了函数指针,只要你有,我就能委托  
{
public:
	event()
	{//构造函数
	}
	vector<Handler>& GetEvent()
	{//获取Event列表
		return m_HandlerList;
	}
	virtual void add(const Handler v)
	{//虚函数,添加时间到vector中
		m_HandlerList.push_back(v);
	}
	virtual void remove(const Handler v)
	{//删除vector
		vector<Handler>::iterator it = m_HandlerList.begin();
		for (; it != m_HandlerList.end(); it++)
		{
			if ((*it) == v)
			{//如果相等,则删除
				m_HandlerList.erase(it);
				break;
			}
		}
	}
private:
	vector<Handler> m_HandlerList;//时间列表
};

//参数列表为空,EventHandler是函数地址
typedef void   (*EventHandler)(void);
class MyClass
{
public:
	MyClass(){}
	void Notify()
	{
		size_t nCount = AllEvent.GetEvent().size();
		for (size_t i = 0; i < nCount; i++)
		{
			EventHandler notifyEvent = AllEvent.GetEvent()[i];
			(*notifyEvent)();

			//另外的两种写法
			//(*(AllEvent.GetEvent().at(i)))();
			//(*(AllEvent.GetEvent()[i]))();
		}
	}
public:
	event <EventHandler> AllEvent;
};


void MyEventHandler1()
{
	printf("This is a event!\n");
}
void MyEventHandler2()
{
	printf("This is another event!\n");
}

int main(void)
{

	MyClass Obj;
	Obj.AllEvent.add(MyEventHandler1);
	Obj.AllEvent.add(MyEventHandler2);
	Obj.Notify();
	Obj.AllEvent.remove(MyEventHandler1);
	Obj.Notify();
	printf("Over!\n");
	system("pause");
	return 0;


}

 

C++中的单例模式

注意C++的单例模式,其static成员需要在外部进行初始化。


//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<bitset>
using namespace std;

class Singleton
{

public:
	static Singleton* GetInstance()
	{
		if (instance == NULL)
			instance = new Singleton();

		return instance;
	}

private:
	Singleton(){};
	static Singleton* instance;
};
//C++单例模式需要先创建instance
//Singleton* Singleton::instance = new Singleton();
Singleton* Singleton::instance = 0;
int main(void)
{
	Singleton*s1 = Singleton::GetInstance();
	Singleton*s2 = Singleton::GetInstance();

	if (s1 == s2)
		cout << "it's same!" << endl;
	return 0;


}

284. Peeking Iterator

1.题目要求实现一个窥探的功能,正常的迭代器,可以输出当前值和使用next指向下一个值。而题目要求我们输出下一个值,但是不移动指针。

2.当使用peek时,利用this指针重建了一个迭代器,在这个这个新的迭代器中执行next操作并返回值,即可不影响原来的迭代器。

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().


Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

AC代码:

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
	Data* data;
public:
	Iterator(const vector<int>& nums);
	Iterator(const Iterator& iter);
	virtual ~Iterator();
	// Returns the next element in the iteration.
	int next();
	// Returns true if the iteration has more elements.
	bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
	    
	}
    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        if(hasNext())
        {
            Iterator same(*this);//复制一个迭代器
                return same.next();//输入这个迭代器的下一个值
        }
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
        return Iterator::next();
	}

	bool hasNext() const {
        return Iterator::hasNext();
	}
};

 

315. Count of Smaller Numbers After Self(方法二:使用MergeSort)

使用树状数组求解:http://maybi.cn/wp_siukwan/?p=850

1.这道题目跟求逆序对的题目类似,但是求逆序对的题目只需要求出总的逆序对数量即可,而这道题目要求求出每个数的右边比它小的数的个数。

2.按照逆序对的思想去编写的时候会发现,mergeSort中会有一个交换赋值的过程,导致我们不能简单的使用用一个数组根据下标去记录当前数的右边比它小的数的个数,因为这个数排序后,不在原下标位置。

3.所以需要设计一个数据结构,这个数据结构记录了原始数组的val,原始数组的idx,以及所求值cnt,然后对这个新的数据结构数组进行mergeSort,同时进行统计。除去复制和复制的O(n)时间复杂度,剩下的就是MergeSort的时间复杂度O(nlogn),所以时间复杂度为O(nlogn),空间复杂度为O(n)。

AC代码:

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<node> num(nums.size());
        for(int i=0;i<nums.size();++i)
        {
            num[i].idx=i;
            num[i].cnt=0;
            num[i].val=nums[i];
        }
        vector<node> tmpNums(nums.size());
        
        Msort(num,tmpNums,0,num.size()-1);
        
        vector<int> result(nums.size());
        for(int i=0;i<num.size();++i)
        {
            result[num[i].idx]=num[i].cnt;
        }
        
        return result;
    }
    struct node{
        int val;//值
        int cnt;//右边比它大的数
        int idx;//原来的idx
        node():val(0),cnt(0),idx(0){};
    };
    void Merge(vector<node>&nums,vector<node>&tmpNums,int l,int k,int r)
    {
        int i=l,j=k+1;
        int idx=l;
        while(i<=k&j<=r)
        {
            if(nums[i].val<=nums[j].val)
            {//填充左边的数,证明之前填充的右边的数比这个数小,我们需要查询之前右边填充了多少个数字
                nums[i].cnt+=j-(k+1);
                tmpNums[idx++]=nums[i++];
            }
            else
                tmpNums[idx++]=nums[j++];
        }
        while(i<=k)
        {
            nums[i].cnt+=j-(k+1);
            tmpNums[idx++]=nums[i++];
        }
        while(j<=r)
            tmpNums[idx++]=nums[j++];
        
        for(i=l;i<=r;++i)
        {
            nums[i]=tmpNums[i];
        }
    }
    
    void Msort(vector<node>&nums,vector<node>&tmpNums,int l,int r)
    {
        if(l>=r) return ;
        
        int k=(l+r)/2;
        Msort(nums,tmpNums,l,k);
        Msort(nums,tmpNums,k+1,r);
        Merge(nums,tmpNums,l,k,r);
    }
};

 

 

338. Counting Bits(Medium)

题目要求给出一个数num,求出小于等于num的数在二进制表示时个位上1的总和。例如给出3,小于等于三的数有0、1、2、3,0包含0个1,1包含1个1,2包含1个1,3包含2个1,所以答案应该是{0,1,1,2}。

我们可以通过统计每个数字上的1求出结果,这样的时间复杂度就为O(n*sizeof(integer))。

其实还有更好的办法,我们来分析一下,我们先列出部分数的二进制表示:
0
1
10
11
100
101
110
111
1000

我们可以看出,第二个数10有一个一,是从第一个数0上多加一个1得到,第三第四个数分别是第一第二个数加上1得到。而第五、六、七、八个数(100,101,110,111)是第一、二、三、四个数(0,1,10,11)加上1得到。

所以我们发现,可以通过已经生成的数来帮助生成后面的数,而上面分析的加1,其实是进位而来的,我们发现每当经过2^n后,一个数的二进制表示就会进1位,意味着前面的数在最高位加1可以得到后面的数,而回归题目,求1的个数,我们先求出前面数的1个数,后面的数就可以通过加1得到。

所以总体思想是,我们额外使用一个指针idx,指向前面的数,然后num[idx]+1为当前数的1的个数。那么问题就在于idx什么时候回到起点(0)?就是当经过2^n后,令idx为0。

 

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

AC代码:

class Solution {
public:
    vector<int> countBits(int num) {
        int idx=0,n2=1;
        vector<int> result;
        result.push_back(0);
        for(int i=1;i<=num;++i)
        {
            if(i==n2)
            {
                idx=0;
                n2*=2;
            }
            result.push_back(result[idx++]+1);
        }
        return result;
    }
};

 

字符串运用-密码截取(manacher)

1.使用manache解法,主要把数组进行填充,每个字符空隙填充’#’,然后再在开头填充’$’;

2.增加辅助变量mx(最大回文的右边界),id(拥有最大回文右边界的字符index),接着分别考虑情况mx>i和mx<=i;最后的结果为max(p[i]-1).

Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214 。因为截获的串太长了,而且存在多种可能的情况(abaaab可看作是aba,或baaab的加密形式),Cathcer的工作量实在是太大了,他只能向电脑高手求助,你能帮Catcher找出最长的有效密码串吗?
输入描述:
输入一个字符串
输出描述:
返回有效密码串的最大长度
输入例子:

ABBA
输出例子:
4

AC代码:

#include<string>
#include<iostream>
#include<vector>

using namespace std;

int manacher(string tmp)
{
    //插入字符串,得到一个新串
    string s="$";
    for(int i=0;i<tmp.size();++i)
    {
        s+="#";
        s+=tmp[i];
    }
    s+="#";
    
    int id=0;//拥有最大回文边界的位置
    int mx=0;//最大的回文边界
    vector<int> p(s.size(),0);
    
    for(int i=1;i<s.size();++i)
    {
        //根据以前的数据计算出暂时最大的p[i]
        if(mx>i)
        {
            p[i]=min(p[2*id-i],mx-i);
        }
        else
            p[i]=1;
        
        //朴素检测
        while(s[i-p[i]]==s[i+p[i]])
        {
            p[i]++;
        }
        
        //更新id和mx
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
    }
    
    int result=-1;
    for(int i=0;i<p.size();++i)
    {
        result=max(p[i]-1,result);
    }
    return result;
}

int main()
{
    string s;
    while(cin>>s)
       	cout<<manacher(s)<<endl;
    return 0;
}

具有地址alignment的malloc实现

最近看到一个有趣的问题,实现具有机制alignment的malloc函数,在网上查找资料,发现一个有趣的实现方法,在GCC下面成功运行,VS在(**void)寻址出错。

下面是实现代码:

//分配对齐地址的指针
void * aligned_malloc(int size, int alignment)
{
	void* ptr = malloc(size + alignment);

	if (ptr)
	{
		//注意是加上alignment后在取与,与stl中的简单向上取整不一样,stl中的向上取整是加上(alignment-1)
		//这里加上alignment,能确保aligned前面的地址空间存在空白部分
		void* aligned = (void*)(((long)ptr + alignment) & ~(alignment - 1));
		((void**)aligned)[-1] = ptr;//相当于*(aligned-1)的意思,由于语法错误,需要强制转换类型,意思是把ptr存放在aligned-1指向的地址的空间中

		return aligned;
	}
	else
		return NULL;
}
//释放函数aligned_free
void aligned_free(void *paligned)
{
	//删除相应的地址空间
	free(((void**)paligned)[-1]);
}

(hiho编程练习赛1)优化延迟

思路:

1.使用大小为n的堆,进行模拟计算。

2.通过二分法,找出最优的堆的大小。

3.注意q和其他输入的取值大小。

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Ho编写了一个处理数据包的程序。程序的输入是一个包含N个数据包的序列。每个数据包根据其重要程度不同,具有不同的”延迟惩罚值”。序列中的第i个数据包的”延迟惩罚值”是Pi。如果N个数据包按照<Pi1, Pi2, … PiN>的顺序被处理,那么总延迟惩罚

SP=1*Pi1+2*Pi2+3*Pi3+…+N*PiN(其中i1, i2, … iN是1, 2, 3, … N的一个排列)。

小Ho的程序会依次处理每一个数据包,这时N个数据包的总延迟惩罚值SP为

1*P1+2*P2+3*P3+…+i*Pi+…+N*PN

小Hi希望可以降低总延迟惩罚值。他的做法是在小Ho的程序中增加一个大小为K的缓冲区。N个数据包在被处理前会依次进入缓冲区。当缓冲区满的时候会将当前缓冲区内”延迟惩罚值”最大的数据包移出缓冲区并进行处理。直到没有新的数据包进入缓冲区时,缓冲区内剩余的数据包会按照”延迟惩罚值”从大到小的顺序被依次移出并进行处理。

例如,当数据包的”延迟惩罚值”依次是<5, 3, 1, 2, 4>,缓冲区大小K=2时,数据包被处理的顺序是:<5, 3, 2, 4, 1>。这时SP=1*5+2*3+3*2+4*4+5*1=38。

现在给定输入的数据包序列,以及一个总延迟惩罚阈值Q。小Hi想知道如果要SP<=Q,缓冲区的大小最小是多少?

输入

Line 1: N Q

Line 2: P1 P2 … PN

对于50%的数据: 1 <= N <= 1000

对于100%的数据: 1 <= N <= 100000, 0 <= Pi <= 1000, 1 <= Q <= 1013

输出

输出最小的正整数K值能满足SP<=Q。如果没有符合条件的K,输出-1。

样例输入
5 38
5 3 1 2 4
样例输出
2

AC代码:


//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<bitset>
//#include "siukwanAlloctor.h"
using namespace std;

long long arr[100002] = { 0 };
int size = 0;

long long pop()
{
	if (size == 0) return 0;
	long long result = arr[0];//获取栈顶元素
	long long x = arr[--size];//把队尾元素提到0号位置
	arr[size] = 0;
	int i = 0;
	int a = i * 2 + 1;//左孩子
	int b = i * 2 + 2;//右孩子

	while (a<size)
	{
		if (b<size&&arr[a]<arr[b])
			a = b;//右孩子比左孩子大
		if (x<arr[a])//孩子的值比父亲大,提上来
			arr[i] = arr[a];
		else//父亲的值比孩子大,停止操作
			break;
		i = a;
		a = i * 2 + 1;
		b = a + 1;
	}
	arr[i] = x;
	return result;
}
void push(long long x)
{
	int i = size++;
	int p = (i - 1) / 2;//父亲节点
	while (x>arr[p])
	{//孩子节点的值比父亲的值大
		arr[i] = arr[p];
		i = p;
		if (i == 0) break;
		p = (i - 1) / 2;
	}
	arr[i] = x;
}

int main()
{

	int n;
	long long quality;
	int data[100002] = { 0 };
	scanf("%d", &n);
	scanf("%ld", &quality);

	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &data[i]);
	}

	long long  sum = 0;
	int result = -1;
	int a = 1;
	int b = n;
	int mid = (a + b) / 2;
	while (a <= b)
	{
		memset(arr, 0, sizeof(arr));
		sum = 0;
		mid = (a + b) / 2;
		//建立大小为mid的堆
		int i = 0;
		int j = 1;//权重
		for (i = 0; i < mid; ++i)
		{
			push(data[i]);
		}

		//一个一个统计
		for (; i < n; ++i)
		{
			long long x = pop();//缓冲区已经满,把头部弹出来
			sum += x*(j++);
			push(data[i]);
		}
		while (size != 0)
		{
			long long x = pop();//缓冲区已经满,把头部弹出来
			sum += x*(j++);
		}

		if (sum <= quality)
			b = mid - 1;//尝试更小的空间
		else
			a = mid + 1;
		if (sum <= quality && (result == -1 || mid < result))
			result = mid;
	}
	cout << result << endl;

	return 0;
}