题目来源：牛客网
题目一 调整数组序列使奇数位于偶数序列前
描述: 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路: 代码
要求:奇数和奇数,偶数和偶数的相对位置不变
- 解法一: 从最后面开始,两个两个比较,如果遇到相邻两个数左边的是偶数,右边的是奇数,则互换位置;否则换下一个; 时间复杂度较高O(n^2);
- 解法二: 在新建两个数组,分别存放奇数和偶数,一次遍历后将奇偶分开存入数组,然后在将两个数组中的数据返回,时间复杂度较低,但是空间复杂度较高;(未给出代码)
题目二 链表中倒数第k个节点
描述:
输出链表中倒数第k个节点;
解题思路: 代码
- 解法一: 使用栈,该方法会消耗较大资源,不建议使用;
- 解法二: 先复制两个节点,第一个节点从头走到k的位置; 然后两个节点以前执行.next,当第一个节点走到链表尾时,第二个节点即走到倒数k的位置;(该解法时间复杂度只有O(n),目前为止最佳解法)
题目三 反转链表
描述:
输入一个链表，反转链表后，输出链表的所有元素。
代码
题目四 合并两个排序的链表
描述: 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路: 代码
- 定义一个新的链表listnode;
- 判断list1和list2的val值,那个小就让listnode的next指向哪个节点;
- 使用递归,将list1和list2的值全部遍历;本题不难,常规的递归;
题目五 树的子结构
描述:
输入两颗二叉树A，B，判断B是不是A的子结构。
解题思路:代码
依旧递归:使用两次递归;
- 在树A中找到和B的根节点的值一样的结点R；第一次递归
- 第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构; 第二次递归
题目六 二叉树的镜像
描述:
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:二叉树的镜像定义：
源二叉树
8
/ \
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ / \
11 9 7 5
解题思路: 代码
千年递归:
- 从叶子节点互换;
- 使用递归,从下往上开始交换;
题目七 顺时针打印矩阵
描述:
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路: 代码
- 找到左上角和右下角元素的坐标,依次顺时针打印第一圈;
- 左上角元素加1,右下角元素减1;
- 按照第一步的方法打印第二圈元素;
- 直到左上角元素坐标值大于右下角坐标值;
题目八 包含min函数的栈
描述:
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数;
解题思路: 代码
- 使用两个栈,data栈存需要存储的元素,min栈存小元素;
- push栈的时候,元素存进data栈,如果该元素小于上一个存入的元素,则存入min栈,否则不如min栈;
- pop:如果data栈和min栈pop出的元素不等,则再将min栈pop出的元素push进去;该步是为了防止min元素被pop出;
- top函数为了将min元素移动到栈顶;
- min函数均是得到最小元素,得到pop后在push进去,类似与peek()函数;
题目九 栈的压入、弹出序列
描述:
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
解题思路: 代码
- 按照栈的压入顺序将元素依次压入栈;
- 入栈过程中同时按照弹出顺序出栈,如果栈顶元素等于出栈的顺序元素,则,出栈;
- 执行完成后,判断栈是否为空,如果为空,则表示该序列为栈的弹出序列;
题目十 从上往下打印二叉树
描述:
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解题思路:代码
该题目即为二叉树的层序遍历: 使用队列解决;
- 将二叉树的跟节点赋给LinkedList<TreeNode>队列;
- 在队列出队的同时将左右两子树分别入队;
- 队列出队完成即得到层序遍历;
题目十一 二叉搜索树的后序遍历序列
描述:
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路:代码
- 二叉搜索数,左子树的值都小于右子树的值;
- 后序遍历,数组最后一个数字为跟节点;
- 得到跟节点后,可以将数组前n-1个数分为左右两部分,左部分的数值均小于右部分的值;
- 递归,3中得到的左右两部分数值均可以按照2,3步骤重复执行;
- 若递归后全部判断正确,则返回true;
题目十二 二叉树中和为某一值的路径
描述:
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解题思路:代码
从头结点开始,使用递归的方法分别向左向右遍历,看是否存在某条路径所有的结点值相加等于该target.
查看代码中控制台输出的值则可理解栈的应用.
剑指Offer笔试题（3）
以上代码全部托管在 Github
