你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

[解题报告](第23讲) 字符串算法(三) - 字符串分割

2021-11-12 19:43:31

 

零、写在前面

         这是打卡的第二十三天,今天题目难度有点狠啊,主要知识点在

《算法零基础100讲》(第23讲) 字符串算法(三) - 字符串分割icon-default.png?t=LA92https://blog.csdn.net/WhereIsHeroFrom/article/details/120875827


一、主要知识点

        1.字符串的切分

        英雄哥给的思路是用一个二维字符组去保存新的串,我发现也可以用一个字符指针数组拆分,更简单一些。其实思路很简单,

  1. 当第一次遇到不是分割字符的时候保存相应的地址
  2. 首次遇到分隔符时将其置为结束符 即变成0
    int size = 0;//记录大小
    char *ans[1000];//记录每个串首地址
    bool flag = true;    //标识是否第一次
    int i = 0;
    while(s[i] == ' ') i++;//跳过第一次的分隔符
    ans[size++] = &s[i];//插入第一个字符串
    for(;s[i];++i){    //继续查找拆分
        if(s[i] == ' '&&flag = true){//第一次遇到分隔符
            s[i] = 0;
            flag = true;
        }
        if(s[i] != 0 &&flag){    //第一次遇到非分隔符
            flag = false;
            ans[size]++ = &s[i];
        }
    }

二、课后习题 

58. 最后一个单词的长度

58. 最后一个单词的长度icon-default.png?t=LA92https://leetcode-cn.com/problems/length-of-last-word/

思路

根据分隔符保存最后一个单词的位置,将后面修改为结束符,返回最后一个 单词的长度。

int lengthOfLastWord(char * s){
    int ans;
    bool flag = true;
    for(int i = 0;s[i];++i){
        if(s[i] == ' '){    //这里是把空格全干成0了
            s[i] = 0;
            flag = true;
        }
        if(s[i] != 0 &&flag){//第一此遇到非分隔符。拆分保存
            flag = false;
            ans = i;    //保存的是最后一个单词首字符
        }
    }
    return strlen(&s[ans]);//返回最后一个单词的长度
}

结果分析

可还满意?


434. 字符串中的单词数

434. 字符串中的单词数icon-default.png?t=LA92https://leetcode-cn.com/problems/number-of-segments-in-a-string/

思路

拆分之后,返回个数就好了?

int countSegments(char * s){
    bool flag = true;
    int ans = 0;    //统计个数
    for(int i = 0;s[i];++i){
        if(s[i] == ' '){//遇到分隔符拆分
            s[i] = 0;
            flag = true;
        }
        if(s[i] != 0 &&flag){//第一次遇到非分隔符,统计
            flag = false;
            ans ++;
        }
    }
    return ans;
}

结果分析

可以了


2042. 检查句子中的数字是否递增

2042. 检查句子中的数字是否递增icon-default.png?t=LA92https://leetcode-cn.com/problems/check-if-numbers-are-ascending-in-a-sentence/

思路

保存每次的数值,然后对比此次看到的值是否比上次大就好了呗?

bool areNumbersAscending(char * s){
    int temp,i = 0;
    while(s[i] && (s[i]<'0' || s[i] >'9')) i++;//不是数字 跳过
    temp = s[i] - '0';        //保存temp的初始值 用于比较
    if(s[i+1] >= '0' && s[i+1] <= '9'){//保存temp初始值
        temp *= 10;
        temp += (s[++i] - '0');
    }

    for(i++ ;s[i]; ++i)        //开始扫描
        if(s[i] >= '0' && s[i] <= '9'){//扫到数字
            int temp2 = s[i] - '0';    //记录本次的值
            if(s[i + 1] >= '0' && s[i + 1] <= '9'){
                temp2 *= 10;
                temp2 += (s[++i] - '0');
            }
            if(temp2 <= temp)//对比 不符合条件丢出
                return false;
            else
                temp = temp2;    //符合开始下次比较
        }

    return true;
}

结果分析

凑合玩


 2047. 句子中的有效单词数

2047. 句子中的有效单词数icon-default.png?t=LA92https://leetcode-cn.com/problems/number-of-valid-words-in-a-sentence/

思路

拆分之后按照它的要求走就好了,除了麻烦,其他没啥,细心,细心,再细心。

