Android面试总结(算法篇)

快速排序

• 每次取一个基准值，然后每次从基准值左边和右边取值，找到基准值左边比基准值大或等于的值，找到基准值右边比基准值小或等于的值，然后左边和右边的值进行交换
• 完成上面一趟交换后，基准值左边的再进行循环比较，基准值右边的再循环比较

/**
 * 快速排序
 *
 * @param arr
 * @param L   指向数组第一个元素
 * @param R   指向数组最后一个元素
 */
public static void quickSort(int[] arr, int L, int R) {
    int i = L;
    int j = R;
    //支点以数组的中间的数为准
    int pivot = arr[(L + R) / 2];
    //左右两端进行扫描，只要两端还没有交替，就一直扫描
    while (i <= j) {
        //在左边找比支点大的数
        while (pivot > arr[i])
            i++;
        //在右边找比支点小的数
        while (pivot < arr[j])
            j--;
        //此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
        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保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
    //“左边”再做排序，直到左边剩下一个数(递归出口)
    if (L < j)
        quickSort(arr, L, j);
    //“右边”再做排序，直到右边剩下一个数(递归出口)
    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]) {
            //前面的数比当前值要大，则将前面的值替换给当前值
            array[j + 1] = array[j];
            //位置向前进一位
            j--;
        }
        //将当前值放到最前面的索引
        array[j + 1] = temp;
    }
}

选择排序

• 第一层循环表示前面的数，后面一层循环表示后面的数
• 而冒泡排序的第一层循环表示每一轮循环的次数

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]);
    }
}

冒泡排序

• 跟选择排序的不同地方是第一层循环表示每一轮循环的次数

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]);
    }
}

二分法查找

• 排序好的数组，找出对应数的位置，没找到的话返回-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;
        //如果要找的数比中间值小，则将最大的索引向左移一位
        //,否则将最小的索引向右移一位
        if (find < array[temp]) {
            max = temp - 1;
        } else if (find > array[temp]) {
            min = temp + 1;
        } else {
            result = temp;
            break;
        }
    }
    return result;
}

两个栈实现队列

• 栈的规则是先进后出，后进先出，队列是先进先出，后进后出

public class StackQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node){
        //实现队列的push直接将元素放到第一个栈中
        stack1.push(node);
    }
    public int pop(){
        //如果第2个栈是空的，需要将第一个栈的数据依次取出来
        if(stack2.empty()){
            //直到第一个栈中的数据取完了
            while(!stack1.empty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

链表常见题

• 常见题型有链表翻转、求倒数第k个节点、判断是不是环形链表、链表部分翻转、链表合并、链表排序等。
• 链表有一个next指向下一个指针，如果next=null说明到了链表的结束位置，环链表除外，后面题型会涉及到环形链表

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

翻转链表

//链表翻转，思想是定义一个节点，然后节点的pre指向了节点的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节点
        listNode.next = preNode;
        //将当前节点给到pre，下次判断节点的时候用得到
        preNode = listNode;
        listNode = nextNode;
    }
    return preNode;
}

求链表中倒数第k个结点

/**
 * 输入一个链表，输出该链表中倒数第k个结点。
 *
 * @param head
 * @param k
 * @return
 */
public static ListNode FindKthToTail(ListNode head, int k) {
     //先求出链表的总长度
    int num = 0;
    ListNode temp = head;
    ListNode result = null;
    while (temp != null) {
        temp = temp.next;
        num++;
    }
    //根据总长度求出倒数k的位置是正序的什么位置
    //由于倒数和正数的位置相加等于num+1,
    //所以根据这个特点能知道正数的位置了
    int index = num + 1 - k;
    num = 0;
    while (head != null) {
        num++;
        if (num == index) {
            result = head;
            break;
        }
        head = head.next;
    }
    return result;
}

判断一个链表是否有环

/**
 * 判断一个链表是不是环形链表
 * 定义个块的指针和慢的指针，如果两个再次相遇说明是环形链表
 * @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) {
            //如果再次相遇，则说明有环，返回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;
}

二叉树常见题

• 二叉树常见题型有二叉树深度计算、二叉树的镜像二叉树、根据二叉树的前序遍历、和中序遍历顺序求出二叉树结构。
• 二叉树有一个左子节点和右子节点。

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

求二叉树的深度

public static int TreeDepth(TreeNode root) {
    //如果当前节点为空，说明已经到底了
    if (root == null)
        return 0;
    //递归调用深度左右子树的深度
    int left = TreeDepth(root.left);
    int right = TreeDepth(root.right);
    //取左右子树大的深度值
    return left > right ? left + 1 : right + 1;//每次将调用次数加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);
        }
        //如果上面分析的结果是不相等，继续判断A树左节点和B树或A右节点和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;
    }
    //继续递归调用对应的左右子树
    return doesTree1HaveTree2(node1.left, node2.left) &&
            doesTree1HaveTree2(node1.right, node2.right);
}

求二叉树的镜像二叉树

• 镜像二叉树是将二叉树在左右方向上旋转下，左边的节点到右边、右边的节点到左边，形如下面:

image.png

• 思路：左右节点进行颠倒，然后递归调用下一个左、右子节点

/**
 * 转成镜像二叉树
 *
 * @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);
    }
}

根据二叉树的前序遍历、和中序遍历顺序求出二叉树结构。

• 树的前序遍历:先是根节点、再到左子节点、再到右子节点
• 树的中序遍历:先是左子节点、再到根节点、再到右子节点
  剑指offer上面一道题，已知前序遍历结果是{1,2,4,7,3,5,6,8}，中序遍历结果是{4,7,2,1,5,3,8,6}，求该二叉树的结构。

• 分析:前序遍历第一个节点根节点、然后去中序遍历里面找根节点左边是左子节点、根节点右边的都是右子节点部分，所以我们能确定1是根节点，4、7、2是1的左子节点部分，5、3、8、6是1的右子节点，然后在4、7、2里面继续通过前序遍历的2是首位，能确定2是左子节点，4、7是2的左子节点部分，依次类推，所以有如下结果:

  
  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;
}

找出一个无序数组中出现超过一半次数的数字

/**
 * 计算数组里面超过一半的数字，如果没有这样的数字，则返回0
 * 先把数组排序，如果有超过一半的数字，则中间位置的数字一定是该数字
 * 然后通过出现该数的次数来判断是否超过一半
 *
 * @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;
}

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

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;
}