我們在面試Android開發崗位時；不僅會面試許多技術問題，還常會問到一些算法題目，那麼這期就來解答這幾種常見算法題。
Android常見算法題
1、排序算法
快排
從平均時間來看，快速排序是效率最高的，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序。
每次找個基數，然後對比基數，l 和 h 指針， 從兩頭開始找比自己小向右移，比自己大的向左移。
public static int[] quickSort(int[] data) {
return quickSort(data, 0, data.length - 1);
}
public static int[] quickSort(int[] data, int low, int height) {
int l = low;
int h = height;
int povit = data[l];
while (l < h) {
while (l < h && data[h] >= povit) h--;
if (l < h) {
data[l] = data[h];
l++;
}
while (l < h && data[l] <= povit) l++;
if (l < h) {
data[h] = data[l];
h--;
}
data[l] = povit;
}
if (l - 1 > low) quickSort(data, low, l - 1);
if (h + 1 < height) quickSort(data, h + 1, height);
return data;
}
冒泡排序
記憶體優先
public static int[] bubbleSort(int[] array) {
if (array == null || array.length <= 1) return array;
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[j] <= array[i]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
} 插入排序
記憶體優先
首先位置1上的數和位置0上的數進行比較，如果位置1上的數大于位置0上的數，将位置0上的數向後移一位，将1插入到0位置，否則不處理。位置k上的數和之前的數依次進行比較，如果位置K上的數更大，将之前的數向後移位，最後将位置k上的數插入不滿足條件點，反之不處理。
public static int[] insertSort(int[] array) {
if (array == null || array.length <= 1)
return array;
int j;
for (int i = 1; i < array.length; i++) {
// 如果 後一個 小于 前一個，就向前繼續查找
if (array[i] < array[i - 1]) {
int temp = array[i];
// 如果 目前大于temp 就向後移動一位
for (j = i; (j > 0) && (array[j-1] > temp); j--) {
array[j] = array[j - 1];
}
array[j] = temp;
}
}
return array;
}
2、連結清單算法
判斷連結清單有環
思路：快慢指針
兩連結清單合并
思路：
1、連結清單 head 記錄初始連結清單，tempHead 記錄目前點的連結清單 2、輸入l1 與 l2 長度可能不一緻 3、進位記錄 carry
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode head = new ListNode();
ListNode tempHead = head;
head.next = tempHead;
while (l1 != null || l2 != null) {
ListNode tempNode = new ListNode();
int l1val = l1 == null ? 0 : l1.val;
int l2val = l2 == null ? 0 : l2.val;
int result = l1val + l2val + carry;
carry = result / 10;
tempNode.val = result % 10;
tempHead.next = tempNode;
tempHead = tempHead.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
ListNode tail = new ListNode(carry);
tempHead.next = tail;
}
return head.next;
} 查找單連結清單中的倒數第k個結點
快慢指針
如何實作一個lru
前後結點
如何定位連結清單尾部前面的第k個節點，寫一下
雙指針
單連結清單的反轉
方式一：
public ListNode reverseList(ListNode head) {
if(head==null) return head;
if (head.next==null) return head;
ListNode lastNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return lastNode;
} 方式二：
public ListNode reverseList(ListNode head) {
if (head == null) return head;
ListNode tempHead = new ListNode(0);
ListNode tempNext = tempHead.next;
while (head != null) {
ListNode curNext = head.next;
head.next = tempNext;
tempNext = head;
head = curNext;
}
return tempNext;
} 從尾到頭列印單連結清單
思路： 使用棧
合并兩個有序的單連結清單，合并之後的連結清單依然有序
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并後 l1 和 l2 最多隻有一個還未被合并完，我們直接将連結清單末尾指向未合并完的連結清單即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
} 3、二叉樹算法
每個結點類：
1 public class TreeNode{
2 private String data;//自己結點資料
3 private TreeNode leftChild;//左孩子
4 private TreeNode rightChild;//右孩子
5
6 public String getData() {
7 return data;
8 }
9
10 public void setData(String data) {
11 this.data = data;
12 }
13
14 public TreeNode(String data){
15 this.data = data;
16 this.leftChild = null;
17 this.rightChild = null;
18 }
19 } 很簡單，每個結點資訊包含自己結點資料以及指向左右孩子的指針（為了友善，我這裡就叫指針了）。
二叉樹的建立
我們建立如下二叉樹：
代碼實作：
public class BinaryTree {
private TreeNode root = null;
public TreeNode getRoot() {
return root;
}
public BinaryTree(){
root = new TreeNode("A");
}
/**
* 建構二叉樹
* A
* B C
* D E F G
*/
public void createBinaryTree(){
TreeNode nodeB = new TreeNode("B");
TreeNode nodeC = new TreeNode("C");
TreeNode nodeD = new TreeNode("D");
TreeNode nodeE = new TreeNode("E");
TreeNode nodeF = new TreeNode("F");
TreeNode nodeG = new TreeNode("G");
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.leftChild = nodeF;
nodeC.rightChild = nodeG;
}
。。。。。。。
} 建立BinaryTree的時候就已經建立根結點A，createBinaryTree()方法中建立其餘結點并且建立相應關系。
獲得二叉樹的高度
樹中節點的最大層次稱為樹的高度，是以獲得樹的高度需要遞歸擷取所有節點的高度，取最大值。
/**
* 求二叉樹的高度
* @author Administrator
*
*/
public int getHeight(){
return getHeight(root);
}
private int getHeight(TreeNode node) {
if(node == null){
return 0;
}else{
int i = getHeight(node.leftChild);
int j = getHeight(node.rightChild);
return (i<j)?j+1:i+1;
}
} 擷取二叉樹的結點數
擷取二叉樹結點總數，需要周遊左右子樹然後相加
1 /**
2 * 擷取二叉樹的結點數
3 * @author Administrator
4 *
5 */
6 public int getSize(){
7 return getSize(root);
8 }
9
10 private int getSize(TreeNode node) {
11 if(node == null){
12 return 0;
13 }else{
14 return 1+getSize(node.leftChild)+getSize(node.rightChild);
15 }
16 } 二叉樹的周遊
二叉樹周遊分為前序周遊，中序周遊，後續周遊，主要也是遞歸思想，下面直接給出代碼
/**
* 前序周遊——疊代
* @author Administrator
*
*/
public void preOrder(TreeNode node){
if(node == null){
return;
}else{
System.out.println("preOrder data:"+node.getData());
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
/**
* 中序周遊——疊代
* @author Administrator
*
*/
public void midOrder(TreeNode node){
if(node == null){
return;
}else{
midOrder(node.leftChild);
System.out.println("midOrder data:"+node.getData());
midOrder(node.rightChild);
}
}
/**
* 後序周遊——疊代
* @author Administrator
*
*/
public void postOrder(TreeNode node){
if(node == null){
return;
}else{
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.println("postOrder data:"+node.getData());
}
} 擷取某一結點的父結點
擷取結點的父節點也是遞歸思想，先判斷目前節點左右孩子是否與給定節點資訊相等，相等則目前結點即為給定結點的父節點，否則繼續遞歸左子樹，右子樹。
1 /**
2 * 查找某一結點的父結點
3 * @param data
4 * @return
5 */
6 public TreeNode getParent(String data){
7 //封裝為内部結點資訊
8 TreeNode node = new TreeNode(data);
9 //
10 if (root == null || node.data.equals(root.data)){
11 //根結點為null或者要查找的結點就為根結點，則直接傳回null，根結點沒有父結點
12 return null;
13 }
14 return getParent(root, node);//遞歸查找
15 }
16
17 public TreeNode getParent(TreeNode subTree, TreeNode node) {
18
19 if (null == subTree){//子樹為null，直接傳回null
20 return null;
21 }
22 //判斷左或者右結點是否與給定結點相等，相等則此結點即為給定結點的父結點
23 if(subTree.leftChild.data.equals(node.data) || subTree.rightChild.data.equals(node.data)){
24 return subTree;
25 }
26 //以上都不符合，則遞歸查找
27 if (getParent(subTree.leftChild,node)!=null){//先查找左子樹，左子樹找不到查詢右子樹
28 return getParent(subTree.leftChild,node);
29 }else {
30 return getParent(subTree.rightChild,node);
31 }
32 } 以上就是Android常見的排序、連結清單、二叉樹算法面試題；當然不止這些比喻： 堆/棧/隊列 、 哈希 、遞歸/回溯 、 動态規劃 、 字元串 、 雙指針 、 貪心算法 、 模拟 等等。想要在面試中披荊斬棘擷取更好的offer，可以前往擷取《Android面試精選題》内容很全面大家可以放心刷題。offer必到手！
【私信：“手冊”擷取】《Android精選面試題庫》
總結
找崗位要注意的是： 找準自己的定位
- 比如你特别想去A公司，你現在公司是10K，
- 先找幾個BCDE公司練練手，薪酬談判的時候直接要高價，比如20K
- 如果對方想也沒想就拒絕了，說明自己現在還不夠格，下次面試要15試試
- 如果對方猶豫或者答應了，下次面試你就可以要20K 以此類推
目的就是找準市場給自己的定價，心裡有一個譜。先找到自己的定位，然後再談判。