Android面试题——算法篇

前言

• 一年之计在于春 金三银四已经要到来，2019的新的开始，作为一个开发人员，你是否面上了自己理想的公司，薪资达到心中理想的高度？

• 如果没有的话， 你就需要掌握更加成熟的技术，也需要更多的知识储备，对于我们上班族而言，工作的好坏就变得格外重要，想要拿高的工资，就好好的做好面试准备，

• 以下是我为大家精心挑选的面试题，话不多说，看东西。

正文

实现阶乘

//采用递归法

    if (number <= 1)
        return 1;
    else
        return number * factorial(number - 1);
}
//采用循环连乘法    
public static int fact(int num){
    int temp=1;
    int factorial=1;
    while(num>=temp){
    factorial=factorial*temp;
    temp++;
    }
    return factorial;
}

二分查找

//递归法

    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (array[mid] > target)
        return binarysearch(array, low, mid - 1, target);
    if (array[mid] < target)
        return binarysearch(array, mid + 1, high, target);
    return mid;
}

//循环法

     int low = 0;
    int high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] > key)
            high = mid - 1;
        else if (a[mid] < key)
            low = mid + 1;
        else
                return mid;
    }
     return -1;
}

二分查找中值的计算

• 这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：
• 算法一：mid = (low + high) / 2
• 算法二：mid = low + (high – low)/2
• 乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。算法一的做法，在极端情况下，(low+high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。

二分查找法的缺陷

• 二分查找法的O(logn)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
• 数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
  解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。

用两个栈实现队列

题目描述：

• 用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
• 思路：
  压入元素直接压入stack1 删除元素先查看stack2是否为空，非空则弹出；空则将stack1中元素取出，置于stack2中
  代码：

    
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node){
        stack1.push(node);
    }
    
    public int pop(){
        if(stack2.empty()){
            while(!stack1.empty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
}

递归和迭代的区别是什么，各有什么优缺点？

• 程序调用自身称为递归，利用变量的原值推出新值称为迭代。
  递归的优点大问题转化为小问题，可以减少代码量，同时代码精简，可读性好；

• 缺点就是递归调用浪费了空间，而且递归太深容易造成堆栈的溢出。
  迭代的好处就是代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销；

• 缺点就是代码不如递归简洁

• 判断101-200之间有多少个素数，并输出所有素数
  素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

• 思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

• 思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ 间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

• 原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。例如 16 能被 2、4、8 整除，16=28，2 小于 4，8 大于 4，16=44，4=√16，因此只需判定在 2~4 之间有无因子即可。

    public static void main(String args[]){
        int i=0;
        for(i=101;i<=200;i++)
        if(math.isPrime(i)==true)
            System.out.println(i);
    }
}
class math
{
    //方法1
    public static boolean isPrime(int x)
    {
        for (int i=2;i<=x/2;i++)
            if (x%2==0)
                return false;
        return true;
    }
    
    //方法2
    public static boolean isPrime2(int m)
    {
        int k=(int)sqrt((double)m);
        for (int i=2;i<=k;i++)
            if (m%i==0)
                    return false;
        return true;
    }
}

字符串小写字母转换成大写字母
public String toUpperCase(String str)
{
    if (str != null && str.length() > 0) {
        for (int i=0; i<str.length(); i++) {
            char c = str.charAt(i);
         c += 32;
      }
   }
    return str;
}

进制转换：给定一个十进制数 n 和 一个整数 k, 将 十进制数 n 转换成 k进制数

    StringBuffer resultNumber = new StringBuffer();
    tenToK(resultNumber, n, k);
    System.out.println("n:k:result: " + n +" "+ k + " " + resultNumber.toString());

    return resultNumber.toString();
}

private void tenToK(StringBuffer stringBuffer, int n, int k) {
    int integral = n/k;
    int mode = n % k;
   stringBuffer.insert(0, mode);
    if (integral >= k) {
        tenToK(stringBuffer, integral, k);
   } else if (integral > 0) {
        stringBuffer.insert(0, integral);
   }
}

位运算实现加法
public int aplusb(int a, int b) {
    int sum_without_carry, carry;

    sum_without_carry = a^b; //没有进位的和
    carry = (a&b)<<1; //进位
    if(carry==0) {
        return sum_without_carry;
    } else {
        return aplusb(sum_without_carry, carry);
    }
}

二叉树排序树
首先定义节点类

    Object obj;
    TreeNode parent;
    TreeNode lchild;
    TreeNode rchild;
      
    public TreeNode(int obj) {
        this.obj = obj;
    }
}
然后创建一个树类

public class Tree {
      
    /**
     * 先序遍历二叉树 
     * @param root
     */  
    public void Fprint(TreeNode root){
        if(root!=null){
            System.out.println(root.obj);
            Fprint(root.lchild);
            Fprint(root.rchild);
        }
    }
      
    /**
     * 中序遍历二叉树 
     * @param root
     */  
    public void Mprint(TreeNode root){
        if(root!=null){
            Mprint(root.lchild);
            System.out.println(root.obj);
              
            Mprint(root.rchild);
        }
    }
      
