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

Aklman 发布于2019-08-22 16:19 / 2574人阅读

摘要：题目中的数字可以分割出来的连续数字串的所有组合，不同组合之间用一个和连接示例和和和和和和和和和和这里给同学提个醒。。解题思路利用二叉树。说到这这个题就很容易解决了，利用二叉树的层次遍历，每一层遍历的时候都基于上一层的遍历结果生成答案。

题目

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算法最小二乘法改进算法最小二乘法滤波算法最小二乘方算法解释

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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