【Leetcode680】验证回文字符串 II(贪心算法)

简介: 审题看清楚,,题目问的不是回文子串,不是子串!!!暴力解法会超时,可以使用双指针:

一、题目


image.png

二、思路

审题看清楚,,题目问的不是回文子串,不是子串!!!


暴力解法会超时,可以使用双指针:


如果当前左右指针指向的元素不相等,可以试着判断删除掉左元素或者右元素后的字符串是否为回文字符串,注意此时i左边和j右边是已经判断完了(再重复一次!判断的不是回文子串);

如果当前左右指针指向的元素相等,则左指针向右一格,右指针向左一格。

每次两指针表示的字符判断相等,则该部分就符合回文串,贪心思想。

注意s.substr(a, b)表示从s字符串的a下标开始算,连续b个字符。


三、代码

class Solution {
public:
    bool validPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        while(i < j){
            if(s[i] != s[j]){
                return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
            }
            i++;
            j--; 
        }
        return true;
    }
    //法一
    bool isPalindrome(string s, int i, int j){
        string temp = s.substr(i, j - i + 1);
        reverse(temp.begin(), temp.end());
        return temp == s.substr(i, j - i + 1);
    }
    //法二
    bool isPalindrome1(string& s,int i, int j){
        while(i < j){
            if(s[i++] != s[j--]){
                return false;
            }
        }
        return true;
    }
};


目录
打赏
0
0
0
0
14
分享
相关文章
|
3月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
55 0
|
28天前
|
Go 语言中实现 RSA 加解密、签名验证算法
随着互联网的发展,安全需求日益增长。非对称加密算法RSA成为密码学中的重要代表。本文介绍如何使用Go语言和[forgoer/openssl](https://github.com/forgoer/openssl)库简化RSA加解密操作,包括秘钥生成、加解密及签名验证。该库还支持AES、DES等常用算法,安装简便,代码示例清晰易懂。
59 12
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
本项目展示了基于FPGA与MATLAB实现的三帧差算法运动目标检测。使用Vivado 2019.2和MATLAB 2022a开发环境,通过对比连续三帧图像的像素值变化,有效识别运动区域。项目包括完整无水印的运行效果预览、详细中文注释的代码及操作步骤视频,适合学习和研究。
|
3月前
|
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
42 2
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
195 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
3月前
【LeetCode 40】98.验证二叉搜索树
【LeetCode 40】98.验证二叉搜索树
21 0
|
5月前
|
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
98 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
88 2
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
61 1