作者：siukwan

GitHub第一步：生成ssh keys

参考自https://help.github.com/articles/generating-ssh-keys/

亲自在Mac OS和cent OS中测试成功，命令均一样。

SSH keys可以无需密码进行github更新，每台电脑均需要生成唯一的SSH并添加到github个人资料的settings中。

centOS需要使用命令sudo yum install git安装git。

Step 1: 检查SSH keys

首先我们需要检测系统是否已经存在SSH keys，可以使用终端输入下列的命令：

ls -al ~/.ssh
# Lists the files in your .ssh directory, if they exist

如果存在，可以看到如下的列表：

  • id_dsa.pub
  • id_ecdsa.pub
  • id_ed25519.pub
  • id_rsa.pub

如果想使用现有的SSH keys，可以忽略步骤2和步骤3，如果没有现成的SSH keys，我们接下来会通过终端来生成。

Step 2: 生成SSH key

  1. 输入下面的命令，其中需要填写自己的邮箱： 
    ssh-keygen -t rsa -b 4096 -C "your_email@example.com"
# Creates a new ssh key, using the provided email as a label
# Generating public/private rsa key pair.
  2. 使用默认设置即可，直接按回车： 
    # Enter file in which to save the key (/Users/you/.ssh/id_rsa): [Press enter]
  3. 这个也可以直接按回车： 
    # Enter passphrase (empty for no passphrase): [Type a passphrase]
# Enter same passphrase again: [Type passphrase again]
  4. 最后我们会看到下面的信息: 
    # Your identification has been saved in /Users/you/.ssh/id_rsa.
# Your public key has been saved in /Users/you/.ssh/id_rsa.pub.
# The key fingerprint is:
# 01:0f:f4:3b:ca:85:d6:17:a1:7d:f0:68:9d:f0:a2:db your_email@example.com

Step 3: 把生成的key添加到ssh-agent

ssh-agent是一种控制用来保存公钥身份验证所使用的私钥的程序，其实ssh-agent就是一个密钥管理器，原型ssh-agent以后，使用ssh-add将私钥交给ssh-agent保管，其他程序需要身份验证的时候可以自动将验证申请交给ssh-agent来完成整个认证过程。

  1. 先检查ssh-agent是否在运行: 
    # start the ssh-agent in the background
eval "$(ssh-agent -s)"
# Agent pid 59566
  2. 把SSH key添加ssh-agent: 
    ssh-add ~/.ssh/id_rsa

注意：如果你采用现有的SSH keys，你需要把id_rsa（这是一个文件名）替换成现有的私钥文件名。

如果出现

  1. Could not open a connection to your authentication agent.

    需要先执行下面的命令，才能进行ssh-add操作

    ssh-agent bash

Step 4: 把SSH key添加到github账户

这个时候需要复制id_rsa.pub的内容，即SSH key，注意这个文件不一定是id_rsa.pub,有可能是id_dsa.pub,id_ecdsa.pub or id_ed25519，需要看自己的设置。

pbcopy < ~/.ssh/id_rsa.pub
# Copies the contents of the id_rsa.pub file to your clipboard

 如果pbcopy失败，可以直接用vi打开id_rsa.pub复制里面的内容。

详细步骤：

  1. Settings icon in the user bar进入个人账户的Settings.
  2. SSH keys选择SSH keys.
  3. SSH Key button点击Add SSH key.
  4. 添加title，题目可为 “Personal MacBook Air”，根据自己的情况添加。
  5. The key field复制key.
  6. The Add key button点击Add key.
  7. 最后会要求输入github的密码进行确认.

Step 5: 测试连接

在完成上述步骤后，可以测试连接，确保ssh正常工作。在尝试ssh连接时，github会提示认证。

  1. 打开终端并输入: 
    ssh -T git@github.com
# Attempts to ssh to GitHub
  2. 然后会看到下面的警告: 
    # The authenticity of host 'github.com (207.97.227.239)' can't be established.
# RSA key fingerprint is 16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48.
# Are you sure you want to continue connecting (yes/no)?

    输入yes:

    # Hi username! You've successfully authenticated, but GitHub does not
# provide shell access.
  3. 看到上面的信息后证明你已经成功ssh连接到github!

If you receive a message about “access denied,” you can read these instructions for diagnosing the issue.

If you’re switching from HTTPS to SSH, you’ll now need to update your remote repository URLs. For more information, see Changing a remote’s URL.

68 Text Justification(Hard)

1.该题主要考察字符串操作。

2.主要思路是，如果单词为当前行的第一个单词，则不需要考虑插入空格，如果单词为当前行的第二个单词，则需要补充空格。这样可以尽可能多地添加单词到同一行中。

3.当完成单词的选择后，需要进行空格补充，从第二个单词开始遍历（第一个单词前面不需要补充空格），每次在单词前面补充一个空格，知道满足宽度要求。

