【直通BAT】剑指Offer-经典试题整理(4)
32.1 不分行从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解法
先将根节点进入队列。
队头元素出队，将值存入 list，判断该元素是否有左/右子树，有的话依次进入队列中。队列为空时结束。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 从上到下打印二叉树
* @param root 二叉树根节点
* @return 结果list
*/
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
list.add(node.val);
}
return list;
}
}
32.2 分行从上往下打印二叉树
来源：AcWing
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
解法
与上一题类似，只不过需要用变量记录每一层要打印多少个节点。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 把二叉树打印成多行
* @param pRoot 二叉树根节点
* @return 结果list
*/
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
if (pRoot == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
int cnt = 1;
while (cnt > 0) {
int num = cnt;
cnt = 0;
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < num; ++i) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
++cnt;
}
if (node.right != null) {
queue.offer(node.right);
++cnt;
}
res.add(node.val);
}
list.add(res);
}
return list;
}
}
32.3 之字形打印二叉树
来源：AcWing
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
如二叉树：
1
/
2 3
/ /
4 5 6 7
打印结果为：
1
3 2
4 5 6 7
解法
对于上述二叉树：
首先访问根结点，之后把2、3存入某结构。打印的时候，先打印3、2。这不就是栈？
依次弹出栈元素，分别是3、2。弹出时需要把3、2的子结点存入结构。由于访问时顺序是4 5 6 7。所以也需要用栈来存放。而且，此时需要先存放右孩子，再存放左孩子。（奇数层/偶数层存放左右孩子的顺序不同）
这里需要用两个栈来实现。如果只用一个栈，那么当弹出3、2 时，先将 3 的孩子节点压入栈。之后弹栈的时候不是先弹出 2，而是弹出了 3 的 孩子节点，就错了。
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 按之字形打印二叉树
* @param pRoot 二叉树的根节点
* @return 结果list
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (pRoot == null) {
return res;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(pRoot);
int i = 1;
Stack<TreeNode> stack = stack1;
while (!stack.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (i % 2 == 1) {
if (node.left != null) {
stack2.push(node.left);
}
if (node.right != null) {
stack2.push(node.right);
}
} else {
if (node.right != null) {
stack1.push(node.right);
}
if (node.left != null) {
stack1.push(node.left);
}
}
}
res.add(list);
++i;
stack = stack1.isEmpty() ? stack2 : stack1;
}
return res;
}
}
33 二叉搜索树的后序遍历序列
来源：AcWing
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解法
序列的最后一个元素是二叉搜索树的根节点。
在序列中从左到右找到根节点的左子树(比根节点小)、右子树(比根节点大)。
-
如果右子树中出现比根节点小的元素，那么为 false。
-
否则递归左右子树。
public class Solution {
/**
* 判断数组是否是某个二叉搜索树的后序遍历序列
*
* @param sequence 数组
* @return 是否属于某二叉搜索树的后序遍历序列
*/
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence == null || sequence.length < 1) {
return false;
}
return verify(sequence, 0, sequence.length - 1);
}
private boolean verify(int[] sequence, int start, int end) {
if (start >= end) {
return true;
}
int val = sequence[end];
int i = start;
for (; i <= end; ++i) {
if (sequence[i] >= val) {
break;
}
}
for (int j = i; j < end; ++j) {
if (sequence[j] < val) {
return false;
}
}
return verify(sequence, start, i - 1) && verify(sequence, i, end - 1);
}
}
34 二叉树中和为某一值的路径
来源：AcWing
题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
解法
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
/**
* 找出二叉树中和为某一值的路径（必须从根节点到叶节点）
*
* @param root 二叉树的根结点
* @param target 目标值
* @return 结果list
*/
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
findPath(root, target, new ArrayList<>());
return res;
}
private void findPath(TreeNode root, int target, ArrayList<Integer> list) {
if (root == null) {
return;
}
list.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null) {
res.add(new ArrayList<>(list));
} else {
findPath(root.left, target, list);
findPath(root.right, target, list);
}
list.remove(list.size() - 1);
}
}
35 复杂链表的复刻
来源：AcWing
题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解法
- 第一步，在每个节点的后面插入复制的节点；
- 第二步，对复制节点的 random 链接进行赋值；
- 第三步，分离两个链表。
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
/**
* 复杂链表的复制
* @param pHead 链表头结点
* @return 复制的链表
*/
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode cur = pHead;
while (cur != null) {
RandomListNode node = new RandomListNode(cur.label);
node.next = cur.next;
cur.next = node;
cur = node.next;
}
cur = pHead;
while (cur != null) {
RandomListNode clone = cur.next;
if (cur.random != null) {
clone.random = cur.random.next;
}
cur = clone.next;
}
cur = pHead;
RandomListNode cloneHead = pHead.next;
while (cur.next != null) {
RandomListNode clone = cur.next;
cur.next = clone.next;
cur = clone;
}
return cloneHead;
}
}
36 二叉搜索树与双向链表
来源：AcWing
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解法
由于是二叉搜索树，因此中序遍历的结果就是排序的。
中序遍历利用栈来实现。遍历时，前一个结点的 right 指向后一个结点，后一个结点的 left 指向前一个结点。
pre.right = cur
cur.left = pre
import java.util.Stack;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 将二叉搜索树转换为双向链表
*
* @param pRootOfTree
* @return
*/
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = pRootOfTree;
TreeNode res = null;
TreeNode pre = null;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (pre == null) {
pre = cur;
res = pre;
} else {
pre.right = cur;
cur.left = pre;
pre = cur;
}
cur = cur.right;
}
}
return res;
}
}
39 数组中出现次数超过一半的数字
来源：AcWing
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。
解法
解法一
利用快排中的 partition 思想。
数组中有一个数字出现次数超过了数组长度的一半，那么排序后，数组中间的数字一定就是我们要找的数字。我们随机选一个数字，利用 partition() 函数，使得比选中数字小的数字都排在它左边，比选中数字大的数字都排在它的右边。
判断选中数字的下标 index：
-
如果
index = n/2，那么这个数字就是中位数。 -
如果
index > n/2，那么接着在 index 的左边进行 partition。 -
如果
index < n/2，则在 index 的右边继续进行 partition。
注意：这种方法会修改输入的数组。时间复杂度为 O(n)。
public class Solution {
/**
* 查找数组中出现次数超过一次的数字
*
* @param array 数组
* @return 返回该数，不存在则返回0
*/
public int MoreThanHalfNum_Solution(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int n = array.length;
int start = 0, end = n - 1;
int mid = n >> 1;
int index = partition(array, start, end);
while (index != mid) {
if (index > mid) {
end = index - 1;
} else {
start = index + 1;
}
index = partition(array, start, end);
}
return isMoreThanHalf(array, array[index]) ? array[index] : 0;
}
/**
* 快排中的 partition 方法
*
* @param array 数组
* @param start 开始位置
* @param end 结束位置
* @return
*/
private int partition(int[] array, int start, int end) {
int small = start - 1;
for (int i = start; i < end; ++i) {
if (array[i] < array[end]) {
swap(array, i, ++small);
}
}
++small;
swap(array, small, end);
return small;
}
private void swap(int[] array, int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
/**
* 判断val元素是否真的超过数组元素个数的一半
*
* @param array 数组
* @param val 某元素
* @return boolean
*/
private boolean isMoreThanHalf(int[] array, int val) {
int cnt = 0;
for (int e : array) {
if (e == val) {
++cnt;
}
}
return cnt * 2 > array.length;
}
}
解法二
利用多数投票算法，从头到尾遍历数组，遇到两个不一样的数就把这两个数同时除去。除去的两个数可能都不是 majority，也可能一个是 majority 另一个不是，但是因为 majority 总数大于一半，所以这么删完最后剩下的肯定是 majority。
此方法时间复杂度为 O(n)，且不会改变数组。
public class Solution {
/**
* 查找数组中出现次数超过一次的数字
*
* @param array 数组
* @return 返回该数，不存在则返回0
*/
public int MoreThanHalfNum_Solution(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int res = array[0];
int times = 1;
for (int i = 1; i < array.length; ++i) {
if (times == 0) {
res = array[i];
times = 1;
} else if (array[i] == res) {
++times;
} else {
--times;
}
}
return isMoreThanHalf(array, res) ? res : 0;
}
/**
* 判断val元素是否真的超过数组元素个数的一半
*
* @param array 数组
* @param val 某元素
* @return boolean
*/
private boolean isMoreThanHalf(int[] array, int val) {
int cnt = 0;
for (int e : array) {
if (e == val) {
++cnt;
}
}
return cnt * 2 > array.length;
}
}
40 最小的k个数
来源：AcWing
题目描述
输入 n 个整数，找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4。
解法
解法一
利用快排中的 partition 思想。
数组中有一个数字出现次数超过了数组长度的一半，那么排序后，数组中间的数字一定就是我们要找的数字。我们随机选一个数字，利用 partition() 函数，使得比选中数字小的数字都排在它左边，比选中数字大的数字都排在它的右边。
判断选中数字的下标 index：
-
如果
index = k-1，结束循环，返回前 k 个数。 -
如果
index > k-1，那么接着在 index 的左边进行 partition。 -
如果
index < k-1，则在 index 的右边继续进行 partition。
注意，这种方法会修改输入的数组。时间复杂度为 O(n)。
import java.util.ArrayList;
public class Solution {
/**
* 获取数组中最小的k个数
*
* @param input 输入的数组
* @param k 元素个数
* @return 最小的k的数列表
*/
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input == null || input.length == 0 || input.length < k || k < 1) {
return res;
}
int n = input.length;
int start = 0, end = n - 1;
int index = partition(input, start, end);
while (index != k - 1) {
if (index > k - 1) {
end = index - 1;
} else {
start = index + 1;
}
index = partition(input, start, end);
}
for (int i = 0; i < k; ++i) {
res.add(input[i]);
}
return res;
}
private int partition(int[] input, int start, int end) {
int index = start - 1;
for (int i = start; i < end; ++i) {
if (input[i] < input[end]) {
swap(input, i, ++index);
}
}
++index;
swap(input, index, end);
return index;
}
private void swap(int[] array, int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
解法二
利用大根堆，存储最小的 k 个数，最后返回即可。
此方法时间复杂度为 O(nlogk)。虽然慢一点，但是它不会改变输入的数组，并且它适合海量数据的输入。
假设题目要求从海量的数据中找出最小的 k 个数，由于内存的大小是有限的，有可能不能把这些海量的数据一次性全部载入内存。这个时候，用这种方法是最合适的。就是说它适合 n 很大并且 k 较小的问题。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
/**
* 获取数组中最小的k个数
*
* @param input 输入的数组
* @param k 元素个数
* @return 最小的k的数列表
*/
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input == null || input.length == 0 || input.length < k || k < 1) {
return res;
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Comparator.reverseOrder());
System.out.println(maxHeap.size());
for (int e : input) {
if (maxHeap.size() < k) {
maxHeap.add(e);
} else {
if (maxHeap.peek() > e) {
maxHeap.poll();
maxHeap.add(e);
}
}
}
res.addAll(maxHeap);
return res;
}
}
41 数据流中的中位数
来源：AcWing
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解法
利用大根堆存放较小的一半元素，小根堆存放较大的一半元素。维持大小堆的元素个数差不超过 1。
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
/**
* 插入一个数
*
* @param num 数
*/
public void Insert(Integer num) {
if (maxHeap.isEmpty() || num < maxHeap.peek()) {
maxHeap.offer(num);
if (maxHeap.size() - minHeap.size() > 1) {
minHeap.offer(maxHeap.poll());
}
} else {
minHeap.offer(num);
if (minHeap.size() - maxHeap.size() > 1) {
maxHeap.offer(minHeap.poll());
}
}
}
/**
* 获取中位数
*
* @return 中位数
*/
public Double GetMedian() {
int size1 = maxHeap.size();
int size2 = minHeap.size();
if (size1 > size2) {
return (double) maxHeap.peek();
}
if (size1 < size2) {
return (double) minHeap.peek();
}
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
42 连续子数组的最大和
来源：AcWing
题目描述
输入一个非空整型数组，数组里的数可能为正，也可能为负。 数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
解法
动态规划法。
res[i] 表示以第 i 个数字结尾的子数组的最大和，那么求出 max(res[i]) 即可。
-
res[i] = array[i], ifres[i - 1] < 0 -
res[i] = res[i - 1] + array[i], ifres[i - 1] >= 0
public class Solution {
/**
* 求连续子数组的最大和
*
* @param array 数组
* @return 最大和
*/
public int FindGreatestSumOfSubArray(int[] array) {
int n = array.length;
int[] res = new int[n];
res[0] = array[0];
int max = res[0];
for (int i = 1; i < n; ++i) {
res[i] = res[i - 1] > 0 ? res[i - 1] + array[i] : array[i];
max = Math.max(max, res[i]);
}
return max;
}
}
44 数字序列中某一位的数字
来源：AcWing
题目描述
数字以 0123456789101112131415… 的格式序列化到一个字符序列中。
在这个序列中，第 5 位（从 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。
请写一个函数求任意位对应的数字。
解法
举个栗子，求序列第 1001 位。
序列的前 10 位是 0~9， 这 10 个只有一位的数字。显然第 1001 位在这 10 个数字之后，因此这 10 个数字可以直接跳过。再从后面序列中找第 991（991=1001-10） 位的数字。接下来有 90 个两位数，共 180 位，由于 991>180，所以继续跳过。从 881 找...最后可以找到对应的数字以及数字的某一位。
public class Solution {
/**
* 求数字序列中某一位的数字
*
* @param n 第n位
* @return 第n位的数字
*/
public int digitAtIndex(int n) {
if (n < 0) {
return -1;
}
int digits = 1;
while (true) {
long numbers = countOfIntegers(digits);
if (n < digits * numbers) {
break;
}
n -= numbers * digits;
++digits;
}
return digitAtIndex(digits, n);
}
private long countOfIntegers(int digits) {
return digits == 1
? 10
: (int) (9 * Math.pow(10, digits - 1));
}
private int digitAtIndex(int digits, int n) {
int beginNumber = getBeginNumber(digits);
int val = beginNumber + n / digits;
int indexFromRight = digits - n % digits;
for (int i = 1; i < indexFromRight; ++i) {
val /= 10;
}
return val % 10;
}
private int getBeginNumber(int digits) {
return digits == 1
? 0
: (int) Math.pow(10, digits - 1);
}
}
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有
扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）
推荐阅读
