剑指Offer

数组中出现次数超过一半的数字(剑指Offer-39) 题面 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 2输出: 2 限制 11 <= 数组长度 <= 50000 思路 摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。 ...

字符串的排列(剑指Offer-38) 题面 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例 1输入：s = "abc" 2输出：["abc","acb","bac","bca","cab","cba"] 限制 11 <= s 的长度 <= 8 思路 dfs遍历回溯。 ...

二叉树中和为某一值的路径(剑指Offer-34) 题面 请实现两个函数，分别用来序列化和反序列化二叉树。 示例 给定如下二叉树，以及目标和 target = 22， 1 5 2 / \ 3 4 8 4 / / \ 5 11 13 4 6 / \ / \ 7 7 2 5 1 返回: ...

序列化二叉树(剑指Offer-37) 题面 请实现两个函数，分别用来序列化和反序列化二叉树。 示例 1你可以将以下二叉树： 2 3 1 4 / \ 5 2 3 6 / \ 7 4 5 8 9序列化为 "[1,2,3,null,null,4,5]" 思路 BFS层序遍历即可，注意，如果节点为null，则它的子节点就不记录。 ...

二叉搜索树与双向链表(剑指Offer-36) 题面 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： ...

复杂链表的复制(剑指Offer-35) 题面 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 示例 1： ...

二叉搜索树的后序遍历序列(剑指Offer-33) 题面 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 ...

从上到下打印二叉树III(剑指Offer-32.3) 题面 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 ...

从上到下打印二叉树II(剑指Offer-32.2) 题面 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null,15,7], 1 3 2 / \ 3 9 20 4 / \ 5 15 7 返回： ...

从上到下打印二叉树(剑指Offer-32.1) 题面 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null,15,7], 1 3 2 / \ 3 9 20 4 / \ 5 15 7 返回： ...

栈的压入、弹出序列(剑指Offer-31) 题面 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 ...

包含min函数的栈(剑指Offer-30) 题面 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例 1MinStack minStack = new MinStack(); 2minStack.push(-2); 3minStack.push(0); 4minStack.push(-3); 5minStack.min(); --> 返回 -3. 6minStack.pop(); 7minStack.top(); --> 返回 0. 8minStack.min(); --> 返回 -2. 限制 1各函数的调用总次数不超过 20000 次 思路 除了常规的栈，再维护一个单调栈，从栈顶到栈底递增 ...

顺时针打印矩阵(剑指Offer-29) 题面 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 示例 1： 1输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 2输出：[1,2,3,6,9,8,7,4,5] 示例 2： ...

对称的二叉树(剑指Offer-28) 题面 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 1 2 / \ 3 2 2 4 / \ / \ 5 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: ...

二叉树的镜像(剑指Offer-27) 题面 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 1 4 2 / \ 3 2 7 4 / \ / \ 51 3 6 9 镜像输出： 1 4 2 / \ 3 7 2 4 / \ / \ 59 6 3 1 示例 1输入：root = [4,2,7,1,3,6,9] 2输出：[4,7,2,9,6,3,1] 限制 10 <= 节点个数 <= 1000 思路 递归。 ...

树的子结构(剑指Offer-26) 题面 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: ...

合并两个排序的链表(剑指Offer-25) 题面 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例 1输入：1->2->4, 1->3->4 2输出：1->1->2->3->4->4 限制 10 <= 链表长度 <= 1000 思路 链表合并，设立一个伪头结点可以方便代码书写。 ...

反转链表(剑指Offer-24) 题面 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例 1输入: 1->2->3->4->5->NULL 2输出: 5->4->3->2->1->NULL 限制 10 <= 节点个数 <= 5000 思路 链表原地转置。 ...

链表中倒数第k个节点(剑指Offer-22) 题面 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 ...

调整数组顺序使奇数位于偶数前面(剑指Offer-21) 题面 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 示例 1输入：nums = [1,2,3,4] 2输出：[1,3,2,4] 3注：[3,1,2,4] 也是正确的答案之一。 限制 0 <= nums.length <= 50000 1 <= nums[i] <= 10000 思路 定义头指针 left，尾指针 right。left 一直往右移，直到它指向的值为偶数，right 一直往左移，直到它指向的值为奇数。交换 nums[left] 和 nums[right]。重复上述操作，直到 left==right . ...

表示数值的字符串(剑指Offer-20) 题面 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"+-5"及"12e+5.4"都不是。 ...

正则表达式匹配(剑指Offer-19) 题面 请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。 ...

删除链表的节点(剑指Offer-18) 题面 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 **注意：**此题对比原题有改动 示例 示例 1： ...

打印从1到最大的n位数(剑指Offer-17) 题面 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例 示例 1： 1输入: n = 1 2输出: [1,2,3,4,5,6,7,8,9] 限制 用返回一个整数列表来代替打印 n 为正整数 思路 简简单单for循环。 ...

二进制中1的个数(剑指Offer-16) 题面 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。 示例 示例 1： 1输入：x = 2.00000, n = 10 2输出：1024.00000 示例 2： ...

二进制中1的个数(剑指Offer-15) 题面 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。 ...

剪绳子II(剑指Offer-14.2) 题面 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 ...

剪绳子(剑指Offer-14.1) 题面 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 ...

机器人的运动范围(剑指Offer-13) 题面 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ ...

矩阵中的路径(剑指Offer-12) 题面 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 ...