下午想通过ssh连接服务器节点使用VTune，结果显示错误：xshell Error: Unable to initialize gtk, is DISPLAY set properly?

折腾了好长时间才解决，因此记录下做备忘。

排查错误的步骤：

1、检查服务器端是否允许X11Forwarding(/etc/ssh/sshd_config文件中“X11Forwarding=yes”)；

2、检查$DISPLAY是否为本机的IP地址；

3、检查XShell是否允许X11Forwarding（http://www.netsarang.com/tutorial/xshell/1018/Using_X11_forwarding）。

Problem Description: Given an array A[1...n] consisting of integers and an integer m. Find three elements in A, so that sum of the three integers in A equals to m. 

for i from 1 to n-2
    do for j from i+1 to n-1
        do for k from j+1 to n
            do if A[i] + A[j] + A[k] = m
                   then print A[i], A[j], A[k]

sort array A
for i from 1 to n-2
    do for j from i+1 to n-1
        do binary_search(A[j+1...n], m-A[i]-[j])

通常关于矩阵的算法，时间复杂度都是，但是下面两个问题可以有的解法

1.这个问题是数据结构课的 story time 老师让思考的一个问题：

给定一个n*n的矩阵，矩阵中的每个元素都比它左边和上边所有的元素大，利用二分查找的思想判断矩阵中是否存在值K

大家很快说出从对角线上的元素开始判断，可是这样二分判断后，如果值不相等，得到一个L型的子矩阵，递归的过程无法继续，于是老师讲了下面这段话并说出答案：In designing a recursive algorithm, make sure you can repeat the strategy after the base case. 答案是从右上方的元素开始判断，伪代码如下：

Input: a matrix M with n rows and n columns, where M[i][k] < M[i][j], k < j and 
       M[k][j] < M[i][j], k < i. A given number K

Output: "yes", if number K is in the matrix; otherwise, "no"

binary_search_in_Matrix(int row, int column, int K)

if row > n or column < 0 then

return "no"

if K > M[i][j] then

binary_search_in_Matrix(row+1, column, K)

else if K < M[i][j] then

binary_search_in_Matrix(row, column-1, K)

else

return "yes"

最多2*n次基本操作，所以时间复杂度O(n)

2. 另一个相似的问题是《算法导论》上的作业，题目如下：

When an adjacency-matrix representation is used, most graph algorithms require time , but there are some exceptions. Show that determining whether a directed graph G contains a "universal sink" - a vertex with in-degree |V| -1 and out-degree 0 - can be determined in time , given an adjacency matrix of G.

算法伪代码如下：

Input: an adjacency matrix M of graph G

       an array named flag to remember whether a vertx is universal sink

Output: "yes", if G contains an "universal sink"; otherwise, return "no"

while i < n and j < n

do if M[i][j] == 1 then// i can't be universal sink

     i++

     flag[i] <-- false

     else // j can't be universal sink

     j++

     flag[j] <-- false

时间复杂度分析与上面的问题相似，为O(n)

折腾了好久，始终没有在网上找到解决问题的办法，偶然发现了这篇文章，心中的郁闷终于消除

http://www.cnblogs.com/ghj1976/archive/2011/01/26/1945476.html

可是U盘只读，需要使用sudo才能修改文件，怎样让U盘可读写呢？晚上回去问超哥吧……

接下来解决Ubuntu用不了wifi 的问题，它也折腾我好久了，每次去实验室还得专门找一台电脑上网，然后在笔记本上写程序，很不方便。

PS: 每次需要手动挂载，很不方便，下了usb管理工具，mountmanager可以自动挂载，方便多了

港大CS一年级data structure的作业，模拟“画鬼脚”游戏，编码测试花了三个小时，总算可以交差。在网上搜了下，发现这个简单游戏背后有着不简单的数学原理。

1. 游戏规则

画鬼脚又称画线抽签。是几个人需要用抽签来决定事物或工作的分配时，最简便的方式。进行时只需要一个能够画线的地方或物品就足够了，人数决定了竖线的条数。

在竖线的一端分别写上参与人，将需分配的事物或工作分成与人数的同等分后分别写在另一端。然后在每两个竖线相隔的区域，每个人任意的画上横线。每个人画横线的条数一般不限，但横线间不可交叉且横线不可横跨穿过两个间隔。

