Android面试题算法篇
Android面试题算法篇,由本人整理汇总,后续将继续推出系列篇,如果喜欢请持续关注和推荐,更多精彩内容可以关注微信公众号(Android高级编程):android-tech
系列文章目录:
- Android面试题View篇
- Android面试题进程篇
- Android面试题线程篇
- Android面试题网络篇
- Android面试题架构篇
- Android面试题系统原理篇
- Android面试题内存&性能篇
- Android面试题Java基础篇
- Android面试题数据结构篇
红黑树特点
- 1.root节点和叶子节点是黑色
- 2.红色节点后必须为黑色节点
- 3.从root到叶子每条路径的黑节点数量相同
实现阶乘
//采用递归法 public static long factorial(long number) { 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;}
二分查找
//递归法 int binarySearch(int array[], int low, int high, int target) { 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 binarySearch2(int a[], int key) { 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中
代码:
public class StackQueue { Stack stack1 = new Stack(); Stack stack2 = new Stack(); 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 class mainCase{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{ //方法1public static boolean isPrime(int x){for (int i=2;i<=x/2;i++)if (x%2==0)return false;return true;}//方法2public 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
进制转换:给定一个十进制数 n 和 一个整数 k, 将 十进制数 n 转换成 k进制数
public String hexConversion(int n, int 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); }}
二叉树排序树
首先定义节点类
public class TreeNode { 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
创建二叉排序树的时候随便传入一个int型数组a[]
然后通过自顶向下的方式一个一个的将a[0]---a[n]个元素创建的节点类一个一个的拼接到树上
此后只需要再创建一个主函数类来调用便行了
public class Test { 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)个记录进行第二轮比较;重复该过程直到进行比较的记录只剩下一个为止。
package sorting; /** * 冒泡排序 * 平均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 插入排序
算法描述:对于给定的一个数组,初始时假设第一个记录自成一个有序序列,其余记录为无序序列。接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止。
package sorting; /** * 插入排序 * 平均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 + " "); }}
选择排序
算法描述:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录与第一个记录的位置进行交换;接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小的记录并与第二个记录进行位置交换;重复该过程,直到进行比较的记录只有一个时为止。
package sorting; /** * 选择排序 * 平均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 + " "); }}
快速排序
算法描述:对于一组给定的记录,通过一趟排序后,将原序列分为两部分,其中前一部分的所有记录均比后一部分的所有记录小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中的所有记录均有序为止。
package sorting; /** * 快速排序 * 平均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的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列。
package sorting; /** * 归并排序 * 平均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); }}
希尔排序
算法描述:先将待排序序列的数组元素分成多个子序列,使得每个子序列的元素个数相对较少,然后对各个子序列分别进行直接插入排序,待整个待排序序列“基本有序”后,再对所有元素进行一次直接插入排序。
package sorting; /** * 希尔排序 * 平均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行数据的个数。
package sorting; /** * 基数排序 * 平均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)个元素重新调整为一个大顶堆,再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录,重复该过程直到调整的堆中只剩下一个元素时为止。
package sorting; /** * 堆排序 * 平均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(安卓)GridView/ListView点击事件并改变控件的背景颜色//
- Android上的CPU信息监测
- Realm for Android(安卓)简单使用
- 天天记录 - Android(安卓)addView源码分析
- Activity(启动模式) Activity(退出)
- Android采坑记录-自动更新APK出现No Activity found to handle I
- Android(安卓)ContentProvider和getContentResolver
- Android菜鸟笔记-Fragment日常使用记录
- Android中文联系人排序及检索补丁的原理(090819更新)
随机推荐