[移动开发]【Android春招每日一练】（二）

概览

剑指offer：重建二叉树、双栈实现队列、斐波那契数列、青蛙跳台阶
Java基础：Java集合、HashMap、Java反射

剑指offer

1.5 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LoD9paD2-1642235714794)(D:\Typora\img\1629825510-roByLr-Picture1.png)]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    HashMap<Integer,Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //将中序遍历的值-索引存入map中，方便递归时获取左子树与右子树的数量及其根的索引
        for(int i=0;i<inorder.length;i++){
            dic.put(inorder[i],i);
        }
        //当前根的的索引，递归树的左边界，递归树的右边界 
        return recur(0,0,inorder.length-1);  
    }

    TreeNode recur(int pre_root,int in_left,int in_right){
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(preorder[pre_root]);
        int in_root = dic.get(preorder[pre_root]);  //获取在中序遍历中根节点所在索引
        //左子树的根的索引为先序中的根节点索引+1 
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        root.left = recur(pre_root+1,in_left,in_root-1);
        //右子树的根的索引为先序中的 （当前根索引 + 左子树的数量 + 1）
        //递归右子树的左边界为中序中当前根节点索引+1
        //递归右子树的右边界为中序中原来右子树的边界
        root.right = recur(pre_root+(in_root-in_left)+1,in_root+1,in_right);
        return root;
    }
}

1.6 双栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

//双栈实现队列，一个栈存储队尾插入元素，一个栈反向第一个栈，用于对头删除操作（反向栈出栈一个元素即可）
class CQueue {
    LinkedList<Integer> stack,rStack;
    public CQueue() {
        stack = new LinkedList<Integer>();
        rStack = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack.push(value);
    }
    
    public int deleteHead() {
        if(!rStack.isEmpty()) return rStack.pop();
        if(stack.isEmpty()) return -1;
        while(!stack.isEmpty()){
            rStack.push(stack.pop());
        }
        return rStack.pop();
    }
}

1.7 斐波那契数列（动态规划）

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1

