满二叉树:
- 对于k层的二叉树来说,拥有 2k -1 个结点的二叉树称为满二叉树
- 度为0的结点(叶子结点)都在同一层上
完全二叉树:
- 二叉树的结点位置按照对应的完全二叉树的位置相吻合
- 最后一层的结点,一定是从左往右依次排满的
满二叉树:
完全二叉树:
动态规划与贪心的区别:
动态规划五部曲:
给定两个字符串 *s*
和 *t*
,编写一个函数来判断 *t*
是否是 *s*
的字母异位词。
**注意:**若 *s*
和 *t*
中每个字符出现的次数都相同,则称 *s*
和 *t*
互为字母异位词。
回溯就是一种搜索的方式,它通常用于在搜索过程中撤销
或回退
一些步骤,以便在发现错误或达到某种条件时重新尝试其他路径。
回溯算法的效率其实并不高,虽然可以通过剪枝操作
来提高效一些效率,但是效率仍然不高!
通过回溯做的题目类型:
深度优先遍历(dfs): 顺着一个方向遍历,就像是不到黄河不回头,直到没有元素了,再换另一个方向继续遍历。
广度优先遍历(bfs): 先遍历与本节点连接的所有节点,然后在遍历与下一个节点相连接的所有节点
其实dfs就是回溯,当遍历到头时,就需要回溯换另一个方向继续遍历。在二叉树中的递归遍历其实就是 dfs,而迭代遍历就是 bfs。
下面通过俩张动图,体会一下dfs和bfs的区别:
dfs:
给你一个整数数组 nums
。如果任一值在数组中出现 至少两次 ,返回 true
;如果数组中每个元素互不相同,返回 false
。
示例 1:
输入:nums = [1,2,3,1]
输出:true
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?
指定每次拿最大的,最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
贪心算法一般分为如下四步:
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。