Android面试题算法篇
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<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 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
{
//方法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进制数
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<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 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<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+” “);
}
}
插入排序
算法描述：对于给定的一个数组，初始时假设*个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至*后一个记录插入到有序序列中为止。
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 + ” “);
}
}
本文完~