常见小问题(待更新)1、求一组数中第K大或第K小的数2、求N的阶乘十进制数最后有多少个03、KMP(字符串模式匹配)4、二叉树建立与遍历5、求一个数组中连续子数组和最大或乘积最大6、约瑟夫环问题7、从n个数中等概率取m个数8、快速求（n^p)%m9、数组中求出现奇数次或一次的数10、求2000000以内的素数

1、求一组数中第K大或第K小的数

思路：使用快速排序

#include <iostream>
#include <ctime>

using namespace std;

const int ARRAY_LEN = 100;
int iarray[ARRAY_LEN];

int divide(int low, int high)
{
	if(low>=high)return low;

	int pvoit = iarray[low];
	while (low<high)
	{
		while (iarray[high]>=pvoit&&low<high)
		{
			high--;
		}
		if(low<high)
		{
			iarray[low] = iarray[high];
			low++;
		}
		while (iarray[low]<=pvoit&&low<high)
		{
			low++;
		}
		if(low<high)
		{
			iarray[high] = iarray[low];
			high--;
		}
	}

	iarray[low] = pvoit;

	return low;
}

int myQsort(int low, int high, int k)
{
	int mid = divide(low, high);
	int res;
	if(k<mid)
		res = myQsort(low, mid-1, k);
	else if(k>mid)
		res = myQsort(mid+1, high, k);
	else
	{
		res = mid;
	}
	return res;
}

int main()
{
	srand(time(NULL));

	//for(int j=0; j<1000; ++j)
	{
		for(int i=0; i<20; ++i)
		{
			iarray[i] = rand()%100;
		}

		int k = 3;
		//int index = myQsort(0, 19,20-k);//寻找第k大的数(从1计数)
		int index = myQsort(0, 19, k-1);//寻找第K小的数(从1计数）

		cout << index << endl;
		cout << iarray[index] << endl;

	}

	system("pause");
	return 0;
}

2、求N的阶乘十进制数最后有多少个0

思路：num = N/5 + N /(5*5) + N/(5*5*5).....知道N/(5的K次方)等于0, 求1-n能分解出多少5(2*5==10而2的个数明显多于5）

 
#include <iostream>

using namespace std;

int main()
{
	int n;
	int num=0;
	
	while(cin>>n&&n)
	{
		num=0;	
		while(n)
		{
	    	n /= 5;
			num += n;
		}
		 
		cout << num << endl;
	}
	return 0;
}

3、KMP(字符串模式匹配)

KMP算法保证了在模式串和主字符串匹配时，主字符串不 回溯，其主要思想就是寻找模式字符串中当前字符前面邻近的字符与模式串开头有多少个是匹配的，如下式：

注：字符串下标从0开始

完整的代码：

#include <iostream>

using namespace std;

void getNext(char* T, int next[])
{
	int i = 0;
	int j = -1;
	int len = strlen(T);
	next[0] = -1;
	
	while (i<len-1)
	{
		if(-1==j || T[i]==T[j])
		{
			++i;
			++j;
			if(T[i]!=T[j])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
			}
		}
		else
		{
			j = next[j];
		}
	}
}

