面试题 -- 字符串替换空格

港控/mmm° 2022-08-25 02:10 175阅读 0赞

![SouthEast][]

以下代码在vs2010测试通过：

/**
    * 解题思路：
    *	方法-：从头开始遍历数组，遇到一个空格替换一个空格，这样每一次空格后面的字符都需要移动，
    		假设字符串长度为n，空格数为n，则时间复杂度为：o（n^2）。
    	方法二：先算出字符串的空格数，替换之后字符串的新的长度是length+blankNumber*2
    		然后从字符串的结尾开始移动字符，遇到空格直接替换，则所有字符只移动一次，便可以替换所有空格，
    		其时间复杂度为：o（n）
    	方法二的代码如下：
    */
    #include "stdafx.h"
    #include "stdlib.h"
    #include "stdio.h"
    #include "string.h"
    
    void replaceBlank(char str[]);
    int _tmain(int argc, _TCHAR* argv[]){
    	char str[50] = "I am a student.";
    	printf("before replace:\n");
    	printf("%s",str);
    	replaceBlank(str);
    	printf("\nafter replace:\n");
    	printf("%s",str);
    	system("pause");
    	return 0;
    }
    void replaceBlank(char str[]){
    	int i=0;
    	int length;
    	int blankNumber = 0;
    	int originalLength,newLength;
    
    	length = strlen(str);
    	while(str[i] != '\0'){
    		if(str[i] == ' '){
    			blankNumber ++ ;
    		}
    		i++;
    	}
    	originalLength = length;
    	newLength = originalLength + blankNumber*2;
    
    	while(originalLength >= 0 && newLength > originalLength ){
    		if(str[originalLength] == ' '){
    			str[newLength--] = '0';
    			str[newLength--] = '2';
    			str[newLength--] = '%';
    		}else{
    			str[newLength--] = str[originalLength];
    
    		}
    		originalLength-- ;
    	}
    
    }

举一反三：

有两个排序的数组A1和A2，内存在A1的末尾有足够多的空间容纳A2。实现一个函数，把A2中所有数字插入到A1中并且所有的数字是排序的。

/**
    *解题思路：
    *	得到数组A1中可用的数字的长度length1，
    *	得到数组A2的长度length2，
    *	得到这两个值的长度 length = length1+length2，
    *	从两个数组的末尾开始比较两个数组的大小，所有的元素都只有移动一次，
    *	其时间复杂度为：o（n）
    */
    #include "stdafx.h"
    #include "stdlib.h"
    #include "stdio.h"
    #define LARRLENGTH 20
    #define SARRLENGTH 4
    
    void mergeArray(int larr[],int larrLength,int larrbeginLength,int sarr[],int sarrLength);
    int _tmain(int argc, _TCHAR* argv[]){
    	int larrbeginLength = 4; //表示数组larr初始化时输入的数字个数
    	int larr[LARRLENGTH] = {0,3,6,8,13};
    	int sarr[SARRLENGTH] = {1,7,10,18};
    
    	mergeArray(larr,LARRLENGTH,larrbeginLength, sarr,SARRLENGTH);
    
    	printf("after merge:\n");
    	for(int i = 0;i < larrbeginLength+SARRLENGTH ; i++){
    		printf("%3d",larr[i]);
    	}
    	system("pause");
    	return 0;
    }
    /*
    *参数介绍：
    *	larr 是数组，
    *	larrLength 是larr的数组长度
    *	larrbeginLength 是larr初始化的数字长度
    *	sarr 是数组
    *	sarrLength 是sarr的数组长度
    */
    void mergeArray(int larr[],int larrLength,int larrbeginLength,int sarr[],int sarrLength){
    	int i = 0 ;
    	int length;
    
    	length = larrbeginLength + sarrLength; //两个数组初始化的可用数字的长度
    	if(length > larrLength){
    		exit;
    	}
    
    	int larr_subscript,sarr_subscript,length_subscript;
    	larr_subscript = larrbeginLength-1;
    	sarr_subscript = sarrLength -1 ;
    	length_subscript = length-1;
    	
    	while(larr_subscript >= 0 || sarr_subscript >= 0 ){
    		if(larr[larr_subscript] > sarr[sarr_subscript]){
    			larr[length_subscript--] = larr[larr_subscript--];
    		}else{
    			larr[length_subscript--] = sarr[sarr_subscript--];
    		}
    	
    		if(sarr_subscript < 0){
    			larr[length_subscript--] = larr[larr_subscript--];
    		}
    		if(larr_subscript < 0){
    			larr[length_subscript--] = sarr[sarr_subscript--];
    		}
    		
    	}	
    }

[SouthEast]: /images/20220824/e99c3839f1de4ae3a6b8c18c0b955143.png