从写有自己名字的竖线一端开始，向另一端前进。每当遇上横线时，则沿着横线转弯走向另一根竖线，到达竖线后继续向前最终到达另一端，而这一端所写的事物便是你所抽到的事物。

2. 数学现象

当游戏结束时总是会出现1:1的对应关系，不会有多个人对应同一物品也不会有物品没有人对应。重要的是这个性质在任意条横线情况下均成立

3. 重要性质

a) 排列性

整个游戏过程会将一串输入元素排列变为另一串顺序不同的输出元素的排列

b) 周期性

可以将游戏过程看作对输入元素的变换M，则在对输入元素重复进行有限次变换后，输出元素排列会与输入元素排列相同。即

c) 可逆性

对任意变换M，存在变换，使得M =

d) 等价性

将输入序列变为同一输出序列的变换M的个数是无无限的，它们之间是等价的。那么如何寻找最小数目横线的变换呢？可以参考：http://en.wikipedia.org/wiki/Ghost_Leg

4. 游戏过程模拟

因为添加的横线距离顶端的高度不能相同，可以用链表结构来组织数据，然后设计链表上的游戏算法，整个过程也就显得清晰简单了。C代码可以从GitHub上下载: https://github.com/jia1546/ghostleg

If you want to know more about Linux Commands, refer to the following URLs:

http://www.computerhope.com/unix/overview.htm

http://code.google.com/edu/tools101/linux/basics.html

http://www.linuxguide.it/command_line/

问题描述： 输入一组整数，求出这组数字子序列和中最大值

Jon Bentley’s在《编程珠玑》中给出的算法如下：

input: an array of integers

output: largest sum of contiguous integers in the given array A

Algorithm:

total = 0 // sum of contiguous integers

maxNow = 0 // the max sum up to the current position

for each element A[i] in the given array A

    do total = max(total + A[i], total)

         maxNow = max(maxNow, total)

output maxNow

time complexity : O(n)

这个算法最核心的思想在于：如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优子序列的前缀

但是这个算法存在问题：如果所有整数都是负数，则输出0，显然不对，这个情况下最大序列和应为数组中所有负数的最大值，所以修改原来的算法，加入判断。详细的C代码如下：

C代码如下：

#include <stdio.h>
#include <stdlib.h>

long long max(long a, long b)
{
	long long result;
	result = a > b ? a : b;
	return result;
}

int main()
{
	int n, i;
	long long *array;
	long long maxNow, total;
	long long maxEle, allNegative;
	
	while(scanf("%d", &n) != EOF)
	{
		array = (long long *) malloc(sizeof(long long) * n);
		for(i=0; i<n; i++)
			scanf("%lld", array+i);
			
		maxNow = 0;
		total = 0;
		allNegative = 1;
		maxEle = array[0];
		
		for(i=0; i<n; i++)
		{
			total= max(total+array[i] , 0);
			maxNow = max(maxNow, total);
			maxEle = max(maxEle, array[i]);
			if(array[i] >= 0)
				allNegative = 0;	
		}
		
		if(allNegative)
			printf("%lld\n", maxEle);
		else
			printf("%lld\n", maxNow);
	}
	return 0;
}

1.问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。按顺序输出列者编号

模拟过程，使用循环链表或者数组，但是链表便于删除，效率更高。使用循环链表的C代码如下:

#include <stdio.h>
#include <stdlib.h>

struct node
{
	int value;
	struct node *next;
};
typedef struct node list;

int main()
{
	int n, m;
	int i;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		list *head, *tmp, *pre;
		head = (list*)malloc(sizeof(list));
		head -> value = 1;
		head -> next = NULL;
		tmp = head;
		for(i=2; i<=n; i++)
		{
			list *node = (list*)malloc(sizeof(list));
			node -> value = i;
			node -> next =NULL;
			tmp -> next = node;
			tmp = node; 
		}
		tmp -> next = head;	//link the last to the head
		
		pre = tmp;
		tmp = head;
		while(tmp -> next != tmp)
		{
			for(i=1; i<m; i++)
			{
				pre = tmp;
				tmp = tmp -> next;
			}
			//delete the node to which tmp point to
			pre -> next = tmp -> next;
			printf("%d ", tmp -> value);
			free(tmp);
			tmp = pre -> next;
		}
		printf("%d\n", tmp -> value);
		free(tmp);
	}
	return 0;
}

