# **[本站小福 利 點我獲取阿里云優(yōu)惠券]** 為什么大多數(shù)程序員相進BAT工作？ 在中國互聯(lián)網(wǎng)技術(shù)發(fā)展過程中，BAT帶給我們程序員太多的回憶，20年發(fā)展過程中，他們各自形成自己的的體系和戰(zhàn)略規(guī)劃，掌握著中國互聯(lián)網(wǎng)信息技術(shù)，很多新技術(shù)都是BAT創(chuàng)新，然后提供技術(shù)支持給我們普通的開發(fā)者，這就是程序員進入BAT工作最有力的說服力。 第一題：二叉搜索樹與雙向鏈表 輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。 解題思路 由于 BST 的特性，采用中序遍歷正好符合排序 要考慮 root 節(jié)點要與 左節(jié)點的最大值連接，與右節(jié)點的最小值連接 增加一個已排序鏈表的指針，指向最后一個已排序節(jié)點 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; nodeList.right = root; nodeList = root; ConvertToLink(root.right, nodeList); } 第二題：合并兩個排序的鏈表 輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 解題思路 雙指針指向兩個鏈表 循環(huán)選取最小值，加入結(jié)果集 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; } 第三題：樹的子結(jié)構(gòu) 輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)） 解題思路 遍歷查找相等根節(jié)點 通過遞歸查找當前根節(jié)點下是否包含子樹 root2 public Boolean HasSubtree(TreeNode root1, TreeNode root2) { if (root2 == null) { return false; } LinkedList 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 解題思路 從上到下進行左右節(jié)點交換 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); } 第五題：順時針打印矩陣 輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10. 解題思路 通過4個指針，表示可打印區(qū)域，并對區(qū)域進行收縮 非 n*n 的矩陣，對于剩余非 4 邊遍歷的元素，要考慮邊界 public ArrayList printMatrix(int[][] matrix) { ArrayList res = new ArrayList<>(); if (matrix.length == 0) { return res; } if (matrix.length == 1) { for (int i : matrix) { res.add(i); } return res; } int top = 0, bottom = matrix.length - 1, left = 0, right = matrix.length - 1; for (; left = left; p--) { res.add(matrix); } bottom--; for (int p = bottom; p >= top; p--) { res.add(matrix); } left++; } return res; } 第六題：包含min函數(shù)的棧 定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的 min 函數(shù)（時間復(fù)雜度應(yīng)為O（1））。 解題思路 通過增加最小棧來記錄當前最小節(jié)點 private LinkedList stack = new LinkedList<>(); private LinkedList 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(); } 第七題：棧的壓入、彈出序列 輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的） 解題思路 通過 Stack 進行模擬 push，當 pop 的節(jié)點等于 Stack 的 top 節(jié)點時，pop Stack 最后如果 Stack 剩余數(shù)據(jù)，則判定為 false public Boolean IsPopOrder(int[] pushA, int[] popA) { if (pushA.length != popA.length) { return false; } if (pushA.length == 0) { return false; } LinkedList stack = new LinkedList<>(); int j = 0; for (int value : pushA) { stack.addLast(value); while (stack.peekLast() != null && popA == stack.getLast()) { j++; stack.removeLast(); } } return stack.isEmpty(); } 第八題：從上往下打印二叉樹 從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。 解題思路 層次遍歷，通過隊列進行輔助遍歷 public ArrayList PrintFromTopToBottom(TreeNode root) { ArrayList res = new ArrayList<>(); LinkedList 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; } 第九題：二叉搜索樹的后序遍歷序列 輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出 Yes ,否則輸出 No 。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。 解題思路 后序遍歷中，最后一個節(jié)點為 root 節(jié)點 由于 BST 的左子樹都小于 root，右子樹都大于 root，那么可以判定該節(jié)點是否為 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; int rightIndex = -1, rightV = Integer.MIN_VALUE; for (int i = start; i < end; i++) { if (rightV == Integer.MIN_VALUE && sequence > rootV) { rightV = sequence; rightIndex = i; continue; } if (rightV != Integer.MIN_VALUE && sequence < rootV) { return false; } } return isBST(sequence, start, rightIndex - 1) && isBST(sequence, rightIndex, end - 1); } 第十題：二叉樹中和為某一值的路徑 輸入一顆二叉樹的跟節(jié)點和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。(注意: 在返回值的 list 中，數(shù)組長度大的數(shù)組靠前) 解題思路 將走過的路徑記錄下來，當走過路徑總和 = target 并且當前節(jié)點是葉子節(jié)點時，該路徑符合要求 通過遞歸遍歷所有可能的路徑 public ArrayList> FindPath(TreeNode root, int target) { ArrayList> res = new ArrayList<>(); FindPath(res, new LinkedList<>(), root, 0, target); res.sort(Comparator.comparingint(list -> -list.size())); return res; } private void FindPath(ArrayList> res, LinkedList 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 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(); } 第十一題：復(fù)雜鏈表的復(fù)制 輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點），返回結(jié)果為復(fù)制后復(fù)雜鏈表的 head 。（注意，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用，否則判題程序會直接返回空） 解題思路 復(fù)制每個節(jié)點，如：復(fù)制節(jié)點 A 得到 A1 ，將 A1 插入節(jié)點 A 后面 遍歷鏈表，并將 A1->random = A->random->next; 將鏈表拆分成原鏈表和復(fù)制后的鏈表 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; } 第十二題：字符串的排列 輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。 輸入描述：輸入一個字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。 解題思路 將字符串劃分為兩個部分，第一個字符以及后面的其他字符 將第一個字符和后面所有字符進行交換 對于 abc 這個字符串，計算出的排列順序為： abc acb bac bca cba cab 代碼： public ArrayList Permutation(String str) { Set res = new HashSet<>(); if (str == null || str.length() == 0) { return new ArrayList<>(); } Permutation(res, str.toCharArray(), 0); ArrayList list = new ArrayList<>(res); list.sort(String::compareTo); return list; } private void Permutation(Set 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; chars = chars; chars = temp; } 第十三題：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出 2 。如果不存在則輸出 0。 解題思路 由于數(shù)組的特性，在排序數(shù)組中，超過半數(shù)的數(shù)字一定包含中位數(shù) 通過 partition 方法，借用快排的思想，隨機選取一個 key，將數(shù)組中小于 key 的移動到 key 的左側(cè)，數(shù)組中大于 key 的移動到 key 的右側(cè) 最終找到中位數(shù)的下標，還需要檢查中位數(shù)是否超過半數(shù) 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; } while (index != mid && start mid) { end = index - 1; index = partition(array, start, end); } else { start = index + 1; index = partition(array, start, end); } } if (checkIsHalf(array, index)) return array; return 0; } private Boolean checkIsHalf(int[] array, int index) { if (index < 0) { return false; } int count = 0; for (int i : array) { if (array == 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; int left = start, right = end; while (left < right) { while (left < right && array >= key) { right--; } if (left < right) { array = array; left++; } while (left < right && array GetLeastNumbers_Solution_Partition(int[] input, int k) { ArrayList 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); } return res; } private int partition(int[] nums, int start, int end) { int left = start, right = end; int key = nums; while (left < right) { while (left < right && nums > key) { right--; } if (left < right) { nums = nums; left++; } while (left < right && nums GetLeastNumbers_Solution(int[] input, int k) { ArrayList 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); 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 0 end{ cases } $$ public int FindGreatestSumOfSubArray(int[] array) { if (array == null || array.length == 0) { return 0; } int max = array; int sum = 0; for (int a : array) { if (sum + a > a) { sum += a; } else { sum = a; } if (sum > max) { max = sum; } } return max; } 我的官網(wǎng) (https://img-blog.csdnimg.cn/20190909211444316.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5qaWFuYW5kaXlp,size_16,color_FFFFFF,t_70) 我的官網(wǎng) 我的CSDN地址 我的簡書地址 我的github 我的碼云地址 阿里云優(yōu)惠券