C++ notes
群里看到一个很有趣的东西
int a=(int)((int*)0+4);
乍一看似乎狂拽酷炫，后来发现int和int 之间转化也是地址值的直接转化，(int)0先变成地址值为0的指针(或者称职NULL，VS认为是等价的)，然后指针+4相当于+4*sizeof(int), 相当于地址值+16,然后将0x00000010(VS似乎是32bit的，32bit，然后直接将地址值转化为int就是值)，a=16
看到微博粉丝狂魔陈立人发了一个面试题，求K linklist的交集，返回一个linklist，类似于Merge K linklist，当时需要用heap优化才能AC。
一开始写个代码，大概想了下可以heap，但是后来发现似乎不行，因为merge是把数据删掉，同时copy到result linklist里，但是这里如果不是全部相等，需要将非max的val对应的linklist指针
后移，同时max的还要保留，heap也必须是maxheap，似乎是不行，于是只好写个朴素的O(n)的遍历了。不确定是否bug free
struct ListNode
{
int val;
ListNode* next;
ListNode(int x):val(x), next(NULL)
{
//val=x;
//next=NULL;
}
};
bool AtLeastOnePointNULL()
{
for(int i=0;i<p.size();i++)
if(p[i]==NULL)
return true;
return false;
}
ListNode* Intersection(vector<ListNode*> ListHead)
{
vector<ListNode*> p;
//vector<int> nextp;
ListNode* resulthead=NULL, *resulttail;
if(ListHead.size()==0)
return resulthead;
//vector<int> curval;
for(int i=0;i<ListHead.size();i++)
p.push_back(ListHead[i]);//curval.push_back(ListHead[i]->val);
//make_heap(curval.begin(),curval.end());//max heap default
bool first=true;
while(1)
{
if(AtLeastOnePointNULL())
break;
int max=p[0]->val;//at least one linklist
bool modified=false;
for(int i=1;i<p.size();i++)
if(p[i]->val>max)
max=p[i]->val,modified=true;
if(modified==false)//at least one linklist
{
if(first==true)
{
resulthead=new ListNode(p[0]->val);
resulttail=resulthead;
first==false;
}
else
{
resulttail->next=new ListNode(p[0]->val),resulttail=resulttail->next;
}
for(int i=0;i<p.size();i++)
p[i]=p[i]->next;
}
else
{
for(int i=0;i<p.size();i++)
{
if(p[i]->val<max)
p[i]=p[i]->next;
}
}
}
return resulthead;
}
昨晚和瞿神讨论这道算法，发现似乎我的稍微有点笨了点，可以一次遍历第二遍遍历的次数，这个时间复杂度不能从循环的角度来计算，因为条件判断比较复杂。
这道应该从结点的某个操作次数累加来看，例如K个Linklist共N个结点，然后每个结点一定只是后移一次，这里面主要就是point后移操作，只要一个linklist空了就结束，
时间复杂度是O(N)
ListNode* Intersection(vector<ListNode*> ListHead)
{
vector<ListNode*> p;
vector<int> curmax;
ListNode* head=NULL,*tail;
if(ListHead.size()==0)
return head;
for(int i=0;i<ListHead.size();i++)
p.push_back(ListHead[i]);
bool first=false;
while(1)
{
if(AtLeastOnePointNULL())
break;
curmax.push_back(0);
for(int i=1;i<p.size();i++)
{
if(p[i]->val<p[curmax[0]]->val)//at least one ele in curmax
p[i]=p[i]->next;
else if(p[i]->val==p[curmax[0]]->val)
curmax.push_back(i);
else//update max
{
for(int j=0;j<curmax.size();j++)
p[curmax[j]]=p[curmax[j]]->next;
curmax.clear();
curmax.push_back(i);
}
}
if(curmax.size()==ListHead.size())
{
if(first==false)
{
head=new ListNode(p[0]->val);
tail=head;
first==true;
}
else
{
tail->next=new ListNode(p[0]->val),tail=tail->next;
}
for(int i=0;i<p.size();i++)
{
p[i]=p[i]->next;
}
}
}
return head;
}
今天碰到一个subfigure的问题，用BMC Bio的模板怎么改都改不好，主要是width height加不进去，识别不了，因此两个subfigure是上下排列的。
周老师过来问我屏幕怎么两个，如果读了博，肯定是不会问了，还好我是拿旧的屏幕，如果新的估计肯定被换掉了。
今天看到陈立人公布了答案，还是用堆来做的，但是不是之前想的最大堆，而是最小堆，同时维护一个最大值，这样保证每次都知道当前堆中的最大值。
算法中维护这个词是很微妙的，我不是很习惯用，导致经常想到遍历一遍当前找最大，其实完全没必要。比较当前堆顶和当前最大值大小，便可以知道是否是交集了，
如果最小的等于最大值，那整个堆都是同一元素，否则需要逐个出堆直到遇到堆顶等于最大值(不可能大于)。但是似乎不需要存储
struct ListNode
{
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL)
{
}
};
bool comp(ListNode* p1,ListNode*p2)
{
return p1->val>p2->val;
}
bool AtLeastOnePointNULL()
{
for(int i=0;i<(int)p.size();i++)
if(p[i]==NULL)
return true;
return false;
}
ListNode* Intersection(vector<ListNode* > ListHead)
{
int max=0x80000000;
//0x7FFFFFFF;
vector<ListHead* > p;
if(ListHead.size()==0)
return NULL;
for(int i=0;i<ListHead.size();i++)
{
p.push_back(ListHead[i]);
if(max<ListHead[i]->val)
max=ListHead[i]->val;
}
make_heap(p.begin(),p.end(),comp);
ListNode* head=NULL, tail;
while(1)
{
if(AtLeastOnePointNULL())
break;
if(p[0]->val<max)
{
while(p[0]->val<max)
{
pop_heap(p.begin(),p.end());
ListNode* pnext=p[p.size()-1]->next;
if(pnext==NULL)
return head;
if(max<pnext->val)
max=pnext->val;
p.pop_back();
p.push_back(pnext);
push_heap(p.begin(),p.end());
}
}
else
{
if(head==NULL)
{
head=new ListNode(p[0]->val);//at least one ele in heap
tail=head;
}
else
{
tail->next=new ListNode(p[0]->val);
tail=tail->next;
}
for(int i=0;i<p.size();i++)
{
p[i]=p[i]->next;
if(p[i]->val>max)
max=p[i]->val;
}
make_heap(p.begin(),p.end(),comp);
}
}
return head;
}