剑指 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)) { ...