code

http://blog.csdn.net/v_july_v/article/details/6855788 一些答案

<1>微软10.15笔试：对于一个数组{1,2,3}它的子数组有{1,2}，{1,3}{2,3}，{1,2,3}，元素之间可以不是连续的，对于数组{5,9,1,7,2,6,3,8,10,4}，升序子序列有多少个？或者换一种表达为：数组int a[]={5,9,1,7,2,6,3,8,10,4}  。求其所有递增子数组(元素相对位置不变)的个数，   例如：{5，9}，{5，7，8，10}，{1，2，6，8}。

int IncreaseSeg(int * str, int len)  
{  
    int * count = new int[len];  
    int sum=0;  
    if (str==NULL)  
    {  
        return -1;  
    }  
  
    for (int i=0;i<len;i++)  
    {  
        count[i]=0;  
        for (int j=i;j>=0;j--)  
        {  
            if(str[i]>str[j])  
            {  
                    count[i]+=(1+count[j]);  
            }  
        }  
        sum+=count[i];  
    }  
    return sum;  
}

<2> http://www.51nod.com/question/index.html#!questionId=671

七夕那天，雯雯的男朋友小俞给她买了一颗神奇的魔石。这颗魔石平常是暗淡无光的，但只要给这颗魔石擦上魔粉，魔石就会从内部发出不同颜色的绚丽光泽。非常好看。发出的光的颜色，是在魔石上擦的所有魔粉的编号的异或(Xor)值（如果异或值为0，也是一种颜色，异或值相同表示颜色相同）。雯雯手上现在一共有6种魔粉，编号是6 7 17 46 47 56。雯雯非常想知道这颗魔石究竟能发出多少种颜色的光。由于组合实在太多，雯雯便跑过来求助聪明的你，相信你不会让她失望。

如果魔粉有20种（编号256以内），又该如何计算？

(该题转化为求矩阵的秩)

<3>M*M的方格矩阵，其中有一部分为障碍，八个方向均可以走，现假设矩阵上有Q+1节点，从(X0，Y0)出发到其他Q个节点的最短路径。
其中，1<=M<=1000，1<=Q<=100。

(最短路径算法Dijkstra和Floyd-Warshall) 顺道回顾下最小生成树算法Prim ·Kruskal

<4>输入两个整数A和B，输出所有A和B之间满足指定条件的数的个数。指定条件：假设C=8675在A跟B之间，若（8+6+7+5）/ 4 > 7，则计一个，否则不计。
要求时间复杂度：log(A)+log(B)。
<5>已知二叉树的前序遍历：- + a * b - c d / e f

后序遍历：a b c d - * + e f / -

求其中序遍历。

<6>http://blog.csdn.net/v_JULY_v/article/details/6347454

一个字符串S1：全是由不同的字母组成的字符串如：abcdefghijklmn另一个字符串S2：类似于S1，但长度要比S1短。问题是，设计一种算法，求S2中的字母是否均在S1中。

<7>今天10.15下午网易游戏笔试题：给一个有序数组array[n]，和一个数字m，判断m是否是这些数组里面的数的和。

<8>旅行商问题

<9>今天完美10.16笔试题：2D平面上有一个三角形ABC，如何从这个三角形内部随机取一个点，且使得在三角形内部任何点被选取的概率相同。

/*设三角形的三个顶点的向量分别为P0，P1，P2，假设三角形内随机的点为P，那么对于这个线性方程：a * (P1 - P0) + b * (P2 - P0) = P - P0 一定成立。如果方程有解，并且满足a, b >= 0，a + b <= 1，则顶点P在三角形内。对于二维的情况，方程必然有解，只需判断a和b是否在其范围内即可；对于三维的情况，如果方程无解，那说明P不在该三角形所决定的平面上。更多的，如果a + b == 1，则说明P点落在线段P12上，如果a == b == 0，则说明P点和P0点重合，如果a == 0，则说明P在线段P02上，等等~因此我们可以通过构造两个随机数a,b 来获得P点的坐标*/

