简单记录牛客top101算法题(初级题C语言实现)BM83 字符串变形 && BM84 最长公共前缀

发布时间:2023年12月31日

1. BM83 字符串变形

??要求:对于一个长度为 n 字符串,我们需要对它做一些变形。首先这个字符串中包含着一些空格,就像"Hello World"一样,然后我们要做的是把这个字符串中由空格隔开的单词反序,同时反转每个字符的大小写。

输入:"This is a sample",16
返回值:"SAMPLE A IS tHIS"
输入:"nowcoder",8
返回值:"NOWCODER"

1.1 自己的整体思路

?? 开始的时候,以为是从中间对称反转一下就可以了,再把大小写反转一下,结果不是这样的,后来没有做出来,就看了官方的代码讲解,找到了思路;

  1. 如果整个字符串没有空格就直接反转,转换大小写即可;如果有空格,则执行下面的操作
  2. 先把整体的字符串,从中间位置,左右对称交换位置。
  3. 遍历交换后的字符串,然后以空格为界,从单词的中间位置,左右对称交换位置,反转每个单词。
  4. 遍历数组,把大写的字符换成小写,小写的字符换成大写。
    举例说明:
原字符串: This is a sample
整体反转: elpmas a si sihT
以空格为界,反正每个单词:sample a is This
转换大小写:SAMPLE A IS tHIS

具体代码如下:

#include <stdio.h>
#include <stdlib.h>
char* trans(char* s, int n ) {
    // write code here
    int flag = 0;
    int k = 0 ;
  for(int i = 0; i < n ; i++) {    //判断字符串里面是否有空格
        if (s[i] == ' ') {
            flag++;
            break;
        }
    }
   if (flag != 0) {                       //如果有空格
    for(int i = 0; i < n / 2 ; i++) {    //整体反转所有的字符串
        // printf("val = %c\r\n",s[i]);
        int temp = s[n - 1 - i];         //中间变量接收
        s[n - 1 - i] =  s[i];
        s[i] = temp;
    }
    //单独反转字符串,循环条件怎么定:空格和结束符
    int head = 0;  //头指针,索引大的值
    int tail = 0;  //尾指针,索引小的值

    for(int i = 0; i <= n; i++) {                //这里要等于n,加上了结尾的'\0'
    if (s[head] == ' ' || s[head] == '\0') {     //找到空格和字符串结束符'\0',最后一个要反转的单词,一定是在字符串结束符'\0'的前面
      for(int l = 0; l < (head - tail + 1) / 2 ; l++) {    //整体反转所有的字符串
        // printf("val = %c\r\n",s[i]);
        int temp = s[head - 1 - l];   //这样再减,都成负数了
        s[head - 1 - l] =  s[l + tail];
        s[l+ tail] = temp;
      }    
        tail = head + 1 ;                 //有空格就自动加上1,这里空格不能交换
        printf("val = %d\r\n", head);
     }
        head++;
 }
    for ( int j = 0; j < n; j++) {        //转换大小写
        if (s[j] >='A' && s[j] <='Z') {
            s[j] = s[j] + 32;           //大写转小写
        }else if (s[j] >='a' && s[j] <='z') {
             s[j] = s[j] - 32;          //小写转大写 
        }
    }

    }else {                           //如果没有空格
       for ( int j = 0; j < n; j++) {
        if (s[j] >='A' && s[j] <='Z') {
            s[j] = s[j] + 32;           //大写转小写
        }else if (s[j] >='a' && s[j] <='z') {
             s[j] = s[j] - 32;          //小写转大写 
        }
    }
 }
    return s;
}

1.2 小结

1.C语言中有库函数,可以判断字母是大写还是小写,并实现相应的转换。

#include <ctype.h>
islower(int c):检查字符是否为小写字母。
isupper(int c):检查字符是否为大写字母。
tolower(int c):将字符转换为小写字母(如果它是大写字母的话)。
toupper(int c):将字符转换为大写字母(如果它是小写字母的话)。

????????在这里插入图片描述


2.不使用库函数,自己编写函数来判断。
?在ASCII表中,a的ASCII值是97,A的ASCII值是65,大写字母是排在小写字母前面的,所以大写字母和自身的小写字母就是相差97 - 65 = 32。

int isLowerCase(char c) {  //判断是否是小写字母
    return (c >= 'a' && c <= 'z');
}

