type
status
date
slug
summary
tags
category
icon
password
😈剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
这道题目是经典的数据结构题目。我们可以用两个栈来实现队列的操作。一个栈用来存储入队的元素，另一个栈用来存储出队的元素。当需要出队时，如果出队的栈为空，则将入队的栈中的元素全部弹出并压入出队的栈中。这样，就可以实现队列的先进先出的操作了。时间复杂度为O(n)。
值得注意的是，当需要出队时，如果入队的栈和出队的栈都为空，则返回-1。
解题思路：
栈无法实现队列功能： 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。
双栈可实现列表倒序： 设有含三个元素的栈A=[1,2,3] 和空栈B=[]。若循环执行A元素出栈并添加入栈B，直到栈A 为空，则A=[]B=[3,2,1] ，即栈B 元素实现栈A 元素倒序 。利用栈B 删除队首元素： 倒序后，B 执行出栈则相当于删除了A 的栈底元素，即对应队首元素。
函数设计：
题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作，因此我们可以设计栈 A 用于加入队尾操作，栈 B 用于将元素倒序，从而实现删除队首元素。
加入队尾 appendTail()函数： 将数字 val 加入栈 A 即可。
删除队首deleteHead()函数： 有以下三种情况。
当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
否则，当 A 为空： 即两个栈都为空，无元素，因此返回−1 。
否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
😈剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
方法一：动态规划
斐波那契数的边界条件是F(0)=0 和F(1)=1。当n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：F(n)=F(n−1)+F(n−2)
由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为F(0) 和F(1)。
根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是
O(n) 的实现。由于F(n) 只和F(n−1) 与F(n−2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成O(1)。如下的代码中给出的就是这种实现。
计算过程中，答案需要取模1e9+7。
时间复杂度：O(n)。
空间复杂度：O(1)。
方法二：矩阵快速幂
首先我们可以构建这样一个递推关系：
方法一的时间复杂度是O(n)。使用矩阵快速幂的方法可以降低时间复杂度。
}
复杂度分析
时间复杂度：O(logn)。
空间复杂度：O(1)。
必杀技：
- Author:KIRITO
- URL:https://kirito.work/article/love
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!