Month: December 2015

1.题目要求在一些现在区间vector中，插入一个新的区间，并更新整个区间集（如果发生交集）。

2.主要思路是遍历一遍（时间复杂度为O（n）），查询当前的区间是否能插入的区间发生合并，合并分为四种情况：相交有两种([2,5]和[4,6]一前一后相交，[4,6]和[2,5]一后一前相交)，包含有两种([1,7]和[4,6]包含，[4,6]和[1,7]被包含)。

3.如果发生合并，记录合并的位置，把之前没有收到影响的区间直接压入新集合，从合并的位置开始使用Merge Intervals的方法进行合并检测。

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

 
AC代码：
[c language=”++”]
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
static bool cmp(const Interval&a, const Interval&b)
{
return a.start < b.start;
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> result=intervals;
bool isMerge=false;
int changeIdx=-1;//记录被改变区间的位置
for(int i=0;i<result.size();i++)
{
if( (newInterval.start<=result[i].end && newInterval.start>=result[i].start )
||(newInterval.end>=result[i].start && newInterval.end<=result[i].end )
||(newInterval.start<=result[i].start && newInterval.end>=result[i].end )
||(newInterval.start>=result[i].start && newInterval.end<=result[i].end ))
{/*共分四种情况:
相交有两种([2,5]和[4,6]一前一后相交，[4,6]和[2,5]一后一前相交)
包含有两种([1,7]和[4,6]包含，[4,6]和[1,7]被包含)*/
isMerge=true;//进行了合并，标记
changeIdx=i;//记录被改变区间的位置
result[i].start=min(result[i].start,newInterval.start);
result[i].end=max(result[i].end,newInterval.end);
break;
}
}
if(!isMerge)
{//没有发生合并，证明新区间与现有的区间没有交集，直接压入并排序
result.push_back(newInterval);
sort(result.begin(), result.end(), cmp);
return result;
}
else
{//进行了合并
vector<Interval> result2(0);
for(int i=0;i<changeIdx;i++)
{//前面的区间没有受影响，直接压进去即可
result2.push_back(result[i]);
}
int start=result[changeIdx].start;
int cover=result[changeIdx].end;
for(int i=changeIdx+1;i<result.size();i++)
{//从受影响的区间开始考虑合并，如Merge Intervals的做法
if (result[i].start <= cover)
cover = max(cover, result[i].end);
else
{
result2.push_back(Interval(start, cover));
start = result[i].start;
cover = result[i].end;
}
}
//把最后的一个区间压进去
result2.push_back(Interval(start, cover));
return result2;
}
}
};
[/c]

1.这道题目没有想象中难。

2.首先初始化start和cover，对于区间[start,cover]和区间[start2,end2]把小于等于cover的start2的区间，进行合并，成为[start,max(cover,end2)]；然后重复这个步骤。不能合并则表示没有交集，压入答案。

3.实现2算法的前提是，数组按照start从小到大排列，这个时候需要重写cmp函数，由于需要写在class里面，所以需要添加static。

4.遍历一遍即可，时间复杂度为O(n)。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

AC代码：
[c language=”++”]
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
static bool cmp(const Interval&a, const Interval&b)
{//需要使用static采用调用
return a.start < b.start;
}
vector<Interval> merge(vector<Interval>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<Interval> result(0);
int start=0, cover=0;//通过不断覆盖起始点，来扩大覆盖范围，譬如[1,6]和[2,7]，cover=6>=2,所以合并两个区间，cover变成7
int n = intervals.size();
if (n != 0)
{//注意初始化
start = intervals[0].start;
cover = intervals[0].end;
}
else if(n==0) return intervals;//注意空时返回空
for (int i = 1; i < n; i++)
{//n>=2
if (intervals[i].start <= cover)//取能覆盖的最大范围
cover = max(cover, intervals[i].end);
else
{//intervals[i].start > cover，不能覆盖，压入[start，cover]，然后更新start和cover
result.push_back(Interval(start, cover));
start = intervals[i].start;
cover = intervals[i].end;
}
}
result.push_back(Interval(start, cover));
return result;
}
};
[/c]

1.题目要求给出一棵二叉树，进行序列化，然后再进行反序列化还原二叉树，而中间的序列化形式不作要求。

2.综合考虑后，我采用&val1*parentAddress1#address1&val2*parentAddress2#address2这样的格式来存储节点数据，即把一个节点的值，父节点地址和自身地址存储。因为地址从1开始递增，所以通过父节点地址的正负来区分左右节点。

3.需要注意考虑边界的情况，一开始我使用了0来作为根节点的地址，但是0没有正负之分，所以不能区分左右孩子，于是改为1作为根节点。

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.

