算法(初级):字符串

2021年8月14日 21:41 阅读 1.09k 评论 0

替换空格

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

点击前往牛客在线练习此题:替换空格

输入: "We Are Happy"

返回值: "We%20Are%20Happy"

算法分析: 这个想必都不需要分析,看到题的第一眼我们就知道这道题遍历去替换就可以了,其实难的不在于思路而是怎么去替换

首先给出Python3的代码,对于动态语言来说此题so easy

class Solution: 
    def replaceSpace(self , s ): 
        return_s = '' 
        for i in s: 
            if i == ' ': 
                i = '%20' 
            return_s += i 
        return return_s        

很简单,把空格替换后加到新的字符串里即可

C就有些不一样了

char* replaceSpace(char* s ) { 
    int s_length = strlen(s); 
    int spaceNum = 0; 
    int i = 0; 
    while(s[i] != '\0'){ 
        if(s[i] == ' '){ 
            spaceNum ++; 
        } 
        i++; 
    } 
    int new_length = s_length + spaceNum; 
    char *new_s = (char*)malloc(sizeof(char)*new_length); 
    i = 0; 
    int j=0; 
    while(s[i] != '\0'){ 
        if(s[i] == ' '){ 
            new_s[j++] = '%'; 
            new_s[j++] = '2' ; 
            new_s[j++] = '0'; 
        }else{ 
            new_s[j++] = s[i]; 
        } 
        i++; 
    }  
    new_s[j] = '\0'; 
    return new_s; 
} 

首先获取字符串s的长度,然后遍历一遍字符串,数出空格的个数,然后创建新的字符串空间,大小为原来的长度+空格个数,再次遍历s字符串,当碰到空格时将其替换放到新的字符串空间即可

第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)

点击前往牛客在线练习此题:第一个只出现一次的字符

输入: "google" 返回值:4

算法分析: 毫无疑问,这题需要用到哈希表,key为字符,value为字符出现个数,完事后找到第一个value为1的字符返回其索引即可

class Solution: 
    def FirstNotRepeatingChar(self, s): 
        d = {} 
        for i in s: 
            if not d.get(i): 
                d[i] = 1 
            else: 
                d[i] += 1 
        for i in range(len(s)): 
            if d[s[i]] == 1: 
                return i 
        return -1  

用Python的字典轻松解决

最后修改于2021年8月28日 22:40
©允许规范转载

版权声明:如无特殊说明,文章均为本站原创,转载请注明出处

本文链接:https://www.yangyingqi.com/53.html

字符串
微信
支付宝
登录后即可进行评论/回复