另一种方法是使用数学方法计算，C代码如下：

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int n, m;
	int i , p;
	int *array, counter;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		i = 0;
		array = (int*)malloc(sizeof(int)*n);
		counter = 0;
		while(++i <= n)
		{
			p = i * m;
			while(p > n)
				p = p - n + (p - n -1)/(m - 1);
			array[counter] = p;
			counter++;
		}
		
		if(counter == 1)
			printf("%d\n", array[0]);
		else
		{
			for(i=0; i<counter-1; i++)
				printf("%d ", array[i]);
			printf("%d\n", array[i]);
		}
		free(array);
	}
	return 0;
}

两种方法的时间复杂度都是O(n)

这道题源于华为校园招聘的机试题，想了很久没有好的解法，google之后发现Manacher's Algorithm可以达到O(n)的复杂度。

这篇文章讲得比较详细：http://www.felix021.com/blog/read.php?2040

C代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1000000

int min(int a, int b)
{
        int result;
	result = a > b ? b : a;
	return result;
}

int main()
{
	char input[MAXSIZE], str[MAXSIZE];
	char *result;
	int p[MAXSIZE];
	int i, j;
	int mx, id;
	int maxlen;
	int pos;
	
	str[0] = '$';
	str[1] = '#';
	while(gets(input))
	{
		memset(p, 0, sizeof(p));
		mx = 0;
		id = 0;
		j = 2;
		for(i=0; i<strlen(input); i++)
		{
			
			str[j] = input[i];
			j++;
			str[j] = '#';
			j++;
		}
		str[j] = '\0';
		
		for(i=1; i<strlen(str); i++)
		{
			p[i] = mx > i ? min(str[2*id-1], mx-i) : 1;
			while(str[i+p[i]] == str[i-p[i]])
				p[i]++;
			if(i+p[i] > mx)
			{
				mx = i + p[i];
				id = i;
			}
		}
		
		maxlen = 0;
		pos = 0;
		for(i=1; i<strlen(str); i++)
			if(p[i] > maxlen)
			{
				maxlen = p[i];
				pos = i;
			}
		
		result = (char*) malloc(sizeof(char)*(maxlen));
		j = 0;
		for(i=pos-(maxlen-1); i<=pos+(maxlen-1); i++)
		{
			if(str[i] != '#')
			{
				result[j] = str[i];
				j++;
			}
		}
		result[j] = '\0';
		
		printf("length of the longest palindrome is %d\n", maxlen-1);
		printf("Palindrome is %s\n", result);	
	}
	return 0;
}

总结:

1. 在字符串中插入'#', 将奇数与偶数长度的回文串统一考虑

2. 使用数组记录已求回文的最右边界，降低时间复杂度到O(n)

给定一个字符串，由小写字母升序排列，且各不相同，输出这个字符串的全排列(字典序)，这个程序会超过一秒，主要是生成全排列部分的算法有问题不能做到输出有序，生成全排列之后不得不使用快速排序，因而会超时。更优化的算法进行中……

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 7

int counter = 0;
char array[1000][MAXSIZE];

int compare(const void *s1, const void *s2)
{
    char *a, *b;
    a = (char*)s1;
    b = (char*)s2;
    return strcmp(a, b);
}

void arrange(char *s, int start, int end)
{
    int i;
    char tmp;
    if(start == end)
    {
	strcpy(array[counter], s);
	counter++;
    }
    else
    {
	for(i=start; i<end; i++)
	{
	    tmp = s[start];
	    s[start] = s[i];
	    s[i] = tmp;
	    arrange(s, start+1, end);
	    tmp = s[start];
	    s[start] = s[i];
	    s[i] = tmp;
	}
    }
}

int main()
{
    char str[MAXSIZE];
    int i;
    while(scanf("%s",str) != EOF)
    {
        counter = 0;
 	arrange(str, 0, strlen(str)); 
        qsort((void*)array, counter, sizeof(char[MAXSIZE]),compare);
        //printf("counter = %d\n",counter);
    	for(i=0; i<counter; i++)
	    printf("%s\n",array[i]);
    }
    return 0;
}