亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

LC 267 Palindrome Permutation II

lowett / 578人閱讀

摘要：判斷一個能否組成一個第一次出現(xiàn)增加一，第二次出現(xiàn)減少一。出現(xiàn)偶數(shù)次的最終對被抵消。出現(xiàn)基數(shù)詞的則會讓加一。類似于，奇數(shù)個的那個多帶帶考慮，必須放中間。得到各個字符一半數(shù)量的長度數(shù)字的終止條件，利用的對稱性輸出結(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) {
        //判斷一個string能否組成panlindrome, LC 266
        int numOdds = 0;
        int[] map = new int[256];
        for(char c : s.toCharArray()){
            map[c]++;
            // 一個char第一次出現(xiàn)numOdds增加一，第二次出現(xiàn)numOdds減少一。
            // 出現(xiàn)偶數(shù)次的char最終對numOdds被抵消。
            // 出現(xiàn)基數(shù)詞的char則會讓numOdss加一。
            numOdds = (map[c]&1) == 1 ? numOdds+1 : numOdds - 1; 
        }
        if(numOdds > 1) return list;
        
        //類似于409 Longest Palindrome， 奇數(shù)個的那個char多帶帶考慮，必須放中間。
        //這里palindrome本身是對稱的，所以只需要找到一半的全排列，利用對稱就能得到完整的string. 
        String mid = "";
        int halfLen = 0;
        for(int i=0; i<256; i++){
            if(map[i] == 0) continue;
            // 找到那個出現(xiàn)奇數(shù)次的字符。
            if((map[i]&1) == 1){
                mid = "" + (char)i;
                map[i]--;
            }
            // 得到各個字符一半數(shù)量的長度
            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的對稱性輸出結(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/66919.html

相關(guān)文章

  • [LeetCode] 267. Palindrome Permutation II

    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...

    huashiou 評論0 收藏0

  • 【LC總結(jié)】回溯 (Subsets I II/Permutation I II/Combinatio

    摘要：不同數(shù)包含重復(fù)數(shù)為的時候，表示在外層的循環(huán)正在被使用，所以當(dāng)前循環(huán)遇到為一定要跳過。對當(dāng)前循環(huán)要添加的數(shù)組，在添加當(dāng)前元素后進(jìn)行遞歸，遞歸之后要將當(dāng)前元素的使用標(biāo)記改為，表示已經(jīng)使用和遞歸完畢，然后再將這個元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

    tuomao 評論0 收藏0

  • [Leetcode] Palindrome Permutation 回文變換

    摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結(jié)果中是否有回文。而中心對稱點(diǎn)如果是字符，該字符會是奇數(shù)次，如果在兩個字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

    svtter 評論0 收藏0

  • [LeetCode] 266. Palindrome Permutation

    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...

    jlanglang 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<