資訊專欄INFORMATION COLUMN
摘要：?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)算法時(shí)遇到了一個(gè)問(wèn)題，至今無(wú)法解決。但是全排列算法又很重要，所以寫這篇文章記錄一下。
算法一：遞歸算法思想：
當(dāng)字符串長(zhǎng)度為1時(shí)，輸出該字符串；
當(dāng)長(zhǎng)度大于1時(shí)，取字符串的首字母，求出長(zhǎng)度-1的串的全排列，將首字母插入每一個(gè)排列的任意位置。
算法實(shí)現(xiàn)：
function permutate(str) {
//保存每一輪遞歸的排列結(jié)果
var result = [];
//初始條件：長(zhǎng)度為1
if (str.length == 1) {
return [str]
} else {
//求剩余子串的全排列,對(duì)每個(gè)排列進(jìn)行遍歷
var preResult = permutate(str.slice(1));
for (var j = 0; j < preResult.length; j++) {
for (var k = 0; k < preResult[j].length + 1; k++) {
//將首字母插入k位置
var temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
result.push(temp);
}
}
return result;
}
}
算法應(yīng)該不難理解吧。但是當(dāng)傳參的字符串是"abcdefghijkl"時(shí)，排列用到的空間是12!=479001600，過(guò)大的內(nèi)存占用導(dǎo)致內(nèi)存溢出。如果你是在自己的PC上執(zhí)行，那么可以使用node --max-old-space-size=8192來(lái)修改內(nèi)存。但是我需要在Codewars上執(zhí)行，所以無(wú)法修改內(nèi)存。于是我想的辦法是利用尾遞歸優(yōu)化。呵呵，Node的尾遞歸優(yōu)化？不管了，先試試吧。
算法二：尾遞歸function permutate(str,result) {
"use strict";
let tempArr = [];
//終止條件str長(zhǎng)度為0
if (str.length == 0) {
return result
} else {
//第一次遞歸時(shí)，插入首字母
if(result.length === 0){
tempArr.push(str[0]);
}else{
for (let i = 0; i < result.length; i++) {
let item = result[i];
let itemLen = item.length;
for (let j = 0; j < itemLen+1; j++) {
let temp = item.slice(0, j) + str[0] + item.slice(j);
tempArr.push(temp);
}
}
}
//遞歸截取了第一個(gè)字符的子串
return permutate(str.slice(0),tempArr);
}
}
permutate("abcdefghijkl",[]);
函數(shù)的第一個(gè)參數(shù)是本次遞歸的字符串，第二個(gè)參數(shù)是前x個(gè)字符的全排列結(jié)果。
思路是：
每次取當(dāng)次遞歸串的第一個(gè)字母；
若第二個(gè)參數(shù)長(zhǎng)度為0說(shuō)明是第一次遞歸，則初始化本次結(jié)果為[首字母]。然后將首字母從遞歸串中剔除，剩余串傳給下一次遞歸;
之后每一次遞歸，都取遞歸串的首字母，將其插入前x個(gè)字符的全排列的所有位置，求出x+1個(gè)字符的全排列；
遞歸直到第一個(gè)參數(shù)為空串，則第二個(gè)參數(shù)為字符串所有字符的全排列。
可能不太好理解，不過(guò)知道這是尾遞歸就行了。雖然尾遞歸在ES6的嚴(yán)格模式中才有效，但是，我加上"use strict";后仍然無(wú)效。事實(shí)上我認(rèn)為并不是函數(shù)調(diào)用棧的溢出，而是存放變量的堆溢出。所以，大概是無(wú)解了吧。畢竟全排列不管怎么樣，空間復(fù)雜度都是O(n!)的。
算法三：循環(huán)最后再貼個(gè)循環(huán)的代碼吧，也是沒(méi)什么用，就當(dāng)擴(kuò)展思路了。
function perm(str) {
let result = [],tempArr = [];
let subStr = str;
while (subStr.length !== 0) {
if (result.length === 0) {
result.push(str[0]);
} else {
for (let i = 0; i < result.length; i++) {
let item = result[i];
let itemLen = item.length;
for (let j = 0; j < itemLen+1; j++) {
let temp = item.slice(0, j) + subStr[0] + item.slice(j);
tempArr.push(temp);
}
}
result = tempArr;
tempArr = [];
}
subStr = subStr.slice(1);
}
return result;
}
總結(jié)
第一次遇到解決不了的問(wèn)題啊，感覺(jué)很不開心。我還特地跑到stackoverflow上問(wèn)了，然后回答的都不能解決。所以我也只好放棄了，真是不甘心。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/93014.html
摘要：本文詳細(xì)描述了堆內(nèi)存模型，垃圾回收算法以及處理內(nèi)存泄露的最佳方案，并輔之以圖表，希望能對(duì)理解內(nèi)存結(jié)構(gòu)有所幫助。該區(qū)域也稱為內(nèi)存模型的本地區(qū)。在中，內(nèi)存泄露是指對(duì)象已不再使用，但垃圾回收未能將他們視做不使用對(duì)象予以回收。 本文詳細(xì)描述了 Java 堆內(nèi)存模型，垃圾回收算法以及處理內(nèi)存泄露的最佳方案，并輔之以圖表，希望能對(duì)理解 Java 內(nèi)存結(jié)構(gòu)有所幫助。原文作者 Sumith Puri，...
摘要：結(jié)構(gòu)型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態(tài)模式策略模式職責(zé)鏈模式責(zé)任鏈模式訪問(wèn)者模式。 主要版本 更新時(shí)間 備注 v1.0 2015-08-01 首次發(fā)布 v1.1 2018-03-12 增加新技術(shù)知識(shí)、完善知識(shí)體系 v2.0 2019-02-19 結(jié)構(gòu)...
摘要：導(dǎo)讀閱讀本文需要有足夠的時(shí)間，筆者會(huì)由淺到深帶你一步一步了解一個(gè)資深架構(gòu)師所要掌握的各類知識(shí)點(diǎn)，你也可以按照文章中所列的知識(shí)體系對(duì)比自身，對(duì)自己進(jìn)行查漏補(bǔ)缺，覺(jué)得本文對(duì)你有幫助的話，可以點(diǎn)贊關(guān)注一下。目錄一基礎(chǔ)篇二進(jìn)階篇三高級(jí)篇四架構(gòu)篇五擴(kuò) 導(dǎo)讀：閱讀本文需要有足夠的時(shí)間，筆者會(huì)由淺到深帶你一步一步了解一個(gè)資深架構(gòu)師所要掌握的各類知識(shí)點(diǎn)，你也可以按照文章中所列的知識(shí)體系對(duì)比自身，對(duì)自己...
摘要：虛擬機(jī)棧線程私有，生命周期跟線程相同。堆用于存放對(duì)象實(shí)例，是虛擬機(jī)所管理的內(nèi)存中最大的一塊，同時(shí)也是所有線程共享的一塊內(nèi)存區(qū)域。統(tǒng)計(jì)監(jiān)測(cè)工具語(yǔ)法格式如下是虛擬機(jī)，在系統(tǒng)上一般就是進(jìn)程。 JDK、JRE、JVM三者的關(guān)系 JDK(Java Development Kit)是針對(duì)Java開發(fā)的產(chǎn)品、是整個(gè)Java的核心，包括Java運(yùn)行環(huán)境JRE、Java工具包和Java基礎(chǔ)類庫(kù)。 JR...
摘要：就是說(shuō)引用計(jì)數(shù)法很難解決對(duì)象之間的相互引用問(wèn)題也無(wú)法通知回收器去及時(shí)回收它。因?yàn)榇嬖谶@種缺點(diǎn)，所以現(xiàn)在的虛擬機(jī)基本上并不是通過(guò)引用計(jì)數(shù)法來(lái)判斷對(duì)象是否存活。 1、為什么要進(jìn)行垃圾回收？ 每當(dāng)在我們寫代碼的時(shí)候，不管是new一個(gè)對(duì)象，還是引用，還是填充數(shù)據(jù)到數(shù)組，都是要占用空間，那么如果不及時(shí)回收就會(huì)對(duì)系統(tǒng)的運(yùn)行產(chǎn)生影響。java和c 一個(gè)很大的區(qū)別就在于，java的垃圾回收主要是jv...
閱讀 3203·2021-10-14 09:42
閱讀 3571·2019-08-26 13:56
閱讀 3480·2019-08-26 11:59
閱讀 948·2019-08-23 18:00
閱讀 2213·2019-08-23 17:51
閱讀 3534·2019-08-23 17:17
閱讀 1486·2019-08-23 15:11
閱讀 5203·2019-08-23 15:05
