【C/C++刷题——leetcode】查找字符串中最大的子串

简介: 【C/C++刷题——leetcode】查找字符串中最大的子串

前言


在字符串处理中,经常需要寻找一个字符串中的最大子串。最大子串指的是在给定字符串中连续出现的长度最长的子串。本文将介绍如何使用C++/C语言来查找一个字符串中的最大子串。


一、示例


输入:"Hello everybody"
输出:"everybody"
输入:"i am C++"
输出:"C++"


空格分割每一个子字符串,遇到'\0'返回


二、要求分析


1、遍历字符串

对于此要求,我们肯定需要遍历整个字符串,才能求出他的最长字符串。

2、定义存储最长字符串的变量

定义存储上一个字符串的变量(如上面这个例子:我遍历到everybody了,那么上一个字符串就是Hello),定义存储现在的字符串(当遇到空格或者'\0'的时候自动给上一个字符串,并清空,好在下一次字符串使用)。创建后两个字符串的意义就是要比较得出最大字符串

3、如果无空格或'\0',在存储现在字符串里面尾添加
4、如果有,则去判断上一个字符串和现在存储的字符串哪个大,从而得出maxStr。


三、C语言版


1、遍历字符串:

  //由于strlen函数并不会加'\0',可以'\0'也是我们的一个判断的一个标准
  //所以需要+1
  int len = strlen(str) + 1;
    for (int i = 0; i < len; i++) 
    {
    }


2、定义存储字符串的变量:

字符数组也可以增大,或者有能力的同学也可以使用malloc等等方法动态申请

实现一个相对智能的函数

  int maxLen = 0;              // 最大子串长度
    char maxStr[100];            // 存储最大子串的字符数组
    char lastStr[100];           // 存储上一个子串的字符数组
    char ret[100];               // 存储当前子串的字符数组


3、如果无空格或'\0',在存储现在字符串里面尾添加:

ret[retLen++] = str[i];


4、如果有,则去判断上一个字符串和现在存储的字符串哪个大,从而得出maxStr。

if (strlen(lastStr) > maxLen) {
                strncpy(maxStr, lastStr, strlen(lastStr) + 1);
                maxLen = strlen(lastStr);
                retLen = 0;
            }
            else {
                strncpy(maxStr, ret, strlen(ret) + 1);
                strncpy(lastStr, ret, strlen(ret) + 1);
                maxLen = strlen(ret);
                retLen = 0;
            }


char* logestStr(const char* str) {
    int maxLen = 0;              // 最大子串长度
    char maxStr[100];            // 存储最大子串的字符数组
    char lastStr[100];           // 存储上一个子串的字符数组
    char ret[100];               // 存储当前子串的字符数组
    int retLen = 0;              // 当前子串的长度
    int len = strlen(str) + 1;
    for (int i = 0; i < len; i++) {
        if (str[i] == ' ' || str[i] == '\0') {
            if (strlen(lastStr) > maxLen) {
                strncpy(maxStr, lastStr, strlen(lastStr) + 1);
                maxLen = strlen(lastStr);
                retLen = 0;
            }
            else {
                strncpy(maxStr, ret, strlen(ret) + 1);
                strncpy(lastStr, ret, strlen(ret) + 1);
                maxLen = strlen(ret);
                retLen = 0;
            }
            continue;
        }
        else {
            ret[retLen++] = str[i];
        }
    }
    return maxStr;
}


四、C++版


1、遍历字符串:

  //由于string::length()函数并不会加'\0',可以'\0'也是我们的一个判断的一个标准
  //所以需要+1
  int len = str.length()+1;
    for(int i = 0;i<len;i++)
    {
    }


2、定义存储字符串的变量:

  string ret;//记录这次的字符串
    string lastStr;//记录上次的字符串
    string maxStr;//最长的字符串,最后用于返回


3、如果无空格或'\0',在存储现在字符串里面尾添加:

ret.append(1,str[i]);//尾添加字符串


4、如果有,则去判断上一个字符串和现在存储的字符串哪个大,从而得出maxStr。

