資訊專(zhuān)欄INFORMATION COLUMN
摘要：判斷一個(gè)能否組成一個(gè)第一次出現(xiàn)增加一，第二次出現(xiàn)減少一。出現(xiàn)偶數(shù)次的最終對(duì)被抵消。出現(xiàn)基數(shù)詞的則會(huì)讓加一。類(lèi)似于，奇數(shù)個(gè)的那個(gè)多帶帶考慮，必須放中間。得到各個(gè)字符一半數(shù)量的長(zhǎng)度數(shù)字的終止條件，利用的對(duì)稱(chēng)性輸出結(jié)果。
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. For example: Given s = "aabb", return ["abba", "baab"]. Given s = "abc", return [].
public class Solution {
private List list = new ArrayList();
public List generatePalindromes(String s) {
//判斷一個(gè)string能否組成panlindrome, LC 266
int numOdds = 0;
int[] map = new int[256];
for(char c : s.toCharArray()){
map[c]++;
// 一個(gè)char第一次出現(xiàn)numOdds增加一，第二次出現(xiàn)numOdds減少一。
// 出現(xiàn)偶數(shù)次的char最終對(duì)numOdds被抵消。
// 出現(xiàn)基數(shù)詞的char則會(huì)讓numOdss加一。
numOdds = (map[c]&1) == 1 ? numOdds+1 : numOdds - 1;
}
if(numOdds > 1) return list;
//類(lèi)似于409 Longest Palindrome， 奇數(shù)個(gè)的那個(gè)char多帶帶考慮，必須放中間。
//這里palindrome本身是對(duì)稱(chēng)的，所以只需要找到一半的全排列，利用對(duì)稱(chēng)就能得到完整的string.
String mid = "";
int halfLen = 0;
for(int i=0; i<256; i++){
if(map[i] == 0) continue;
// 找到那個(gè)出現(xiàn)奇數(shù)次的字符。
if((map[i]&1) == 1){
mid = "" + (char)i;
map[i]--;
}
// 得到各個(gè)字符一半數(shù)量的長(zhǎng)度
map[i] = map[i]/2;
halfLen += map[i];
}
// 數(shù)字的permutation.
generatePalindromes("", map, halfLen, mid);
return list;
}
public void generatePalindromes(String half, int[] map, int halfLen, String mid){
// 終止條件，利用palindrome的對(duì)稱(chēng)性輸出結(jié)果。
if(half.length() == halfLen){
StringBuilder reverse= new StringBuilder(half).reverse();
list.add(half + mid + reverse);
return;
}
for(int i=0; i<256; i++){
if(map[i] > 0){
map[i]--;
generatePalindromes(half+(char)i, map, halfLen, mid);
map[i]++;
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66919.html
Problem Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. Example Given s = aabb, return [abba,baa...
摘要：不同數(shù)包含重復(fù)數(shù)為的時(shí)候，表示在外層的循環(huán)正在被使用，所以當(dāng)前循環(huán)遇到為一定要跳過(guò)。對(duì)當(dāng)前循環(huán)要添加的數(shù)組，在添加當(dāng)前元素后進(jìn)行遞歸，遞歸之后要將當(dāng)前元素的使用標(biāo)記改為，表示已經(jīng)使用和遞歸完畢，然后再將這個(gè)元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...
摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來(lái)判斷結(jié)果中是否有回文。而中心對(duì)稱(chēng)點(diǎn)如果是字符，該字符會(huì)是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...
Problem Given a string, determine if a permutation of the string could form a palindrome. Example 1: Input: codeOutput: falseExample 2: Input: aabOutput: trueExample 3: Input: careracOutput: true Solu...
摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。 順序整理 1~50 1...
閱讀 3086·2021-11-22 09:34
閱讀 2537·2021-09-30 09:47
閱讀 1472·2021-09-03 10:32
閱讀 3764·2021-08-16 10:49
閱讀 1814·2019-08-30 15:55
閱讀 2500·2019-08-30 15:52
閱讀 3354·2019-08-30 15:44
閱讀 1383·2019-08-30 15:44
