剑指 Offer 10- I. 斐波那契数列

难度 简单

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

1
2

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1
2

输入：n = 2
输出：1

示例 2：

1
2

输入：n = 5
输出：5

提示：

• 0 <= n <= 100

前言：最近刷剑指offer刷到了动态规划相关的问题，之前没怎么学过，所以特地抽一天时间来学一下，以下为学习的笔记

动态规划

题目类型

1. 计数： 有多少种方式走到右下角 有多少种方法选出k个数使得和为Sum 2. 求最大最小值： 从左上角走到右下角路径的最大数字和 最长上升子序列长度 3. 求存在性： 取石子游戏，先手是否必胜 能不能选出k个数使得和是Sum

解题步骤

1. 确定状态 简单的说，就是解动态规划时需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似解数学题中，xyz代表什么一样，具体分为下面两个步骤：
   • 研究最优策略的最后一步
   • 化为子问题
2. 转移方程 根据子问题定义直接得到
3. 初始条件和边界情况 初始条件一般都是a[0]、a[1]这种，多看看 边界条件主要是看数组的边界，数组越不越界
4. 计算顺序 大部分从小到大迭代，精髓在于使用之前计算得到的结果

剑指 Offer 26. 树的子结构

难度 中等

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

3 / \ 4 5 / \ 1 2 给定的树 B：

4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1
2

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

1
2

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

1

0 <= 节点个数 <= 10000

剑指 Offer 32 - II. 从上到下打印二叉树 II

难度 简单

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

1
2
3
4
5

[
  [3],
  [9,20],
  [15,7]
]

提示：

1. 节点总数 <= 1000

注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

剑指 Offer 32 - I. 从上到下打印二叉树

难度 中等

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

返回：

1

[3,9,20,15,7]

提示：

1. 节点总数 <= 1000
   阅读全文 »