本文共 3295 字，大约阅读时间需要 10 分钟。

1.替换空格

题目要求：请实现一个函数，把字符串中的每个空格替换成"%20",例如输入"We are happy.",则输出"We%20are%20happy."

应用场景：在网络编程中，如果URL参数中含有特殊字符，如空格，“#”等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是"%"后面跟上ASCII码的两位十六位进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如#"的ASCII码为35，即十六进制的0x23，它在URL中被替换成"%23"

（1）时间复杂度为O（n^2）的解法

最直观的的做法是从头到尾扫描字符串，每一次碰到空格字符的时候就做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面对的所有字符都后移两个字节，否则就有两个字符被覆盖。

（2）时间复杂度为O（n）的解法

我们可以先遍历一次字符串，这样就能统计出字符串中空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。

我们从字符串的后面开始复制和替换。首先准备两个指针，P1和P2，P1指向原始字符串对的末尾，而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把P2向前移动3格。

当P1和P2指向同一个位置时，表明所有空格已经替换完毕。

//length为字符数组string的总容量	void ReplaceBlank(char string[],int length) {				if(string==null||length<=0) {			return ;		}				int originalLength=0;//originalLength为字符串string的实际长度		int numberOfBlank=0;//存储空格的数量		int i=0;		while(string[i]!='\0') {			++originalLength;			if(string[i]==' ') {				++numberOfBlank;			}			++i;		}				int newLength=originalLength+numberOfBlank*2;//newLength为把空格替换成'%20'之后的长度		if(newLength>length) {			return ;		}				int indexOfOriginal=originalLength;//原始的数组末尾的指针		int indexOfNew=newLength;//新的数组末尾的指针		while(indexOfOriginal>=0&&indexOfNew>indexOfOriginal) {			if(string[indexOfOriginal]==' ') {				string[indexOfNew--]='0';				string[indexOfNew--]='2';				string[indexOfNew--]='%';			}else {				string[indexOfNew--]=string[indexOfOriginal];			}			--indexOfOriginal;		}	}

2.裴波那契数列

题目要求：写一个函数，输入n，求裴波那契数列的第n项，裴波那契数列的定义如下：

（1）效率很低的解法，挑剔的面试官不会喜欢

解：很多C语言教科书在讲述递归函数的时候，都会用Fibonacci作为例子，因此很多人都能很快的写出如下代码：

long Fibonacci( int n) {		if(n<=0) {			return 0;		}		if(n==1) {			return 1;		}		return Fibonacci(n-1)+Fibonacci(n-2);	}

（2）面试官期待的使用解法

其实改进的方法并不复杂，上述递归代码之所以慢是因为重复的计算太多，我们只要想办法避免重复计算就行了。比如我们可以把已经得到的数列中间项可以保存出来，如果下次需要计算的时候我们先查找一下。更简单的办法是从下往上计算

long Fibonacci(int n) {		int result[]= {0,1};		if(n<2) {			return result[n];		}				long fibNMinusZero=0;		long fibNMinusOne=1;		long fibN=0;		for(int i=2;i<=n;i++) {			fibN=fibNMinusZero+fibNMinusOne;			fibNMinusZero=fibNMinusOne;			fibNMinusOne=fibN;		}		return fibN;	}

3.青蛙走台阶

题目要求：一只青蛙一次可以跳上一级台阶，也可以跳上两个两级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目分析：首先我们考虑最简单的情况。如果只有1个台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳一阶，另外一种是一次跳两阶。

接着我们再来讨论一般情况，我们把n级台阶时的跳法看成是n的函数，记为f(n).当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2).因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2).同第二题。

4.二进制中1的个数

题目要求：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制数是1001，有2位是1.因此如果输入9，该函数输出为2.

（1）可能引起死循环的解法

注意：把整数右移一位和把整数除以2在数学上是等价的，那上面的代码可以把右移运算换成除以2吗？答案是否定的。因为除法的运算比移位运算要低得多，在实际编程中应尽可能地用移位运算符代替除法。

上面的函数如果输入一个负数，如0x80000000，会导致一直做右移运算，最终这个数字会变成0xFFFFFFFF而陷入死循环。

int NumberOf1(int n) {		int count=0;		while(n!=0) {			if((n&1)!=0) {//整数和1做位于运算				count++;			}			n=n>>1;//把整数右移一位和把整数除以2在数学上是等价的		}		return count;	}

（2）常规解法

为了避免死循环，我们可以不右移输入的数字n。首先把n和1做与运算，判断n的最低位是不是为1.接着把1左移一位得到2,，再和n做与运算，就能判断n的次低位是不是1，...这样反复左移，每次都能判断n的其中一位是不是1.

int NumberOf2(int n) {		int count=0;		int flag=1;		while(flag!=1) {			if((n&1)!=0) {				count++;			}			flag=flag<<1;		}		return count;	}

（3）能给面试官带来惊喜的算法

解答：把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.基于这种思路，我们可以写成新的代码。

int NumberOf3(int n) {		int count=0;		while(n!=0) {			count++;			n=(n-1)&count;		}		return count;	}

转载地址：https://codingchaozhang.blog.csdn.net/article/details/79642904 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！