敬畏自然绿水青山

Category: ICT-Information and Communication Technology

  • 树结构相关算法实例系列2-二叉搜索树相关的算法

    树结构是数据结构中常常出现的，且用到非常多的一种数据结构。树结构中常见的有二叉树，二叉搜索树，AVL树以及B树等。树结构一般可以用递归去求解，如二叉树的遍历算法中，有先序，中序和后续遍历，一般的树结构的遍历中，有DFS（深度优先遍历）和BFS（宽度优先遍历）等都是用递归来实现。今天的实例中，有用递归直接实现的，也有用递归间接实现的。具体问题要具体分析，下面将要介绍几种具体的方法。 实例1：判断一颗二叉树是否是一个有效的二叉搜索树？ 浅析：根据二叉搜索树的递归定义，其每个节点的左子树都要比当前节点小，其右子树都要比当前节点大。一个直观的想法是：1、首先判断根节点是否满足要求，如果不满足，直接返回false，程序停止；2、再递归判断左子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算；3、再递归判断右子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算。但仔细分析发现这个思路有缺陷，不能保证右子树的最小节点比根节点要大，或者左子树的最大节点比根节点要小。这道题可以先用中序遍历（可以用递归）的方式将结果存起来，因为二叉搜索树的中序遍历结果是有序的。通过检查中序遍历结果的有序性即可判断是否为二叉搜索树。 实例2：二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。 浅析：首先判断当前节点的值，如果比low要小，说明左子树都要比low小，直接递归调用右子树即可。反之如果比high值要大，则递归调用左子树。如果在low和hight之间（假设其值为val），则，左子树上，递归调用trim[low,val]或trim[low,high],右子树上递归调用trim[low,high],或trim[val, high]。 实例3：给定二叉树的根节点root ，返回所有左叶子之和。 浅析：比较容易判断是否为叶子节点，当为叶子节点时，还需要考虑其父节点指向的左孩子是否为当前的叶子节点。递归实现的示例代码如下： 实例4：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 浅析：通过递归可以找到要删除的节点，如果节点是叶子节点，则好办。如果不是叶子节点呢，这个时候需要找到该节点的后继节点（successor）进行替换，然后递归调用后继节点的删除操作。由于后继节点一般是右子树的最左边的节点（可能是叶子节点，可能是含有右子树的节点），删除相对比较容易，不会再次出现递归调用。这道题的具体分析可以参考引文中的说明，比较详细。 后续将继续分析更多的树类型的数据结构的不同的问题场景和解题思路。 Reference

  • 数据结构算法题解分析系列-动态规划的又三个实例浅析纪要

    动态规划(dynamic programming)是数据结构与算法中常用到的策略算法，一般是通过状态转移方程和初始状态来一起定义问题，从而将更大的问题转换为前面已经计算出结果的动态的更新的过程。动态规划的难点在于状态转移方程的定义，有得问题比较显而易见，而有的问题可能就比较难以定义，需要多从实际问题中总结相关的经验。 今天向大家介绍动态规划的三个示例，具体一一向大家进行介绍。 实例1：爬楼梯问题，也是经典的动态规划问题，描述如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 分析及解答，假设爬到n阶有methods[n]种方法，则有两种可能，先爬到n-2阶，然后跨2个台阶到达n阶，或者先爬到n-1阶，然后跨1个台阶达到n阶。因此状态转移方程为：dp[n]=dp[n-1]+dp[n-2]。初始状态为dp[0]=0,dp[1]=1,dp[2]=2。然后就可以用递推来进行循环计算了。 实例2：找零钱问题，给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。 分析及解答：假设所需最少的硬币个数为f[amount]，则状态转移方程可以表示为f[amount]=min(f[amount-conins[j]+1)，其中要求满足amount-conins[j]>0的所有的j。在递推求解的过程中，可以用双重循环来实现，外层从1到amount，内层j从0到硬币的个数-1，然后循环有个条件，及当前amount-coins[j]要大于零。 实例3：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 分析和解答：这是和第二个问题相似但思路差别较大的问题，这里不做详细分析，直接先给出状态转移方程并作出一定的解释。状态转移方程为：problem(k,i) = problem(k-1, i) + problem(k, i-k)。其中problem(k,i) 为一个二维的状态，其中第一个维度表示用到了前面的k个硬币，i表示当前的凑的金额。problem(k-1, i)表示只用到了前面k-1个硬币就已经凑到了i，不需要第k个硬币，problem(k, i-k)表示用到了前面k个硬币凑到了i-k，已经用到了第k个硬币。 关于代码实现，后续有机会再向大家进行分享，也希望自己后面有机会向大家逐步整理关于数据结构和算法的较为系统全面的介绍，欢迎大家提出意见和建议。

  • 交大老校区听讲座

    昨天去交大老校区去听了一下午的讲座，这是今年第一次去，恰巧很很高兴碰到了好多年未见得老同事们，感概大家还是老样子，感觉还是那么亲切，老校区的变化也不是很大，感觉也还是挺亲切，傍晚在食堂和听讲座新认识的律师朋友一起吃了碗面，短聊了会天，关于讲座的内容也在这里简要记录一下，仅供大家参考，也以备后需。 这次讲座主要的内容是医疗卫生行业的科技发展及产业转化的现状，学校有附属医院，有大规模的真实病例数据，以及医疗过程数据和相关治疗科技进展，也已经有相关的产业化的推进。这里记录两三个比较有印象的案例。 第一个关于精神类疾病的影像数据及人工智能辅助诊断系统，可以针对不同类别的病人的真实数据收集整理了大量的跨病类的数据集，并通过设计的人工智能算法达到对个体的影像数据进行自动诊断的目的，现有精确度尚可。当然最后的诊断还是以有经验的医生的判断为准； 第二个是基于脑电信号的情感智能以及疾病检测（如癫痫检测）方面的研究及在医疗方面的应用，对脑电信号的不断的精确的解码，专家们也相信以后机器人也将具有喜怒哀乐的情感。对于脑电信号的疾病检测以后也可能会应用到更多的疾病检测上，或者说以后的疾病检测的标记物不仅仅有影像数据，还有体液以及脑电等多模态数据，这样的诊断也会更加全面和精准； 第三个是基于脑机接口的视觉重建等方向，也许以后可以为失明失聪的人带来福音，期待对于这样的残疾人以后也能够有享受人类更多的天伦之乐的机会。 期待医疗行业随着数字化和智能技术的发展走上更加系统和全面科学化的道路，给全人类带来更多的福音，辅以图片以作纪念。感谢组织方的精心准备和可口的小点心。

  • AIGC体验7-Stable Diffusion使用技巧之ControlNet模型的使用2

    上篇短文向大家部分的介绍了ControlNet的使用示例，在Stable Diffusion的使用过程中，基础模型对于图像生成的质量的影响是挺关键的。在上篇介绍的短文中，我们使用了v1-5-pruned-emaonly这个模型，而在本文的示例中，我们将选择AnythingV5V3_v5PrtRE这个模型，从使用体验来说，该模型在生成人物方面的性能要明显优于v1-5-pruned-emaonly模型。相关的模型链接可以参考引文。 ControlNet还有更多的用法，读者可以进一步自行去尝试和积累经验，关于提示词的写法等还有不少的trick去在实践中模型和进一步总结，后续有相关的心得再去继续在这里分享。

  • AIGC体验6-Stable Diffusion使用技巧之ControlNet模型的使用1

    在文生图的应用中，用户经常会对生成的图形有特殊的要求，如局部重绘，满足边缘或深度条件，模糊变清晰，黑白变彩色，人体特定姿势(pose)等等。这篇短文将向大家介绍基于Stable Diffusion的ControlNet实现图像可控生成的几个示例，更加完整的介绍可以参考相关文献（这篇短文基于stable diffusion 1.5版本，具体可以使用引文3中给出的notebook）。 现有的stable diffusion的基础模型在人物生成上效果不是特别好，这篇短文暂时没有演示可控人物生成的效果，更多的场景会在后面的短文中进一步补充，欢迎大家关注，并提出意见建议。 References

  • AIGC体验5-Stable Diffusion使用技巧之LoRA模型的使用

    Stable Diffusion（SD）是开源的文生图大模型，随着相关技术的发展，已经迭代了多个版本（关于版本间不同的特性可以搜索查询，这里以1.5版本为例进行介绍，如和其兼容的lora模型比较多），并且其支持多种可控图像生成技巧，这篇短文将要向大家介绍相关的Stable Diffusion的使用技巧，不足支持欢迎读者提出意见建议并予以补充。 首先我们采用webui的方式使用比较便捷，参考文献1即为我们的Stable Diffusion V2.1版本的webui的jupyter notebook代码链接。具体使用可以在本地或colab里边。这篇短文将介绍SD的一般用法和基于LoRA模型的风格化用法。 一、一般用法：这里没有特别要强调说明的地方，主要是要写好提示词。这里举一个示例，提示词为：Two yellow orioles sing amid the green willows. 效果图为： 二、LoRA模型，lora模型是一种小模型技术，其显著的优点表现在：1、LoRA 通过低秩适应方法在较少的参数增加下微调大模型，资源消耗较少。2、在特定任务或小数据集上快速适应大模型，提升生成质量或特定任务的表现。3、LoRA模型可以作为额外模块加载到现有大模型中，灵活性高。使用LoRA模型的方法如下，1、首先，下载LoRA模型，如参考文献1所示；2、将下载的模型拷贝到lora的模型目录，如/content/stable-diffusion-webui/models/Lora，然后更新webui加载最新加入的lora模型(设置扫描lora模型路径)，提示词为：Two yellow orioles sing amid the green willows. SONG DYNASTY FLOWER AND BIRD PAINTING如下图所示。 其中该界面的操作流程为：settings–>additional networks–>Extra paths to scan for LoRA models(设置为/content/stable-diffusion-webui/models/Lora)–>apply settings–>Reload UI。在上面的图中，我们用到了一个LoRA模型，具体可以参考引文1。 下一篇相关文章将介绍ControlNet的相关用法，欢迎读者继续关注，提出问题和意见建议。 References

  • AIGC体验4-midjourney中人物一致性的实现

    在一般的电影和短视频中，一般的都存在的多个镜头(storyboard)，为了保证镜头切换的时候的人物的一致性，需要文生图模型对此有较好的支持，否则在文生图的自动生成的场景中就会存在着不满足分镜头设计的需求，大模型的可用性就会受到交大影响。 今天向大家介绍midjourney中怎么实现人物一致性，主要通过一个实例向大家做演示介绍。 首先，我们通过提示词生成一个人物的不同角度的4张图片，提示词如下： 根据上述提示词生成的图片效果为： 将图像保存到本地，然后通过工具裁剪成4个小的图片，然后点击下图中左下脚的“+”号按钮在弹出的菜单中选择“上传文件”，将上面裁剪的4个图片上传后，将其链接保存下来（通过点击放大每个图片然后鼠标右键图片上方获取图片链接，供四个链接）。 然后用/prefer option set命令来进行设置风格一致性，具体的指令形如下面截图： 然后，就可以指定以该”littleboy”的option来生成人物一致性的场景了。具体的示例指令为： 最终的效果为： 后面有机会将继续向大家介绍关于图像视频多媒体方面的大模型应用的一些技巧。欢迎感兴趣的读者关注并提出问题一起来商议探讨共同提高。

  • AIGC体验3-用Fliki+大模型制作短视频

    前面两篇短文向大家简要介绍了midjourney来进行绘图，今天向大家简要介绍一个支持在线的短视频制作的工具Fliki，不足之处欢迎大家批评指正并予以补充。 Fliki的官网为Fliki – Turn text into videos with AI voices， 其主要是根据故事分镜头来制作短视频，分镜头（storyboard）是影视制作中的术语，大概是一个连续的镜头来描述一个场景（如长镜头，宽镜头，远镜头等）。这方面经验也不是很足，以后有机会再补充相关细节。 首先我们用大模型（ChatGPT，通义千问，文心一言等）生成故事的分镜头脚本描述，也可以自己去描写。这里我们以登鹳雀楼为例，自己写的一个简单的分镜头场景描述来进行说明（暂时没有用到大模型来生成场景描述），用的是通义万象来生活场景图。 基于上述场景文字生成的图片后，我们就可以再Fliki中去生成这首小诗的短视频了，具体方法为下面的截图演示： 有必要对语音进行优化，可以考虑借助第三方语音合成平台生成整个的语音放到common sense的场景中去（最上方）。然后在每个分场景中去掉voiceover的layer。基本设置好后，就可以export然后就download了(注：为了去除水印，需要upgrade成会员） 更多的经验会在后续继续向大家介绍。 References

  • AIGC体验2-midjourney使用配置对生成的图片进行约束和限制

    上篇短文主要向大家介绍了midjourney的基本使用，在文生图的时候，有时作者期望有更多的控制条件，比如生成图片的大小和横竖比，生成图片的风格等。 首先可以通过命令/settings进行相关版本，以及模式的设置，输出结果为如下图示，具体关于这些模式的含义可以参考引文，这里不做赘述。 下面主要介绍一个使用一些约束和控制的示例 输出的结果如下图所示 点击“U4”后显示结果为： 加上图片风格和长宽比之后的示例如下： 点击“U4”后显示结果为： 后面将继续介绍相关使用的一些技能点。欢迎读者反馈意见和建议。 Reference

  • AIGC体验1-midjourney的初步使用

    midjourney在图片生成方向上有较高的质量，这篇博客简要记录一下其初步的使用方法。欢迎读者给出意见和建议，以及补充相关的说明。 注册后（注册过程忽略），可以建立自己的频道，方法如下几个图示。 然后就可以在对应的服务器里用相关命令生成图片了，这里举个示例，假设提示词为“Bright forest, little bunny Lily in front of home, sunlight shining on the grass”，则生成后的效果如下图所示： 具体后面更多的使用经验将在后续的体验过程中进一步加以记录。 References