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

Aklman 發布于2019-08-22 16:19 / 2636人閱讀

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

題目

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

示例：
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"進行組合后的來的。

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

代碼

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

輸出測試：

這個算法的時間空間復雜度均為O(二叉樹的節點數)，也就是O(2^n)

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

云服務器 GPU云服務器 webrtc之vad算法最小二乘法改進算法最小二乘法濾波算法最小二乘方算法解釋

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/94233.html

算法之不定期更新（四）—— 從前序與中序遍歷序列構造二叉樹（2018-06-02）

摘要：樹的前序，中序遍歷的結構如下圖可以看出，通過前序遍歷可以確定根節點，再通過中序遍歷和根節點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。從前序與中序遍歷序列構造二叉樹今天帶來的是Leetcode上的一個經典題：從前序與中序遍歷序列構造二叉樹原題干： /** Definition for a binary ...

charles_paul 2019-08-26 11:57 評論0 收藏0
算法之不定期更新（三）（2018-04-24）

摘要：實現這個想法之后就發現，時間復雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級，還有好多已經說爛了的題就不分享了。如果有什么意見或者想法歡迎在評論區和我交流題目 input: n // 代表無向圖的頂點數 // 從1開始 m // 無向圖的邊數 arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點0和頂點2相連，頂點3和頂點4相連） ...

darryrzhong 2019-08-22 16:40 評論0 收藏0
算法之不定期更新（一）（2018-04-12）

摘要：算法的確有他獨特的魅力。然后我在做這個題的時候，其實也用到了類似質因數分解，只是其實我們可以更好的利用到因數這一個特性。判斷一個數是否是質數質數列表一開始我們認為每一個數都可能是自身的冪線性篩為質數遍歷質數列表為質數的冪前言從三月份到現在，大大小小筆試了十幾家公司（主要是因為一直solo code，沒人內推），然后也能感覺到自己的進步把。從編程題只能ac一題到后來的ak。今天面騰訊...

Martin91 2019-08-22 16:16 評論0 收藏0
前端資源系列（4）-前端學習資源分享&前端面試資源匯總

摘要：特意對前端學習資源做一個匯總，方便自己學習查閱參考，和好友們共同進步。特意對前端學習資源做一個匯總，方便自己學習查閱參考，和好友們共同進步。本以為自己收藏的站點多，可以很快搞定，沒想到一入匯總深似海。還有很多不足&遺漏的地方，歡迎補充。有錯誤的地方，還請斧正... 托管: welcome to git，歡迎交流，感謝star 有好友反應和斧正，會及時更新，平時業務工作時也會不定期更...

princekin 2019-08-20 11:28 評論0 收藏0
使用Docker搭建Squid代理服務器

摘要：已發出請求，正在等待回應長度正在保存至用時已保存認證失敗正在連接已連接。參考參考一參考二 title: Docker搭建代理服務器 tags: - Squid categories: - Linux [TOC] 環境說明項目說明系統 Deepin 15.5 步驟安裝Docker 安裝Squid容器生成認證文件配置Squid服務器啟動Squid...

syoya 2019-06-28 16:23 評論0 收藏0