AC代码：
[c language=”++”]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
string int2str(int a)
{
bool sign = true;
if (a < 0)
{//注意负数情况
sign = false;
a = -a;
}
if (a == 0) return "0";
string result = "";
while (a != 0)
{
char c = a % 10 + ‘0’;
result = c + result;
a /= 10;
}
if (!sign) result = "-" + result;
return result;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
int address = 1;//根节点地址需要为1，因为需要通过正负的父地址来判断左右子树
queue<pair<TreeNode*, int>> q;//first为节点，second为地址
vector<pair<int, pair<int, int>>> arr(0);//first为val,second.first为父亲地址，second.second为自己地址
int count1 = 0;
int count2 = 0;
if (root != NULL)
{//根节点的父节点地址为1
arr.push_back({ root->val, { INT_MAX, address } });
q.push({ root, address });
address++;
count1++;
}
while (!q.empty())
{
//广度遍历树，记录每个节点的值，父节点地址，地址
for (int i = 0; i < count1; i++)
{
pair<TreeNode*, int> head = q.front();
q.pop();
int parentAdd = head.second;//父亲节点的地址
TreeNode* tmp = head.first;
if (tmp->left != NULL)
{//左儿子不为空
arr.push_back({ tmp->left->val, { parentAdd, address } });
q.push({ tmp->left, address });
address++;
count2++;
}
if (tmp->right != NULL)
{//父节点为负数，表示是右儿子
arr.push_back({ tmp->right->val, { -parentAdd, address } });
q.push({ tmp->right, address });
address++;
count2++;
}
}
count1 = count2;
count2 = 0;
}
string result = "";//最终结果
for (int i = 0; i < arr.size(); i++)
{//格式为&val*parentAddress#address
result += "&" + int2str(arr[i].first) + "*" + int2str(arr[i].second.first) + "#" + int2str(arr[i].second.second);
}
return result;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
map<int, TreeNode*> m;
vector<pair<int, pair<int, int>>> arr(0);//还原成数组
int process = -1;
bool sign = true;
int val=-1, parentAdd=INT_MAX, add=0;
for (int i = 0; i < data.size(); i++)
{
if (process == 0)
{//此时检测的是val
if (data[i] == ‘-‘)
sign = false;
else if (data[i] == ‘*’)
{
if (!sign) val = -val;
process++;
sign = true;
}
else
val = val * 10 + data[i] – ‘0’;
}
else if (process == 1)
{//此时检测的是parentAdd
if (data[i] == ‘-‘)
sign = false;
else if (data[i] == ‘#’)
{
if (!sign) parentAdd = -parentAdd;
process++;
sign = true;
}
else
parentAdd = parentAdd * 10 + data[i] – ‘0’;
}
else if (process == 2)
{//此时检测的是add
if (data[i] == ‘-‘)
sign = false;
else if (data[i] == ‘&’)
process = -1;
else
add = add * 10 + data[i] – ‘0’;
}
//检测是否到了下一个开始
if (process == -1 && data[i] == ‘&’)
{
if (i != 0)
{//如果i==0，初始值，不需要压入，i>0才需要
if (!sign) add = -add;
arr.push_back({ val, { parentAdd, add } });
}
sign = true;//初始化符号为正号
val = 0;
parentAdd = 0;
add = 0;
process++;
}
}
//补充最后一个值
if (data != "")
{
if (!sign) add = -add;
arr.push_back({ val, { parentAdd, add } });
}

for (int i = 0; i < arr.size(); i++)
{//把arr通过map还原成树
int parentAdd = arr[i].second.first;
int add = arr[i].second.second;
int val = arr[i].first;
m[add] = new TreeNode(val);
if (parentAdd != INT_MAX)
{
if (parentAdd < 0)
m[-parentAdd]->right = m[add];
else
m[parentAdd]->left = m[add];
}
}
if (data!="")
return m[1];
else return NULL;
}
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
[/c]

1.这道题目要求输出数据流中的中位数，有两个操作，一个是添加元素addNum，另外一个是寻找中位数findMedian。

2.主要思路：

1）建立两个堆，分别为小根堆和大根堆；

2）维持这两个堆的大小相等，或者小根堆比大根堆多一个元素，这样在输出最后结果的时候只需要输出大根堆的堆顶元素或者大根堆与小根堆堆顶元素的平均值即可。

3）根据上面的要求，需要保证小根堆的堆顶>=大根堆的堆顶。

4）下面为示意图，其中a<=b<=c<=d<=maxHeap.top()<=minHeap.top()<=e<=f<=g

a,b,c,d,maxHeap.top(),minHeap.top(),e,f,g
|—-maxHeap—-| Median |—-minHeap—-|

 

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) – Add a integer number from the data stream to the data structure.
• double findMedian() – Return the median of all elements so far.

