剑指 Offer 10- I. 斐波那契数列
简单动态规划
//
题目链接-来源：力扣（LeetCode）
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2输出：1
思路：最简单的动态规划，每次用2个变量迭代存储前2次的计算结果即可。为了免去2个变量来回转存的麻烦，可以用一个队列来存储这两个变量，把旧的变量弃置出队即可。
时间复杂度：O(n)空间复杂度：O(1)
实现：12345678910111213141516class Solution { public int fib(int n) { int mod = 1000000007; Q ...
剑指 Offer 09. 用两个栈实现队列
用栈实现队列
//
题目链接-来源：力扣（LeetCode）
示例 1：
输入：[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”][[],[3],[],[]]输出：[null,null,3,-1]
思路：栈的特点是后进先出，队列特点是后进后出。对于『后进』的特点， appendTail() 可以直接调用 push() ，我们只需特殊考虑怎么用『先出』实现『后出』。容易想到，用一个辅助栈 helper，将主栈 main 的元素依次压入辅助栈中，即『逆序』了主栈中的元素，此时弹出辅助栈顶元素即为我们需要的队列的头部元素，也即 deleteHead() 的返回值。然后将 helper 中元素依次放回 main 中。为了避免将元素在两个栈来回搬运，注意到从队列的视角看，helper 中的元素相对 main 都是较早进队的元素，那么出队时，我们优先考虑 helper 即可；同理，main中的元素较新，在入队时，我们要优先考虑 main。也就是说，在 helper 不空时，需要出队时我们只要对 helper 调用 pop() 即可，而入队时 对 ...
剑指 Offer 07. 重建二叉树
重建二叉树
//
题目链接-来源：力扣（LeetCode）
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder =[3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / 9 20 / 15 7
思路：经典二叉树题。给出一个中序序列和一个前序（后序）序列，建树（注意只有前序、后序序列的话无法唯一地建立一棵二叉树）。此类问题只要想办法定位根节点即可。对于本题，前序序列中的每一个节点，一定是后续子树的根节点，那么在中序序列中找到这个根节点，左侧即为左子树，右侧即为右子树。对每一个子树递归地重复这个建树过程即可。注意到不管是前序、中序还是后序序列，一个子树当中的所有元素总是紧邻地出现在一起，那么我们只需要分别记录两个序列中该子树的起始元素的指针、末尾元素的指针，就能在两个序列中划定子树范围，从而递归地执行。
时间复杂度：O(n)空间复杂度：O(n)
实现：12345678 ...
剑指 Offer 06. 从尾到头打印链表
反转链表
//
题目链接-来源：力扣（LeetCode）
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]输出：[2,3,1]
思路：题目不要求重组链表，只要求反向打印内容，那么用栈存储内容再逐个打印即可。
实现：12345678910111213141516class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> s = new Stack<>(); while (head != null) { s.push(head); head = head.next; } int[] ret = new int[s.size()]; int i = 0; while (!s.isEmpty()) { ...
剑指 Offer 05. 替换空格
字符串替换
//
题目链接-来源：力扣（LeetCode）
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：
输入：s = “We are happy.”输出：”We%20are%20happy.”
思路：字符串替换，可以用 StringBuilder 类轻松实现。对空格所在的指针 i 进行删除与插入操作即可。时间复杂度：O(n)空间复杂度：O(n)
实现：12345678910111213class Solution { public String replaceSpace(String s) { StringBuilder sb = new StringBuilder(s); for (int i = 0; i < sb.length(); i++) { if (sb.charAt(i) == ' ') { sb.deleteCharAt(i); sb.inser ...
剑指 Offer 04. 二维数组中的查找
有序矩阵查询
//
题目链接-来源：力扣（LeetCode）
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路：观察后可发现，对于某个矩阵元素，可以确定大小关系的是下侧（大于）和左侧（小于）。那么从右上角出发，与 target 相比较，target 较大则下移，反之左移，到达边界后如还未找到，即可返回 false。时间复杂度：O(m + n) m n为矩阵长度和宽度空间复杂度：O(1)
实现：123456789101112131415161718class So ...
剑指 Offer 03. 数组中重复的数字
先刷完剑指，再刷力扣主站。
//
题目链接-来源：力扣（LeetCode）
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
思路：越简单的题越要警惕执行效率。找出重复数字，需要O(1)复杂度的方案，容易想到用哈希表存储访问过的元素，之后碰见表中相同元素返回即可。时间复杂度：O(1)空间复杂度：O(N)
实现：123456789101112class Solution { public int findRepeatNumber(int[] nums) { Set<Integer> s = new HashSet<>(); for (int item : nums) { if (s.contains(item)) { ...