script (⏱,💰)

script (⏱,💰)

NG#2 - 二叉树

没有完成入门任务的参考安装入门

Puzzling Pyramids 是 Cairo 的 数据结构与算法任务 Think Cairo 的第二篇,主要解决二叉树问题,共有两个小题。

中序 DFS#

pyramids_02_cd51837de0

如图需要把二叉树从左到右转换为列表,稍微懂算法就知道是中序的 DFS (深度优先搜索),可以在互联网上搜到很多解析。

在实际写 cairo 代码时,当遇到该如何定义空 array,如何索引等问题,可以参考 https://book.cairo-lang.org/ch03-01-arrays.html

lower_chambers 是 Option 类型,不知道如何操作 Option 类型可参考 https://book.cairo-lang.org/ch06-02-the-match-control-flow-construct.html?highlight=Option#matching-with-options

这个问题可用非递归的方式解决,也可用递归方式来解决。由于 cairo 的 array 内置函数不够(写上一个任务应该能感受到),实际写起来会更麻烦。所以建议用递归来写。

可先看看官方的 fib 的递归版本,道理是一样的 https://github.com/starkware-libs/cairo/blob/main/examples/fib_array.cairo

递归函数实现每个节点执行 "判断并递归左叶 -> 添加节点 -> 判断并递归右叶" 的逻辑。

有几个重点:

  • 递归需要把元素 append 到列表里,该列表需要加上 ref 关键字,在递归中会引用同一个 array。
  • 递归函数也需要实现 Clone和 Drop,写法和 PyramidIntoArray 中一样。但 GitHub 库里的 cairo 新版本写法有点不同。
  • chambers 先转成 snapshot,就可以多次引用不会导致所有权问题。再用 clone 转回原来的类型,append 进列表里。
  • 如果测试不通过,可用 use debug::PrintTrait;[变量].print(); 去 debug

搜索路径#

puzzling_pyramids_04_683fbd4b56

第二小题需要实现搜索路径,同样是 DFS,但比第一题要难写得多。

测试用例如下,寻找 k,需要返回 [h,l,j,k]

         h
   d           l
 b    f     j     n
a c  e g   i k   m o

同样还是递归解决,建一个列表用于存储结果,调用递归函数,递归函数需要实现每个节点执行:

  1. 任意一个节点,如果值就是 key,就返回 index
  2. 如果值不是 key,就查 left 和 right,进行递归,返回 array,或者返回 None
  3. 拿到子叶递归返回的 array,append 上当前 index

例如上面测试用例的 j 进行递归,得到 Option::None[k].append(j),返回到 l 节点就是 [k,j].append(l)Option::None,返回到 h 就是 [k,j,l].append(h)。(以上都需要换成 index 操作,原因见下面的注意事项)

由于 cairo 不支持 append_front,只能往后面 append,最后写个 loop 翻转得到的路径 array

注意事项:

总结#

ng3_result

如果算法基础不好,任务还是挺难的。一开始我用的非递归方法,最终遇到了 ref array 的循环赋值语言层面报错 bug。后来编写递归,也遇到了很多语法问题,写了很久才完成,收获很大。希望以上思路对你有帮助。

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。