    /**
     * 根据一个int数组建立二叉排序树 
     * @param a 数组 
     * @return
     */  
    public TreeNode Build(int[] a){
        if(a.length==0){
            return null;
        }
        TreeNode root = new TreeNode(a[0]);
        for(int i=1;i<a.length;i++){
            TreeNode newnode = new TreeNode(a[i]);
            sort(root,newnode);
        }
        return root;
    }
    /**
     * 在二叉排序树中添加一个节点 
     * @param root 二叉树的根节点 
     * @param newnode 新加入的加点 
     * @return
     */  
    public void sort(TreeNode root,TreeNode newnode){
        TreeNode node = root;
        if((Integer)newnode.obj<=(Integer)node.obj){
            if(node.lchild==null){
                newnode.parent = node;
                node.lchild = newnode;
            }else{
                sort(node.lchild,newnode);
            }
        }else{
            if(node.rchild==null){
                newnode.parent = node;
                node.rchild = newnode;
            }else{
                sort(node.rchild,newnode);
            }
        }
    }
}

创建二叉排序树的时候随便传入一个int型数组a[]
然后通过自顶向下的方式一个一个的将a[0]---a[n]个元素创建的节点类一个一个的拼接到树上
此后只需要再创建一个主函数类来调用便行了

  
    public static void main(String[] args) {
        int a[] = {100,35,3,44,212,453};
        Tree t = new Tree();
        TreeNode root = t.Build(a);
        t.Mprint(root);
    }
  
}

• 这样便可通过创建二叉排序树并且中序遍历该二叉树的方式，来将一组混乱的数据整理成一组从小到大的数据了。

冒泡排序

• 算法描述：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和交换后，n个记录中的最大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。

 
/**
 * 冒泡排序
 * 平均O(n^2),最好O(n),最坏O(n^2);空间复杂度O(1);稳定;简单
 * @author zeng
 *
 */
public class BubbleSort {
     
    public static void bubbleSort(int[] a){
 
        int n = a.length;
        int temp = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(a[j]<a[j+1]){
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }
     
    public static void main(String[] args){
        int[] a ={49,38,65,97,76,13,27,50};
        bubbleSort(a);
        for(int j:a)
            System.out.print(j+" ");
    }
}

插入排序

• 算法描述：对于给定的一个数组，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

 
/**
 * 插入排序
 * 平均O(n^2),最好O(n),最坏O(n^2);空间复杂度O(1);稳定;简单
 * @author zeng
 *
 */
public class InsertionSort {
 
    public static void insertionSort(int[] a) {
        int tmp;
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    tmp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = tmp;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        insertionSort(a);
        for (int i : a)
            System.out.print(i + " ");
    }
}

选择排序

• 算法描述：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。

 
/**
 * 选择排序
 * 平均O(n^2),最好O(n^2),最坏O(n^2);空间复杂度O(1);不稳定;简单
 * @author zeng
 *
 */
public class SelectionSort {
 
    public static void selectionSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int k = i;
            // 找出最小值的小标
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[k]) {
                    k = j;
                }
            }
            // 将最小值放到排序序列末尾
            if (k > i) {
                int tmp = a[i];
                a[i] = a[k];
                a[k] = tmp;
            }
        }
    }
 
    public static void main(String[] args) {
        int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
        selectionSort(b);
        for (int i : b)
            System.out.print(i + " ");
    }
}

快速排序

• 算法描述：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

 
/**
 * 快速排序
 * 平均O(nlogn),最好O(nlogn),最坏O(n^2);空间复杂度O(nlogn);不稳定;较复杂
 * @author zeng
 *
 */
public class QuickSort {
 
    public static void sort(int[] a, int low, int high) {
        if(low>=high)
            return;
        int i = low;
        int j = high;
        int key = a[i];
        while (i < j) {
            while (i < j && a[j] >= key)
                j--;
            a[i++] = a[j];
            while (i < j && a[i] <= key)
                i++;
            a[j--] = a[i];
        }
        a[i] = key;
        sort(a,low,i-1);
        sort(a,i+1,high);
    }
 
    public static void quickSort(int[] a) {
        sort(a, 0, a.length-1);
        for(int i:a)
            System.out.print(i+" ");
    }
 
    public static void main(String[] args) {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        quickSort(a);
    }
}

归并排序

• 算法描述：对于给定的一组记录，首先将每两个相邻的长度为1的子序列进行归并，得到 n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。

 
/**
 * 归并排序
 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂
 * @author zeng
 *
 */
public class MergeSort {
 
    public static void merge(int[] a, int start, int mid,
            int end) {
        int[] tmp = new int[a.length];
        System.out.println("merge " + start + "~" + end);
        int i = start, j = mid + 1, k = start;
        while (i != mid + 1 && j != end + 1) {
            if (a[i] < a[j])
                tmp[k++] = a[i++];
            else
                tmp[k++] = a[j++];
        }
        while (i != mid + 1)
            tmp[k++] = a[i++];
        while (j != end + 1)
            tmp[k++] = a[j++];
        for (i = start; i <= end; i++)
            a[i] = tmp[i];
        for (int p : a)
            System.out.print(p + " ");
        System.out.println();
    }
 
