本站小福利點我擷取阿裡雲優惠券

為什麼大多數程式員相進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;
}

第四題：二叉樹的鏡像

操作給定的二叉樹，将其變換為源二叉樹的鏡像。

輸入描述：

二叉樹的鏡像定義：源二叉樹

從上到下進行左右節點交換

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 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 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();

第七題：棧的壓入、彈出序列

輸入兩個整數序列，第一個序清單示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列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 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> 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> 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 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 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,。

Partition

該算法基于 Partition

public ArrayList 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;

小根堆算法

該算法基于小根堆，适合海量資料，時間複雜度為：n*logk

public ArrayList 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)

定義為以第

個數字結尾的子數組的最大和，那麼

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;

我的官網