- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/longest-palindrome/open in new window
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
判断一个字符串能够成的最长的回文字符串长度是多少。
题目的意思是找出字符串能够成的最长的回文字符串的长度。
思路是需要找出规律:
1、 先加上所有能够成偶数次的字符串次数:
Python解法:
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
count = collections.Counter(s)
res = 0
prime = 0
for k, v in count.items():
if v % 2 == 1:
res += v - 1
prime = 1
else:
res += v
return res + prime
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
C++代码如下:
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> count;
for (char c : s)
++count[c];
int res = 0;
bool hasOne = false;
for (auto d : count) {
if (d.second % 2 == 0)
res += d.second;
else {
res += d.second - 1;
hasOne = true;
}
}
if (hasOne)
++res;
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
看了高票的答案,可以HashSet的方法,统计一个字符是否出现了偶数次,一增一减相抵消,这样的个数*2,如果HashSet中还有元素再加上1即可。
Java代码如下:
public class Solution {
public int longestPalindrome(String s) {
HashSet<Character> hashset=new HashSet<Character>();
int count=0;
for(int i =0; i< s.length(); i++){
if(hashset.contains(s.charAt(i))){
hashset.remove(s.charAt(i));
count++;
}else{
hashset.add(s.charAt(i));
}
}
if(!hashset.isEmpty()) return count*2 +1;
return count*2;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
AC:23 ms
虽然只遍历了一遍,但是用到了HashSet,因此效率没我的高。
用两个int[26],分别保存大小写字符,统计字符出现的对数,最后判断这些字符对数相加是否等于原字符的长度,如果不等说明有奇数的出现,在/2的时候被舍去了。方法思想挺巧妙的。
Java代码如下:
public int longestPalindrome(String s) {
int[] lowercase = new int[26];
int[] uppercase = new int[26];
int res = 0;
for (int i = 0; i < s.length(); i++){
char temp = s.charAt(i);
if (temp >= 97) lowercase[temp-'a']++;
else uppercase[temp-'A']++;
}
for (int i = 0; i < 26; i++){
res+=(lowercase[i]/2)*2;
res+=(uppercase[i]/2)*2;
}
return res == s.length() ? res : res+1;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在解决这个问题 longest palindromic substring leetcode 上的问题,我遵循动态编程方法,创建了一个 n*n bool 表(我猜这也是此问题的标准解决方案)并成功
我是编程新手,所以请多多包涵。我目前正在研究函数逻辑。我正在尝试编写一个函数来查看传递的字符串是否为回文(真或假)。 这是我的代码, function palindrome(word){ if(w
题目地址:https://leetcode.com/problems/super-palindromes/description/ 题目描述 Let's say a positive intege
本文关键词:回文数,回文,题解,Leetcode, 力扣,Python, C++, Java 题目地址:https://leetcode.com/problems/palindrome-number
题目地址:https://leetcode.com/problems/palindrome-partitioning/description/ 题目描述 Given a string s, par
题目地址:https://leetcode.com/problems/valid-palindrome/description/ 题目描述 Given a string, determine if
题目地址:https://leetcode.com/problems/shortest-palindrome/description/ 题目描述 Given a string s, you are
题目地址:https://leetcode.com/problems/palindrome-pairs/description/ 题目描述 Given a list of unique words
题目地址:https://leetcode.com/problems/palindromic-substrings/description/ 题目描述 Given a string, your t
题目地址:https://leetcode.com/problems/longest-palindrome/open in new window Difficulty: Easy 题目描
该程序运行时不会引发任何异常,但无论输入如何,结果始终相同:““空白”是回文。”每次输入都是回文时,我只是想知道是否有人对为什么会发生这种情况有任何建议?下面是该程序的代码: class Palind
我是一名 Java 开发新手。我想用Java编写代码来计算段落中回文词的数量。 假设是:用户可以输入包含尽可能多的句子的段落。每个单词之间以空格分隔,每个句子之间以句点分隔,单词前后的标点符号将被忽略
我正在上一门编程入门类(class),通过 myProgrammingLab 将大量 Material 深入到我们的脑海中。我在递归的概念上遇到了一些麻烦……对我来说它有点被击中或错过了。这个特殊的问
#include using namespace std; void palindrome(char *s){ if (s[1] == 0) { return;
我的一般问题是如何弄清楚如何使用 DFS。这似乎是我知识的薄弱部分。我的想法很模糊,但当问题发生变化时,我经常会卡住。这让我很困惑。 对于这个问题,我卡在了如何用递归编写 DFS 上。给定一个字符串
最长回文子串,题解,leetcode, 力扣,python, C++, java 题目地址:https://leetcode.com/problems/longest-palindromic-sub
题目地址:https://leetcode.com/problems/palindrome-linked-list/#/descriptionopen in new window 题目描述 Giv
题目地址:https://leetcode.com/problems/longest-palindromic-subsequence/description/ 题目描述 Given a strin
这是一些代码,以“直接样式”确定列表是否是 n+1 比较中的回文 pal_d1 :: Eq a => [a] -> Bool pal_d1 l = let (r,_) = walk l l in r
这个问题在这里已经有了答案: String replace method is not replacing characters (5 个答案) 关闭 2 年前。 我正在努力理解我的代码对于这个 L
我是一名优秀的程序员,十分优秀!