剑指 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
    阅读全文 »