4.在3中，条件是从第二个单词开始补充。需要注意的是，假如一个单词为一行，但是这行不是结束行，那么在这个单词后面补充足够多的空格即可。

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactlyL characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

click to show corner cases.

Corner Cases:

  • A line other than the last line might contain only one word. What should you do in this case?
    In this case, that line should be left-justified.

 

AC代码：

class Solution {
public:
	vector<string> fullJustify(vector<string>& words, int maxWidth) {
		int newStrCount = 0;
		int n = words.size();
		int nowIdx = 0;
		vector<string> result(0);
		while (nowIdx < n)
		{
			int nowStrWidth = 0;
			int startIdx = nowIdx;
			int endIdx = nowIdx;
			for (; nowIdx < n; nowIdx++)
			{
				if (nowStrWidth == 0 && maxWidth >= nowStrWidth + words[nowIdx].size())
				{//这是这个字符串的第一个单词,包含了最后一个单词单独为一行的状态
					endIdx = nowIdx;
					nowStrWidth += words[nowIdx].size();
					
				}
				else if (nowStrWidth > 0 && maxWidth >= nowStrWidth + words[nowIdx].size() + 1)
				{//不是字符串的第一个单词,需要补充一个空格
					endIdx = nowIdx;
					nowStrWidth += words[nowIdx].size() + 1;
				}
				else//大于的话退出循环
					break;
			}
			string thisStr = "";//这次生成的text string
			vector<string> thisStrWords(0);
			for (int i = startIdx; i <= endIdx; i++)
			{
				thisStrWords.push_back(words[i]);
			}
			if (nowIdx == n)//最后一行的单词
			{
				thisStr += thisStrWords[0];
				for (int i = 1; i < thisStrWords.size(); i++)
				{//添加单词，从第二个单词开始，每个单词前面都需要补充一个空格
					thisStr = thisStr+" "+thisStrWords[i];
				}
				for (int i = 0; i < maxWidth - nowStrWidth; i++)
					thisStr += " ";//补充缺少的空格
			}
			else
			{
				for (int i = 1; i < thisStrWords.size(); i++)
				{//因为之前对压进来的单词没有加空格，现在先加上
					thisStrWords[i] = " " + thisStrWords[i];
				}
				//开始进行justification
				while (nowStrWidth < maxWidth)
				{
					if (thisStrWords.size() > 1)
					{//如果有两个单词或以上
						for (int i = 1; i < thisStrWords.size(); i++)
						{//在第二个单词前面补充空格，优先补充左边的空格，一旦符合要求，马上退出
							if (nowStrWidth == maxWidth)//满足宽度要求
								break;
							thisStrWords[i] = " " + thisStrWords[i];
							nowStrWidth++;
						}
					}
					else
					{//如果只有一个单词
						int blankCount = maxWidth - nowStrWidth;
						for (int i = 0; i < blankCount; i++)
						{
							nowStrWidth++;
							thisStrWords[0] += " ";//补充缺少的空格
						}
					}
				}
				for (int i = 0; i < thisStrWords.size(); i++)
				{//把单词合并成text string
					thisStr += thisStrWords[i];
				}
			}
			result.push_back(thisStr);
		}
		return result;
	}
};

57 Insert Interval(Hard)

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代码：

