# **[本站小福 利 點(diǎn)我獲取阿里云優(yōu)惠券]** 為什么大多數(shù)程序員相進(jìn)BAT工作？ 在中國互聯(lián)網(wǎng)技術(shù)發(fā)展過程中，BAT帶給我們程序員太多的回憶，20年發(fā)展過程中，他們各自形成自己的的體系和戰(zhàn)略規(guī)劃，掌握著中國互聯(lián)網(wǎng)信息技術(shù)，很多新技術(shù)都是BAT創(chuàng)新，然后提供技術(shù)支持給我們普通的開發(fā)者，這就是程序員進(jìn)入BAT工作最有力的說服力。 第一題：二叉搜索樹與雙向鏈表 輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。 解題思路 由于 BST 的特性，采用中序遍歷正好符合排序 要考慮 root 節(jié)點(diǎn)要與 左節(jié)點(diǎn)的最大值連接，與右節(jié)點(diǎn)的最小值連接 增加一個(gè)已排序鏈表的指針，指向最后一個(gè)已排序節(jié)點(diǎn) 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); } 第二題：合并兩個(gè)排序的鏈表 輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 解題思路 雙指針指向兩個(gè)鏈表 循環(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：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)） 解題思路 遍歷查找相等根節(jié)點(diǎn) 通過遞歸查找當(dāng)前根節(jié)點(diǎn)下是否包含子樹 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 解題思路 從上到下進(jìn)行左右節(jié)點(diǎn)交換 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í)針打印矩陣 輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(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個(gè)指針，表示可打印區(qū)域，并對(duì)區(qū)域進(jìn)行收縮 非 n*n 的矩陣，對(duì)于剩余非 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)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的 min 函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））。 解題思路 通過增加最小棧來記錄當(dāng)前最小節(jié)點(diǎn) 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(); } 第七題：棧的壓入、彈出序列 輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長度是相等的） 解題思路 通過 Stack 進(jìn)行模擬 push，當(dāng) pop 的節(jié)點(diǎn)等于 Stack 的 top 節(jié)點(diǎn)時(shí)，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(); } 第八題：從上往下打印二叉樹 從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。 解題思路 層次遍歷，通過隊(duì)列進(jìn)行輔助遍歷 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; } 第九題：二叉搜索樹的后序遍歷序列 輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出 Yes ,否則輸出 No 。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。 解題思路 后序遍歷中，最后一個(gè)節(jié)點(diǎn)為 root 節(jié)點(diǎn) 由于 BST 的左子樹都小于 root，右子樹都大于 root，那么可以判定該節(jié)點(diǎn)是否為 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é)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的 list 中，數(shù)組長度大的數(shù)組靠前) 解題思路 將走過的路徑記錄下來，當(dāng)走過路徑總和 = target 并且當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)時(shí)，該路徑符合要求 通過遞歸遍歷所有可能的路徑 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ù)制 輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的 head 。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空） 解題思路 復(fù)制每個(gè)節(jié)點(diǎn)，如：復(fù)制節(jié)點(diǎn) A 得到 A1 ，將 A1 插入節(jié)點(diǎn) 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; } 第十二題：字符串的排列 輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。 輸入描述：輸入一個(gè)字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。 解題思路 將字符串劃分為兩個(gè)部分，第一個(gè)字符以及后面的其他字符 將第一個(gè)字符和后面所有字符進(jìn)行交換 對(duì)于 abc 這個(gè)字符串，計(jì)算出的排列順序?yàn)椋?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ù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長度為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 方法，借用快排的思想，隨機(jī)選取一個(gè) key，將數(shù)組中小于 key 的移動(dòng)到 key 的左側(cè)，數(shù)組中大于 key 的移動(dòng)到 key 的右側(cè) 最終找到中位數(shù)的下標(biāo)，還需要檢查中位數(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)惠券