【Python3】【力扣题】409. 最长回文串

news/2024/11/1 15:52:24/
【力扣题】题目描述:

(题意理解)统计如下:

① 字母个数本身是偶数。

② 字母个数是奇数,统计奇数中的偶数部分,例如:字母个数为3,统计其中的2。

③ 中间可以有一个奇数字母。即只要有奇数,不论多少奇数,最终总和再加一个1。

【Python3】代码:

解题思路:先统计出各字符总共出现次数,加和偶数部分(包括奇数的偶数部分),若有奇数最后再加1。用变量isodd记录是否有奇数。

知识点:{ }:空字典。字典:键值对的序列。

              字典[键]:获取或修改键对应的值。

             字典.values():返回字典中所有值。

             b % 2 == 0:判断数值是否为偶数。

class Solution:def longestPalindrome(self, s: str) -> int:# 遍历字符串中每个字符,用字典统计出现个数adict = {}for a in s:if a not in adict: adict[a] = 1 else: adict[a] += 1# 遍历字典的所有值,所有偶数加和(含奇数的偶数部分)isodd = 0      # 用于记录是否有奇数total = 0for b in adict.values():if b % 2 == 0: total += belse: total += b - 1isodd = 1# 最多一个奇数在中间,若有奇数最后再加1return total + 1 if isodd == 1 else total

可以在用字典统计个数时,加总偶数,最后总和小于字符串长度,则表示有奇数,最后加1。

class Solution:def longestPalindrome(self, s: str) -> int:# 遍历字符串所有字符,用字典统计个数,统计到偶数个,加入总和,字典中恢复为0total = 0adict = {}for a in s:if a not in adict: adict[a] = 1 else: adict[a] += 1# 若个数是偶数即2,则总和+2,字典中对应值恢复为0if adict[a] % 2 == 0:total += 2adict[a] = 0# 若总和小于字符串长度(即有奇数),则总和加1return total + 1 if total < len(s) else total

python的collections库中Counter类可直接统计各元素出现个数。类似字典。

class Solution:def longestPalindrome(self, s: str) -> int:# 统计各字母出现次数adict = collections.Counter(s)# 遍历各字母的个数,偶数部分加和total = 0for b in adict.values():if b % 2 == 0: total += belse: total += b - 1# 若有奇数,最后总和加1return total + 1 if total < len(s) else total 

(官方题解)贪心

统计各字母出现次数,遍历各字母个数,加总偶数部分,若有奇数只加一次1。

知识点: b // 2:除法取整。例如:3 // 2 = 1。

                b % 2 == 1:判断数值是否是奇数。

class Solution:def longestPalindrome(self, s: str) -> int:# 统计各字母出现次数adict = collections.Counter(s)# 遍历各字母个数,偶数部分加和,若有奇数且总和为偶数则加1total = 0for b in adict.values():total += b // 2 * 2# 字母个数为奇数,总和为偶数,即确保只有一个奇数在中间位置if b % 2 == 1 and total % 2 == 0:total += 1return total


http://www.ppmy.cn/news/1543622.html

相关文章

MyEclipse中讲解Git使用——结合GitLab

1、什么是Git Git是分布式版本控制系统 Git是一款免费、开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目。 2、在myeclipse安装Git插件 下载该文件&#xff0c;将egit.zip解压放入 myeclipse安装路径>dropins>下重新启动myeclipse EGit -…

【部署与升级-会议签到的web安装】

部署与升级-会议的远程安装 技术路线界面规划flaskAPI以及socketio.emit shellout浏览器和后端交互到处是偶遇 技术路线 运行的基础是Flask-Soketio, 并借鉴了后台运行系统指令的代码 和scrncpy项目,app安装的脚本 #mermaid-svg-8H9rbzbpgpnAXfA3 {font-family:"trebuche…

算法笔记(new)

算法 线性插值 线性插值 公式如下 线性插值公式&#xff1a;(x - x1) / (x2 - x1) * (y2 - y1) y1如果要计算两个区间之内的某个点所在的比例值可以用如上公式 例&#xff1a;假设有64个数&#xff0c;我随便取一个数&#xff0c;输出给我一个百分数&#xff0c;这个百分数从…

字符串逆序(c语言)

错误代码 #include<stdio.h>//字符串逆序 void reverse(char arr[], int n) {int j 0;//采用中间值法//访问数组中第一个元素和最后一个元素//交换他们的值&#xff0c;从而完成了字符串逆序//所以这个需要临时变量for (j 0; j < n / 2; j){char temp arr[j];arr[…

STM32应用详解(11)I2C驱动程序

文章目录 前言一、I2C驱动程序的编写1.I2C发送一个字节的函数2.I2C发送一串字节的函数3.I2C接收一个字节的函数4.I2C接收一串字节的函数 前言 使用STM32F103固件函数库函数&#xff0c;介绍I2C驱动程序的编写&#xff0c;包括&#xff1a;I2C发送一个字节的函数、I2C发送一串字…

CoTAM——思维属性操纵链,一种利用大规模语言模型的新的高效快速学习方法

概述 近年来&#xff0c;大规模语言模型已显示出惊人的能力&#xff0c;可以从少量样本中学习。然而&#xff0c;这种能力需要昂贵的大规模模型&#xff0c;其运行成本是一大挑战。此外&#xff0c;在推理过程中&#xff0c;需要对所有测试输入的上下文&#xff08;包括演示&a…

Python+Appium+Pytest+Allure自动化测试框架-代码篇

文章目录 自动化测试框架工程目录示例测试代码示例结果查看allurepytest编写pytest测试样例的规则pytest conftest.py向测试函数传参 appium启动appium服务代码端通过端口与appium服务通信对设备进行操作在pytest测试用例中调用appium 更多功能 PythonAppiumPytestAllure自动化…

pip install fitz -i https://pypi.doubanio.com/simple/

安装fitz包 pip install fitz -i https://pypi.doubanio.com/simple/ C:\Users\hlg>pip install fitz -i https://pypi.doubanio.com/simple/ Looking in indexes: https://pypi.doubanio.com/simple/ Collecting fitzDownloading https://mirrors.cloud.tencent.com/pypi/…