每天10道：Android面试题整理五（数据结构算法）
在这篇帖子中，我将分享10 道数据结构及算法的题目，相信对于任何Android开发者来说，面试题能够给予他们有所帮助。
糟糕的程序员担心代码。优秀的程序员担心数据结构及其算法。 ——Linus Torvalds
由于怕文章太长我就不做太多说明了，看题目就知道这是啥了，ok，废话不多说，看下面整理出来的题，希望可以对想从事Android开发的兄弟姐妹们有所帮助，下面的题整理出来的，并不全面，欢迎各位提问和补充！Android面试题和答案已按照规范已整理完成，大家可看文末或评论/私信，一起交流技术、进阶提升~
1. Vector，ArrayList与LinkedList有什么区别，应用场景是什么？
● Vector实现了基于动态Object数组的数据结构，线程安全，可以设置增长因子，效率比较低，不建议使用。
● ArrayList实现了基于动态Object数组的数据结构，非线程安全，地址连续，查询效率比较高，插入和删除效率比较低。适合查询操作频繁的场景。
● LinkedList实现了基于链表的数据结构，非线程安全，地址不连续，查询效率比较低，插入和删除效率比较高。适合插入和删除操作频繁的场景。
2. 简单说一说SpareArray的插入流程？
SpareArray的key是一个int有序数组，查找过程使用的二分查找。
- 用二分查找法查找元素的key。
- 如果插入的数据冲突了，则直接覆盖原则。
- 如果当前插入的key上的数据为DELETE，则直接覆盖。
- 如果前面几步都失败了，则检查是否需要gc()并且在索引上插入数据。
3. 从长度为m的int数组中随机取出n个元素，每次取的元素都是之前未取过的，如何优化？
string: Hello
length: 5
0 1 2 3 4
before: H e l l o
after: o l l e H
index sum
0: H--->o 0-->4 4
1: e--->l 1-->3 4
2: l--->l 2-->2 4解法一：使用数组
- 将字符串转换为char数组
- 遍历循环给char数组赋值
public static String strReverseWithArray2(String string){
if(string==null||string.length()==0)return string;
int length = string.length();
char [] array = string.toCharArray();
for(int i = 0;i<length/2;i++){
array[i] = string.charAt(length-1-i);
array[length-1-i] = string.charAt(i);
}
return new String(array);
}解法二：使用栈
- 将字符串转换为char数组
- 将char数组中的字符依次压入栈中
- 将栈中的字符依次弹出赋值给char数组
public static String strReverseWithStack(String string){ if(string==null||string.length()==0)return string; Stack<Character> stringStack = new Stack<>(); char [] array = string.toCharArray(); for(Character c:array){ stringStack.push(c); } int length = string.length(); for(int i= 0;i<length;i++){ array[i] = stringStack.pop(); } return new String(array); }
解法三：逆序遍历
- 逆序遍历字符串中的字符，并将它依次添加到StringBuilder中
public static String strReverseWithReverseLoop(String string){
if(string==null||string.length()==0)return string;
StringBuilder sb = new StringBuilder();
for(int i = string.length()-1;i>=0;i--){
sb.append(string.charAt(i));
}
return sb.toString();
}4. HashSet、LinkedHashSet与TreeSet有什么区别，应用场景是什么？
● HashSet：基于HashMap实现，非线程安全，地址不连续，查询效率比较低，插入和删除效率比较高。适合插入和删除操作频繁的场景。
● LinkedHashSet：基于hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的。
● TreeSet基于红黑树实现，非线程安全，可以按照自然顺序或者自定义顺序自动排序，不允许插入null值。适合需要排序的场景。
● HashSet基于hash表实现，非线程安全，允许插入null，查找效率高。适合查找操作频繁的场景。
5. 简单说一说SpareArray的插入流程？
SpareArray的key是一个int有序数组，查找过程使用的二分查找。
- 用二分查找法查找元素的key。
- 如果插入的数据冲突了，则直接覆盖原则。
- 如果当前插入的key上的数据为DELETE，则直接覆盖。
- 如果前面几步都失败了，则检查是否需要gc()并且在索引上插入数据。
6. 单链表反转，合并多个单链表
单链表的结构就像一个火车的结构，火车头拉着许多车厢，实现链表翻转，可以利用递归翻转法，在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始，逆向反转各个结点的指针域指向。
public class LinkedListReverse {
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
// 打印反转前的链表
Node h = head;
while (null != h) {
System.out.print(h.getData() + " ");
h = h.getNext();
}
// 调用反转方法
head = Reverse1(head);
System.out.println("\n**************************");
// 打印反转后的结果
while (null != head) {
System.out.print(head.getData() + " ");
head = head.getNext();
}
}
/**
* 递归，在反转当前节点之前先反转后续节点
*/
public static Node Reverse1(Node head) {
// head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
if (head == null || head.getNext() == null) {
return head;// 若为空链或者当前结点在尾结点，则直接还回
}
Node reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()
head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
head.setNext(null);// 前一结点的指针域令为null;
return reHead;// 反转后新链表的头结点
}
}
class Node {
private int Data;// 数据域
private Node Next;// 指针域
public Node(int Data) {
// super();
this.Data = Data;
}
public int getData() {
return Data;
}
public void setData(int Data) {
this.Data = Data;
}
public Node getNext() {
return Next;
}
public void setNext(Node Next) {
this.Next = Next;
}
}7. 字符串反转技术
public class ReverseInPlace {
static char[] str=null;
public static void main(String s[]) {
if(s.length==0)
System.exit(-1);
str=s[0].toCharArray();
int begin=0;
int end=str.length-1;
System.out.print("Original string=");
for(int i=0; i<str.length; i++){
System.out.print(str[i]);
}
while(begin<end){
str[begin]= (char) (str[begin]^str[end]);
str[end]= (char) (str[begin]^str[end]);
str[begin]= (char) (str[end]^str[begin]);
begin++;
end--;
}
System.out.print("\n" + "Reversed string=");
for(int i=0; i<str.length; i++){
System.out.print(str[i]);
}
}
}
public AbstractStringBuilder reverse() {
boolean hasSurrogate = false;
int n = count - 1;
for (int j = (n-1) >> 1; j >= 0; --j) {
char temp = value[j];
char temp2 = value[n - j];
if (!hasSurrogate) {
hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
|| (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
}
value[j] = temp2;
value[n - j] = temp;
}
if (hasSurrogate) {
// Reverse back all valid surrogate pairs
for (int i = 0; i < count - 1; i++) {
char c2 = value[i];
if (Character.isLowSurrogate(c2)) {
char c1 = value[i + 1];
if (Character.isHighSurrogate(c1)) {
value[i++] = c1;
value[i] = c2;
}
}
}
}
return this;
}8. 说说搜索算法中你知道的算法
- 无序线性搜索
- 排序/有序线性搜索
- 二进制搜索
9. 给定 n 个[0,n)区间内的数，统计每个数出现的次数，不使用额外空间
vector<int> nums;
void init(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
nums[nums[i]] += n;
}
}
int cnt(int k) {
return nums[k] / n;
}10. 如何判断单链表交叉
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
```
ListNode currA = headA;
ListNode currB = headB;
int lengthA = 0;
int lengthB = 0;
// 让长的先走到剩余长度和短的一样
while (currA != null) {
currA = currA.next;
lengthA++;
}
while (currB != null) {
currB = currB.next;
lengthB++;
}
currA = headA;
currB = headB;
while (lengthA > lengthB) {
currA = currA.next;
lengthA--;
}
while (lengthB > lengthA) {
currB = currB.next;
lengthB--;
}
// 然后同时走到第一个相同的地方
while (currA != currB) {
currA = currA.next;
currB = currB.next;
}
// 返回交叉开始的节点
return currA;
```
}
公众号：Android Jasper 专注分享面试题｜面试技巧｜Android学习资料。（dd：16）