//动态规划
class Solution {
    public int fib(int n) {
        int a = 0,b = 1,sum;
        for(int i=0;i<n;i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;	//精华
    }
}

1.8 青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

//动态规划，就是斐波那契数列；
//跳1个台阶有1种方法，跳2个台阶有2种方法（可以看作跳两个1级台阶），跳3个台阶有三种方法（可以看作1+2）即前两个台阶种数相加；
class Solution {
    public int numWays(int n) {
        int a=1,b=1,sum;
        for(int i=0;i<n;i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

Java基础

2.1 Java集合

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r5qa5c98-1642235743267)(D:\Typora\img\1155586-20191121113020194-1422948337.jpg)]

List集合

有序列表，允许存放重复的元素；
实现类：

• ArrayList：数组实现，查询快，增删慢，轻量级(线程不安全)；
• LinkedList：双向链表实现，增删快，查询慢 (线程不安全)；
• Vector：数组实现，重量级 (线程安全、使用少)；

ArrayList

底层是Object数组，所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点。

LinkedList

LinkedList是采用双向循环链表实现的。利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。

查询速度慢、增删速度快；

Vector

与ArrayList相似，区别是Vector是重量级的组件，使用使消耗的资源比较多。

在考虑并发的情况下用Vector（保证线程的安全）。

在不考虑并发的情况下用ArrayList（不能保证线程的安全）。

Set集合

扩展Collection接口
无序集合，不允许存放重复的元素；允许使用null元素；对 add()、equals() 和 hashCode() 方法添加了限制

实现类 :

• HashSet：equals返回true，hashCode返回相同的整数；哈希表；存储的数据是无序的。
• LinkedHashSet：此实现与HashSet的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。
• TreeSet：该类实现了Set接口，可以实现排序等功能。

HashSet类

HashSet类直接实现了Set接口，其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。

HashSet的特征:

• 不仅不能保证元素插入的顺序，而且在元素在以后的顺序中也可能变化（这是由HashSet按HashCode存储对象（元素）决定的，对象变化则可能导致HashCode变化）
• HashSet是线程非安全的
• HashSet元素值可以为NULL

LinkedHashSet的特征

LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。

底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。

TreeSet的特征

底层数据结构采用二叉树来实现，元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。

Map集合

Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。所以通过指定的key就可以取出对应的value。

(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yi1dFAqg-1642236040738)(D:\Typora\img\20170513133210763)]

2.2 HashMap

2.2.1 问：HashMap 有用过吗？您能给我说说他的主要用途吗？

答：有用过，我在平常工作中经常会用到 HashMap 这种数据结构，HashMap 是基于 Map 接口实现的一种键-值对<key,value>的存储结构，允许 null 值，同时非有序，非同步(即线程不安全)。HashMap 的底层实现是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）。它存储和查找数据时，是根据键 key 的 hashCode的值计算出具体的存储位置。HashMap 最多只允许一条记录的键 key 为 null，HashMap 增删改查等常规操作都有不错的执行效率，是 ArrayList 和 LinkedList等数据结构的一种折中实现。

2.2.2 问：您能说说 HashMap 常用操作的底层实现原理吗？如存储 put(K key, V value)，查找get(Object key)，删除 remove(Object key)，修改 replace(K key, V value)等操作.

答：调用 put(K key, V value)操作添加 key-value 键值对时，进行了如下操作：

1.判断哈希表 Node<K,V>[] table 是否为空或者 null，是则执行 resize()方法进行扩容。

2.根据插入的键值 key 的 hash 值， hash 值 % hash 表长度计算出存储位置 table[i]。如果存储位置没有元素存放，则将新增结点存储在此位置table[i]。如果存储位置已经有键值对元素存在，则判断该位置元素的 hash 值和 key值是否和当前操作元素一致，一致则证明是修改 value 操作，覆盖 value即可。

3.当前存储位置即有元素，又不和当前操作元素一致，则证明此位置table[i]已经发生了 hash 冲突，则通过判断头结点是否是 treeNode，如果是 treeNode 则证明此位置的结构是红黑树，已红黑树的方式新增结点。如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，随后判断当前链表长度是否 大于等于 8，是则将当前存储位置的链表转化为红黑树。遍历过程中如果发现 key 已经存在，则直接覆盖 value。

4.插入成功后，判断当前存储键值对的数量 大于 阈值 threshold 是则扩容。

2.2.3 问：HashMap 的容量为什么一定要是 2 的 n 次方？

答：因为调用 put(K key, V value)操作添加 key-value 键值对时，具体确定此元素的位置是通过 hash 值 % 模上 哈希表 Node<K,V>[] table 的长度 hash % length 计算的。但是"模"运算的消耗相对较大，通过位运算 h & (length-1)也可以得到取模后的存放位置，而位运算的运行效率高，但只有 length 的长度是2 的 n 次方时，h & (length-1) 才等价于 h % length。

而且当数组长度为 2 的 n 次幂的时候，不同的 key 算出的 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

2.2.4 问：HashMap 的负载因子是什么，有什么作用？

答：负载因子表示哈希表空间的使用程度（或者说是哈希表空间的利用率）。

底层哈希表 Node<K,V>[] table 的容量大小 capacity 为 16，负载因子load factor 为 0.75，则当存储的元素个数 size = capacity 16 * load factor 0.75 等于 12 时，则会触发 HashMap 的扩容机制，调用 resize()方法进行扩容。

当负载因子越大，则 HashMap 的装载程度就越高。也就是能容纳更多的元素，元素多了，发生 hash 碰撞的几率就会加大，从而链表就会拉长，此时的查询效率就会降低。

当负载因子越小，则链表中的数据量就越稀疏，此时会对空间造成浪费，但是此时查询效率高。

我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，默认负载因子 (0.75) 在时间和空间成本上寻求一种折中，程序员无需改变负载因子的值。

2.2.5 问：您说 HashMap 不是线程安全的，那如果多线程下，它是如何处理的？并且什么情况下会发生线程不安全的情况？

答：HashMap 不是线程安全的，如果多个线程同时对同一个 HashMap 更改数据的话，会导致数据不一致或者数据污染。如果出现线程不安全的操作时，HashMap会尽可能的抛出 ConcurrentModificationException 防止数据异常，当我们在对一个 HashMap 进行遍历时，在遍历期间，我们是不能对 HashMap 进行添加，删除等更改数据的操作的，否则也会抛出 ConcurrentModificationException 异常，此为 fail-fast（快速失败）机制。从源码上分析，我们在 put,remove 等更改 HashMap数据时，都会导致 modCount 的改变，当 expectedModCount != modCount 时，则抛出 ConcurrentModificationException。

2.2.6 问：我们在使用 HashMap 时，选取什么对象作为 key 键比较好，为什么？

答：我们在使用 HashMap 时，最好选择不可变对象作为 key。例如 String，Integer 等不可变类型作为 key 是非常明智的。

如果 key 对象是可变的，那么 key 的哈希值就可能改变。在 HashMap 中可变对象作为 Key 会造成数据丢失。因为我们再进行 hash & (length - 1)取模运算计算位置查找对应元素时，位置可能已经发生改变，导致数据丢失。

2.3 Java反射

JAVA反射机制是在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制。

Java中编译类型有两种：

• 静态编译：在编译时确定类型，绑定对象即通过。
• 动态编译：运行时确定类型，绑定对象。动态编译最大限度地发挥了Java的灵活性，体现了多态的应用，可以减低类之间的耦合性。

Java反射是Java被视为动态（或准动态）语言的一个关键性质。这个机制允许程序在运行时透过Reflection APIs取得任何一个已知名称的class的内部信息，包括其modifiers（诸如public、static等）、superclass（例如Object）、实现之interfaces（例如Cloneable），也包括fields和methods的所有信息，并可于运行时改变fields内容或唤起methods。

Reflection可以在运行时加载、探知、使用编译期间完全未知的classes。即Java程序可以加载一个运行时才得知名称的class，获取其完整构造，并生成其对象实体、或对其fields设值、或唤起其methods。

反射（reflection）允许静态语言在运行时（runtime）检查、修改程序的结构与行为。
在静态语言中，使用一个变量时，必须知道它的类型。在Java中，变量的类型信息在编译时都保存到了class文件中，这样在运行时才能保证准确无误；换句话说，程序在运行时的行为都是固定的。如果想在运行时改变，就需要反射这东西了。

实现Java反射机制的类都位于java.lang.reflect包中：

1. Class类：代表一个类
2. Field类：代表类的成员变量（类的属性）
3. Method类：代表类的方法
4. Constructor类：代表类的构造方法
5. Array类：提供了动态创建数组，以及访问数组的元素的静态方法

一句话概括就是使用反射可以赋予jvm动态编译的能力，否则类的元数据信息只能用静态编译的方式实现，例如热加载，Tomcat的classloader等等都没法支持。

总结

1.剑指四道算法题，第一道二叉树的遍历与重建熟悉了二叉树的操作，重拾记忆；斐波那契的动态规划算法非常巧妙；
2.学习和熟悉了Java的集合，了解HashMap底层原理和Java反射机制基础；