Android面試總結(算法篇)

快速排序

• 每次取一個基準值审孽，然后每次從基準值左邊和右邊取值，找到基準值左邊比基準值大或等于的值，找到基準值右邊比基準值小或等于的值，然后左邊和右邊的值進行交換
• 完成上面一趟交換后格嗅，基準值左邊的再進行循環(huán)比較番挺，基準值右邊的再循環(huán)比較

/**
 * 快速排序
 *
 * @param arr
 * @param L   指向數(shù)組第一個元素
 * @param R   指向數(shù)組最后一個元素
 */
public static void quickSort(int[] arr, int L, int R) {
    int i = L;
    int j = R;
    //支點以數(shù)組的中間的數(shù)為準
    int pivot = arr[(L + R) / 2];
    //左右兩端進行掃描，只要兩端還沒有交替屯掖，就一直掃描
    while (i <= j) {
        //在左邊找比支點大的數(shù)
        while (pivot > arr[i])
            i++;
        //在右邊找比支點小的數(shù)
        while (pivot < arr[j])
            j--;
        //此時已經(jīng)分別找到了比支點小的數(shù)(右邊)玄柏、比支點大的數(shù)(左邊)，它們進行交換
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        for (int m = 0; m < arr.length; m++) {
            System.out.print(" " + arr[m]);
        }
        System.out.println("");
    }
    //上面一個while保證了第一趟排序支點的左邊比支點小贴铜，支點的右邊比支點大了禁荸。
    //“左邊”再做排序，直到左邊剩下一個數(shù)(遞歸出口)
    if (L < j)
        quickSort(arr, L, j);
    //“右邊”再做排序阀湿，直到右邊剩下一個數(shù)(遞歸出口)
    if (i < R)
        quickSort(arr, i, R);
}

插入排序

//插入排序
public void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];//當前的值
        int j = i - 1;//定位到當前索引的前一個
        while (j >= 0 && temp < array[j]) {
            //前面的數(shù)比當前值要大，則將前面的值替換給當前值
            array[j + 1] = array[j];
            //位置向前進一位
            j--;
        }
        //將當前值放到最前面的索引
        array[j + 1] = temp;
    }
}

選擇排序

• 第一層循環(huán)表示前面的數(shù)瑰妄，后面一層循環(huán)表示后面的數(shù)
• 而冒泡排序的第一層循環(huán)表示每一輪循環(huán)的次數(shù)

