[笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 5

章节连结

一脚踏入软件工程师写 Code 的世界,不免俗地会碰上 Leetcode 的测验,来测试你的沟通力、系统性地解决问题的能力和如何化抽象为具体。第五周的活动要进入抽象的资料结构 Stacks, Queues & Tree 实作。
[笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 3


课程相关资讯

[连结]:https://www.accupass.com/event/2010251353233453323900

课程对应章节:Week5 U32~U39

请注意:本系列文章为个人对应课程的消化吸收后,所整理出来的内容。换言之,并不一定会包含全部的课程内容,也有可能会添加其他资源来说明。


内容

Array

在内存中是连续组成,这也是和 Linked List 最大差别。在后者要查找元素,必然得从头开始一个个遍历。

Stack

Last In First Out ( LIFO ),一般会有 push() [将一个东西新增], pop() [将一个东西移除], peek() / top() [取出顶端的值], isFull(), isEmpty() 这几种方法。

Queue

First In First Out ( FIFO ),一般会有 enqueue(), dequeue(), peek() / top(), isFull(), isEmpty()  这几种方法。

不过在 JavaScript 中,其 Array 已经内建了 push(), pop(), shift(), unshift() 这四种好用的方法,仅需要搭配组合就可以当成 stack 和 queue。Stack 为 push + pop. Queue 为 push + shift

Stack / Heap Memory

Stack Memory ( 由上往下的去存放静态变量到内存 ) / Heap Memory (由下往上存放动态变量到内存),而两者中间的区块就是尚未使用到的区块。

Stack Overflow

指的是内存中的 Stack,表示你的程式中的静态变量已经超出了内存 Stack 部分的使用量。

Garbage Collection

它会自己去猜想你的动态内存部分 (Heap) 是否有需要被清理掉的东西,然后帮你执行。例如 JAVA 有内建这个机制。

Tree

用下面图解来说明吧:你会发现这是每一条路径都是单向的连结,才不会有无穷循环的情形tree data structure

在实际练习时,也可以使用视觉化工具(如:Tree 视觉化工具)

Binary Search Tree

子节点最多两个、由左到右是由小到大的排序

Binary Heaps

子节点最多两个、可以细分为 Min-heap 和 Max-heap。以 Min-heap 为例子,父节点一定会比下方的子节点小

Tree Traversal

为何会有 Traversal 的区别,是因为这种立体的结构,若要显示在命令列中,那势必得转换成线性的状态。这样一来,就要决定怎样输出。

In-order

输出顺序是由小到大 ( 左中右 )

Pre-order

输出顺序是先 root,再左右 ( 中左右 )

Post-order

输出顺序 root 为最后 ( 左右中 )

LevelOrder

输出顺序依照阶层,然后同层中为左中右的形式

Traversal 的途径

BFS ( Breadth First Search )

广度优先,常搭配 Queue + loop / iteration 的形式,因为具有先进先出的特质,很适合用循环来执行

DFS ( Depth First Search )

深度优先,常搭配 Stack + Recursion 的形式,因为可使用递回找到目标物,再层层堆叠输出


LeetCode 题目

700. Search in a Binary Search Tree

连结:https://leetcode.com/problems/search-in-a-binary-search-tree/

100. Same Tree

连结:https://leetcode.com/problems/same-tree/

144. Binary Tree Preorder Traversal

连结:https://leetcode.com/problems/binary-tree-preorder-traversal/

841. Keys and Rooms

连结:https://leetcode.com/problems/keys-and-rooms/

102. Binary Tree Level Order Traversal

连结:https://leetcode.com/problems/binary-tree-level-order-traversal/


相关文章

  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 1
  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 2
  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 3
  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 4
  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 5-2
  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 6
  • [笔记] AlphaCamp 不只是刷题的 Leetcode 训练营 – 7
  • 按赞加入粉丝团

    延伸阅读