<10>定义一个宏实现一个整数中偶数比特位与奇数比特位互换

#define SWAP(x) ( (x&0x55555555)<<1 | (x&0xAAAAAAAA)>>1 )

<11>代码改错, 函数foo找错，该函数的作用是将一个字符串中的a-z的字母的频数找出来

void foo(char a[100],int cnt[256])//报错 应为 a[] 或 *a, cnt[] 或 * cnt
{
	memset(cnt ,0, sizeof(cnt));//报错 sizeof(cnt)==4
	while (*a!='\0')
	{
		++cnt[*a]; //报错 当a为汉字时，编码范围超越了0-255 为负数 应在这里做边界检查
		++a;
	}
	for ( char c='a';c<='z';++c)
	{
		printf("%c:%d\n",c,cnt[c]);
	}
}
int main()
{
	char a[100]="百度abc";
	int cnt[256];
	printf("%d\n",sizeof(cnt));// 输出 1024
	foo(a,cnt);
	return 0;

http://blog.csdn.net/v_JULY_v/article/details/6234496

 <12>有一个整数数组，请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。

只能想到排序了。。

<13>利用下一个排列生成全排列，(Find next permuation, POJ 1883)

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

void swap(char& a, char& b)
{
	char tmp=a;
	a=b;
	b=tmp;
}

char* next(char * str, int len)
{
	int i=len-1;
	while(str[i-1]>=str[i] && (i-1)>=0)
	{
		i--;
	}

	if(i==0) return NULL;
	
	int j=len-1;
	while(j>=i&&str[j]=<str[i-1])
	{
		j--;
	}

	//swap i-1 & j
	swap(str[i-1],str[j]);

	//翻转后面的序列
	int pl=i,pr=len-1;
	while(pl<pr)
	{
		swap(str[pl],str[pr]);
		pl++;
		pr--;
	}

	return str;
}

int main()
{
	char t[] ="1234";
	char * a=t;
	int i=0;
	cout<<string(t)<<endl;
	while(1)
	{
		a=next(a,strlen(t));
		if(a==NULL) break;
		cout<<string(a)<<endl;
	}
 return 0;
}

<14>给定一个字符串里面只有"R" "G" "B" 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。
要求：空间复杂度是O(1)，且只能遍历一次字符串。

#include <iostream>
#include <string>
using namespace std;

void swap(char& a, char& b)
{
	char tmp=a;
	a=b;
	b=tmp;
}

/*
* RGBBGRRBRGRBBG
* iR-----i----iB 
* i从头开始扫到iB结束，当为R时，和iR交换,iR++；当为B时，和iB交换，iB--
* 当为G时不变
*/
void RGBSort(char * str, int len)
{
	if(str==NULL) return;
	int iR=0,iB=len-1,i=0;
	while(str[iR]=='R') iR++;//iR内要么是G 要么是B
	while(str[iB]=='B') iB--;//iB内要么是R 要么是G
	i=iR;//只能是 G或B 来判断
	for(;i<=iB;i++)
	{
		if(str[i]=='R')
		{
			swap(str[i],str[iR]);
			iR++;
			i--;
		}
		else if(str[i]=='B')
		{
			swap(str[i],str[iB]);
			iB--;
			i--;
		}
	}
	return;
}

int main()
{
	char t[] ="RGBBGRRBRGRBBG";
	RGBSort(t,strlen(t));
	cout<<string(t)<<endl;
 return 0;
}

<15>只用4行代码编写出一个从字符串到长整形的函数

long str2long(char* str, int len)
{
	long sum=0;
	if(str==NULL) return 0xFFFFFFFF;
	if((len==1))
		return str[0]=='-'?0:str[0]-'0';
	else
		return str[0]=='-'?str2long(str,len-1)*10-(str[len-1]-'0'):str2long(str,len-1)*10+(str[len-1]-'0');
}

int main()
{
	char t[] ="-123";
	cout<<str2long(t,strlen(t))<<endl;
	return 0;
}

<16>有N个数的数组，没有顺序。现在的问题是让你在数组中找出两个数，使得这两个数的和尽可能的接近0。

#include <iostream>
#include <string>
using namespace std;

int abscomp(int a , int b)
{
	return (abs(a)-abs(b));
}

void quicksort(int data[],int s, int t)
{
	if(s>=t) return;

	int i=s,j=t;
	int key = data[s];
	while(i<j)
	{
		//while(data[j]>=key && i<j) j--;
		while(abscomp(data[j],key)>=0 && i<j) j--;
		if(i<j) 
		{
			data[i]=data[j];
			i++;
		}
		//while(data[i]<=key && i<j) i++;
		while(abscomp(data[i],key)<=0 && i<j) i++;
		if(i<j)
		{
			data[j]=data[i];
			j--;
		}
	}
	data[i]=key;
	quicksort(data,s,i-1);
	quicksort(data,i+1,t);
}

int MinTwoSum(int data[],int len)
{
	int minsum=0x7FFFFFFF;// 最大的正整数0x7FFFFFFF 最小的负整数0x80000000
	quicksort(data,0,len-1);
	for (int i=0;i<len-1;i++)
	{
		if(abs(data[i]+data[i+1])<minsum)
			minsum=abs(data[i]+data[i+1]);
	}
	return minsum;
}

//按照绝对值排序，最小的和的绝对值一定是相邻两个数
int main()
{
	int t[] ={-2, 3 , 4,  -7,  9 ,5};
	cout<<MinTwoSum(t,6);
	return 0;
}

<17> 编程实现两个正整数的除法，不能用除法操作符。

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

//x/y
int specialdiv(const int x, const int y) 
{
	if (x<y)
		return 0;
	int tmpx=x;
	int tmpy=y;
	int count=0;
	int res=0;
	while(tmpx>=y)
	{
		tmpy=y;
		count=0;
		while (tmpx>=(tmpy<<1))//tmpx>=y*(2^count)
		{
			tmpy=tmpy<<1;
			count++;
		}
		res+=(1<<count);//res+=(1*2^count)
		tmpx=tmpx-(y<<count);//tmpx - (y*2^count)
	}
	return res;
}

int main()
{
	cout<<specialdiv(2,2);
	return 0;
}

<18>在排序数组中，找出给定数字的出现次数。比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

/** 
* 题目：在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。 
* 解法：使用二分查找的方法分别找出给定数字的开始和结束位置，最坏情况下时间复杂度为O(logn) 
*/
#include<iostream>

int Up(int * data, int len, int x)
{
	int i=0,j=len-1;
	int m;
	if(len==1) return (x==data[0]);

	while(i<j)
	{
		m=(i+j)/2;
		if(data[m]>=x)
		{
			j=m-1;
		}
		else
		{
			i=m+1;
		}
	}
	if(data[i]==x)
		return i;
	else if (data[i+1]==x)
		return i+1;
	else return -1;
}

int Down(int * data, int len, int x)
{
	int i=0,j=len-1;
	int m;
	if(len==1) return (x==data[0]);

	while(i<j)
	{
		m=(i+j)/2;
		if(data[m]>x)
		{
			j=m-1;
		}
		else if (data[m]<=x)
		{
			i=m+1;
		}
	}
	if(data[j]==x)
		return j;
	else if (data[j-1]==x)
		return j-1;
	else return -1;
}

int main()
{
	int arr3[] = {0,1,1,2,2,2,2,4,4,4};
	int arr2[] = {0,1,1,1,1,2,3,4,4,4};
	int arr[] = {3,2,2,2,2,2,2,2,2,2};
	std::cout<<Up(arr,10, 2)<<", "<<Down(arr,10,2);
    return 0;
}

<19> O(n) 求 最长回文子串 ref:http://www.cnblogs.com/wuyiqi/archive/2012/06/25/2561063.html

#include<iostream>
#define MIN(x,y) (x<y?x:y)
int Palindrome(char * src, int len)
{
	if(src==NULL)
		return 0;

	if(len==1)
		return 1;

	//preprocess insert '#' into each space between two characters and front & end. such "abc" -> "#a#b#c#"
	//make the str an odd palindrome
	//and insert a '$' into front of str
	int newlen=len*2+2;
	char * str = new char[newlen];
	int * p = new int[newlen]();
	str[0]='$'; str[newlen-1]='#';
	for (int i=0;i<len;i++)
	{
		str[i*2+1]='#';
		str[i*2+2]=src[i];
	}

	//充分利用回文的对称性，若i,j (假设i>j)是关于中心节点mrc是左右对称的，
	//那么其i的回文长度
	//<1>要么和j是一样的，
	//<2>要么没有j大(此时至少为most_right - i);
	//<3>要么比j大，
	//但是由于后面的元素存在诸多不确定性，因此我们还是需要进一步验证，执行while语句
	int most_right = 0;
	int mrc=0;//most_right_center
	for (int i=1;i<newlen;i++)
	{
		if(i<most_right)
		{
			p[i]=MIN(p[mrc-(i-mrc)],most_right-i);
		}
		else
			p[i]=1;
		
		while(str[i-p[i]]==str[i+p[i]]) p[i]++;
		if(i+p[i]>most_right)
		{
			most_right = i+p[i];
			mrc = i;
		}
	}

	//遍历p，找到半径的最大值；去掉#，乘以2
	int longest_palindrome=1;
	for (int i=1;i<newlen;i++)
	{
		if(p[i]>longest_palindrome) longest_palindrome = p[i];
	}
	return longest_palindrome-1;
}

int main()
{
	char t[]="waabwswfd";
	std::cout<<Palindrome(t,strlen(t));
    return 0;
}

<20> 输入一个链表的头结点，从尾到头反过来输出每个结点的值。

struct ListNode
{
  int  m_nKey;
  ListNode* m_pNext;
};

void InverseOutput(ListNode * head)
{
	if(head->m_pNext==NULL)
	{
		cout<<(head->m_nKey)<<endl;
	}
	else
	{
		InverseOutput(head->m_pNext);
		cout<<(head->m_nKey)<<endl;
	}
}

<21> 最大公约数gcd Greatest Common Divisor 最小公倍数 lcm Least Common Multiple 辗转相除法

//最大公约数
int _gcd(int a, int b)
{
	if(b>0)
	{
		_gcd(b,a%b);
	}
	else
	{
		return a;
	}
}

//最小公倍数
int _lcm(int a, int b)
{
	return a*b/_gcd(a,b);
}

<22>  字符串匹配实现 KMP 不回溯算法: http://blog.csdn.net/v_JULY_v/article/details/6545192

#include<iostream>
using std::cout;
using std::endl;

/*
next
* 0  1  2  3  4  5
* a  b  c  a  b  e
* -1 0  0  -1 0  2
*-------------------
* a  a  a  a  a  a
* -1 -1 -1 -1 -1 -1
*/
void GetNext(char * str, int * next,int len)
{
	if(str==NULL) return;
	next[0]=-1;
	int j=-1;
	int i=0;
	while(i<len-1)
	{
		if(j==-1||str[i]==str[j])
		{
			i++;
			j++;
			if(str[i]!=str[j])
			{
				next[i]=j;
			}
			else
			{
				next[i]=next[j];
			}
		}
		else
			j=next[j];
	}
}

int kmp(char* str, char* pat, int* next, int strlen, int patlen)
{
	int i=0,j=0;
	while(i<strlen&&j<patlen)
	{
		if(str[i]==pat[j]||j==-1)
		{
			i++;j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j==patlen)
	{
		return i-j;
	}
	else
		return -1;
}

int main()
{
	char str[]="abcadbccccabcabeba";
	char pat[]="abcabe";
	int next[6];
	GetNext(pat,next,6);
	cout<<kmp(str,pat,next,strlen(str),strlen(pat));
    return 0;
}

<23>