时间复杂度为O(n),空间复杂度为O(1)的字符串去空格

 #include<stdio.h>
 void fun(char * a )
{
 int b = 0 ,c =0 ;
 for ( c = 0; a != '\0'; c++)
 {
if (a != ' ')
 {
 if ( c != b)
 {
 a[b] = a;
 }
 b++;
 }
 }
a[b] = 0;
 }
 int main()
 {
 char a[] = "i have a dream!"; 

 printf("a = %s \n",a);
 fun(a);

 printf("a = %s \n",a);

}

2进制数字求1的个数

算法课程整理

求1的个数:

给定一个32位,2进制的unsigned int N,求N二进制中1的个数。

显然,该问题可以通过不断右移动N,并且判断当前数字最低位是否为1,直到整数为0,即可。平均情况需要16次移动,以及16次加法。

int CountOne (int n)

{

int num =0;

while(n ){

num += (n&1);

n>>=1;

return num;

}

}

思路二:

用N与N-1做位与,每次把最低位清0,即可;

int CountOne(int n)

{

int num = 0;

while (n){

n &= (n-1);

num++;

}

}

 

字符串的旋转

一个题目:给定字符串,要求把字符串前面的若干字符移动到字符串的尾部,例如:字符串“abcdef”,前三个字符’a’,’b’,’c’移动到字符串的尾部,字符串变成”defabc”,用函数实现。

一般最先想到的办法是将需要移动的字符一个个的移动到字符串的尾部(开始的时候,我这个都没有想到–!,基础差到无边无际)

一:定义一个指向字符串的指针s,字符长度为n书写函数。

void moveone(char *s,int n)

{

char t =s [0];

int i = 0;

for (i  =1 ;i < n; i++){

s[i – 1] = s[i];

}

s[n -1] = t;

}

然后调用m次moveone函数,使得字符串开头的m个字符移动到字符串尾部:

void  formoveone( char *s,int n, int m)

{

while(m–){

moveone(s,n);

}

}

这样就完成了将若干字符移动到字符串尾部了。但是这种方法对于长度为n的字符串来说,移动m个字符,一共进行了m*n此操作,并且用了一个字符保存变量,所以时间复杂度为(m*n),空间复杂度为O(1)。手动执行了一把程序,运行时间还是比较长。

进一步思考:如何降低时间复杂度。

如果把需要移动的字符和不需要移动的字符分成两部分,比如分为abc,def,分别反转,最后对整个字符串进行反转,这样也可以达到移动字符串的目的。反转第一部分abc,为cba,在反转def为fed,整体字符串变为cbafed,进而继续反转整个字符串得到defabc,就实现了字符串的反转。

解法:

void  fun( char *s ,int from,int to)

{

while(from < to ){

char t = s[from];

s[from ++] = s[to];

s[to–]=t;       }

}

void formovestring(char *s, int n,int m)

{

m%=n;

fun(s,0,m-1);

fun(s,m,n-1);

fun(s,0,n-1);

}

再来看代码,时间复杂度为O(n),空间复杂度为O(1);俗称”三步反转“得到结果。

该题目以及步骤均来自July《编程之法》