leetcode 409 Longest Palindrome 最长回文串(简单)
LeetCode 简单 最长 回文 Longest Palindrome
2023-09-11 14:22:52 时间
一、题目大意
给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。
在构造过程中,请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。
示例 1:
输入:s = “abccccdd”
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = “a”
输入:1
提示:
- 1 <= s.length <= 2000
- s 只由小写 和/或 大写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
思路:先统计每个字符出现的次数,再遍历统计后的字符次数,如果是偶数次,那么一定可以是回文字符串的一部分,加上该次数;如果是奇数n字,那么加上n-1次;最后判断如果出现过奇数次的字符,那么最后结果加1。
三、解题方法
3.1 Java实现
public class Solution {
public int longestPalindrome(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
boolean odd = false;
int ans = 0;
for (Integer count : map.values()) {
if (count % 2 == 0) {
ans += count;
} else {
odd = true;
ans += (count - 1);
}
}
ans += odd ? 1 : 0;
return ans;
}
}
四、总结小记
- 2022/8/31 不合理的管理是造成内耗的原因之一
相关文章
- Leetcode: Remove Invalid Parentheses
- Leetcode: Find the Celebrity
- Leetcode: Copy List with Random Pointer
- LeetCode 145:Binary Tree Postorder Traversal
- LeetCode高频题:二分法求开根号sqrt(x),保留3位小数,速度快,简单
- 【Leetcode】746. 使用最小花费爬楼梯(简单)
- 【Leetcode】169. 多数元素(简单)
- 【Leetcode】121. 买卖股票的最佳时机(简单)
- 【Leetcode】237. 删除链表中的节点(简单)
- JS Leetcode 70. 爬楼梯 题解分析,斐波那契数列与动态规划
- (看懂LeetCode)1. 两数之和
- [LeetCode]剑指 Offer 11. 旋转数组的最小数字
- 127、【贪心算法】leetcode ——455. 分发饼干:DFS+双指针法(C++版本)
- 【LeetCode】118. Pascal's Triangle
- LeetCode 9. 回文数
- [LeetCode] 1325. Delete Leaves With a Given Value 删除给定值的叶子结点
- [LeetCode] Design Compressed String Iterator 设计压缩字符串的迭代器
- [LeetCode] 301. Remove Invalid Parentheses 移除非法括号
- LeetCode二叉树相同树比较
- leetcode 530. Minimum Absolute Difference in BST二叉搜索树的最小绝对差 (简单)
- leetcode 538. Convert BST to Greater Tree 把二叉搜索树转换为累加树(简单)
- leetcode 513. Find Bottom Left Tree Value 找树左下角的值 (简单)
- leetcode 637. Average of Levels in Binary Tree 二叉树的层平均值(简单)
- leetcode 110. Balanced Binary Tree 平衡二叉树(简单)
- leetcode 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素(简单)
- leetcode 206. Reverse Linked List 反转链表(简单)
- leetcode 205. Isomorphic Strings 同构字符串(简单)
- leetcode 69. Sqrt(x) x 的平方根(简单)
- leetcode算法112. 路径总和