For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.

AC代码：

[c language=”++”]
class MedianFinder {
public:
struct cmpMinHeap{
bool operator()(const int&a, const int&b)
{
return a > b;
}
};
/*
a,b,c,d,maxHeap.top(),minHeap.top(),e,f,g
|—-maxHeap—-| Median |—-minHeap—-|
*/
priority_queue<int, vector<int>, cmpMinHeap> minHeap;//存储大于等于中位数的元素
priority_queue<int> maxHeap;//存储小于等于中位数的元素
// Adds a number into the data structure.
void addNum(int num) {
if (minHeap.size() == maxHeap.size())
{//如果两个堆大小相等，需要插入到minHeap，保证minHeap.size()>=maxHeap.size()
if (minHeap.size() == 0 || num >= maxHeap.top())
{//如果两个堆均为空，或者num大于maxHeap，则直接放到minHeap中
minHeap.push(num);
}
else if (num<maxHeap.top())
{//如果num小于maxHeap.top()，则把maxHeap.top()移到minHeap中，把num放到maxHeap中
minHeap.push(maxHeap.top());
maxHeap.pop();
maxHeap.push(num);
}
}
else
{//肯定是minHeap.size()>maxHeap.size()，所以插入到maxHeap
if (num >= minHeap.top())
{//如果num大于minHeap.top()，则把minHeap.top()移到maxHeap中，把num放到minHeap中
maxHeap.push(minHeap.top());
minHeap.pop();
minHeap.push(num);
}
else
{//直接插入到maxHeap即可
maxHeap.push(num);
}
}
}

// Returns the median of current data stream
double findMedian() {
if (maxHeap.size() == minHeap.size())
{//两个堆相等，即为偶数，输出中间两个数的平均值
double median = maxHeap.top() + minHeap.top();
median /= 2.0;
return median;
}
else//否则，一定是奇数，且minHeap比maxHeap多一个元素，所以输出minHeap.top()
return minHeap.top();
}
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();
[/c]

今天计划通过VNC远程登录服务器，但是发现服务器拒绝连接。

服务器用的centOS系统，已经安装好了VNCserver，之前连接没有问题。客户端是win8.1系统，用的是VNC-Viewer-5.2.3-Windows-64bit。

于是我通过ssh登录服务器查看服务器的网络状态，使用下面的命令：

[shell]

[lxk@ndc ~]$ netstat -lp|grep -i vnc
(Not all processes could be identified, non-owned process info
will not be shown, you would have to be root to see it all.)
[lxk@ndc ~]$

[/shell]

发现没有找到vnc的相关监听端口信息。然后直接用vncserver命令：

[shell]
vncserver -list
[/shell]

用来列出所有的vncserver服务，发现是有一个4号的端口在监听，但是在netstat中查询不了，应该是服务挂了。于是重启4号端口的服务：

[shell]
[lxk@ndc ~]$ vncserver :4

New ‘www.xxxxxxx.com:4 (lxk)’ desktop is www.xxxxxxx.com:4

Starting applications specified in /home/lxk/.vnc/xstartup
Log file is /home/lxk/.vnc/www.xxxxxxx.com:4.log

[lxk@ndc ~]$ netstat -lp|grep -i vnc
(Not all processes could be identified, non-owned process info
will not be shown, you would have to be root to see it all.)
tcp 0 0 0.0.0.0:5904 0.0.0.0:* LISTEN 41052/Xvnc
tcp 0 0 0.0.0.0:6004 0.0.0.0:* LISTEN 41052/Xvnc
tcp6 0 0 [::]:6004 [::]:* LISTEN 41052/Xvnc
unix 2 [ ACC ] STREAM LISTENING 6179297 41052/Xvnc @/tmp/.X11-unix/X4
unix 2 [ ACC ] STREAM LISTENING 6179298 41052/Xvnc /tmp/.X11-unix/X4
[lxk@ndc ~]$
[/shell]

再vncserver -list后，发现PID更新了，表示已经重启了服务进程。然后再用VNC客户端，顺利登录。
[shell]
[lxk@ndc ~]$ vncserver -list

TigerVNC server sessions:

X DISPLAY # PROCESS ID
:4 41052
[/shell]

如果没有指定端口，直接使用

[shell]
vncserver
[/shell]

系统回以此开启监听端口，譬如刚才已经开启了4号端口，那么接下来会开启5、6、7。。。。号端口。

可以通过kill命令关闭进程，如下：

[shell]
vncserver -kill :4
[/shell]

直接杀掉4号端口的vncserver进程。

另外，如果其他用户已经开启了4号端口，那么在执行vncserver :4命令时，会提示：

[shell]

A VNC server is already running as :4

[/shell]