本文是Android面试题整理中的一篇，结合右下角目录食用更佳，包括：
- 数据结构
- 排序算法
- 加解密
- 常见题型举例
数据结构
1. 二叉树
每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
2. 完全二叉树
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
特性：完全二叉树中任何一层最左的节点编号n,则其左子树为2n,右子树为2n+1，利用这种特性，可以用数组作为二叉树的物理结构
3. 满二叉树
除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
特点：满二叉树有2^k-1个节点（k为高度）
4. 平衡二叉树
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
5. 红黑树
是一种自平衡二叉查找树
特性：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶节点（NIL节点，空节点）是黑色的。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
6. 二叉树的遍历
// 节点
class Node{
int value;
Node leftNode;
Node rightNode;
}
//以下知识简略步骤，省去判空等操作,每种只选取了一种简单实现方式
// 遍历的顺序指访问根结点的操作发生在遍历其左右子树的前后中
// 前序 （递归）
public void preOrder(Node node){
System.out.print(node.value);
preOrder(node.leftNode);
preOrder(node.rightNode);
}
// 中序 （递归）
public void inOrder(Node node){
inOrder(node.leftNode);
System.out.print(node.value);
inOrder(node.rightNode);
}
// 后序 （递归）
public void posOrder(Node node){
posOrder(node.leftNode);
posOrder(node.rightNode);
System.out.print(node.value);
}
// 计算深度 （递归）
public int level(Node node){
if (node == null)
return 0;
return level(node.leftNode) + 1 > level(node.rightNode) + 1 ? level(node.leftNode) + 1
: level(node.rightNode) + 1;
}
// 层序 （非递归）
public void levelOrder(Node node){
Queue<Node> nodes = new LinkedList<>();
nodes.add(node);
while (!nodes.isEmpty()){
Node node1 = nodes.poll();
System.out.print(node1.value);
nodes.offer(node1.leftNode);
nodes.offer(node1.rightNode);
}
}
7. 堆的概念
堆是一棵完全二叉树，分为大根堆（父结点>子节点）和小根堆（父结点<子节点）
算法
1. 排序
//冒泡排序（时间复杂度n^2）
public int[] blueblueSort(int[] array){
for (int i = 0 ; i < array.length ; i++){
for (int j = 0 ; j< array.length -i-1; j++){
if (array[j] > array[j+1]){
int temp = array[j+1]; // 元素交换
array[j+1] = array[j];
array[j] = temp;
}
}
}
return array;
}
//选择排序 （n^2）
public int[] sellectionSort(int[] array){
for (int i = 0 ; i < array.length - 1 ; i++){
int tempk = i;
for (int j = i+1 ; j < array.length; j++){
if (array[tempk] > array[j]){
tempk = j;
}
}
int temp = array[i];
array[i] = array[tempk];
array[tempk] = temp;
}
return array;
}
//插入排序 （n^2）
public int[] insertSort(int[] array){
for (int i = 1 ; i < array.length; i++){
int j = i-1;
int current = array[i];
while (j >= 0 && array[j] > current ){
array[j+1] = array[j];
j--;
}
array[j+1] = current;
}
return array;
}
// 归并排序 （n log n）
public int[] mergeSort(int[] array){
int length = array.length;
if (length < 2){
return array;
}
int[] left = new int[array.length/2];
int[] right = new int[array.length - array.length/2];
for (int i = 0; i < array.length/2 ; i++){
left[i] = array[i];
}
for (int j = 0;j < right.length;j++){
right[j] = array[array.length/2+j];
}
return merge(mergeSort(left),mergeSort(right));
}
public int[] merge(int[] left, int[] right){
int[] result = new int[left.length+right.length];
int i = 0;
int j = 0;
int k = 0;
while (i < left.length && j < right.length){
if (left[i] > right[j]){
result[k] = right[j];
j++;
} else {
result[k] = left[i];
i++;
}
k++;
}
while (i<left.length){
result[k] = left[i];
k++;
i++;
}
while (j<right.length){
result[k] = right[j];
k++;
j++;
}
return result;
}
// 快排 （n log n）
public void quickSort1(int[] array,int begin ,int end) {
if (begin<end){
int p = partition(array,begin,end);
quickSort1(array,begin,p-1);
quickSort1(array,p+1,end);
}
}
public int partition(int[] array,int begin ,int end){
int key = array[begin];
int left = begin;
int right = end;
while (left < right){
while (array[right] > key && left < right)
right--;
while (array[left] <= key && left < right)
left++;
if (left < right){
int temp1 = array[left];
array[left] = array[right];
array[right] = temp1;
}
}
array[begin] = array[left];
array[left] = key;
return left;
}
2， 二分查找
时间复杂度log n
//非递归
public static int binarySearch(Integer[] srcArray, int des) {
//定义初始最小、最大索引
int low = 0;
int high = srcArray.length - 1;
//确保不会出现重复查找，越界
while (low <= high) {
//计算出中间索引值
int middle = (high + low)>>>1 ;//防止溢出
if (des == srcArray[middle]) {
return middle;
//判断下限
} else if (des < srcArray[middle]) {
high = middle - 1;
//判断上限
} else {
low = middle + 1;
}
}
//若没有，则返回-1
return -1;
}
//递归
public int binarySearch(int[] array,int begin,int end,int key){
if ( begin > end ){
return -1;
}
int mid = begin + end >>> 1;
if (array[mid] == key){
return mid;
} else if (array[mid] > key){
return binarySearch(array,begin,mid-1,key);
} else {
return binarySearch(array,mid+1,end,key);
}
}
3. 计数排序
如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
4. 堆排序
public void heapSort(int[] array){
for (int i = array.length / 2 ; i >= 0 ; i--){ //初始化堆
heapAdjust(array,i,array.length-1);
}
for (int i = array.length-1;i>0;i--){ //排序
int temp = array[i];
array[i] = array[0];
array[0] = temp;
heapAdjust(array,0,i);
}
}
private void heapAdjust(int[] array , int parent, int length){
int temp = array[parent];
int child = parent*2+1;
while (child < length){
if (child+1<length && array[child]<array[child+1] )
child++;
if (temp > array[child])
break;
array[parent] = array[child];
parent = child;
child = 2*child+1;
}
array[parent] = temp;
}
5. 快排范型实现
public static <T extends Comparable<T>> void quickSort(T[] array, int left, int right) {
if (left < right){
int p = partition(array,left,right);
quickSort(array,left,p-1);
quickSort(array,p+1,right);
}
}
private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
T key = array[left];
int start = left;
while (left<right){
while (left < right && array[right].compareTo(key) > 0)
right --;
while (left < right && array[left].compareTo(key) <= 0)
left ++;
if (left < right){
T temp1 = array[left];
array[left] = array[right];
array[right] = temp1;
}
}
array[start] = array[left];
array[left] = key;
return left;
}
6. 冒泡排序范型
public static <T extends Comparable<T>> void bubbleSort(T[] array){
for (int i = 0 ; i < array.length - 1 ; i++){ //外层循环控制排序趟数
for (int j = 0 ; j < array.length - i- 1 ; j++){
if (array[j].compareTo(array[j+1])>0){ //内层循环控制每一趟排序多少次
T temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
public class CountSort {
public static void countSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int max = max(arr);
int[] count = new int[max+1];
Arrays.fill(count, 0);
for(int i=0; i<arr.length; i++) {
count[arr[i]] ++;
}
int k = 0;
for(int i=0; i<=max; i++) {
for(int j=0; j<count[i]; j++) {
arr[k++] = i;
}
}
}
public static int max(int[] arr) {
int max = Integer.MIN_VALUE;
for(int ele : arr) {
if(ele > max)
max = ele;
}
return max;
}
}
加解密
0. Base64
Base64 是一种编码方式，不具有可读性，便与传输
1. MD5
- 压缩性：任意长度的数据，算出的MD5值长度都是固定的。
- 容易计算：从原数据计算出MD5值很容易。
- 抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。
- 强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。
- 不可逆：知道md5，不能还原出加密前数据
2. [MD5加盐]（https://blog.csdn.net/blade2001/article/details/6341078）
3. AES 对称加密
4. RSA 非对称加密
例题
1. 找数组中第k大的数字
使用类似快排的方式：
- 随机选一个基值X，分为将数组分为两块Sa > X > Sb
- Sa个数大于k，则递归Sa找第k大数；Sa个数小于k，递归Sb找第(k-Sa.size)大数
复杂度O（n）
2. 在两个等长有序数组中找到中位数
- X[n/2],Y[n/2]；比较两数的大小，若X[n/2]>Y[n/2]，那么我们可以舍去X[n/2]之后和Y[n/2]之前的数；若X[n/2]<Y[n/2]，对应的，我们可以舍去X[n/2]之前和Y[n/2]之后的数；若X[n/2]=Y[n/2]，那表明当前值就是所求的中位数。
- 递归的在剩余的数中进行比较筛选
3. 判断链表中是否存在环
两个指针一快一慢，有环的话快慢肯定会相遇
4. 判断一个二叉树是不是平衡二叉树
平衡二叉树的定义：空树或者左右子树高度相差不超过1；子树也是平衡二叉树
利用这一特性，我们可以用递归的方式判断
class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val) {
this.val = val;
}
}
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null)
return true;
//如果树为 null 返回 TRUE。否则判断根的左右子树的高度差的绝对值是否大于1，若大于1 则返回false。
// 否则判断树的左右孩子是否是平衡二叉树，当两者都是平衡二叉树时返回TRUE，否则返回false.
else if(Math.abs(TreeDepth(root.left)-TreeDepth(root.right))>1)
return false;
else return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
}
//求树的深度。
public int TreeDepth(TreeNode root){
if(root==null)
return 0;
//如果树为 null 返回0 否则返回左右孩子的最大值+1。
return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;
}
因为上述方法会多次计算相同子树深度，优化：
public class IsBalancedTree {
boolean isBalance=true;
public boolean IsBalanced_Solution(TreeNode root) {
TreeDepth1(root);
return isBalance;
//isBalance 会在 TreeDepth1(root)中赋值。
}
public int TreeDepth1(TreeNode root)
{
if(root==null)
return 0;
int left=TreeDepth1(root.left);
//左子树高度
int right=TreeDepth1(root.right);
//右子树高度
if(Math.abs(left-right)>1)
{
isBalance=false;
//只要有一个子树的左右子树的高度绝对值大于 1 isBalance=false
}
return Math.max(left, right)+1;
}
5. 从扑克牌中随机抽 5 张牌,判断是不是顺子,即这 5 张牌是不是连续的。 2-10 为数字本身,A 为 1,J 为 11,Q 为 12,K 为 13,而大小王可以看成任意的 数字。
解题思路：我们可以把5张牌看成是由5个数字组成的俄数组。大小王是特殊的数字，我们可以把它们都定义为0，这样就可以和其他的牌区分开来。
首先把数组排序，再统计数组中0的个数，最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的，反之则不连续。如果数组中的非0数字重复出现，则该数组是不连续的。换成扑克牌的描述方式就是如果一幅牌里含有对子，则不可能是顺子。
public boolean isContinuous(int[] array){
Arrays.sort(array);
int wang = 0;
int gap = 0;
for (int i : array){
if (array[i] == 0){
wang++;
continue;
}
if (i < array.length-1){
if (array[i] == array[i+1]){
return false;
} else {
gap += array[i+1] - array[i]-1;
}
}
}
return wang >= gap;
}
6. 圆圈中最后剩下的数字
题目：0,1,...,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求这个圆圈里剩下的最后一个数字。
变形：标号1-n的n个人首尾相接，1到3报数，报到3的退出，求最后一个人的标号
解答:
1、环形链表模拟圆圈
创建一个n个节点的环形链表，然后每次在这个链表中删除第m个节点；
可以用std::list来模拟环形链表，list本身不是环形结构，因此每当迭代器扫描到链表末尾的时候，需要将迭代器移到链表的头部。
2、分析每次被删除的数字的规律，动态规划
假设从0-n-1中删除了第m个数字，则下一轮的数字排列为m,m+1,.....n,1,2,3...m-2，将该数字排列重新映射为0~n-2，则为
m    0
m+1   1  
....    ....
n-1   n-1-m
0    n-m
1    n-m+1
...    ....
m-2   n-2
可以看出从右往左的映射关系为left=(right+m)%n，即0~n-1序列中最后剩下的数字等于（0~n-2序列中最后剩下的数字+m）%n，很明显当n=1时，只有一个数，那么剩下的数字就是0.
问题转化为动态规划问题，关系表示为：
f(n)=(f(n-1)+m)%n； 当n=1,f(1)=0;
代码如下：
public static int lastRemaining(int n, int m){
if(n < 1 || m < 1){
return -1;
}
int last = 0;
for(int i = 2; i <= n; i++){
last = (last + m) % i;
}
return last;
}
7. 给定一个字符串，求第一个不重复的字符 abbcad -> c
思路：和计数排序类似，通过一个数组来表示字符（数组太长时也可以考虑bitmap)，统计每个位置的个数。
8. 重建二叉树
题目：输入二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设前序遍历和中序遍历结果中都不包含重复的数字,例如输入的前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建出如图所示的二叉树。
前序遍历第一个地址是父地址，在中序遍历中，此地址前是左子树（个目m），右边是右子树（个数n）；前序遍历第一个地址后的m个是其左子树，其余是其右子树。有了左右子树的前序遍历和中序遍历，我们就可以用递归的方法来构建树了
public class BinaryTreeNode {
public static int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;
}
public BinaryTreeNode build(int[] pre, int[] in){
if(pre == null || in == null || pre.length != in.length){
throw new Exception("heiheihei");
}
BinaryTreeNode root = new BinaryTreeNode();
root.value = pre[0];
for(int i = 0; i < in.length ;i++){
if(pre[0] == in[i]){
root.leftNode = build(Array.copyOfRange(pre,1,i+1),Array.copyOfRange(in,0,i));
root.rightNode = build(Array.copyOfRange(pre,i+1,pre.length),Array.copyOfRange(in,i+1,in.length));
break;
}
}
return root;
}
9. two-sum
给定一个数组和一个目标值target，在数组中找到一组和为target的数，并输出他们的下标，并且要求下标1 < 下标2
public int[] find(int[] array,int target){
HashMap<int,int> map = new HashMap<>();
int[] result = new int[2];
for(int i = 0;i<array.length;array++){
if(map.get(array[i])!=null){
result[0] = map.get(array[i])+1;
result[1] = i+1;
break;
}
}
return result;
}
10. 实现一个特殊的栈，在实现栈的基本功能的基础上，在实现返回栈中最小元素的操作（有求存、取、getmin时间复杂度都为1）
思路：通过两个栈来实现，一个栈正常存储，另一个栈记录最小数据
11. 编写一个类，用两个栈实现队列，支持队列的基本操作(add、poll、peek)
思路：将栈1数据存入栈2，即完成了读取栈2的内容，即是队列。
解法：1.add时将数据存入栈1 2.读取时读取栈2，若栈2为空，将栈1数据存入栈2
12. 如何仅用递归函数和栈操作逆序一个栈
13. 单链表反转java代码
class Node{
int value;
Node next;
}
// 非递归
public Node reverse(Node node){
Node pre = null;
Node now = node;
while(now!=null){
Node temp = now.next;
now.next = pre;
pre = now;
now = temp;
}
return pre;
}
//递归
public Node reverse3(Node node) {
if(node.next==null)return node;
Node next = node.next;
node.next = null;
Node re = reverse3(next);
next.next = node;
return re;
}
14, 有一个一维整型数组int[]data保存的是一张宽为width，高为height的图片像素值信息。请写一个算法，将该图片所有的白色不透明(0xffffffff)像素点的透明度调整为50%。
final int size = data.length;
for(int i = 0; i< size; i++){
if(data[i] == 0xffffffff)
data[i] = 0x80ffffff;
}
15. int a = 10; int b=5; 怎么在不引入其他变量的情况下,让a和b互换？
//方法1
a = a+b;
b = a-b;
a = a-b;
//方法2
a = a^b;
b = b^a;
a = a^b;
16. 在一个长字符串A中找一个短字符串
17. 求二进制数中1的个数
任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4
思路：利用n&(n-1)消除n转换成二进制后最低位的1
public void count(int n){
int count = 0;
while(n>0){
count++;
n = n&(n-1)
}
扩展:求一个数是不是偶数：n > 0 && ((n & (n - 1)) == 0 )
18. 将数组中元素排列为奇数在前偶数在后
思路：和快排思想类似，从前向后找到偶数，从后向前找到奇数，交换
private void jiOu(int a[]) //将数组a中奇数放在前面，偶数放在后面
{
int len = a.length;
if(len <= 0) //数组长度为0则返回
return ;
int front = 0, end = len-1;//设置两个指针，一个指向头部，一个指向尾部
while(front<end)
{
while(front<len && (a[front]&1)==1) //从前往后找偶数
front++;
while(end>=0 && (a[end]&1)==0) //从后往前找奇数
end--;
if(front<end)
{
int swap = a[front]; //将奇数往前挪，偶数往后挪
a[front] = a[end];
a[end] = swap;
}
}
}
19. 找出未打卡的员工
输入两行数据，第一行为全部员工的 id，第二行为某一天打卡的员工 id，已知只有一个员工没有打卡，求出未打卡员工的 id。（员工 id 不重复，每行输入的 id 未排序）
- 思路1：遍历一边员工id，将员工id填入HashMap或计数排序；再遍历一遍打卡员工，从HashMap或者技术排序的数组中查找。因为HashMap和技术排序的数组查找的时间复杂度都是1，随意整体的时间复杂度是两次遍历即2n
- 思路2:我们有两个数组，打卡的员工id肯定会在两个数组里各出现一次，一共2次，未打卡的员工id只出现了一次；利用a^a = 0;0^b = b;的特性。
int result = 0;
for (int i = 0; i < ids.length; i++) {
result ^= Integer.parseInt(ids[i]);
}
for (int i = 0; i < marks.length; i++) {
result ^= Integer.parseInt(marks[i]);
}
20. 赛马
25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名？
- 25匹马分成5组，先进行5场比赛
- 再将刚才5场的冠军进行第6场比赛，得到第一名。按照第6场比赛的名词把前面5场比赛所在的组命名为 A、B、C、D、E 组，即 A 组的冠军是第6场第一名，B 组的冠军是第二名 …
- 分析第2名和第3名的可能性，如果确定有多于3匹马比某匹马快，那它可以被淘汰了。因为 D 组是第6场的第四名，整个D 组被淘汰了，同意整个 E 组被淘汰。剩下可能是整体的第2、3名的就是C组的第1名、B组的1、2名、A组的第2、3名。取这5匹马进行第7场比赛
- 所以，一共需要7场比赛
21. 扑克牌随机发牌
对于52张牌，实现一个随机打算扑克牌顺序的程序。52张牌使用 int 数组模拟
思路：随机选取一张，和第一张交换；再剩下的牌中选取一张，和第二张交换，以此类推
public void randomCards() {
int[] data = new int[52];
Random random= new Random();
for (int i = 0; i < data.length; i++)
data[i] = i;
for (int i = data.length - 1; i > 0; i--) {
int temp = random.nextInt(i+1); //产生 [0,i] 之间的随机数
swap(data,i,temp);
}
}
22. 括号字符串是否合法
某个字符串只包括 ( 和 ） ，判断其中的括号是否匹配正确，比如 (()()) 正确， ((())() 错误， 不允许使用栈 。
思路：这种类似题的常见思路是栈，对于左括号入栈，如果遇到右括号，判断此时栈顶是不是左括号，是则将其出栈，不是则该括号序列不合法；面试官要求不能使用栈，可以使用计数器，利用 int count 字段。
public static boolean checkBrackets(String str) {
char[] cs = str.toCharArray();
int count = 0;
for (int i = 0; i < cs.length; i++) {
if (cs[i] == '(')
count++;
else {
count--;
if (count < 0) {
return false;
}
}
}
return count == 0;
}
23. 字符串是否包含问题
假设这有一个各种字母组成的字符串A，和另外一个字符串B，字符串里B的字母数相对少一些。什么方法能最快的查出所有小字符串B里的字母在大字符串A里都有？
思路1：使用计数排序，复杂度m+n 思路2: 借助hashmap
24. 查找兄弟单词
一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程
思路：使用HashMap和链表，单词排序后的值作为HashMap的key，链表作为value
25. 链表环路问题
一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空，这两种情形都定义为null。这样构成一个单链表。给两条这样单链表，判断里面是否存在同样的url。url以亿级计，资源不足以hash
思路：先判断是否有环路（快慢指针），再判断是否交叉（有交叉最后指向相同节点）
26. 寻找最长不重复子串
- 遍历字符串，过程中将出现过的字符存入字典，key为字符，value为字符下标
- 用maxLength保存遍历过程中找到的最大不重复子串的长度
- 用start保存最长子串的开始下标
- 如果字符已经出现在字典中，更新start的值
- 如果字符不在字典中，更新maxLength的值
- return maxLength
27. Leetcode 买卖股票问题
参考资料
https://blog.csdn.net/fengqiangfeng/article/details/8049903
