本文轉載自：中高級Java面試題解析，劍指BATJ，提前祝大家程序員節快樂
為什么大多數程序員相進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;
}
寫在最后
- 雄心是成功路上的指南，
- 信心是永不放棄的呼喚，
- 熱心是成功者的胸懷，
- 耐心是驅趕困難的利劍，
- 責任心是邁向成功的必然。
- 愿五心伴您度過每一天!
- 衷心祝大家面試一帆風順，馬到成功！
總結
以上是生活随笔為你收集整理的中高级Java面试题解析，剑指BATJ，提前祝大家程序员节快乐的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
