当前位置: 首页 > news >正文

【LeetCode每日一题】——680.验证回文串 II

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【解题思路】
  • 七【题目提示】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 贪心算法

二【题目难度】

  • 简单

三【题目编号】

  • 680.验证回文串 II

四【题目描述】

  • 给你一个字符串 s,最多 可以从中删除一个字符。
  • 请你判断 s 是否能成为回文字符串:如果能,返回 true ;否则,返回 false 。

五【题目示例】

  • 示例 1:

    • 输入:s = “aba”
    • 输出:true
  • 示例 2:

    • 输入:s = “abca”
    • 输出:true
    • 解释:你可以删除字符 ‘c’ 。
  • 示例 3:

    • 输入:s = “abc”
    • 输出:false

六【解题思路】

  • 利用贪心算法的思想,由外到内逐层判断是否是回文串
  • 要判断一个字符串是不是回文串,可以从外面开始判断,只有两种情况:
    • 第一个字符和最后一个字符相等,那么只需要判断里面的其余字符
    • 第一个字符和最后一个字符不相等,那么这个字符串就不是回文串,根据题目要求,可以去掉第一个字符或者最后一个字符再次进行判断,但是需要注意的是,只能删除一次
  • 根据以上思路,我们首先从最外层开始判断,如果没发现有对应位置不相等的字符就判断是一个回文串
  • 如果发现有对应位置不相等的字符,去掉最左边或者最右边的字符再进行一次是否是回文串的判断,如果还有对应位置不相等的字符,肯定就不满足题意了,返回false即可,如果没有对应位置不相等的字符,返回true即可

七【题目提示】

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

八【时间频度】

  • 时间复杂度:O(n)O(n)O(n),其中nnn为传入字符串长度
  • 空间复杂度:O(1)O(1)O(1)

九【代码实现】

  1. Java语言版
class Solution {public boolean validPalindrome(String s) {int left = 0;int right = s.length() - 1;while(left < right){if(s.charAt(left) != s.charAt(right)){return isPalindrome(s,left + 1,right) || isPalindrome(s,left,right - 1);}left++;right--;}return true;}public boolean isPalindrome(String s,int i,int j){while(i < j){if(s.charAt(i) != s.charAt(j)){return false;}i++;j--;}return true;}
}
  1. C语言版
bool isParlindrome(char *s,int i,int j)
{while(i < j){if(s[i] != s[j]){return false;}i++;j--;}return true;
}bool validPalindrome(char * s)
{int left = 0;int right = strlen(s) - 1;while(left < right){if(s[left] != s[right]){return isParlindrome(s,left + 1,right) || isParlindrome(s,left,right - 1);}left++;right--;}return true;
}
  1. Python版
class Solution:def validPalindrome(self, s: str) -> bool:def isPalindrome(i,j):while i < j:if s[i] != s[j]:return Falsei += 1j -= 1return Trueleft = 0right = len(s) - 1while left < right:if s[left] != s[right]:return isPalindrome(left + 1,right) or isPalindrome(left,right - 1)left += 1right -= 1return True

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. C语言版
    在这里插入图片描述

  3. Python语言版
    在这里插入图片描述

相关文章:

【LeetCode每日一题】——680.验证回文串 II

文章目录一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【解题思路】七【题目提示】八【时间频度】九【代码实现】十【提交结果】一【题目类别】 贪心算法 二【题目难度】 简单 三【题目编号】 680.验证回文串 II 四【题目描述】 给你一个字…...

【C语言进阶:指针的进阶】你真分得清sizeof和strlen?

本章重点内容&#xff1a; 字符指针指针数组数组指针数组传参和指针传参函数指针函数指针数组指向函数指针数组的指针回调函数指针和数组面试题的解析这篇博客 FLASH 将带大家一起来练习一些容易让人凌乱的题目&#xff0c;通过这些题目来进一步加深和巩固对数组&#xff0c;指…...

【前端必看】极大提高开发效率的网页 JS 调试技巧

大家好&#xff0c;我是前端西瓜哥。本文讲解如何使用浏览器提供的工具进行 JS 代码的断点调试。 debugger 在代码中需要打断点的地方&#xff0c;加上 debugger&#xff0c;表示一个断点。浏览器代码执行到该位置时&#xff0c;会停下来&#xff0c;进入调试模式。 示例代码…...

【春招面经】视源股份前端一面

前言 本次主要记录一下视源股份CVTE前端一面 &#xff08;3.3下午4点15&#xff09; 文章目录前言本次主要记录一下视源股份CVTE前端一面 &#xff08;3.3下午4点15&#xff09;问题总结介绍一下项目的来源以及做这个项目的初衷一直监听滚动&#xff0c;有没有对性能产生影响&a…...

插件化开发入门

一、背景顾名思义&#xff0c;插件化开发就是将某个功能代码封装为一个插件模块&#xff0c;通过插件中心的配置来下载、激活、禁用、或者卸载&#xff0c;主程序无需再次重启即可获取新的功能&#xff0c;从而实现快速集成。当然&#xff0c;实现这样的效果&#xff0c;必须遵…...

tftp、nfs 服务器环境搭建

目录 一、认识 tftp、nfs 1、什么是 tftp&#xff1f; 2、什么是 nfs&#xff1f; 3、tftp 和 nfs 的区别 二、tftp的安装 1、安装 tftp 服务端 2、配置 tftp 3、启动 tftp 服务 三、nfs 的安装 1、安装 nfs 服务端 2、配置 nfs 3、启动 nfs 服务 一、认识 tftp、…...

汇编系列03-不借助操作系统输出Hello World