if(lastStr.length() > ret.length())//上次的字符串比这次的大,maxstr赋值成上次的字符串
{
      maxStr = lastStr;
      ret = "";//存储现在字符串清空,好下次使用
}
else
{
      maxStr = ret;//最大的是此次字符串,赋值给maxstr
      lastStr = ret;//我们需要存储起lastStr好下次对比
      ret = "";//存储现在字符串清空,好下次使用
}


全部代码如下

string logestStr(const string &str)
{
    int Strcount = 0;
    string ret;//记录这次的字符串
    string lastStr;//记录上次的字符串
    string maxStr;//最长的字符串,最后用于返回
  //由于string::length()函数并不会加'\0',可以'\0'也是我们的一个判断的一个标准
  //所以需要+1
    int len = str.length()+1;
    for(int i = 0;i<len;i++)
    {
        if(str[i] == ' ' || str[i]== '\0')//当遇到分隔符的时候
        {
            if(lastStr.length() > ret.length())//上次的字符串比这次的大,maxstr赋值成上次的字符串
            {
                maxStr = lastStr;
                ret = "";//存储现在字符串清空,好下次使用
            }
            else
            {
                maxStr = ret;//最大的是此次字符串,赋值给maxstr
                lastStr = ret;//我们需要存储起lastStr好下次对比
                ret = "";//存储现在字符串清空,好下次使用
            }
            continue;//执行下一次循环
        }
        else
        {
            ret.append(1,str[i]);//尾添加字符串
        }
    }
    return maxStr;
}


我们还可以实现他一个重载函数,以便char数组使用:

char *logestStr(const char *str)
{
    return const_cast<char*>(logestStr(string(str)).c_str());
}


重载函数代码分析:

由于logestStr(string).c_str()他的返回值是一个const char *,但是我们的返回值是char*,因为我们也不知道使用者是否会操作这个char*,所以我们不要写const char*

所以我们就需要使用const_cast去除const属性,然后通过return返回就可以了


总结


通过以上代码,我们可以利用C++/C语言来查找一个字符串中的最大子串。这个函数的实现利用循环遍历字符串,通过比较字符的连续性来确定最大子串的位置和长度,并提取出最大子串作为结果。


总结一下,本文介绍了如何使用C++/C语言来查找一个字符串中的最大子串。通过编写一个辅助函数,我们能够方便地在程序中进行最大子串的查找,为字符串处理提供了便利。

相关文章
|
2月前
|
C语言 C++
【实战指南】 C/C++ 枚举转字符串实现
本文介绍了在C/C++中实现枚举转字符串的实用技巧,通过宏定义与统一管理枚举名,提升代码调试效率并减少维护错误。
231 50
|
3月前
|
Java C++
力扣第一道困难题《3. 无重复字符的最长子串》,c++
首先我们看到这个题是肯定有一种暴力的硬解思路的,那就是将两个vector直接链接起来,然后再排序后,直接返回中间值,这个方法实现起来还是非常容易的,
61 0
|
5月前
|
Go 索引
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
141 6
|
6月前
|
存储 机器学习/深度学习 缓存
🚀 力扣热题 394:字符串解码(详细解析)(Go语言版)
文章提供了两种解法:栈结构和递归解法。栈解法通过维护数字栈与字符串栈,依次处理 `[` 和 `]`,构造解码结果;递归解法则利用函数调用逐层解析嵌套结构。两者时间复杂度均为 $O(n)$,空间复杂度也为 $O(n)$。栈解法直观易懂,适合初学者;递归解法优雅简洁,适合处理深度嵌套规则。掌握这两种方法,可灵活应对类似问题,提升解题能力。
188 11
|
7月前
|
消息中间件 Linux C++
c++ linux通过实现独立进程之间的通信和传递字符串 demo
的进程间通信机制,适用于父子进程之间的数据传输。希望本文能帮助您更好地理解和应用Linux管道,提升开发效率。 在实际开发中,除了管道,还可以根据具体需求选择消息队列、共享内存、套接字等其他进程间通信方
156 16
|
12月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
194 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
10月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
243 1
|
11月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
114 1
|
11月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
77 9
|
11月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
125 0

热门文章

最新文章