public static void order() {
    int[] a = {3, 0, 1, 2, 11, 7};
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i; j < a.length; j++) {
            int temp;
            if (a[i] > a[j]) {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
    for (int i = 0; i < a.length; i++) {
        System.out.println("result:" + a[i]);
    }
}

冒泡排序

• 跟選擇排序的不同地方是第一層循環(huán)表示每一輪循環(huán)的次數(shù)

public static void sort() {
    int[] a = {3, 0, 1, 2, 11, 7};
    for (int i = 1; i < a.length; i++) {
        for (int j = 0; j < a.length - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
    }
    for (int i = 0; i < a.length; i++) {
        System.out.println("result:" + a[i]);
    }
}

二分法查找

• 排序好的數(shù)組陷嘴，找出對應數(shù)的位置，沒找到的話返回-1

//二分法查找
public  int erfenfa(int[] array, int find) {
    int min = 0;
    int max = array.length - 1;
    int result = -1;
    while (min <= max) {
        int temp = (max + min) / 2;
        //如果要找的數(shù)比中間值小间坐，則將最大的索引向左移一位
        //,否則將最小的索引向右移一位
        if (find < array[temp]) {
            max = temp - 1;
        } else if (find > array[temp]) {
            min = temp + 1;
        } else {
            result = temp;
            break;
        }
    }
    return result;
}

兩個棧實現(xiàn)隊列

• 棧的規(guī)則是先進后出灾挨，后進先出，隊列是先進先出竹宋，后進后出

public class StackQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node){
        //實現(xiàn)隊列的push直接將元素放到第一個棧中
        stack1.push(node);
    }
    public int pop(){
        //如果第2個棧是空的劳澄，需要將第一個棧的數(shù)據(jù)依次取出來
        if(stack2.empty()){
            //直到第一個棧中的數(shù)據(jù)取完了
            while(!stack1.empty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

鏈表常見題

• 常見題型有鏈表翻轉、求倒數(shù)第k個節(jié)點蜈七、判斷是不是環(huán)形鏈表秒拔、鏈表部分翻轉、鏈表合并飒硅、鏈表排序等砂缩。
• 鏈表有一個next指向下一個指針，如果next=null說明到了鏈表的結束位置三娩，環(huán)鏈表除外庵芭，后面題型會涉及到環(huán)形鏈表

public static class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

翻轉鏈表

//鏈表翻轉，思想是定義一個節(jié)點雀监，然后節(jié)點的pre指向了節(jié)點的next
//1->2->3->4->5
//5->4->3->2->1
public  ListNode revertListNode(ListNode listNode) {
    ListNode preNode = null;
    ListNode nextNode;
    while (listNode != null) {
        //先取出next双吆，后面放到listNode的時候用
        nextNode = listNode.next;
        //preNode指向next節(jié)點
        listNode.next = preNode;
        //將當前節(jié)點給到pre，下次判斷節(jié)點的時候用得到
        preNode = listNode;
        listNode = nextNode;
    }
    return preNode;
}

求鏈表中倒數(shù)第k個結點

/**
 * 輸入一個鏈表会前，輸出該鏈表中倒數(shù)第k個結點好乐。
 *
 * @param head
 * @param k
 * @return
 */
public static ListNode FindKthToTail(ListNode head, int k) {
    ListNode second = head;
    ListNode first = head;
    //雙指針的思想，讓第一個指針先走回官，走到第k個結點后曹宴，第二個指針也跟著走，
    // 當?shù)谝粋€節(jié)點走到最后的時候歉提，第二個節(jié)點位置就是倒數(shù)第k個結點的位置
    for (int i = 0; i < k; i++) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    return second;
}

判斷一個鏈表是否有環(huán)

/**
 * 判斷一個鏈表是不是環(huán)形鏈表
 * 定義個塊的指針和慢的指針笛坦，如果兩個再次相遇說明是環(huán)形鏈表
 * @param head
 * @return
 */
private boolean isLoop(ListNode head) {
    //定義快慢指針
    ListNode fast = head.next;
    ListNode slow = head.next;
    while(fast != null && slow != null && fast.next != null) {
            //快指針每次走兩步区转，慢指針每次走一步
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                //如果再次相遇，則說明有環(huán)版扩，返回true
                return true;
            }
        }
    }
    return false;
}

每k位進行翻轉鏈表

• 每k位翻轉鏈表是在整個鏈表翻轉的基礎上演變而來的废离，它是先將鏈表分成每k個來進行翻轉，然后將當前翻轉的結果給上一次翻轉結果的最后一個指針

public static ListNode reverse(ListNode head, int k) {
    ListNode current = head;
    ListNode next = null;
    ListNode prev = null;
    int count = 0;
     //翻轉的條件
    while (current != null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }
    //如果后面還有元素礁芦，則遞歸翻轉
    if (next != null) {
          //將下一次翻轉的結果給當前最后一個元素的next位置
        head.next = reverse(next, k);
    }
    return prev;
}

二叉樹常見題

• 二叉樹常見題型有二叉樹深度計算蜻韭、二叉樹的鏡像二叉樹、根據(jù)二叉樹的前序遍歷柿扣、和中序遍歷順序求出二叉樹結構肖方。
• 二叉樹有一個左子節(jié)點和右子節(jié)點。

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

求二叉樹的深度

public static int TreeDepth(TreeNode root) {
    //如果當前節(jié)點為空未状，說明已經(jīng)到底了
    if (root == null)
        return 0;
    //遞歸調用深度左右子樹的深度
    int left = TreeDepth(root.left);
    int right = TreeDepth(root.right);
    //取左右子樹大的深度值
    return left > right ? left + 1 : right + 1;//每次將調用次數(shù)加1
}

輸入兩棵二叉樹A俯画，B，判斷B是不是A的子結構

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
 boolean result = false;
    //如果兩個樹都不為空才會走這里
    if (root2 != null && root1 != null) {
        //如果根的值相等
        if (root1.val == root2.val) {
            //找左右子樹是否相等
            result = doesTree1HaveTree2(root1, root2);
        }
        //如果上面分析的結果是不相等司草，繼續(xù)判斷A樹左節(jié)點和B樹或A右節(jié)點和B樹
        if (!result)
            return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }
    return result;
}

public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
    //如果右邊的樹為空直接說明相等
    if (node2 == null) {
        return true;
    }
    //如果左邊的樹為空直接返回不相等艰垂，說明不包含
    if (node1 == null) {
        return false;
    }
    //如果兩個值也不相等，說明也是不相等的
    if (node1.val != node2.val) {
        return false;
    }
    //繼續(xù)遞歸調用對應的左右子樹
    return doesTree1HaveTree2(node1.left, node2.left) &&
            doesTree1HaveTree2(node1.right, node2.right);
}

