題1 最長回文串

描述

給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構(gòu)造成的最長的回文串。
在構(gòu)造過程中，請注意區(qū)分大小寫。比如 “Aa” 不能當(dāng)做一個回文字符串。
注意:
假設(shè)字符串的長度不會超過 1010。
示例 1:
輸入:
“abccccdd”
輸出:
7
解釋:
我們可以構(gòu)造的最長的回文串是"dccaccd", 它的長度是 7。

方法1 用HashMap

思路：自己想的方法，內(nèi)存和時間消耗比較大。首先用hashmap存字符串中每個字母的個數(shù)。字母為偶數(shù)，則全部可以用來做回文串，若字母為奇數(shù)，則要減1剩余的可以用來做回文串。奇數(shù)字母中只有一個字母可以用奇數(shù)做回文串，多出來的位于中間，所以結(jié)果+1。

class Solution {public int longestPalindrome(String s) {int len = s.length();boolean flag = false;Map<Character, Integer> map= new HashMap<>();int cnum = 0;for(char c: s.toCharArray()){if(!map.containsKey(c)){map.put(c, 1);}else{map.put(c, map.get(c)+1);}}int result = 0;for(Map.Entry<Character, Integer> entry: map.entrySet()){cnum += 1;if(entry.getValue() % 2 == 0){result += entry.getValue();}else{flag = true;result += entry.getValue()-1;} }if(cnum == 1){return len;}if(flag){return result+1;}else{return result;}} }

方法2 用數(shù)組統(tǒng)計字母數(shù)

class Solution {public int longestPalindrome(String s) {int[] count = new int[128];for (char c: s.toCharArray())count[c]++;int ans = 0;for (int v: count) {ans += v / 2 * 2; //除2把奇數(shù)的去掉了if (v % 2 == 1 && ans % 2 == 0) //奇數(shù)的+1ans++;}return ans;} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】3月19日打卡-Day4的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。