[leetcode] 0680. 验证回文串 ii-编程思维

680. 验证回文串 II

点击上方标题跳转至leetcode

题目描述

给你一个字符串 s最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串:如果能,返回 true ;否则,返回 false

 

示例 1:

输入:s = "aba"
输出:true

示例 2:

输入:s = "abca"
输出:true
解释:你可以删除字符 'c' 。

示例 3:

输入:s = "abc"
输出:false

 

提示:

  • 1 <= s.length <= 105
  • s 由小写英文字母组成

解题

Python3

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def checkPalindrome(low, high):
            i, j = low, high
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        low, high = 0, len(s) - 1
        while low < high:
            if s[low] == s[high]: 
                low += 1
                high -= 1
            else:
                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)
        return True
        
        
fun = Solution()
s = "abc"
res = fun.validPalindrome(s)
print(res)

C++

#include<iostream>
#include<string.h>
using namespace std;

class Solution {
public:

    bool checkPalindrome(const string& s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    bool validPalindrome(string s) {
        int low = 0,high =s.size() -1;
        while(low<high){
            char c1 = s[low],c2 = s[high];
            if(c1 == c2){
                ++low;
                --high;
            }
            else{
                return  checkPalindrome(s,low+1,high)|| checkPalindrome(s,low,high-1);
            }
        }
        return true;
    }
};

int main(){

    string s ="abca";
    // string s ="abc";
    bool res = Solution().validPalindrome(s);
    cout << res << endl;
    return 0;
}
//g++ 680.cpp -std=c++11

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/yege/p/17373284.html

[leetcode] 0682. 棒球比赛-编程思维

682. 棒球比赛 点击上方标题跳转至leetcode 题目描述 你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成,过去几回合的得分可能会影响以后几回合的得分。 比赛开始时,记录是空白的。你会得到一个记录操作的字符串列表 ops,其中 ops[i] 是你需要记录的第 i 项操作,ops 遵循下述规则:

[leetcode] 0693. 交替位二进制数-编程思维

693. 交替位二进制数 点击上方标题跳转至leetcode 题目描述 给定一个正整数,检查它的二进制表示是否总是 0、1 交替出现:换句话说,就是二进制表示中相邻两位的数字永不相同。   示例 1: 输入:n = 5 输出:true 解释:5 的二进制表示是:101 示例 2: 输入:n = 7 输出:false

[leetcode] 0696. 计数二进制子串-编程思维

696. 计数二进制子串 点击上方链接跳转至leetcode 题目描述 给定一个字符串 s,统计并返回具有相同数量 0 和 1 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是成组连续的。 重复出现(不同位置)的子串也要统计它们出现的次数。   示例 1: 输入:s = "00110011

[leetcode] 0674. 最长连续递增序列-编程思维

674. 最长连续递增序列 题目描述 给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[

[leetcode] 0661. 图片平滑器-编程思维

661. 图片平滑器 题目描述 图像平滑器 是大小为 3 x 3 的过滤器,用于对图像的每个单元格平滑处理,平滑处理后单元格的值为该单元格的平均灰度。 每个单元格的  平均灰度 定义为:该单元格自身及其周围的 8 个单元格的平均值,结果需向下取整。(即,需要计算蓝色平滑器中 9 个单元格的平均值)。 如果一个单元格周

[leetcode] 0657. 机器人能否返回原点-编程思维

657. 机器人能否返回原点 题目描述 在二维平面上,有一个机器人从原点 (0, 0) 开始。给出它的移动顺序,判断这个机器人在完成移动后是否在 (0, 0) 处结束。 移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R(右),L(左),U(上)和 D(下)。 如果