定义键盘快捷键 控制跳转 Java Spring SQLMAP cookies jaxb Uploadify java后台框架 jquery循环 mysql当前时间减一天 java多行注释 java使用redis excel加减混合求和 java高级特性 python报错 python调用方法 python写脚本 python使用正则表达式 python安装环境变量 python正则替换 java学习教程 java创建集合 java可变参数 java线程死锁 java当前日期 java程序设计教程 远程登录linux 金山wps2003 运行时错误1004 flash相册制作 groupby EasyCHM 图片链接生成器 只狼脚本 vfloppy 心理学与生活pdf gunzip 碧桂园园宝 js切割字符串 如何用ai设计字体
当前位置: 首页 > 学习教程  > 编程语言

LeetCode:647. Palindromic Substrings回文子串(C语言)

2020/7/24 11:21:09 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述:
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

示例 1:

输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.

示例 2:

输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

注意:

输入的字符串长度不会超过1000。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解答:

int isPalindrome(char *buf, int left, int right){
    while(left < right){
        if(buf[left] == buf[right]){
            left++;
            right--;
        }
        else{
            return false;
        }
    }
    return true;
}

int countSubstrings(char * s){
    int len = strlen(s);
    int i,j;
    int count = 0;

    for(i = 0;i < len;i++){
        for(j = 0;i + j < len;j++){
            if(isPalindrome(s, i, i + j)){
                count++;
            }
        }
    }
    return count;
}

运行结果:
在这里插入图片描述

Notes:
类似暴力法,但是第二层指针起点从字符串起始位置开始,第二层指针所指位置和第一层指针所指位置的长度的和要小于字符串总长度,在小于总长度的条件下判断第一层指针位置上的元素(right)与第二层指针位置上的元素(left)是否相等,若相等,left自减right自加,若最后left与right相等则表明是回文字符子串,返回true,否则不是,返回false。如此循环,直到遍历结束。


本文链接: http://www.dtmao.cc/news_show_50404.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?