为什么大多数程序员相进BAT工作？
在中国互联网技术发展过程中，BAT带给我们程序员太多的回忆，20年发展过程中，他们各自形成自己的的体系和战略规划，掌握着中国互联网信息技术，很多新技术都是BAT创新，然后提供技术支持给我们普通的开发者，这就是程序员进入BAT工作最有力的说服力。
第一题：二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
- 由于 BST 的特性，采用中序遍历正好符合排序
- 要考虑 root 节点要与 左节点的最大值连接，与右节点的最小值连接
- 增加一个已排序链表的指针，指向最后一个已排序节点
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
TreeNode[] nodeList = {new TreeNode(-1)
}
;
ConvertToLink(pRootOfTree, nodeList);
TreeNode cursor = pRootOfTree;
while (cursor.left != null) {
cursor = cursor.left;
}
cursor.right.left = null;
return cursor.right;
}
private void ConvertToLink(TreeNode root, TreeNode[] nodeList) {
if (root == null) {
return;
}
ConvertToLink(root.left, nodeList);
root.left = nodeList[0];
nodeList[0].right = root;
nodeList[0] = root;
ConvertToLink(root.right, nodeList);
}
第二题：合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
- 双指针指向两个链表
- 循环选取最小值，加入结果集
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1);
ListNode cursor = head;
while (list1 != null || list2 != null) {
if (list1 == null) {
while (list2 != null) {
cursor.next = list2;
cursor = cursor.next;
list2 = list2.next;
}
continue;
}
if (list2 == null) {
while (list1 != null) {
cursor.next = list1;
cursor = cursor.next;
list1 = list1.next;
}
continue;
}
if (list1.val < list2.val) {
cursor.next = list1;
cursor = cursor.next;
list1 = list1.next;
} else {
cursor.next = list2;
cursor = cursor.next;
list2 = list2.next;
}
}
return head.next;
}
第三题：树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
- 遍历查找相等根节点
- 通过递归查找当前根节点下是否包含子树 root2
public Boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) {
return false;
}
LinkedList<TreeNode> pipeline = new LinkedList<>();
pipeline.addLast(root1);
while (!pipeline.isEmpty()) {
TreeNode node = pipeline.pop();
if (node == null) {
continue;
}
pipeline.addLast(node.left);
pipeline.addLast(node.right);
if (node.val == root2.val && isSub(node, root2)) {
return true;
}
}
return false;
}
private Boolean isSub(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null) {
return false;
}
if (root2 == null) {
return true;
}
if (root1.val == root2.val) {
return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
} else {
return false;
}
}
第四题：二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述：
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
解题思路
- 从上到下进行左右节点交换
public void Mirror(TreeNode root) {
if (root == null) return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
第五题：顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.
解题思路
- 通过4个指针，表示可打印区域，并对区域进行收缩
- 非 n*n 的矩阵，对于剩余非 4 边遍历的元素，要考虑边界
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
if (matrix.length == 0) {
return res;
}
if (matrix.length == 1) {
for (int i : matrix[0]) {
res.add(i);
}
return res;
}
int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
for (; left <= right && top <= bottom; ) {
if (top == bottom) {
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
break;
}
if (left == right) {
for (int i = top; i <= bottom; i++) {
res.add(matrix[i][left]);
}
break;
}
for (int p = left; p <= right; p++) {
res.add(matrix[top][p]);
}
top++;
for (int p = top; p <= bottom; p++) {
res.add(matrix[p][right]);
}
right--;
for (int p = right; p >= left; p--) {
res.add(matrix[bottom][p]);
}
bottom--;
for (int p = bottom; p >= top; p--) {
res.add(matrix[p][left]);
}
left++;
}
return res;
}
第六题：包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数（时间复杂度应为O（1））。
解题思路
- 通过增加最小栈来记录当前最小节点
private LinkedList<Integer> stack = new LinkedList<>();
private LinkedList<Integer> min = new LinkedList<>();
public void push(int node) {
stack.addLast(node);
if (min.isEmpty()) {
min.addLast(node);
return;
}
if (node < min.peekLast()) {
min.addLast(node);
} else {
min.addLast(min.peekLast());
}
}
public void pop() {
if (stack.isEmpty()) {
return;
}
stack.removeLast();
min.removeLast();
}
public int top() {
if (stack.peekLast() == null) {
return 0;
}
return stack.peekLast();
}
public int min() {
if (min.peekLast() == null) {
return 0;
}
return min.peekLast();
}
第七题：栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
解题思路
- 通过 Stack 进行模拟 push，当 pop 的节点等于 Stack 的 top 节点时，pop Stack
- 最后如果 Stack 剩余数据，则判定为 false
public Boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA.length != popA.length) {
return false;
}
if (pushA.length == 0) {
return false;
}
LinkedList<Integer> stack = new LinkedList<>();
int j = 0;
for (int value : pushA) {
stack.addLast(value);
while (stack.peekLast() != null && popA[j] == stack.getLast()) {
j++;
stack.removeLast();
}
}
return stack.isEmpty();
}
第八题：从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解题思路
- 层次遍历，通过队列进行辅助遍历
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
if (root == null) {
return res;
}
nodeQueue.addLast(root);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.pollFirst();
if (node == null) {
continue;
}
nodeQueue.addLast(node.left);
nodeQueue.addLast(node.right);
res.add(node.val);
}
return res;
}
第九题：二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 Yes ,否则输出 No 。假设输入的数组的任意两个数字都互不相同。
解题思路
- 后序遍历中，最后一个节点为 root 节点
- 由于 BST 的左子树都小于 root，右子树都大于 root，那么可以判定该节点是否为 BST
- 依次类推，通过递归方式，再判定左右子树
public Boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length == 0) {
return false;
}
if (sequence.length == 1) {
return true;
}
return isBST(sequence, 0, sequence.length - 1);
}
private Boolean isBST(int[] sequence, int start, int end) {
if (start < 0 || end < 0 || start >= end) {
return true;
}
int rootV = sequence[end];
int rightIndex = -1, rightV = Integer.MIN_VALUE;
for (int i = start; i < end; i++) {
if (rightV == Integer.MIN_VALUE && sequence[i] > rootV) {
rightV = sequence[i];
rightIndex = i;
continue;
}
if (rightV != Integer.MIN_VALUE && sequence[i] < rootV) {
return false;
}
}
return isBST(sequence, start, rightIndex - 1) && isBST(sequence, rightIndex, end - 1);
}
第十题：二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的 list 中，数组长度大的数组靠前)
解题思路
- 将走过的路径记录下来，当走过路径总和 = target 并且当前节点是叶子节点时，该路径符合要求
- 通过递归遍历所有可能的路径
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
FindPath(res, new LinkedList<>(), root, 0, target);
res.sort(Comparator.comparingint(list -> -list.size()));
return res;
}
private void FindPath(ArrayList<ArrayList<Integer>> res,
LinkedList<Integer> path,
TreeNode node,
int pathSum,
int target) {
if (node == null) {
return;
}
if (pathSum > target) {
return;
}
if (pathSum + node.val == target && node.right == null && node.left == null) {
ArrayList<Integer> resPath = new ArrayList<>(path);
resPath.add(node.val);
res.add(resPath);
return;
}
path.addLast(node.val);
if (node.left != null) {
FindPath(res, path, node.left, pathSum + node.val, target);
}
if (node.right != null) {
FindPath(res, path, node.right, pathSum + node.val, target);
}
path.removeLast();
}
第十一题：复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head 。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路
- 复制每个节点，如：复制节点 A 得到 A1 ，将 A1 插入节点 A 后面
- 遍历链表，并将 A1->random = A->random->next;
- 将链表拆分成原链表和复制后的链表
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode cursor = pHead;
while (cursor != null) {
RandomListNode copyNode = new RandomListNode(cursor.label);
RandomListNode nextNode = cursor.next;
cursor.next = copyNode;
copyNode.next = nextNode;
cursor = nextNode;
}
cursor = pHead;
while (cursor != null) {
RandomListNode copyNode = cursor.next;
if (cursor.random == null) {
cursor = copyNode.next;
continue;
}
copyNode.random = cursor.random.next;
cursor = copyNode.next;
}
RandomListNode copyHead = pHead.next;
cursor = pHead;
while (cursor.next != null) {
RandomListNode copyNode = cursor.next;
cursor.next = copyNode.next;
cursor = copyNode;
}
return copyHead;
}
第十二题：字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路
- 将字符串划分为两个部分，第一个字符以及后面的其他字符
- 将第一个字符和后面所有字符进行交换
对于 abc 这个字符串，计算出的排列顺序为：
abc
acb
bac
bca
cba
cab
代码：
public ArrayList<String> Permutation(String str) {
Set<String> res = new HashSet<>();
if (str == null || str.length() == 0) {
return new ArrayList<>();
}
Permutation(res, str.toCharArray(), 0);
ArrayList<String> list = new ArrayList<>(res);
list.sort(String::compareTo);
return list;
}
private void Permutation(Set<String> res, char[] chars, int start) {
if (start == chars.length) {
res.add(new String(chars));
return;
}
for (int i = start; i < chars.length; i++) {
swap(chars, start, i);
Permutation(res, chars, start + 1);
swap(chars, start, i);
}
}
private void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
第十三题：数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出 2 。如果不存在则输出 0。
解题思路
- 由于数组的特性，在排序数组中，超过半数的数字一定包含中位数
- 通过 partition 方法，借用快排的思想，随机选取一个 key，将数组中小于 key 的移动到 key 的左侧，数组中大于 key 的移动到 key 的右侧
- 最终找到中位数的下标，还需要检查中位数是否超过半数
public int MoreThanHalfNum_Solution(int[] array) {
int start = 0, end = array.length - 1;
int mid = array.length / 2;
int index = partition(array, start, end);
if (index == mid) {
return array[index];
}
while (index != mid && start <= end) {
if (index > mid) {
end = index - 1;
index = partition(array, start, end);
} else {
start = index + 1;
index = partition(array, start, end);
}
}
if (checkIsHalf(array, index)) return array[index];
return 0;
}
private Boolean checkIsHalf(int[] array, int index) {
if (index < 0) {
return false;
}
int count = 0;
for (int i : array) {
if (array[index] == i) {
count++;
}
}
return count > array.length / 2;
}
private int partition(int[] array, int start, int end) {
if (start >= array.length || start < 0
|| end >= array.length || end < 0) {
return -1;
}
int key = array[start];
int left = start, right = end;
while (left < right) {
while (left < right && array[right] >= key) {
right--;
}
if (left < right) {
array[left] = array[right];
left++;
}
while (left < right && array[left] <= key) {
left++;
}
if (left < right) {
array[right] = array[left];
right--;
}
}
array[left] = key;
return left;
}
第十四题：最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解题思路
1. Partition
该算法基于 Partition
public ArrayList<Integer> GetLeastNumbers_Solution_Partition(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (k > input.length || k < 1) {
return res;
}
int start = 0, end = input.length - 1;
int index = partition(input, start, end);
while (index != k - 1) {
if (index > k - 1) {
end = index - 1;
index = partition(input, start, end);
} else {
start = index + 1;
index = partition(input, start, end);
}
}
for (int i = 0; i < input.length && i < k; i++) {
res.add(input[i]);
}
return res;
}
private int partition(int[] nums, int start, int end) {
int left = start, right = end;
int key = nums[left];
while (left < right) {
while (left < right && nums[right] > key) {
right--;
}
if (left < right) {
nums[left] = nums[right];
left++;
}
while (left < right && nums[left] <= key) {
left++;
}
if (left < right) {
nums[right] = nums[left];
right++;
}
}
nums[left] = key;
return left;
}
2. 小根堆算法
该算法基于小根堆，适合海量数据，时间复杂度为：n*logk
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (k > input.length||k==0) {
return res;
}
for (int i = input.length - 1; i >= 0; i--) {
minHeap(input, 0, i);
swap(input, 0, i);
res.add(input[i]);
if (res.size() == k) break;
}
return res;
}
private void minHeap(int[] heap, int start, int end) {
if (start == end) {
return;
}
int childLeft = start * 2 + 1;
int childRight = childLeft + 1;
if (childLeft <= end) {
minHeap(heap, childLeft, end);
if (heap[childLeft] < heap[start]) {
swap(heap, start, childLeft);
}
}
if (childRight <= end) {
minHeap(heap, childRight, end);
if (heap[childRight] < heap[start]) {
swap(heap, start, childRight);
}
}
}
private void swap(int[] nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
第十五题：连续子数组的最大和
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
解题思路
通过动态规划计算最大和，$$f(i)$$定义为以第$$i$$个数字结尾的子数组的最大和，那么$$max(f(i))$$就有以下公式：
$$ max(f(i))=begin{cases} num[i] & i=0 or f(i)<0\ num[i]+f(i) & ine0 and f(i)>0 end{
cases
}
$$
public int FindGreatestSumOfSubArray(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int max = array[0];
int sum = 0;
for (int a : array) {
if (sum + a > a) {
sum += a;
} else {
sum = a;
}
if (sum > max) {
max = sum;
}
}
return max;
}
写在最后：
面试题还有很多，但是本文章限于篇幅，只分享15到一线互联网面试真题；关于本人所设计到的面试题，本人都已经整理成一份完整的PDF面试题集合，现免费分享给各位有需要的Java工程师朋友，点击下方传送门即可免费领取哟
传送门
- 雄心是成功路上的指南，
- 信心是永不放弃的呼唤，
- 热心是成功者的胸怀，
- 耐心是驱赶困难的利剑，
- 责任心是迈向成功的必然。
- 愿五心伴您度过每一天!
- 衷心祝大家面试一帆风顺，马到成功！
网友评论