int isUpperCase(char c) {   //判断是否是大写字母
    return (c >= 'A' && c <= 'Z');
}

char toLowerCase(char c) {  //把大写转成小写
    if (c >= 'A' && c <= 'Z') {
        return c + ('a' - 'A');
    }
    return c;
}
char toUpperCase(char c) {  //把小写转成大写
    if (c >= 'a' && c <= 'z') {
        return c - ('a' - 'A');
    }
    return c;
}
#include <stdio.h>
int isLowerCase(char c) {
    return (c >= 'a' && c <= 'z');
}
int isUpperCase(char c) {
    return (c >= 'A' && c <= 'Z');
}
char toLowerCase(char c) {
    if (c >= 'A' && c <= 'Z') {
        return c + ('a' - 'A');
    }
    return c;
}
char toUpperCase(char c) {
    if (c >= 'a' && c <= 'z') {
        return c - ('a' - 'A');
    }
    return c;
}
int main()
{
	char ch = 'A';
    if (isLowerCase(ch)) {
        printf("%c 是小写字母\n", ch);
    } else if (isUpperCase(ch)) {
        printf("%c 是大写字母\n", ch);
    } else {
        printf("%c 不是字母\n", ch);
    }
    printf("原始字符:%c\n", ch);
    // 转换为小写字母
    char lowerCh = toLowerCase(ch);
    printf("小写字母:%c\n", lowerCh);
    // 转换为大写字母
    char upperCh = toUpperCase(ch);
    printf("大写字母:%c\n", upperCh);	
   return 0;
}

????????????????在这里插入图片描述

2. BM84 最长公共前缀

??要求:给你一个大小为 n 的字符串数组 strs ,其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。

输入:["abca","abc","abca","abc","abcc"]
返回值:"abc"

2.1 自己的整体思路

  1. 先找到字符串中长度最短的哪个字符,记录长度到数组中,找到数组中长度最短的,记为flag。
  2. 遍历整个字符串数组,就是相当于二维数组,i记录是哪一个字符串,j是记录该字符串里面的字符,i应该小于传进来的参数(字符串数组的个数),j应该小于刚刚记录的flag,就是字符串数组中最短的字符串长度。;依次比较字符,找到不相等的字符。
  3. 使用strncpy函数,拷贝出不相等字符前面的所有字符,然后再补上一个‘\0’,输出该字符串即可。
#include <malloc.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* longestCommonPrefix(char** strs, int strsLen){
   int flag = 0;
    //公共字符串长度
    if ( strsLen == 1 ){        //长度小于1,就代表只有一个或者没有元素
        return *strs;
        // return strs[0];
    }
    if ( strsLen == 0 ) {        //长度小于1,就代表只有一个或者没有元素
        // return NULL;
        // char *ptr = ""; // 声明一个指向整数的空指针
        return "";
    }
    int * arr = (int *)malloc(strsLen * sizeof(int));
    //必须要找到最短的那个字符串,最短的才可能是公共字符串
    for (int i = 0;i < strsLen; i++) {
        arr[i] = strlen(strs[i]);
    }
    for (int i = 0;i < strsLen - 1; i++) {     //必须减去1,不然错的   没有注意到["aa","ab"]
        
       if (arr[0] > arr[i + 1] ) {              //找到最小哪个值
        int temp = arr[i + 1];
        arr[0] = arr[i + 1];
        arr[i + 1] = arr[0];
        flag = i + 1;
        //printf("val = %d\r\n",arr[0]); 
       } 
    }
   for (int h = 0; h < arr[flag];  h++) {        //小于的是索引对应的长度,需要知道最小长度,作为i的判断条件
     for (int j = 0; j < strsLen - 1;  j++) {    //["abcc","abcc","abcb"]
       if (strs[j][h] != strs[j + 1][h]) {
         char * subString = (char *)malloc( h  *sizeof(char) + 1) ;    //这里的长度是多少,还是i吗
         strncpy(subString, *strs, h);    //这里的是第i个不相同,就是i是个数,不是i - 1 
         subString[h] = '\0';             //字符串的结束符一定是'\0'
          return   subString;
    }
   }
  }
    free(arr);
    arr = NULL;
   return strs[flag];   //全部都相同的情况
}
文章来源:https://blog.csdn.net/m0_64053511/article/details/132415373
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。