【牛客刷题-算法】NC141 判断是否为回文字符串

Java光头强 • 2023年2月20日上午8:52 • 后端漫谈 • 阅读 191

CSDN话题挑战赛第2期
参赛话题：学习笔记

学习之路，长路漫漫，写学习笔记的过程就是把知识讲给自己听的过程。这个过程中，我们去记录思考的过程，便于日后复习，梳理自己的思路。学习之乐，独乐乐，不如众乐乐，把知识讲给更多的人听，何乐而不为呢?

个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法
推荐一款面试、刷题神器：👉点击开始刷题学习👈

文章目录

1.题目
2.算法设计思路
3.代码实现
4.运行结果
结束语：

1.题目

描述
给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。

字符串回文指该字符串正序与其逆序逐字符一致。

数据范围：

≤

10000000

0 < n \le 10000000

$0 < n \leq 10000000$
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

示例

2.算法设计思路

该题思路较为简单：只需从头、尾同时开始遍历字符串，逐个比较对应位置的字符是否相同即可。

具体到我使用的C语言，我们只需从字符数组的一端开始遍历，通过strlen()函数可以得到字符串的长度，由此我们就可以通过前面的下标计算出后面对称处的下标。同时我们并不需要循环遍历完整个数组，而只需遍历到数组的中间位置即可。

在遍历的过程中，一旦发现对应位置的字符出现不相同的情况，即可停止遍历，并返回false。如果遍历完发现对应位置字符都相同，则可返回true。

3.代码实现

注：这里并不是完整代码，而只是核心代码的模式

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param str string字符串 待判断的字符串
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
bool judge(char* str ) {
     // write code here
    int len = strlen(str);
    
    if(len <= 1){
        return true;
    }
    
    for(int i = 0; i <= (len - 1) / 2; i++){
        if(str[i] != str[len - 1 - i]){
            return false;
        }
    }
    return true;
}