/**
 * 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;
        }
    }
};

56 Merge Intervals(Hard)

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代码：

/**
 * 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;
	}
};

297 Serialize and Deserialize Binary Tree(Medium)

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代码：

/**
 * 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));

295 Find Median from Data Stream(Hard)

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.

Subscribe to see which companies asked this question

AC代码：

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();

关于VNC的一些使用问题

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

QQ截图20151201181420

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

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


[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 ~]$

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

vncserver -list

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

[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 ~]$

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

[lxk@ndc ~]$ vncserver -list

TigerVNC server sessions:

X DISPLAY #     PROCESS ID
:4              41052

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

vncserver

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

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

vncserver -kill :4

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

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


A VNC server is already running as :4

A级103道PAT题目的简单总结

2015-11-30:对103道PAT题目做简单的总结：

1001 A+B Format (20) string处理，注意正负号

1002 A+B for Polynomials (25) 直接建立两个数组，相加输出

1003 Emergency (25) Dijkstra+DFS

1004 Counting Leaves (30) 计算每层叶子节点的数量

1005 Spell It Right (20) 字符串操作，计算digit总和并输出英文

1006 Sign In and Sign Out (25) 重写cmp进行排序

1007 Maximum Subsequence Sum (25) 最长连续子序列的和

1008 Elevator (20) 计算电梯时间

1009 Product of Polynomials (25) 多项式相乘，直接创建1000*1000+1个数组

1010 Radix (25) 重点：radix可以>=35，二分法查找radix

1011 World Cup Betting (20) 按照公式计算

1012 The Best Rank (25) 注意分数相同，排名相同

1013 Battle Over Cities (25) 使用并查集

1014 Waiting in Line (30) 银行排队模拟，一分钟一分钟地遍历

1015 Reversible Primes (20) 进制转换，质数判定

1016 Phone Bills (25) 排序，分类

1017 Queueing at Bank (25) 银行排队模拟

1018 Public Bike Management (30) Dijkstra+DFS

1019 General Palindromic Number (20) 回文判定+进制转换

1020 Tree Traversals (25) 后序+中序还原二叉树

1021 Deepest Root (25) BFS求最深的根，并查集。

1022 Digital Library (30) 哈希

1023 Have Fun with Numbers (20) string 大整数运算

1024 Palindromic Number (25) 回文判断（可以考虑manacher）

1025 PAT Ranking (25) 排名，排序

1026 Table Tennis (30) 队列模拟，30秒的四舍五入

1027 Colors in Mars (20) 10进制转换成13进制

1028 List Sorting (25) 排序，strcmp

1029 Median (25) 重点：二分法求两个数的中位数

1030 Travel Plan (30) Dijkstra+DFS

1031 Hello World for U (20) string处理

1032 Sharing (25) 求两个链表的公共点

1033 To Fill or Not to Fill (25) 重点：加油问题，队列，数组

1034 Head of a Gang (30) 并查集

1035 Password (20) 简单的string处理

1036 Boys vs Girls (25) 简写的排序，重写cmp比较函数

1037 Magic Coupon (25) 简写的排序，重写cmp比较函数

1038 Recover the Smallest Number (30) 贪心算法，注意贪心标准

1039 Course List for Student (25) 哈希查询，注意超时

1040 Longest Symmetric String (25) 最长回文字串

1041 Be Unique (20) 简单的哈希

1042 Shuffling Machine (20) 简单的数组位置更换

1043 Is It a Binary Search Tree (25)重点：写两个函数进行判断BST,MirrorBST

1044 Shopping in Mars (25) 尺取法求连续子序列的和

1045 Favorite Color Stripe (30) 动态规划，LCS变形

1046 Shortest Distance (20) 简单的和累加（算是DP）

1047 Student List for Course (25) 重点：选择合适的数据结构

1048 Find Coins (25) 和twosum一样，使用hash遍历一次

1049 Counting Ones (30) 重点：计算‘1’的个数，扩展到计算‘0’的个数

1050 String Subtraction (20) 简单的string处理

1051 Pop Sequence (25) 栈模拟操作

1052 Linked List Sorting (25) 排序，注意head=-1的情况（段错误）

1053 Path of Equal Weight (30) 求根到叶子节点的权重和（DFS）

1054 The Dominant Color (20) moore投票法

1055 The World’s Richest (25) 重点：根据题目特点选择合适的数据结构

1056 Mice and Rice (25) 模拟，注意排名的规则

1057 Stack (30) 重点：栈+树状数组+二分查找

1058 A+B in Hogwarts (20) string+进制转换

1059 Prime Factors (25) 质因数分解，注意输入为1的情况

1060 Are They Equal (25) string处理

1061 Dating (20) string处理

1062 Talent and Virtue (25) 根据要求排序，重写cmp比较函数

1063 Set Similarity (25) 重点：使用合适的数据结构来求集合的相似度

1064 Complete Binary Search Tree (30) 创建完全二叉搜索树，进行中序遍历（记录地址），然后再填值

1065 A+B and C (64bit) (20) string，大整数相加

1066 Root of AVL Tree (25) 重点：AVL树的基本操作

1067 Sort with Swap(0,*) (25) 每次都确保*移动在最终位置，注意优化

1068 Find More Coins (30) DFS

1069 The Black Hole of Numbers (20) string操作

1070 Mooncake (25) 贪心，单位价格高的优先

1071 Speech Patterns (25) 哈希求出现最多的单词（注意题目对单词的定义）

1072 Gas Station (30) 循环+Dijkstra，求出每个加油站到各个屋子的最短路程

1073 Scientific Notation (20) 科学计数法，还原出原数字，string操作

1074 Reversing Linked List (25) 链表翻转，把链表复制到数组，然后再翻转

1075 PAT Judge (25) 统计分数进行排名，重写cmp比较函数

1076 Forwards on Weibo (30) 层序遍历

1077 Kuchiguse (20) 简单的string处理

1078 Hashing (25) 哈希的平方探测实现

1079 Total Sales of Supply Chain (25) 层序遍历

1080 Graduate Admission (30) 事件模拟

1081 Rational Sum (20) 分数相加，gcd（扩展学习lcm的计算）

1082 Read Number in Chinese (25) string处理

1083 List Grades (25) 哈希，排序

1084 Broken Keyboard (20) 哈希

1085 Perfect Sequence (25) M<=m*p，二分法查找，排序

1086 Tree Traversals Again (25) 重点：利用栈进行中序遍历，还原二叉树

1087 All Roads Lead to Rome (30) Dijkstra+DFS

1088 Rational Arithmetic (20) 分数的四则运算

1089 Insert or Merge (25) 插入和归并排序（需要学习归并排序）

1090 Highest Price in Supply Chain (25) 层序遍历， 求最深的层

1091 Acute Stroke (30) 并查集

1092 To Buy or Not to Buy (20) 哈希

1093 Count PAT’s (25) 组合数统计

1094 The Largest Generation (25) 层序遍历

1095 Cars on Campus (30) 停车时间模拟

1096 Consecutive Factors (20) 重点：连续因数，DFS

1097 Deduplication on a Linked List (25) 哈希，链表操作

1098 Insertion or Heap Sort (25) 插入和堆排

1099 Build A Binary Search Tree (30) 中序遍历填值，建立二叉树

1100 Mars Numbers (20) 进制转换，10进制转13进制

1101 Quick Sort (25) 重点：判断能够作为pivot的元素，大根堆，小根堆的额外维护操作

1102 Invert a Binary Tree (25) 反转二叉树

1103 Integer Factorization (30) 因式分解，DFS

1103. Integer Factorization (30)

1.题目要求把一个数转化为固定项数的p次方数相加。

2.根据题目的特点，n的最大值不超过400，可以使用深度遍历搜索答案

3.加入限制条件进行剪枝，如i的p次方不能大于n-k+1，因为剩下的数至少均为1，剩下还需要k-1个数需要进行分配，每个数至少分配为1，共k-1，所以i的p次方最大只能为n-（k-1）=n-k+1，而最大值不能超过上一次分配的。

时间限制
1200 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.

Input Specification:

Each input file contains one test case which gives in a line the three positive integers N (<=400), K (<=N) and P (1<P<=7). The numbers in a line are separated by a space.

Output Specification:

For each case, if the solution exists, output in the format:

N = n1^P + … nK^P

where ni (i=1, … K) is the i-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122 + 42 + 22 + 22 + 12, or 112+ 62 + 22 + 22 + 22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen — sequence { a1, a2, … aK } is said to be larger than { b1, b2, … bK } if there exists 1<=L<=K such that ai=bi for i<L and aL>bL

If there is no solution, simple output “Impossible”.

Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

 
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>
using namespace std;
void dfs(int n, int count, int p,int preNum, vector<int>&ans,int ansSum, vector<pair<int,vector<int>>>&totalAns, vector<vector<int>>&num)
{
	if (n == 0 && count == 0)
	{
		totalAns.push_back({ansSum, ans});
	}
	else if ((n == 0 && count != 0) || (n != 0 && count == 0))
		return;
	else
	{
		for (int i = min(n - count+1,preNum); i >= 1; i--)
		{//进行剪枝
			if (num[i][p - 1] != -1 && num[i][p - 1]<=n-count+1)
			{
				ans.push_back(i);
				ansSum += i;
				dfs(n - num[i][p - 1], count - 1, p,i, ans,ansSum, totalAns, num);
				ansSum -= i;
				ans.pop_back();
			}
		}
	}
}
bool cmp(const pair<int, vector<int>>&a, const pair<int, vector<int>>&b)
{
	if (a.first > b.first)
		return true;
	else if (a.first == b.first)
	{
		for (int i = 0; i < a.second.size(); i++)
		{
			if (a.second[i] > b.second[i]) return true;
			else if (a.second[i] < b.second[i]) return false;
		}

	}
	else return false;
}
int main(void)
{
	
	int n, k, p;
	cin >> n >> k >> p;
	vector<vector<int>> num(401, vector<int>(7, 0));
	for (int i = 1; i < 401; i++)
	{
		num[i][0] = i;
		for (int j = 1; j < 7; j++)
		{
			if (num[i][j - 1] == -1) num[i][j] = -1;
			else
			{
				num[i][j] = num[i][j - 1] * i;
				if (num[i][j] > 400) num[i][j] = -1;
			}
		}
	}
	vector<int> ans(0);
	vector<pair<int,vector<int>>> totalAns(0);
	int ansSum = 0;

	dfs(n, k, p,n, ans,ansSum, totalAns, num);
	sort(totalAns.begin(), totalAns.end(), cmp);
	if (totalAns.size() != 0)
	{
		cout << n << " = ";
		for (int i = 0; i < totalAns[0].second.size(); i++)
		{
			cout << totalAns[0].second[i] << "^" << p;
			if (i != totalAns[0].second.size() - 1)
			{
				cout << " + ";
			}
		}
		cout << endl;
	}
	else 
	{
		cout << "Impossible" << endl;
	}

	return 0;
}