国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

字符串的全排列

sunny5541 / 2189人閱讀

摘要：?jiǎn)栴}輸入一個(gè)字符串按字典序打印出該字符串中字符的所有排列。如此遞歸處理，從而得到所有字符的全排列。記斐波那契數(shù)列的第位這件事為，則有。其中，表示去掉那個(gè)開(kāi)頭字符的剩余字符串的全排列。

問(wèn)題

輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

地址：https://www.nowcoder.com/prac...

遞歸

思路：從字符串中選出一個(gè)字符作為排列的第一個(gè)字符，然后對(duì)剩余的字符進(jìn)行全排列。如此遞歸處理，從而得到所有字符的全排列。

分析：我們可以先根據(jù)一個(gè)實(shí)際的例子想想，怎樣才能無(wú)遺漏的輸出全排列：

兩個(gè)數(shù)就不用說(shuō)了，對(duì)于 ab，只有 ab 和 ba 兩種
三個(gè)數(shù)，比如 abc，我們先分為三種情況，就是 a 開(kāi)頭，b 開(kāi)頭和 c 開(kāi)頭
對(duì)于 a 開(kāi)頭的情況，剩下 b 和 c，這就回到了兩個(gè)數(shù)的排列；
對(duì)于 b 開(kāi)頭的情況，剩下 a 和 c，這也回到了兩個(gè)數(shù)的排列；
c 開(kāi)頭的情況同理；
四個(gè)數(shù)，先按照開(kāi)頭分為四種情況，然后按照三個(gè)數(shù)的排列去處理
……
以此類推

由此可看出，這是一個(gè)遞歸。就好像求斐波那契數(shù)列的某一個(gè)元素，我們要先求出前面的；要想求出前面的，我們就要求出更前面的。記 “斐波那契數(shù)列的第 n 位” 這件事為 F(n)，則有 F(n) = F(n - 1) + F(n - 2)。

類似地，記 “求出 n 個(gè)字符串的全排列” 這件事為 P(n)，則有 P(n) = 分別以這n個(gè)字符之一開(kāi)頭 + P(n - 1)。其中，P(n - 1) 表示去掉那個(gè)開(kāi)頭字符的剩余字符串的全排列。哪怕只有兩個(gè)字符，比如對(duì)于上面例子中的 ab，同樣符合這一條結(jié)論。

分析：以 "abc" 為例，執(zhí)行步驟如下：

a 作為開(kāi)頭 -> 求 bc 全排列 -> 得到 bc 和 cb -> 與 a 合并 -> 得到 abc 和 acb


b 作為開(kāi)頭 -> 求 ac 全排列 -> 得到 ac 和 ca -> 與 b 合并 -> 得到 bac 和 bca


c 作為開(kāi)頭 -> 求 ab 全排列 -> 得到 ab 和 ba -> 與 c 合并 -> 得到 cab 和 cba

注：之前遞歸過(guò)程選擇的字符，下一次不能再被選。

時(shí)間復(fù)雜度：O(n！)。

function permutation(str) {
    if(str.length == 0) {
        return [];
    }
    var result = [];
    var sortTemp = "";
    var arr = str.split("");
    // var len = arr.length;
    var result = sortString(arr, sortTemp, result);
    return result;

    function sortString(arr, sortTemp, res) {
        if(arr.length == 0) {
            return res.push(sortTemp);
        } else {
            let isRepeat = {};
            for(let i = 0; i < arr.length; i++) { // 不要用 len
                if(!isRepeat[arr[i]]) {
                    let temp = arr.splice(i, 1)[0]; // i 取出第i個(gè)字符作為第一個(gè)字符
                    sortTemp += temp;
                    sortString(arr, sortTemp, res); // 固定第一個(gè)字符的剩下字符的全排列已完成
                    arr.splice(i, 0, temp); // i 補(bǔ)全 恢復(fù)原字符串
                    sortTemp = sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp: 每次截掉字符串中的最后一個(gè)字符
                    isRepeat[temp] = true; // 相同的字符便不再在第一個(gè)字符中固定并對(duì)剩下的字符進(jìn)行全排列了
                }
            }    
        }
        return res;
    }
}
permutation("abc")