求二叉樹的鏡像二叉樹

• 鏡像二叉樹是將二叉樹在左右方向上旋轉下埋虹，左邊的節(jié)點到右邊猜憎、右邊的節(jié)點到左邊，形如下面:

image.png

• 思路：左右節(jié)點進行顛倒搔课，然后遞歸調用下一個左胰柑、右子節(jié)點

/**
 * 轉成鏡像二叉樹
 *
 * @param root
 */
public void Mirror(TreeNode root) {
    if (root != null) {
        TreeNode left = root.left;
        TreeNode right = root.right;
        TreeNode temp = left;
        root.left = right;
        root.right = temp;
        Mirror(left);
        Mirror(right);
    }
}

根據(jù)二叉樹的前序遍歷、和中序遍歷順序求出二叉樹結構辣辫。

• 樹的前序遍歷:先是根節(jié)點旦事、再到左子節(jié)點、再到右子節(jié)點
• 樹的中序遍歷:先是左子節(jié)點急灭、再到根節(jié)點姐浮、再到右子節(jié)點
  劍指offer上面一道題，已知前序遍歷結果是{1,2,4,7,3,5,6,8}葬馋，中序遍歷結果是{4,7,2,1,5,3,8,6}卖鲤，求該二叉樹的結構。

• 分析:前序遍歷第一個節(jié)點根節(jié)點畴嘶、然后去中序遍歷里面找根節(jié)點左邊是左子節(jié)點蛋逾、根節(jié)點右邊的都是右子節(jié)點部分，所以我們能確定1是根節(jié)點窗悯，4区匣、7、2是1的左子節(jié)點部分蒋院，5亏钩、3莲绰、8、6是1的右子節(jié)點姑丑，然后在4蛤签、7、2里面繼續(xù)通過前序遍歷的2是首位栅哀，能確定2是左子節(jié)點震肮，4、7是2的左子節(jié)點部分留拾，依次類推戳晌，所以有如下結果:

  
  
  image.png

/**
 * pre前序的結果:根左右
 * in后序的結果:左根右
 * pre:{1,2,4,7,3,5,6,8}
 * in:{4,7,2,1,5,3,8,6}
 *
 * @param pre
 * @param in
 * @return
 */
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    TreeNode root = new TreeNode(pre[0]);
    for (int i = 0; i < pre.length; i++) {
        if (pre[0] == in[i]) {
            root.left = reConstructBinaryTree(
                    Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
            root.right = reConstructBinaryTree(
                    Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
        }
    }
    return root;
}

找出一個無序數(shù)組中出現(xiàn)超過一半次數(shù)的數(shù)字

/**
 * 計算數(shù)組里面超過一半的數(shù)字，如果沒有這樣的數(shù)字痴柔，則返回0
 * 先把數(shù)組排序躬厌，如果有超過一半的數(shù)字，則中間位置的數(shù)字一定是該數(shù)字
 * 然后通過出現(xiàn)該數(shù)的次數(shù)來判斷是否超過一半
 *
 * @param array
 * @return
 */
public static int MoreThanHalfNum_Solution(int[] array) {
    Arrays.sort(array);
    int temp = array[array.length / 2];
    int num = 0;
    for (int i = 0; i < array.length; i++) {
        if (temp == array[i]) {
            num++;
        }
    }
    if (num <= array.length / 2) {
        temp = 0;
    }
    return temp;
}

在一個二維數(shù)組中（每個一維數(shù)組的長度相同）竞帽，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序鸿捧。請完成一個函數(shù)屹篓，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)匙奴。

public boolean Find(int target, int [][] array) {
    int row=0;
    int column=array[0].length-1;
    while(row<array.length&&column>=0){
        if(array[row][column]==target){
            return true;
        }
        if(array[row][column]>target){
            column--;
        }else{
            row++;
        }
    }
    return false;
}