每天进步一点点&#xff0c;加油&#xff01; 上一节&#xff0c;我们通过汇编指令&#xff0c;借助操作系统的系统调用实现了向标准输出打印Hello world。这一节我们打算绕过操作系统&#xff0c;直接在显示屏幕上打印Hello world。 计算机的启动过程 当我们给计算机加电启…...

TPU编程竞赛系列|算能赛道冠军SO-FAST团队获第十届CCF BDCI总决赛特等奖!

近日&#xff0c;第十届中国计算机学会&#xff08;CCF&#xff09;大数据与计算智能大赛总决赛暨颁奖典礼在苏州顺利落幕&#xff0c;算能赛道的冠军队伍SO-FAST从2万余支队伍中脱颖而出&#xff0c;获得了所有赛道综合评比特等奖&#xff01; 本届CCF大赛吸引了来自全国的2万…...

【C++】AVL树,平衡二叉树详细解析

文章目录前言1.AVL树的概念2.AVL树节点的定义3.AVL树的插入4.AVL树的旋转左单旋右单旋左右双旋右左双旋AVL树的验证AVL树的删除AVL树的性能前言 前面对map/multimap/set/multiset进行了简单的介绍&#xff0c;在其文档介绍中发现&#xff0c;这几个容器有个共同点是&#xff1…...

C/C++开发,无可避免的多线程(篇四).线程与函数的奇妙碰撞

一、函数、函数指针及函数对象 1.1 函数 函数&#xff08;function&#xff09;是把一个语句序列&#xff08;函数体, function body&#xff09;关联到一个名字和零或更多个函数形参&#xff08;function parameter&#xff09;的列表的 C 实体&#xff0c;可以通过返回或者抛…...

elisp简单实例: taglist

从vim 转到emacs 下,一直为缺少vim 中的tablist 插件而感到失落. 从网上得到的一个emacs中的taglist, 它的功能很简陋,而且没有任何说明, 把它做为elisp的简单实例,供初学者入门倒不错,我给它加了很多注释,帮助理解, 说实话,感觉这百行代码还是挺有深度的,慢慢体会,调试才会有收…...

Azure AI基础到实战(C#2022)-认知服务(3)

目录 OpenFileDialog 类上一节代码的API剖析ComputerVisionClientExtensions.ReadAsync MethodReadHeaders ClassReadHeaders.OperationLocation Property探索ReadHeaders加上调试代码可用于 Azure 认知服务的身份验证标头使用单服务订阅密钥进行身份验证使用多服务订阅密钥进行…...

aws apigateway 使用restapi集成lambda

参考资料 代理集成&#xff0c;https://docs.aws.amazon.com/zh_cn/apigateway/latest/developerguide/api-gateway-create-api-as-simple-proxy-for-lambda.html非代理集成&#xff0c;https://docs.aws.amazon.com/zh_cn/apigateway/latest/developerguide/getting-started-…...

HTML基础

HTML 基础 文章目录HTML 基础列表标签无序列表有序列表自定义列表表格标签表格基本标签表格基本结构表格完整结构&#xff1a;合并行和合并列表单标签input 系列标签属性标签text 标签radio 标签 单选框file 标签 文件选择button 标签 按钮input系列标签总结button按钮标签sele…...

ThreadPoolExecutor参数 keepAliveTime allowCoreThreadTimeOut

/*** Timeout in nanoseconds for idle threads waiting for work.* Threads use this timeout when there are more than corePoolSize* present or if allowCoreThreadTimeOut. Otherwise they wait* forever for new work.*/ private volatile long keepAliveTime;等待工作的…...

什么是Hibernate框架?

简单介绍&#xff1a;Hibernate框架是当今主流的java持久层框架之一&#xff0c;是一个开放源码的ORM&#xff08;Object Relational Mapping&#xff0c;对象关系映射&#xff09;框架&#xff0c;它对JDBC进行了轻量级的封装&#xff0c;使得JAVA开发人员可以使用面向对象的编…...

指针面试笔试题练习

前言 &#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;推荐专栏: &#x1f354;&#x1f35f;&#x1f32f; c语言进阶 &#x1f511;个人信条: &#x1f335;知行合一 &#x1f349;本篇简介:>:介绍c语言中有关指针更深层的知识. 金句分享: ✨星光…...

docker(三)仓库的搭建、官方私有仓库的加密和认证

文章目录一、docker仓库二、仓库Registry工作原理三、搭建本地私有仓库四、配置镜像加速器五、私有仓库的加密认证1.非加密下上传拉取2.insecure registry3.仓库加密4.仓库认证一、docker仓库 什么是仓库 Docker 仓库是用来包含镜像的位置&#xff0c;Docker提供一个注册服务器…...

FPGA实现SDI视频编解码 SDI接收发送,提供2套工程源码和技术支持

目录1、前言2、设计思路和框架SDI接收SDI缓存写方式处理SDI缓存读方式处理SDI缓存的目的SDI发送3、工程1详解4、工程2详解5、上板调试验证并演示6、福利&#xff1a;工程代码的获取1、前言 FPGA实现SDI视频编解码目前有两种方案&#xff1a; 一是使用专用编解码芯片&#xff0…...

Android 基础知识4-3.5 RadioButton(单选按钮)Checkbox(复选框)详解

一、RadioButton&#xff08;单选按钮&#xff09; 1.1、简介 RadioButton表示单选按钮&#xff0c;是button的子类&#xff0c;每一个按钮都有选择和未选中两种状态&#xff0c;经常与RadioGroup一起使用&#xff0c;否则不能实现其单选功能。RadioGroup继承自LinearLayout&a…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...