這里固定字符串?dāng)?shù)組元素中的第一個(gè)字符的方式：是利用數(shù)組中splice()方法通過(guò)截取出來(lái)（刪掉一個(gè)元素），完成全排列后再將該字符補(bǔ)全回原字符串中splice()（添加元素）的方式。遍歷該字符串?dāng)?shù)組，依次截取掉每個(gè)字符元素的方式來(lái)作為字符串?dāng)?shù)組元素的第一個(gè)字符。

當(dāng)然還可以通過(guò)依次向后交換的方式、或者取出元素以后向后插入的方式、以及經(jīng)典的回溯法的方式等等。

References

leetcode題解(遞歸和回溯法)
July 算法習(xí)題 - 字符串4（全排列和全組合）

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/97236.html

相關(guān)文章

  • July 算法習(xí)題 - 字符串4（全排列和全組合）

    摘要：求字符串的全排列字符串的全排列設(shè)計(jì)一個(gè)算法，輸出一個(gè)字符串字符的全排列。的做法沒(méi)有結(jié)果的，都是在一個(gè)字符串上進(jìn)行的操作。字符串的全組合輸入三個(gè)字符，則它們的組合有。因此可以循環(huán)字符串長(zhǎng)度，然后輸出對(duì)應(yīng)代表的組合即可。 求字符串的全排列 字符串的全排列 設(shè)計(jì)一個(gè)算法，輸出一個(gè)字符串字符的全排列。 比如，String = abc 輸出是abc,bac,cab,bca,cba,...

    tuniutech 評(píng)論0 收藏0

  • JS 字符串全排列算法及內(nèi)存溢出

    摘要：?jiǎn)栴}給定字符串，求出所有由該串內(nèi)字符組合的全排列。于是我想的辦法是利用尾遞歸優(yōu)化。算法二尾遞歸終止條件長(zhǎng)度為第一次遞歸時(shí)，插入首字母遞歸截取了第一個(gè)字符的子串函數(shù)的第一個(gè)參數(shù)是本次遞歸的字符串，第二個(gè)參數(shù)是前個(gè)字符的全排列結(jié)果。 問(wèn)題 給定字符串，求出所有由該串內(nèi)字符組合的全排列。所包含的字符不重復(fù)。 輸入：abc 輸出：[abc,acb,bac,bca,cab,cba] 我在實(shí)現(xiàn)算法...

    sihai 評(píng)論0 收藏0

  • 如何求ABC的全排列？--如何理解回溯算法？

    摘要：它真的是深度優(yōu)先搜索嗎是真的嗎是真的如果是的話，那它的搜索空間解空間是什么是向量組成的集合，而。既然深度優(yōu)先搜索剪枝回溯。 什么是全排列？從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。那么ABC的全排列有哪些？根據(jù)定義得到：ABCACBBACBCACABCBA 如何通過(guò)程序求解？方法一：暴力...

    zero 評(píng)論0 收藏0

  • 數(shù)字全排列

    摘要：數(shù)字全排列問(wèn)題描述給一個(gè)不重復(fù)的數(shù)字?jǐn)?shù)組，寫(xiě)一個(gè)程序，輸出全排列。那么兩個(gè)數(shù)字的全排列怎么算呢，以為例，就是第一個(gè)數(shù)字為的剩下的數(shù)的全排列第一個(gè)數(shù)字為的剩下的數(shù)的全排列。依次類推到個(gè)數(shù)字的全排列設(shè)數(shù)組，設(shè)的全排列為，設(shè)。 數(shù)字全排列 問(wèn)題描述 給一個(gè)不重復(fù)的數(shù)字?jǐn)?shù)組，寫(xiě)一個(gè)程序，輸出全排列。 比如給定數(shù)組： [1, 2, 3] 輸出： [1, 2, 3] [1, 3, 2] [2, 1...

    zoomdong 評(píng)論0 收藏0

  • 《劍指offer》分解讓復(fù)雜問(wèn)題更簡(jiǎn)單

    摘要：拆分鏈表，將和進(jìn)行拆分，保證原始鏈表不受影響。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。輸入一個(gè)字符串長(zhǎng)度不超過(guò)可能有字符重復(fù)字符只包括大小寫(xiě)字母。遞歸，記錄一個(gè)當(dāng)前節(jié)點(diǎn)的位置，該位置指向最后一個(gè)節(jié)點(diǎn)時(shí)記錄一次排列。 1.復(fù)雜鏈表的復(fù)制 輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的hea...

    wawor4827 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<