算法之不定期更新（二）（2018-04-15）

Aklman 發(fā)布于2019-08-22 16:19 / 2617人閱讀

摘要：題目中的數(shù)字可以分割出來的連續(xù)數(shù)字串的所有組合，不同組合之間用一個(gè)和連接示例和和和和和和和和和和這里給同學(xué)提個(gè)醒。。解題思路利用二叉樹。說到這這個(gè)題就很容易解決了，利用二叉樹的層次遍歷，每一層遍歷的時(shí)候都基于上一層的遍歷結(jié)果生成答案。

題目

input: n
output: 1...n中的數(shù)字可以分割出來的連續(xù)數(shù)字串的所有組合，不同組合之間用一個(gè)"和"連接

示例：
input: 3
output: 1,2,3和1,23和12,3和123

input: 4
output: 1,2,3,4和12,3,4和1,23,4和1,2,34和12,34和123,4和1,234和1234

這里給同學(xué)提個(gè)醒。。再往下直接就是我寫得解題思路了，希望大家可以先自己思考一下這個(gè)問題。

解題思路

利用二叉樹。

當(dāng)input = 1時(shí)，output = 1
當(dāng)input = 2時(shí)，output = 1,2和12,其實(shí)我們可以看做output = ("1" + ",2") + "和" + ("1" + "2")
當(dāng)input = 3時(shí)，output = 1,2,3和12,3和1,23和123,其實(shí)我們可以看做output = ("1,2" + ",3") + "和" + ("12" + ",3") + 和 + ....

下面用一個(gè)圖來說明n為5的時(shí)候的解決思路

也就是說，n=5時(shí)候的輸出，是由n=4的輸出和"5", ",5"進(jìn)行組合后的來的。

說到這這個(gè)題就很容易解決了，利用二叉樹的層次遍歷，每一層遍歷的時(shí)候都基于上一層的遍歷結(jié)果生成答案。

代碼

function solution (n) {
    let result = ["1"] // 存放當(dāng)前遍歷層次的結(jié)果
    for (let i = 2; i <= n; i++) { // i 為當(dāng)前遍歷到的層數(shù)
        for (let j = Math.pow(2, i - 2); j >= 1; j--) { // j 為上一層共有結(jié)點(diǎn)數(shù)}
            let temp = result.shift() // 取出一個(gè)結(jié)果
            result.push(`${temp},${i}`) // 放進(jìn) temp + ,i
            result.push(`${temp}${i}`) // 放進(jìn) temp + i
        }
    }
    return result.join("和")
}

輸出測(cè)試：

這個(gè)算法的時(shí)間空間復(fù)雜度均為O(二叉樹的節(jié)點(diǎn)數(shù))，也就是O(2^n)

那么這個(gè)算法題就到這了，如果大家又什么好的想法或者我的有什么問題，歡迎在討論區(qū)和我交流