int countValidWords(char * sentence){
    char *ans[500];//创建单词数组
    int wordsize = 0;//记录大小
    bool flag = true;
    for(int i = 0;sentence[i];++i){     //拆分所有单词
        if(sentence[i] == ' '&& flag == false){
            flag = true;
            sentence[i] = 0;
        }
        else if(sentence[i] != ' ' && flag == true){
            flag = false;
            ans[wordsize++] = &sentence[i];
        }
    }
    int res = 0;        //统计最后的结果
    for(int i = 0;i < wordsize;++i){
        int num = 0,zimu = 0,lianzifu = 0,biaodian = 0,j = 0;    //统计所有类型的东西个数
        for(j = 0;ans[i][j];++j){
            if(ans[i][j] >= '0' && ans[i][j] <= '9')  num++;
            else if(ans[i][j] >= 'a' && ans[i][j] <= 'z') zimu++;
            else if(ans[i][j] == '-')      lianzifu++;
            else if(ans[i][j] == '!'||ans[i][j] == '.'||ans[i][j] == ',')    biaodian++;
        }
        if(num) continue;//包含字母 直接继续
        if(lianzifu > 1||(lianzifu == 1 && (ans[i][0] == '-' || ans[i][j-1] == '-'))) continue;//连字符包含一个以上 或者只有一个但是不能出现最后和第一个
        if(lianzifu == 1 && biaodian == 1 && (ans[i][j-1] == '!'||ans[i][j-1] == '.'||ans[i][j-1] == ',') && ans[i][j-2] == '-')  continue;
        //连字符和标点都有并且连字符在第一个或者倒数第二个
        if(biaodian >1 ||(biaodian == 1 && (!(ans[i][j-1] == '!'||ans[i][j-1] == '.'||ans[i][j-1] == ',')))) continue;//标点不在最后
        printf("%d ",i);
        res++;
    }
    return res;
}

结果分析

满意


 1816. 截断句子

1816. 截断句子icon-default.png?t=LA92https://leetcode-cn.com/problems/truncate-sentence/

思路

数拆分字符,到地方直接赋值0返回就好了。

char * truncateSentence(char * s, int k){
    for(int i = 0;s[i];++i)
        if(s[i] == ' '&&!(--k))//到地方
                s[i] = 0;//插入结束符
    return s;
}

结果分析

可以了


 1784. 检查二进制字符串字段

1784. 检查二进制字符串字段icon-default.png?t=LA92https://leetcode-cn.com/problems/check-if-binary-string-has-at-most-one-segment-of-ones/

思路

题意比题难得多,一开始看不懂,其实就是出现0不能出现1,那么不能包含01字串就行了。

bool checkOnesSegment(char * s){
    return !strstr(s,"01");
}

结果分析

还行了


 468. 验证IP地址

468. 验证IP地址icon-default.png?t=LA92https://leetcode-cn.com/problems/validate-ip-address/

思路

难是不难,但是是真的费劲,太费劲了。

  1. 判断分割符是否是3个点或者7个冒号
  2. 分别判断是否是IPv4 是否是IPv6
  3. 返回
char answer[3][10] = {"IPv4","IPv6","Neither"};
int  validIPv4(char **);
int  validIPv6(char **);

char * validIPAddress(char * queryIP){
    char *cou[10];
    cou[0] = queryIP;
    int dot = 1,colons = 1;
    for(int i = 0;queryIP[i];++i)       //拆分字符串
        if(queryIP[i] == '.'){
            if(dot + colons > 9)    return answer[2];//防止溢出
            cou[dot++] = &queryIP[i+1];
            queryIP[i] = 0;
        }
        else if(queryIP[i] == ':'){
            if(dot + colons > 9)    return answer[2];//防止溢出
            cou[colons++] = &queryIP[i+1];
            queryIP[i] = 0;
        }
    if(dot == 4 && colons == 1)  return answer[validIPv4(cou)];    //3个点
    if(colons == 8 && dot == 1)     return answer[validIPv6(cou)];    //7个冒号
    return answer[2];    //啥也不是
}

int  validIPv4(char **cou){
    for(int i = 0;i < 4;i++){
        int temp = 0;
        if(!cou[i][0])  return 2;   //空组
        for(int j = 0;cou[i][j];j++){
            if(cou[i][j] < '0' ||cou[i][j] > '9')   return 2;   //包含非数字不符要求返回
            temp *= 10;
            temp += cou[i][j] - '0';
            if(temp > 255||temp < 0)  return 2; //不符合要求
        }
        if(temp == 0 && cou[i][1]) return 2;//0多了
        else if(temp !=0 && cou[i][0] == '0')   return 2;//头部多0
    }
    return 0;   //正常
}

int  validIPv6(char **cou){
    for(int i = 0;i < 8;++i){
        if(!cou[i][0])  return 2;   //空组不符合要求
        int size = 0;               //统计数组大小
        for(;cou[i][size];size++){  //如果不是给定的字符
            if(!((cou[i][size] >='0'&&cou[i][size] <='9')||(cou[i][size] >='a'&&cou[i][size] <='f')||(cou[i][size] >='A'&&cou[i][size] <='F'))) return 2;
        }
        if(size > 4)    return 2;    //如果超过4位
    }
    return 1;
}

结果分析

可以了


 写在最后

最近好暴躁,为啥总有人不喜欢学习,还要打扰别人学习,我也不希望任何人能帮我什么,只要不妨碍我做事就好了,就这么难么,唉,哭唧唧。

等我给平板做好驱动能运行win10我就死在图书馆!