    static void mergeSort(int[] a, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid);// 左边有序
            mergeSort(a, mid + 1, end);// 右边有序
            merge(a, start, mid, end);
        }
    }
 
    public static void main(String[] args) {
        int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
        mergeSort(b, 0, b.length - 1);
    }
}

希尔排序

• 算法描述：先将待排序序列的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。

 
/**
 * 希尔排序
 * 平均O(nlogn),最坏O(nlogn);空间复杂度O(1);不稳定;较复杂
 * @author zeng
 *
 */
public class ShellSort {
 
    public static void shellSort(int[] a) {
        int n = a.length;
        int d = n / 2;
        while (d > 0) {
            for (int i = d; i < n; i++) {
                int j = i - d;
                while (j >= 0 && a[j] > a[j + d]) {
                    int tmp = a[j];
                    a[j] = a[j + d];
                    a[j + d] = tmp;
                    j = j - d;
                }
            }
            d = d / 2;
        }
    }
 
    public static void main(String[] args) {
        int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
        shellSort(b);
        for (int i : b)
            System.out.print(i + " ");
    }
}

基数排序

• 算法思想：依次按个位、十位...来排序，每一个pos都有分配过程和收集过程，array[i][0]记录第i行数据的个数。

 
/**
 * 基数排序
 * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
 * d为位数,r为分配后链表的个数
 * @author zeng
 *
 */
public class RadixSort {
 
    //pos=1表示个位，pos=2表示十位
    public static int getNumInPos(int num, int pos) {
        int tmp = 1;
        for (int i = 0; i < pos - 1; i++) {
            tmp *= 10;
        }
        return (num / tmp) % 10;
    }
 
    //求得最大位数d
    public static int getMaxWeishu(int[] a) {
        int max = a[0];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max)
                max = a[i];
        }
        int tmp = 1, d = 1;
        while (true) {
            tmp *= 10;
            if (max / tmp != 0) {
                d++;
            } else
                break;
        }
        return d;
    }
 
    public static void radixSort(int[] a, int d) {
 
        int[][] array = new int[10][a.length + 1];
        for (int i = 0; i < 10; i++) {
            array[i][0] = 0;// array[i][0]记录第i行数据的个数
        }
        for (int pos = 1; pos <= d; pos++) {
            for (int i = 0; i < a.length; i++) {// 分配过程
                int row = getNumInPos(a[i], pos);
                int col = ++array[row][0];
                array[row][col] = a[i];
            }
            for (int row = 0, i = 0; row < 10; row++) {// 收集过程
                for (int col = 1; col <= array[row][0]; col++) {
                    a[i++] = array[row][col];
                }
                array[row][0] = 0;// 复位，下一个pos时还需使用
            }
        }
    }
 
    public static void main(String[] args) {
        int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };
        radixSort(a, getMaxWeishu(a));
        for (int i : a)
            System.out.print(i + " ");
    }
}

堆排序

• 算法描述：对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素进行交换后，堆的最后一个元素即为最大记录；接着将前（n-1）个元素重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩下一个元素时为止。

 
/**
 * 堆排序
 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(1);不稳定;较复杂
 * @author zeng
 *
 */
public class HeapSort {
 
    public static void heapSort(int[] a) {
        int i;
        int len = a.length;
        // 构建堆
        for (i = len / 2 - 1; i >= 0; i--)
            heapAdjust(a, i, len - 1);
        //交换堆顶元素与最后一个元素的位置
        for (i = len - 1; i > 0; i--) {
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            heapAdjust(a, 0, i - 1);
        }
    }
 
    public static void heapAdjust(int[] a, int pos, int len) {
        int child = 2 * pos + 1;
        int tmp = a[pos];
        while (child <= len) {
            if (child < len && a[child] < a[child + 1])
                child++;
            if (a[child] > tmp) {
                a[pos] = a[child];
                pos = child;
                child = 2 * pos + 1;
            } else
                break;
        }
        a[pos] = tmp;
    }
 
    public static void main(String[] args) {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        heapSort(a);
        for (int i : a)
            System.out.print(i + " ");
    }
}

总结

以上就是这篇文章的内容了，喜欢的可以关注一下哦，也可以加android学习交流群1005956838，谢谢！

最后

希望大家能有一个好心态，想进什么样的公司要想清楚，并不一定是大公司，我选的也不是特大厂。当然如果你不知道选或是没有规划，那就选大公司！希望我们能先选好想去的公司再投或内推，而不是有一个公司要我我就去！还有就是不要害怕，也不要有压力，平常心对待就行，但准备要充足。最后希望大家都能拿到一份满意的 offer ！如果目前有一份工作也请好好珍惜好好努力，找工作其实挺累挺辛苦的。