int KMP(char* S, char* T, int pos, int next[])
{
	int i = pos;
	int j = -1;
	int lenS = strlen(S);
	int lenT = strlen(T);

	while (i<lenS && j <lenT)
	{
		if(-1==j || S[i]==T[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}
	if(j==lenT)
		return (i-lenT);

	return -1;
}

int main()
{
	char str1[] = "acabaabaabcacaabc";
	char str2[] = "abaabc";
	int next[100];

	getNext(str2, next);
	cout << KMP(str1, str2, 0, next) << endl;

	system("pause");
	return 0;
}

4、二叉树建立与遍历

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

typedef struct _BiTree
{
	char val;
	_BiTree* lchild;
	_BiTree* rchild;
}*BiTree, BiNode;

//注意指针本身是一个变量，因此这里需要加上&，
//（若不加T的值在返回被调函数时不发生变化，发生变化的仅是指针存放的那个地址里面所存放的值）
bool CreateBiTree(BiTree& T)
{
	char ch;
	scanf("%c", &ch);
	if('*' == ch)
	{
		T = NULL;
	}
	else
	{
		if(!(T=(BiNode*)malloc(sizeof(BiNode))))
		{
			exit(0);
		}
		T->val = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}

	return true;
}

//以下三个函数实现非递归先、中、后遍历二叉树
bool PreOrderTraverse(BiTree T)
{
	stack<BiNode*> S;
	BiNode* p = T;
	while (p || !S.empty())
	{
		if(p)
		{
			cout << p->val << " ";
			S.push(p);
			p = p->lchild;
		}
		else
		{
			p = S.top();
			S.pop();
			p = p->rchild;
		}
	}

	cout << endl;
	return true;
}

bool InOrderTraverse(BiTree T)
{
	stack<BiNode*> S;
	BiNode* p = T;
	while (p || !S.empty())
	{
		if(p)
		{
			S.push(p);
			p = p->lchild;
		}
		else
		{
			p = S.top();
			S.pop();
			cout << p->val << " ";
			p = p->rchild;
		}
	}
	cout << endl;
	return true;
}

int dep = 0;
bool PastOrderTraverse(BiTree T)
{
	stack<BiNode*> S;
	BiNode* p = T;
	BiNode* pre = NULL;
	while (p || !S.empty())
	{
		if(p)
		{
			S.push(p);
			p = p->lchild;
		}
		else
		{
			p = S.top();
			if(p->rchild!=NULL&&pre!=p->rchild)//第二个条件保证P的右孩子没有访问过
			{
				p = p->rchild;
			}
			else
			{
				if(dep<S.size())//可以顺便求取二叉树的深度
				{
					dep = S.size();
				}
				S.pop();
				pre = p;
				cout << p->val << " ";
				p = NULL;//已经输出了这个元素，需要再退一个栈因此p设为NULL
			}
		}
	}
	cout << endl;
	return true;
}

//递归获取二叉树的深度（非递归方法可以通过非递归后序遍历法获得）
int GetBiTreeDepth(BiTree T)
{
	if(NULL==T)
	{
		return 0;
	}

	int lDepth = GetBiTreeDepth(T->lchild);
	int rDepth = GetBiTreeDepth(T->rchild);

	return ((lDepth>rDepth) ? (lDepth+1) : (rDepth+1));
}

//求二叉树的宽度(广度遍历的过程)
int GetWidth(BiNode *pRoot)
{
	if (pRoot == NULL)
	{
		return 0;
	}

	int nCurLevelWidth = 1;   //记录当前层的宽度(初始化为根那一层为1)
	int nWidth = 1;           //二叉树的宽度(初始化为根那一层为1)
	queue<BiNode *> myQueue;
	myQueue.push(pRoot);      //将根节点入队列
	
	BiNode *pCur = NULL;

	while (!myQueue.empty())//队列不空
	{
		for(int i=0; i<nCurLevelWidth; ++i)
		{
			pCur = myQueue.front();  //取出队列头元素
			myQueue.pop();

			if (pCur->lchild!= NULL)
			{
				myQueue.push(pCur->lchild);
			}

			if (pCur->rchild != NULL)
			{
				myQueue.push(pCur->rchild);
			}

		}

		nCurLevelWidth = myQueue.size();
		nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;
	}

	return nWidth;
}


int main()
{
	BiTree T = NULL;
	CreateBiTree(T);

	PreOrderTraverse(T);
	InOrderTraverse(T);
	PastOrderTraverse(T);
	cout << dep << endl;

	cout << "Depth = " << GetBiTreeDepth(T) << endl;
	cout << "Width = " << GetWidth(T) << endl;

	system("pause");
	return 0;
}

输入样例：ABC**DE*G**F***

5、求一个数组中连续子数组和最大或乘积最大

#include<stdio.h>
#include <string.h>
#include <Windows.h>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
	double maxSum(vector<double> arr)
	{
		if(0==arr.size())
			return 0;
		double subSum = arr[0];
		double tmp = arr[0];
		for(int i=1; i<arr.size(); ++i)
		{
			if(tmp>0)
			{
				tmp += arr[i];
			}
			else
			{
				tmp = arr[i];
			}
			if(tmp>subSum)
			{
				subSum = tmp;
			}
		}

		return subSum;
	}
	double maxProduct(vector<double> arr) {
		if(0==arr.size())
			return 0;

		double minPre = arr[0];
		double maxPre = arr[0];
		double maxProuct = arr[0];
		double minCur, maxCur;

		for(int i=1; i<arr.size(); ++i)
		{
			maxCur = gmax(arr[i], gmax(arr[i]*maxPre, arr[i]*minPre));
			minCur = gmin(arr[i], gmin(arr[i]*maxPre, arr[i]*minPre));

			if(maxCur>maxProuct)
			{
				maxProuct = maxCur;
			}
			maxPre = maxCur;
			minPre = minCur;
		}

		return maxProuct;
	}
private:
	double gmax(double x, double y)
	{
		if(x>y)
		{
			return x;
		}
		else
		{
			return y;
		}
	}
	double gmin(double x, double y)
	{
		if(x<y)
		{
			return x;
		}
		else
		{
			return y;
		}
	}
};

int main(void)
{
	double darr1[] = {-0.1};
	vector<double> vec;
	vec.push_back(-0.1);
	Solution sol;
	cout << sol.maxProduct(vec) << endl;
	
	system("pause");
	return 0;
}

6、约瑟夫环问题

#include <iostream>

using namespace std;

int main()
{
	int n, m;
	while(cin>>n>>m)
	{
		int s = 0;
		for(int i=2; i<=n; ++i)
		{
			s = (s+m)%i;
		}
		cout << s+1 << endl;
		
		s = 1; //当我们把初始值设为1时要特别注意等于0的情况，其实是最后一个元素 
		for(int i=2; i<=n; ++i)
		{
			s = (s+m)%i;
			if(s==0)s=i;
		}
		if(s==0)cout << n << endl;
		else cout << s << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()
{
	int n, m, k;
	while(cin>>n>>m>>k)
	{
		int s = 0;
		for(int i=2; i<=n; ++i)
		{
			s = (s+m)%i;
		}
		s = (s+k-1)%n;
		cout << s+1 << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()
{
	int n, m, k;
	while(cin>>n>>m>>k)
	{
		int s = 0;
		for(int i=2; i<=n; ++i)//无论哪种变种，都是在编号为0到n-1中先找到那个元素然后再变回到1到n中
		{
			s = (s+m)%i;
		}
		s = (s+(k-m+n))%n;
		cout << s+1 << endl;
	}
	return 0;
}

约瑟夫环总结：对于n个数数到m，都是先变换到0,1,..., n-2,n-1, 每次从0开始数数到m-1，得到这个数列的最终解，然后再映射到此数列的变种上，然后再+1映射回1,2,3,...,n上。

7、从n个数中等概率取m个数

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
	int n, m;
	while(cin>>n>>m)
	{
		int radix = n;
		int tm = m;
		for(int i=0; i<n; ++i)
		{
			if(rand()%radix < tm)
			{
				cout << i << " ";
				tm--;
			}
			radix--;
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
	int array[10] ={0,1,2,3,4,5,6,7,8,9};
	int size = 10;
	for(int i=0; i<size; ++i)
	{
		swap(array[i], array[i+rand()%(size-i)]);
	}
	
	for(int i=0; i<size; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	return 0;
}

8、快速求（n^p)%m

int GetNPowerModM(int n, int p, int m)
{
	unsigned k = 1;
	n %= m;
	while(p!=1)
	{
		if(p&1)k = (k*n)%m;
		n = (n*n)%m;
		p >>= 1;
	}

	return (n*k)%m;
}

#include <iostream>

using namespace std;

int array[] = {1,1,2,3,3,4,4,5,5,6,6,7,8,8};

int lowbit(int n)  //求二进制最后一个1的位置，比如0110100的结果为0000100 
{
	return (n&(-n));
}

int main()
{
	int len = sizeof(array)/sizeof(array[0]);
	int x = 0;
	for(int i=0; i<len; ++i)
	{
		x ^= array[i];
	}
	
	int x_lowbit = lowbit(x);
	int a = 0, b = 0;
	for(int i=0; i<len; ++i)
	{
		if(x_lowbit&array[i])
		{
			a ^= array[i];
		}
		else
		{
			b ^= array[i];
		}
	}
	cout << a << " " << b << endl;
	
	return 0;
}

#include <iostream>

using namespace std;

int array[] = {1,1,2,3,3,4,5,5,6,6,7,8,8};

int lowbit(int n)  //求二进制最后一个1的位置，比如0110100的结果为0000100 
{
	return (n&(-n));
}

int main()
{
	int len = sizeof(array)/sizeof(array[0]);
	int x = 0;
	for(int i=0; i<len; ++i)
	{
		x ^= array[i];
	}
	
	int y = 0;
	for(int i=0; i<len; ++i)
	{
		y ^= lowbit(x^array[i]);
	}
	
	int y_lowbit = lowbit(y);
	int xa = 0, bc = 0;
	for(int i=0; i<len; ++i)
	{
		if(y_lowbit&(x^array[i]))
		{
			xa ^= (x^array[i]);
		}
		else
		{
			bc ^= (x^array[i]);
		}
	}
	
	int a = x^xa;
	int b = 0;
	int c = 0;
	
	int bc_lowbit = lowbit(bc);
	if(a&bc_lowbit)
	{
		b ^= a;
	}
	else 
	{
		c ^= a;
	}
	
	for(int i=0; i<len; ++i)
	{
		if(bc_lowbit&array[i])
		{
			b ^= array[i];
		}
		else 
		{
			c ^= array[i];
		}
	}
	
	cout << a << " " << b << " " << c << " " << endl;
	
	return 0;
}

#include <iostream>

using namespace std;

int array[] = {1,1,1,3,3,3,4,5,5,5,8,8,8};

int main()
{
	int len = sizeof(array)/sizeof(array[0]);
	
	int ones = 0;
	int twos = 0;
	int mask = 0;
	
	for(int i=0; i<len; ++i)
	{
		//当前数array[i]各个二进制位上的与以往累积ones各个位上
		//若同时为1则说明此位到目前位置1的个数为2个
		twos ^= (ones&array[i]); 
		//把array[i]中新增出现一次的加到ones中  
		ones ^= array[i];
		//若ones与twos二进制某位同时1则为3的倍数清零 
		mask = ~(ones&twos);
		twos &= mask;
		ones &= mask;
	}
	cout << ones << endl;//若是求出现两次的数则输出twos
	
	return 0;
}

#include <iostream>

using namespace std;

int array[] = {1,1,1,1,1,4,4,4,4,5,5,5,5,5};

int main()
{
	int len = sizeof(array)/sizeof(array[0]);
	
	int ones = 0;
	int twos = 0;
	int threes = 0;
	int mask = 0;
	
	for(int i=0; i<len; ++i)
	{
		threes ^= (twos&ones&array[i]); 
		twos ^= (ones&array[i]);
		ones ^= array[i];
		mask = ~(ones&~twos&threes);
		threes &= mask;
		twos &= mask;
		ones &= mask;
	}
	cout << threes << endl; //4的二进制位0100它有1的为是在右起第三个上因此输出threes
	
	return 0;
}

10、求2000000以内的素数

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int MAX_SIZE = 2000001;
int primes[15000];
bool total[MAX_SIZE];

void compute()
{
	total[0] = total[1] = true;
	int t = sqrt(MAX_SIZE);
	int k = 0;
	for(int i=2; i<t; ++i)
	{
		for(int j=i*i; j<MAX_SIZE; j+=i)
		{
			total[j] = true;
		}
		
	}
	
	for(int i=2; i<MAX_SIZE; ++i)
	{
		if(!total[i])
		{
			primes[k++] = i;
		}	
	}
}

int main()
{
	int N;
	compute();
	while(scanf("%d", &N) && N)
	{
		if(primes[0]<=N)
		{
			printf("%d", primes[0]);
		}
		for(int i=1; primes[i]<=N; ++i)
		{
			printf(" %d", primes[i]);
		}
		printf("n");
	}
	return 0;
}

 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <ctype.h>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
bool nPrime[2000001];
int prime[148940],tot = 0;
void getPrime(){
    int i,j;
    LL temp;
    for(i = 2; i < 2000001; i++){
        if(!nPrime[i]) prime[tot++] = i;
        //若i是素数则j会增加到tot,也即让i与已经求出的每一个素数相乘
		//若i是合数，那么只需找到i%prime[j]即可，因为其后的可以通过是prime[j+1]的倍数求 
        for(j = 0; j < tot && (temp = (LL)i*prime[j]) < 2000001; j++){
            nPrime[temp] = true;
            if(i%prime[j] == 0) break; //prime[j]是i的最小素因子时结束循环
        }
    }
}
int main(){
    getPrime();
    int kase,x,i;
    while(scanf("%d",&x),x){
        for(i = 0; prime[i] <= x && i < tot; i++)
            printf("%d ",prime[i]);
        putchar('n');
    }
    return 0;
}
        

注：以上代码均是在Win7+VS2012环境中运行

最后

以上就是贪玩冰淇淋最近收集整理的关于常见小问题(待更新)1、求一组数中第K大或第K小的数2、求N的阶乘十进制数最后有多少个03、KMP(字符串模式匹配)4、二叉树建立与遍历5、求一个数组中连续子数组和最大或乘积最大6、约瑟夫环问题7、从n个数中等概率取m个数8、快速求（n^p)%m9、数组中求出现奇数次或一次的数10、求2000000以内的素数的全部内容，更多相关常见小问题(待更新)1、求一组数中第K大或第K小内容请搜索靠谱客的其他文章。