資訊專欄INFORMATION COLUMN
摘要：題目中的數(shù)字可以分割出來的連續(xù)數(shù)字串的所有組合，不同組合之間用一個和連接示例和和和和和和和和和和這里給同學提個醒。。解題思路利用二叉樹。說到這這個題就很容易解決了，利用二叉樹的層次遍歷，每一層遍歷的時候都基于上一層的遍歷結(jié)果生成答案。
題目
input: n
output: 1...n中的數(shù)字可以分割出來的連續(xù)數(shù)字串的所有組合，不同組合之間用一個"和"連接
示例：
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
這里給同學提個醒。。再往下直接就是我寫得解題思路了，希望大家可以先自己思考一下這個問題。
解題思路利用二叉樹。
當input = 1時，output = 1
當input = 2時，output = 1,2和12,其實我們可以看做output = ("1" + ",2") + "和" + ("1" + "2")
當input = 3時，output = 1,2,3和12,3和1,23和123,其實我們可以看做output = ("1,2" + ",3") + "和" + ("12" + ",3") + 和 + ....
下面用一個圖來說明n為5的時候的解決思路
也就是說，n=5時候的輸出，是由n=4的輸出和"5", ",5"進行組合后的來的。
說到這這個題就很容易解決了，利用二叉樹的層次遍歷，每一層遍歷的時候都基于上一層的遍歷結(jié)果生成答案。
代碼function solution (n) {
let result = ["1"] // 存放當前遍歷層次的結(jié)果
for (let i = 2; i <= n; i++) { // i 為當前遍歷到的層數(shù)
for (let j = Math.pow(2, i - 2); j >= 1; j--) { // j 為上一層共有結(jié)點數(shù)}
let temp = result.shift() // 取出一個結(jié)果
result.push(`${temp},${i}`) // 放進 temp + ,i
result.push(`${temp}${i}`) // 放進 temp + i
}
}
return result.join("和")
}
輸出測試：
這個算法的時間空間復雜度均為O(二叉樹的節(jié)點數(shù))，也就是O(2^n)
那么這個算法題就到這了，如果大家又什么好的想法或者我的有什么問題，歡迎在討論區(qū)和我交流
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/94233.html
摘要：樹的前序，中序遍歷的結(jié)構(gòu)如下圖可以看出，通過前序遍歷可以確定根節(jié)點，再通過中序遍歷和根節(jié)點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。 從前序與中序遍歷序列構(gòu)造二叉樹 今天帶來的是Leetcode上的一個經(jīng)典題：從前序與中序遍歷序列構(gòu)造二叉樹原題干： /** Definition for a binary ...
摘要：實現(xiàn)這個想法之后就發(fā)現(xiàn)，時間復雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級，還有好多已經(jīng)說爛了的題就不分享了。如果有什么意見或者想法歡迎在評論區(qū)和我交流 題目 input: n // 代表無向圖的頂點數(shù) // 從1開始 m // 無向圖的邊數(shù) arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點0和頂點2相連，頂點3和頂點4相連） ...
摘要：算法的確有他獨特的魅力。然后我在做這個題的時候，其實也用到了類似質(zhì)因數(shù)分解，只是其實我們可以更好的利用到因數(shù)這一個特性。判斷一個數(shù)是否是質(zhì)數(shù)質(zhì)數(shù)列表一開始我們認為每一個數(shù)都可能是自身的冪線性篩為質(zhì)數(shù)遍歷質(zhì)數(shù)列表為質(zhì)數(shù)的冪 前言 從三月份到現(xiàn)在，大大小小筆試了十幾家公司（主要是因為一直solo code，沒人內(nèi)推），然后也能感覺到自己的進步把。從編程題只能ac一題到后來的ak。今天面騰訊...
摘要：特意對前端學習資源做一個匯總，方便自己學習查閱參考，和好友們共同進步。 特意對前端學習資源做一個匯總，方便自己學習查閱參考，和好友們共同進步。 本以為自己收藏的站點多，可以很快搞定，沒想到一入?yún)R總深似海。還有很多不足&遺漏的地方，歡迎補充。有錯誤的地方，還請斧正... 托管: welcome to git，歡迎交流，感謝star 有好友反應和斧正，會及時更新，平時業(yè)務(wù)工作時也會不定期更...
摘要：已發(fā)出請求，正在等待回應長度正在保存至用時已保存認證失敗正在連接已連接。參考參考一參考二 title: Docker搭建代理服務(wù)器 tags: - Squid categories: - Linux [TOC] 環(huán)境說明 項目 說明 系統(tǒng) Deepin 15.5 步驟 安裝Docker 安裝Squid容器 生成認證文件 配置Squid服務(wù)器 啟動Squid...
閱讀 3790·2021-11-18 13:20
閱讀 2810·2021-10-15 09:40
閱讀 1966·2021-10-11 10:58
閱讀 2216·2021-09-27 13:36
閱讀 2689·2021-09-07 10:06
閱讀 1949·2021-08-11 11:21
閱讀 1485·2019-08-29 17:04
閱讀 2146·2019-08-29 14:06
