面试过程

Java后端实习/全职

自我介绍：

• 项目描述每一个自己实现的都必须了解，因为我很久没写代码，说的很不好，太菜了

• 网易和滴滴实习：多问基础技能，项目问的不多，我还能糊弄过去，基础技能面感觉还行

• 字节实习：只问项目细节，设置各种场景，我根本不会，一直懵逼，前面太差，后面叫我写二分查找都写错了…

问技能：

• 反射获取私有属性/方法是怎么实现的，单例设计模式线程不安全，反射是否可以破解，怎么防止？
• 常用的多线程有哪些（每家必问），说说你知道的Hashmap底层源码，底层扩容原理，为什么线程安全？(必问)
• JDK线程池5大参数是哪些？使用线程池创建线程，这几个参数执行流程是啥？拒绝策略有哪些？
• volatile特性是啥？为啥不保证原子性？和synchronized底层都是怎么实现的？
• 说说你知道的JVM垃圾回收器和内存模型?CMS垃圾回收的过程有哪些？
• SpringAOP的动态代理，JDK和Cglib动态代理区别有哪些？
• SpringBoot自动装配原理有了解过吗？
• Redis常用数据结构有哪些？底层源码用什么怎么实现的？
• Redis的缓存失效、穿透、雪崩你怎么解决？
• 事务隔离级别有哪些？解决了哪些问题？（必问）
• 说说你的Mysql底层数据机构，主键id为啥都是int类型，不能选char类型吗？
• Mysql索引最左前缀原则是什么？设定场景怎么断开不走索引的？
• 网易实习：Mysql中Explain关键字，你都看哪些字段？（我忘了，就说了key字段）
• Mysql你怎么优化的？
• 你使用RocketMQ怎么防止消息丢失、消息重复消费？（没实际用过，完全不会）
• 网易实习：问了自己实现服务注册和发现，你怎么实现？（完全不会)
• 网易二面：问了设计上的问题，8G的数据，怎么放到2G内存中（完全不会）
• 字节实习：问了自己怎么实现RPC远程调用（完全不会）

算法：

• 斐波那契，递归和迭代（最高频）
• 快排、归并算法
• 面试被问到其他的算法我根本不会….我都整理到了下面“算法”分类里

闲聊：

• 自己平时怎么解决遇到的难题？
• 你有什么问题问我吗？

反射

反射概念：反射就是动态调用一个类/一个对象的成员变量/属性、方法、构造器的功能

定义测试的User：看到原类的构造器、成员属性、方法，想着怎么使用反射生成

package reflect;
public class User {
    private int id=1;
    private String name="张三";
    private static Date date;

    public User() {
    }

    public User(int id) {
        this.id = id;
    }

    private User(String name) {
        this.name = name;
    }

    public User(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public void fun1() {
        System.out.println("无参的fun1被调用");
    }

    public void fun2(int id) {
        System.out.println("fun2:" + id);
    }

    public void fun3(int id, String s) {
        System.out.println("fun3:" + id + "," + s);
    }

    private void fun4(Date date) {
        System.out.println("fun4:" + date);

    }

    public static void fun5() {
        System.out.println("fun5");
    }

    public static void fun6(String[] args) {
        System.out.println(args.length);
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public static Date getDate() {
        return date;
    }

    public static void setDate(Date date) {
        User.date = date;
    }
}

获取构造器

getConstructor（私有getDeclaredConstructor，有setAccessible）后newInstance

public class Demo1 {

    /**
     * 三种获取字节码的方法
     */
    @Test
    public void test1() throws Exception {
        // 类.class
        Class<String> stringClass = String.class;
        // Class。forName(className)
        Class<?> userClazz = Class.forName("reflect.User");
        User user = new User();
        // 对象.getClass()
        Class<? extends User> userClazz1 = user.getClass();
    }

    /**
     * 获取非私有构造器
     */
    @Test
    public void test2() throws Exception {
        Class<?> userClazz = Class.forName("reflect.User");
        Constructor<?> c1 = userClazz.getConstructor();
        Constructor<?> c2 = userClazz.getConstructor(int.class);
        Constructor<?> c3 = userClazz.getConstructor(int.class, String.class);
        User user = (User) c3.newInstance(1, "A");
        System.out.println(user);
    }

    /**
     * 获取私有构造器
     */
    @Test
    public void test3() throws Exception {
        Class<?> userClazz = Class.forName("reflect.User");
        // 私有需要declared修饰
        Constructor<?> c = userClazz.getDeclaredConstructor(String.class);
        // setAccessible设置暴露破解
        c.setAccessible(true);
        User user = (User) c.newInstance("A");
        System.out.println(user);
    }

    /**
     * 获取所有构造器：私有和非私有
     */
    @Test
    public void test4() throws Exception {
        Class<?> userClazz = Class.forName("reflect.User");
        Constructor<?>[] constructors = userClazz.getDeclaredConstructors();
        for (Constructor c : constructors) {
            System.out.println(c);
        }
    }
}

获取方法

getMethod（私有getDeclaredMethod，有setAccessible）后invoke

特殊情况：因为1.4是将字符数组分开作为小个体，String[]作为方法参数需要（Object）强转/new Object[]{包装}

public class Demo2 {

    /**
     * 获取非私有的成员方法
     */
    @Test
    public void test1() throws Exception {
        Class<?> claszz = Class.forName("reflect.User");
        User user = (User) claszz.newInstance();
        Method fun1 = claszz.getMethod("fun1", null);
        fun1.invoke(user, null);
        Method fun2 = claszz.getMethod("fun2", int.class);
        fun2.invoke(user, 1);
        Method fun3 = claszz.getMethod("fun3", int.class, String.class);
        fun3.invoke(user, 1, "A");
    }

    /**
     * 获得私有方法
     */
    @Test
    public void test2() throws Exception {
        Class<?> claszz = Class.forName("reflect.User");
        User user = (User) claszz.newInstance();
        // declared修饰private
        Method fun4 = claszz.getDeclaredMethod("fun4", Date.class);
        // setAccessible设置暴露破解
        fun4.setAccessible(true);
        fun4.invoke(user, new Date());
    }

    /**
     * 获得无数组参数的静态方法
     */
    @Test
    public void test3() throws Exception {
        Class<?> claszz = Class.forName("reflect.User");
        Method fun5 = claszz.getDeclaredMethod("fun5");
        fun5.invoke(null);
    }

    /**
     * 特殊情况：获得String数组参数的静态方法
     */
    @Test
    public void test4() throws Exception {
        Class<?> claszz = Class.forName("reflect.User");
        Method fun6 = claszz.getDeclaredMethod("fun6", String[].class);
        // fun6.invoke(null, new String[]{"1","2"}); 是要报错的，因为JDK4是把字符数组当做一个个对象解析
        // 以下两种方式解决：
        fun6.invoke(null, (Object) new String[]{"1", "2"});
        fun6.invoke(null, new Object[]{new String[]{"1", "2"}});
    }
}

获取成员属性

一般来说成员属性都是私有的：getDeclaredField（setAccessible）后set值

public class Demo3 {
    /**
     * 获取非静态的私有成员变量
     */
    @Test
    public void test1() throws Exception {
        Class<?> userClass = Class.forName("bean.User");
        User user = (User) userClass.newInstance();
        Field id = userClass.getDeclaredField("id");
        id.setAccessible(true);
        id.set(user, 2);
        Field name = userClass.getDeclaredField("name");
        name.setAccessible(true);
        name.set(user, "李四");
        System.out.println(user);
    }

    /**
     * 获取静态成员变量
     */
    @Test
    public void test2() throws Exception {
        Class<?> userClass = Class.forName("bean.User");
        Field date = userClass.getDeclaredField("date");
        date.setAccessible(true);
        date.set(null, new Date());
        System.out.println("User的Date:" + User.getDate());
    }
}

值传递和引用传递

方法中的局部变量，按顺序进栈中的方法内

• 基本数据类型，直接进栈
• 引用类型，地址进栈

实参向形参传递：

• 基本数据类型，直接传值
• 引用类型，传地址值；数组类型，传首地址

public class Test {
    public static void main(String[] args) {
        int i = 1;
        String str = "hello";
        Integer num = 200;
        int[] arr = {1, 2, 3, 4, 5};
        MyData my = new MyData();

        change(i, str, num, arr, my);

        System.out.println("i = " + i);
        System.out.println("str = " + str);
        System.out.println("num = " + num);
        System.out.println("arr = " + Arrays.toString(arr));
        System.out.println("my.a = " + my.a);
    }

    public static void change(int j, String s, Integer n, int[] a, MyData m) {
        j += 1;
        s += "world";
        n += 1;
        a[0] += 1;
        m.a += 1;
    }
}

结果：

i = 1
str = hello
num = 200
arr = [2, 2, 3, 4, 5]
my.a = 11

结论：

• 不会改变：基本数据类型；String、包装类（Integer等）
• 会改变：自定义类、数组

public class TransferValueTest {

    public static void main(String[] args) {
        TransferValueTest test = new TransferValueTest();
        //传基本类型，传的是副本，原值不会变
        int age = 20;
        test.changeValue1(age);
        System.out.println("age:" + age);

        //传bean，传的是地址值，原值会发生改变
        Person person = new Person(1, "张三");
        test.changeValue2(person);
        System.out.println("personName;" + person.getPersonName());

        //传字符串，String和包装类是final修饰的，无论是new或者""，都不会发生改变
        String str1 = new String("1231");
        test.changeValue3(str1);
        System.out.println("str1:" + str1);
        String str2 = "ABC";
        test.changeValue3(str2);
        System.out.println("str2:" + str2);
    }

    public void changeValue1(int age) {
        age = 10;
    }

    public void changeValue2(Person person) {
        person.setPersonName("张三改");
    }

    public void changeValue3(String str) {
        str = "字符串";
    }
}

类的初始化顺序

创建父类和子类

public class Father {
    private int i = test();
    private static int j = method();

    // 父类静态方法
    public static int method(){
        System.out.print("(5)");
        return 1;
    }
    // 执行父类静态代码块
    static{
        System.out.print("(1)");
    }
    // 被重写的方法，去子列执行，父类不执行
    public int test(){
        System.out.print("(4)");
        return 1;
    }
    // 非静态代码块
    {
        System.out.print("(3)");
    }
    // 父类构造方法
    Father(){
        System.out.print("(2)");
    }
}

public class Son extends Father {
    private int i = test();
    private static int j = method();

    // 执行子列静态方法
    public static int method() {
        System.out.print("(10)");
        return 1;
    }
    // 执行子类非静态代码块
    static {
        System.out.print("(6)");
    }
    // 被重写的非静态方法方法被执行2次
    @Override
    public int test() {
        System.out.print("(9)");
        return 1;
    }
    // 子类非静态代码块
    {
        System.out.print("(8)");
    }
    // 子类构造方法
    Son() {
        System.out.print("(7)");
    }

    public static void main(String[] args) {
        Son s1 = new Son();
        System.out.println();
        // 静态方法只执行一次
        Son s2 = new Son();
    }
}

结果：

(5)(1)(10)(6)(9)(3)(2)(9)(8)(7)
(9)(3)(2)(9)(8)(7)

集合

集合安全

// 线程不安全的例子
public class ConnectionNotSafeDemo {
    public static void main(String[] args) {
        // list资源被共享，必然线程不安全
        ArrayList<String> list = new ArrayList<String>();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0,8));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }
}

报错：Exception in thread "8" java.util.ConcurrentModificationException

保证集合类线程安全的方式

1. vector修饰，1.0的东西，已经不使用了
2. Collections.synchronized(list)
3. 读写锁

public class ConnectionSafeDemo {

    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();
        for (int i = 1; i < 30; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }
}

读写锁add底层源码：用lock加锁保证了写锁操作的线程安全

 public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

HashMap

数组默认容量：16，每次达到3/4容量时扩容成2倍；

链表有8个时，转成红黑树；红黑树到6个时，红黑树转成链表

// 默认容量：2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// 最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 加载因子:0.75 原因：空间和时间开销的最大取舍
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转红黑树时hash表最小容量阈值，达不到优先扩容。
static final int MIN_TREEIFY_CAPACITY = 64;

线程不安全的原因：JDk1.7

• JDK7的transfer方法，使用头插法在多线程下会有死循环的问题

// JDK7以前，造成高并发下死锁的方法：头插法
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 指针e：指向当前节点
    for (Entry<K,V> e : table) {
        while(null != e) {
            // 记录老表中的结点的下一个结点
            Entry<K,V> next = e.next;
            // 是否重新计算hash值，同时影响效率
            if (rehash) {
                e.hash = (null == e.key) ? 0 : hash(e.key);
            }
            // 算法新表中的数组待插下下标
            int i = indexFor(e.hash, newCapacity);
            // 头插法是产生多线程下死循环的祸首                                     
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

ConcurrentHashMap

private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 16;
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
private static final float LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
//  默认16, table扩容时, 每个线程最少迁移table的槽位个数
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
static final int MOVED     = -1; // 正在扩容
static final int TREEBIN   = -2; // 代表此元素后接红黑树。
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int NCPU = Runtime.getRuntime().availableProcessors();

Java7 ConcurrentHashMap基于ReentrantLock实现分段锁

Java8中 ConcurrentHashMap基于分段锁+CAS保证线程安全，分段锁基于synchronized关键字实现

// JDK8协助扩容源码
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

JVM

类加载器

 ClassLoader appClassLoader = ClassLoader.getSystemClassLoader();
 ClassLoader extClassLoader = appClassLoader.getParent();
 ClassLoader bootstrapClassLoader = extClassLoader.getParent();

• 引导类加载器（bootstrapClassLoader）：负责加载支撑JVM运行的位于JRE的lib目录下的核心类库，比如 rt.jar、charsets.jar等。底层是用C++书写，所以JVM输出为null。
• 扩展类加载器（extClassLoader）：负责加载支撑JVM运行的位于JRE的lib目录下的ext扩展目录中的JAR 类包
• 应用类加载器（appClassLoader）：用户classpath下自己写的类
• 自定义加载器（重写某些方法）：负责加载用户自定义路径下的类包

public class TestJDKClassLoader {
    public static void main(String[] args) {
        System.out.println(String.class.getClassLoader());
        System.out.println(com.sun.crypto.provider.DESCipher.class.getClassLoader());
        System.out.println(TestJDKClassLoader.class.getClassLoader());
        System.out.println("--------");
        /* 运行结果：
            null（底层是用C++书写，所以JVM输出为null）
            sun.misc.Launcher$ExtClassLoader@5e2de80c
            sun.misc.Launcher$AppClassLoader@18b4aac2
         */
    }
}

双亲委派机制

• 概念：加载某个类时会先找父亲加载，层层向上，如果都不行，再逐步向下由儿子加载。
• 例子：比如我们的Math类，最先会找应用程序类加载器加载，应用程序类加载器会先委托扩展类加载 器加载，扩展类加载器再委托引导类加载器，顶层引导类加载器在自己的类加载路径里找了半天 没找到Math类，则向下退回加载Math类的请求，扩展类加载器收到回复就自己加载，在自己的 类加载路径里找了半天也没找到Math类，又向下退回Math类的加载请求给应用程序类加载器， 应用程序类加载器于是在自己的类加载路径里找Math类，结果找到了就自己加载了。
• ApplicationClassLoader中双亲委派机制：通过逐步调用父类ClassLoader的的loadClass方法：

protected Class<?> loadClass(String name, boolean resolve)
        throws ClassNotFoundException
    {
        synchronized (getClassLoadingLock(name)) {
            // 1 检查当前加载器是否记载了该类。如果没被加载，检查父类加载器是否加载
            Class<?> c = findLoadedClass(name);
            if (c == null) {
                long t0 = System.nanoTime();
                try {
                    if (parent != null) {
                        c = parent.loadClass(name, false);
                    } else {
                        c = findBootstrapClassOrNull(name);
                    }
                } catch (ClassNotFoundException e) {
                    // ClassNotFoundException thrown if class not found
                    // from the non-null parent class loader
                }
                // 2 如果父类加载都没有加载，则会调用URLClassLoader的findClass方法在加载器的类路径里查找并加载该类
                if (c == null) {
                    // If still not found, then invoke findClass in order
                    // to find the class.
                    long t1 = System.nanoTime();
                    c = findClass(name);

                    // this is the defining class loader; record the stats
                    sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
                    sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
                    sun.misc.PerfCounter.getFindClasses().increment();
                }
            }

            if (resolve) {
                resolveClass(c);
            }
            return c;
        }
    }

• 设计双亲委派机制的好处：
  • 沙箱安全机制：比如自己写的String类不会被加载，防止JDK核心API不会被随意篡改
  • 避免类的重复加载：当父类加载过该类后，子类不会再加载，保证了被加载类的唯一性

自定义类加载器和打破双亲委派机制

• 自定义类加载器只需要extends ClassLoader 类，该类有两个核心方法：
  • loadClass(String, boolean)，实现了双亲委派机制
  • findClass（），默认实现是空 方法，所以我们自定义类加载器主要是重写findClass方法。

package JVM;
public class MyClassLoaderTest {

    static class MyClassLoader extends ClassLoader {
        private String classPath;

        public MyClassLoader(String classPath) {
            this.classPath = classPath;
        }


        private byte[] loadByte(String name) throws Exception {
            name = name.replaceAll("\\.", "/");
            FileInputStream fis = new FileInputStream(classPath + "/" + name + ".class");
            int len = fis.available();
            byte[] data = new byte[len];
            fis.read(data);
            fis.close();
            return data;
        }

        /**
         * 自定义加载器，自定加载路径，就是重写findClass()
         */
        @Override
        protected Class<?> findClass(String name) throws ClassNotFoundException {
            try {
                byte[] data = loadByte(name);
                // 转换成class对象返回
                return defineClass(name, data, 0, data.length);
            } catch (Exception e) {
                e.printStackTrace();
                throw new ClassNotFoundException();
            }
        }

        /**
         * 打破双亲委派机制，重写loadClass()
         */
        @Override
        protected Class<?> loadClass(String name, boolean resolve) throws ClassNotFoundException {
            synchronized (getClassLoadingLock(name)) {
                Class<?> c = findLoadedClass(name);
                if (c == null) {
                    long t0 = System.nanoTime();
                    long t1 = System.nanoTime();
                    // 指定包下的类打包双亲委派，否则使用双亲委派
                    if (!name.startsWith("JVM")) {
                        c = this.getParent().loadClass(name);
                    } else {
                        c = findClass(name);
                    }
                    sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
                    sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
                    sun.misc.PerfCounter.getFindClasses().increment();
                }
                if (resolve) {
                    resolveClass(c);
                }
                return c;
            }
        }

        public static void main(String[] args) throws Exception {
            MyClassLoader classLoader = new MyClassLoader("E:/test");
            Class<?> aClass = classLoader.loadClass("JVM.User1");
            Object object = aClass.newInstance();
            Method method = aClass.getDeclaredMethod("sout", null);
            method.invoke(object, null);
            System.out.println(aClass.getClassLoader().getClass().getName());
        }
        /*运行结果：
            自己的加载器加载调用方法
            JVM.MyClassLoaderTest$MyClassLoader
         */
    }
}
package JVM;

public class User1 {
    private String userName ;

    public String getUserName() {
        return userName;
    }

    public void setUserName(String userName) {
        this.userName = userName;
    }
    public void sout(){
        System.out.println("自己的加载器加载调用方法");
    }
}

内存模型

// Spring Boot程序的JVM参数设置格式(Tomcat启动直接加在bin目录下catalina.sh文件里)：
‐Xms2048M ‐Xmx2048M ‐Xmn1024M ‐Xss512K 
‐XX:MetaspaceSize=256M ‐XX:MaxMetaspaceSize=256M

// 常用的调优参数，自己必须要看的懂
JAVA_OPTS="-Xms4096m –Xmx4096m -XX:NewRatio=2 -XX:SurvivorRatio=8 -Xloggc:/home/work/log/serviceName/gc.log -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+PrintGCApplicationStoppedTime -XX:+UseConcMarkSweepGC -XX:+UseParNewGC -XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSCompactAtFullCollection -XX:CMSFullGCsBeforeCompaction=10 "

对象初始化过程

Mysql

 show variables like 'tx_isolation';# 查看隔离级别
 set tx_isolation = 'REPEATABLE-READ';# 默认隔离级别就是可重复读，Spring框架如果没有指定也是可重复读

事务

底层数据结构

B+树优点

• 非叶子节点不存储数据，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能

索引引擎

INNODB和MYISAM区别

联合索引

存储原则：最左前缀原理（左到右，依次大小比较）

非常重要：查询时，是怎样使用到了该联合主键？

• 必须先定位最左字段，才能是正确使用了联合索引，比如联合主键如下图所示，只能是where name =XX开头才能走联合索引，否则会失效。

总结：判断是否使用联合索引，联想下面这张图是否能走！

索引优化

SQL语句优化

尽量避免使用子查询

用in替代or

尽量K%这种查询

Limi offset count转换成 id>offset limit count

group by 可以使用group by null

尽量不要使用not等负向条件

IN适合于外表大而内表小的情况；EXISTS适合于外表小而内表大的情况

Spring

Spring中的AOP主要有两种实现方式：

JDK动态代理

1. 真实角色：创建业务接口，业务类实现接口

   public interface PeopleInterface {
       public void fun();
   }
   public class People implements PeopleInterface{
       @Override
       public void fun() {
           System.out.println("这是People的fun方法");
       }
   }

2. 代理角色：继承 InvocationHandler，重写invoke()，构造器获得真实角色，封装获取代理对象

   public class MyHandle implements InvocationHandler {
       // 被代理对象实例
       private Object object;
   
       // 构造器
       public MyHandle(Object object) {
           this.object = object;
       }
   
       // 封装获取代理对象
       public Object getProxy() {
           return Proxy.newProxyInstance(
                   this.getClass().getClassLoader(),
                   object.getClass().getInterfaces(), this);
       }
   
       // 实现抽象接口的实体方法
       @Override
       public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
           before();
           Object result = method.invoke(this.object, args);
           after();
           return result;
   
       }
   
       // 增强的方法
       private void before() {
           System.out.println("增强的before方法");
       }
       private void after() {
           System.out.println("增强的after方法");
       }
   }

3. 通过代理类调用方法

   public class DynamicProxy {
       public static void main(String[] args) {
           // 1 被代理对象：真实角色
           PeopleInterface peopleI = new People();
           // 2 自定义处理器：代理角色
           // 代理角色实现真实角色的抽象接口
           MyHandle myHandle = new MyHandle(peopleI);
           // 3 代理角色获得代理类
           PeopleInterface people = (PeopleInterface) myHandle.getProxy();
           // 4 由proxy动态代理调用被代理的接口方法
           people.fun();
       }
   }

cglib实现动态代理

1. 创建被代理类，无需实现其他接口

   public class Person {
       public void eat() {
           System.out.println("Person：我要开始吃饭了");
       }
   
       public void play() {
           System.out.println("Person：我要出去玩了");
       }
   }

2. 两个方法实现MethodInterceptor

   public class MyApiInterceptor implements MethodInterceptor {
       @Override
       public Object intercept(Object obj, Method method, Object[] args, MethodProxy proxy) throws Throwable {
           System.out.println("吃饭前，必须得洗手");
           Object result = proxy.invokeSuper(obj, args);
           System.out.println("吃饭后，我要看会儿电视");
           return result;
       }
   }
   public class MyApiInterceptorForPlay implements MethodInterceptor {
   
       @Override
       public Object intercept(Object obj, Method method, Object[] args, MethodProxy proxy) throws Throwable {
           System.out.println("出去玩，我要带玩具");
           Object result = proxy.invokeSuper(obj,args);
           System.out.println("玩完后，我就要回家");
           return result;
       }
   }

3. 实现失败过滤器，实现CallbackFilter

   public class CallbackFilterImpl implements CallbackFilter {
       @Override
       public int accept(Method method) {
           if (method.getName().equals("play")) {
               return 1;
           } else {
               return 0;
           }
       }
   }

4. 实现cglib动态代理

   public class CglibTest {
       public static void main(String[] args) {
           // 定义回调函数的接口
           Callback[] callbacks = new Callback[]{
                   new MyApiInterceptor(), new MyApiInterceptorForPlay()
           };
           // cglib使用enhancer实现动态代理
           Enhancer enhancer = new Enhancer();
           // 设置被动态代理的父类
           enhancer.setSuperclass(Person.class);
           // 回调的拦截器数组
           enhancer.setCallbacks(callbacks);
           // 回调选择器
           enhancer.setCallbackFilter(new CallbackFilterImpl());
           // 创建代理对象
           Person person = (Person) enhancer.create();
           person.eat();
           System.out.println("------");
           person.play();
       }
   }

• DK动态代理只提供接口的代理，不支持类的代理。核心InvocationHandler接口和Proxy类，InvocationHandler 通过invoke()方法反射来调用目标类中的代码，动态地将横切逻辑和业务编织在一起；接着，Proxy利用 InvocationHandler动态创建一个符合某一接口的的实例, 生成目标类的代理对象。
• 如果代理类没有实现 InvocationHandler 接口，那么Spring AOP会选择使用CGLIB来动态代理目标类。CGLIB（Code Generation Library），是一个代码生成的类库，可以在运行时动态的生成指定类的一个子类对象，并覆盖其中特定方法并添加增强代码，从而实现AOP。CGLIB是通过继承的方式做的动态代理，因此如果某个类被标记为final，那么它是无法使用CGLIB做动态代理的。

SpringBoot

自动装配

@SpringBootConfiguration

• 说明里面的 @Component 这就说明，启动类本身也是Spring中的一个组件而已，负责启动应用！

@SpringBootApplication
    @SpringBootConfiguration// 表明是一个SpringBoot配置文件
        @Configuration// 再次说明这是一个Spring配置

@EnableAutoConfiguration

• @AutoConfigurationPackage
  • @AutoConfigurationPackages.Registrar.class:
    • Registrar.class作用就是将主启动所在的包及以下的所有子包都扫描进spring容器中

@AutoConfigurationPackage
@Import(AutoConfigurationImportSelector.class)

• @Import(AutoConfigurationImportSelector.class) ，找到getCandidateConfigurations方法
  • getCandidateConfigurations方法:获得候选的配置

protected List<String> getCandidateConfigurations(AnnotationMetadata metadata, AnnotationAttributes attributes) {
        List<String> configurations = SpringFactoriesLoader.loadFactoryNames(getSpringFactoriesLoaderFactoryClass(),
                getBeanClassLoader());
        Assert.notEmpty(configurations, "No auto configuration classes found in META-INF/spring.factories. If you "
                + "are using a custom packaging, make sure that file is correct.");
        return configurations;
    }

• 找到SpringFactoriesLoader.loadFactoryNames，点进去，找到loadSpringFactories方法
  • SpringFactoriesLoader类中的预定义的自动装配路径 FACTORIES_RESOURCE_LOCATION = "META-INF/spring.factories";

public static final String FACTORIES_RESOURCE_LOCATION = "META-INF/spring.factories";

public static List<String> loadFactoryNames(Class<?> factoryType, @Nullable ClassLoader classLoader) {
        String factoryTypeName = factoryType.getName();
        return loadSpringFactories(classLoader).getOrDefault(factoryTypeName, Collections.emptyList());
    }

private static Map<String, List<String>> loadSpringFactories(@Nullable ClassLoader classLoader) {
    //获得classLoader
    MultiValueMap<String, String> result = cache.get(classLoader);
    if (result != null) {
        return result;
    }

    ...
}

• 多次出现的spring.factories，就是预定好的加载配置文件
  

@ComponentScan

• 自动扫描并加载符合条件的组件bean,并将这个组件bean注入到IOC容器中

@ComponentScan(excludeFilters = { @Filter(type = FilterType.CUSTOM, classes = TypeExcludeFilter.class),
        @Filter(type = FilterType.CUSTOM, classes = AutoConfigurationExcludeFilter.class) })

3.2 自动装配

• 自动配置真正实现是从classpath中搜寻所有的META-INF/spring.factories配置文件 ，并将其中对应的org.springframework.boot.autoconfigure.包下的配置项，通过反射实例化为对应标注了 @Configuration的JavaConfig形式的IOC容器配置类 ， 然后将这些都汇总成为一个实例并加载到IOC容器中。

• 用户如何书写yml配置，需要去查看META-INF/spring.factories下的某自动配置，如HttpEncodingAutoConfiguration

  • EnableConfigrutionProperties(xxx.class):表明这是一个自动配置类，加载某些配置
  • XXXProperties.class：封装配置文件中的属性，yam中需要填入= 它指定的前缀+方法

3.3 工作原理总结

1. 读取spring.properties文件
   1. SpringBoot在启动的时候从spring-boot-autoConfigure.jar包下的的META-INF/spring.factories中获取EnableAutoConfiguration属性的值加载自动配置类
   2. 将这些值作为自动配置类导入容器 ， 自动配置类就生效 ， 帮我们进行自动配置工作；
2. 加载XXXProperties类
   1. 根据自动配置类中指定的xxxxProperties类设置自动配置的属性值，开发者可以根据该类在yml配置文件中修改自动配置
3. 根据@ConditionalXXX注解决定加载哪些组件
   1. Springboot通过该注解指定组件加入IOC容器时锁需要具备的特定条件。这个组件会在满足条件时候加入到IOC容器内

Redis

Redis主要有5种数据类型，包括String，List，Set，Zset，Hash，满足大部分的使用要求

缓存设计

缓存穿透

缓存穿透是指查询一个根本不存在的数据， 缓存层和存储层都不会命中， 通常出于容错的考虑， 如果从存储层查不到数据则不写入缓存层。

缓存穿透将导致不存在的数据每次请求都要到存储层去查询， 失去了缓存保护后端存储的意义。

造成缓存穿透的基本原因有两个：

第一， 自身业务代码或者数据出现问题。

第二， 一些恶意攻击、 爬虫等造成大量空命中。

缓存穿透问题解决方案：

1、缓存空对象

import com.google.common.hash.BloomFilter;

//初始化布隆过滤器
//1000：期望存入的数据个数，0.001：期望的误差率
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.001);  

//把所有数据存入布隆过滤器
void init(){
    for (String key: keys) {
        bloomFilter.put(key);
    }
}

String get(String key) {
    // 从布隆过滤器这一级缓存判断下key是否存在
    Boolean exist = bloomFilter.mightContain(key);
    if(!exist){
        return "";
    }
    // 从缓存中获取数据
    String cacheValue = cache.get(key);
    // 缓存为空
    if (StringUtils.isBlank(cacheValue)) {
        // 从存储中获取
        String storageValue = storage.get(key);
        cache.set(key, storageValue);
        // 如果存储数据为空， 需要设置一个过期时间(300秒)
        if (storageValue == null) {
            cache.expire(key, 60 * 5);
        }
        return storageValue;
    } else {
        // 缓存非空
        return cacheValue;
    }
}

2、布隆过滤器

对于恶意攻击，向服务器请求大量不存在的数据造成的缓存穿透，还可以用布隆过滤器先做一次过滤，对于不存在的数据布隆过滤器一般都能够过滤掉，不让请求再往后端发送。当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。

布隆过滤器就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都为 1，只要有一个位为 0，那么说明布隆过滤器中这个key 不存在。如果都是 1，这并不能说明这个 key 就一定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤，这个概率就会降低。

这种方法适用于数据命中不高、 数据相对固定、 实时性低（通常是数据集较大） 的应用场景， 代码维护较为复杂， 但是缓存空间占用很少。

可以用guvua包自带的布隆过滤器，引入依赖：

<dependency>    
    <groupId>com.google.guava</groupId>    
    <artifactId>guava</artifactId>    
    <version>22.0</version> 
</dependency>

示例伪代码：

import com.google.common.hash.BloomFilter;

//初始化布隆过滤器
//1000：期望存入的数据个数，0.001：期望的误差率
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.001);  

//把所有数据存入布隆过滤器
void init(){
    for (String key: keys) {
        bloomFilter.put(key);
    }
}

String get(String key) {
    // 从布隆过滤器这一级缓存判断下key是否存在
    Boolean exist = bloomFilter.mightContain(key);
    if(!exist){
        return "";
    }
    // 从缓存中获取数据
    String cacheValue = cache.get(key);
    // 缓存为空
    if (StringUtils.isBlank(cacheValue)) {
        // 从存储中获取
        String storageValue = storage.get(key);
        cache.set(key, storageValue);
        // 如果存储数据为空， 需要设置一个过期时间(300秒)
        if (storageValue == null) {
            cache.expire(key, 60 * 5);
        }
        return storageValue;
    } else {
        // 缓存非空
        return cacheValue;
    }
}

缓存失效

由于大批量缓存在同一时间失效可能导致大量请求同时穿透缓存直达数据库，可能会造成数据库瞬间压力过大甚至挂掉，对于这种情况我们在批量增加缓存时最好将这一批数据的缓存过期时间设置为一个时间段内的不同时间。

示例伪代码：

String get(String key) {
    // 从缓存中获取数据
    String cacheValue = cache.get(key);
    // 缓存为空
    if (StringUtils.isBlank(cacheValue)) {
        // 从存储中获取
        String storageValue = storage.get(key);
        cache.set(key, storageValue);
        //设置一个过期时间(300到600之间的一个随机数)
        int expireTime = new Random().nextInt(300)  + 300;
        if (storageValue == null) {
            cache.expire(key, expireTime);
        }
        return storageValue;
    } else {
        // 缓存非空
        return cacheValue;
    }
}

缓存雪崩

缓存雪崩指的是缓存层支撑不住或宕掉后， 流量会像奔逃的野牛一样， 打向后端存储层。

由于缓存层承载着大量请求， 有效地保护了存储层， 但是如果缓存层由于某些原因不能提供服务(比如超大并发过来，缓存层支撑不住，或者由于缓存设计不好，类似大量请求访问bigkey，导致缓存能支撑的并发急剧下降)， 于是大量请求都会达到存储层， 存储层的调用量会暴增， 造成存储层也会级联宕机的情况。

预防和解决缓存雪崩问题， 可以从以下三个方面进行着手。

1） 保证缓存层服务高可用性，比如使用Redis Sentinel或Redis Cluster。

2） 依赖隔离组件为后端限流并降级。比如使用Hystrix限流降级组件。

3） 提前演练。 在项目上线前， 演练缓存层宕掉后， 应用以及后端的负载情况以及可能出现的问题， 在此基础上做一些预案设定。

热点缓存key重建优化

开发人员使用“缓存+过期时间”的策略既可以加速数据读写， 又保证数据的定期更新， 这种模式基本能够满足绝大部分需求。 但是有两个问题如果同时出现， 可能就会对应用造成致命的危害：

• 当前key是一个热点key（例如一个热门的娱乐新闻），并发量非常大。
• 重建缓存不能在短时间完成， 可能是一个复杂计算， 例如复杂的SQL、 多次IO、 多个依赖等。

在缓存失效的瞬间， 有大量线程来重建缓存， 造成后端负载加大， 甚至可能会让应用崩溃。

要解决这个问题主要就是要避免大量线程同时重建缓存。

我们可以利用互斥锁来解决，此方法只允许一个线程重建缓存， 其他线程等待重建缓存的线程执行完， 重新从缓存获取数据即可。

String get(String key) {
    // 从Redis中获取数据
    String value = redis.get(key);
    // 如果value为空， 则开始重构缓存
    if (value == null) {
        // 只允许一个线程重建缓存， 使用nx， 并设置过期时间ex
        String mutexKey = "mutext:key:" + key;
        if (redis.set(mutexKey, "1", "ex 180", "nx")) {
             // 从数据源获取数据
            value = db.get(key);
            // 回写Redis， 并设置过期时间
            redis.setex(key, timeout, value);
            // 删除key_mutex
            redis.delete(mutexKey);
        }// 其他线程休息50毫秒后重试
        else {
            Thread.sleep(50);
            get(key);
        }
    }
    return value;
}

算法

斐波那契

/**
 * 斐波那契函数
 */
public class StepNum {
    public static void main(String[] args) {
        System.out.println("递归：" + function1(7));
        System.out.println("迭代：" + function2(7));
    }

    private static int function1(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n异常");
        } else {
            if (n == 0 || n == 1 || n == 2) {
                return n;
            } else {
                return function1(n - 1) + function1(n - 2);
            }
        }
    }

    private static int function2(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n异常");
        } else {
            if (n == 0 || n == 1 || n == 2) {
                return n;
            } else {
                int one = 1;
                int two = 2;
                int sum = 0;
                for (int i = 3; i <= n; i++) {
                    sum = one + two;
                    one = two;
                    two = sum;
                }
                return sum;
            }
        }
    }
}

数组

1 两数之和

题目：给定一个整数数组 nums 和一个目标值 target，找出和为目标值的那 两个 整数，并返回他们的数组下标。

public class Leet1 {
    /**
     * 暴力破解法：
     * 1 第一次for从0开始，遍历到末尾
     * 2 第二个for从上一个for遍历指针的下一个数开始遍历，遍历到末尾
     * 3 判断是否两数之和为target
     */
    public int[] towSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    /**
     * hashMap法：
     * 1 第一次for从0开始，遍历到末尾
     * 2 map.containsKey判断是够有目标值-当前数组值
     * 3 有就返回；无就map.put(数值值，数组下标)
     */
    public int[] towSum2(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            // key=数组值。value=数组下标
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

268 丢失的数字

题目：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

要求：实现线性时间复杂度、仅使用额外常数空间的算法解决此问题

public class Leet268 {
    /**
     * 排序法：
     */
    public int missingNumber1(int[] nums) {
        Arrays.sort(nums);
        // 判断排序后的首位和末尾是否是期望值
        if (nums[0] != 0) {
            return 0;
        } else if (nums[nums.length - 1] != nums.length) {
            return nums.length;
        }
        // 如果首末尾都是期望值，期望值一定是(0,n)之间一个相差大于1的数
        for (int i = 1; i < nums.length; i++) {
            // 当前数的期望值=上一个数+1
            int expect = nums[i - 1] + 1;
            if (expect != nums[i]) {
                return expect;
            }

        }
        return -1;
    }

    /**
     * set法
     */
    public int missingNumber2(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        // 数组中的数都放入set中
        for (int num : nums) {
            set.add(num);
        }
        // 遍历[0,n]是否出现在set中
        for (int i = 0; i <= nums.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 异或法:速度最快
     * 数组：[0,1,3,4] n=4，缺失2
     * 下标： 0 1 2 3 下标只能到n-1，缺少n
     * 结果：(0^0)^(1^1)^(2)^(3^3)^(4^n)=2 一次遍历完成
     */
    public int missingNumber3(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            n = n ^ (i ^ nums[i]);
        }
        return n;
    }
}

链表

206 反转单链表

题目：反转单链表

public class ListNode {
    public int val;
    public ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Leet209 {
    /**
     * 迭代法一：cur遍历
     * 1 先获取cur.next
     * 2 每次迭代到cur，都将cur的next指向pre
     * 3 然后pre和cur前进一位。
     * 4 cur==null时，pre指向最后一个结点，返回pre
     */
    public ListNode reverseList1(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // next存cur的下一个节点
            ListNode tmp = cur.next;
            // 每次迭代到cur，cur.next都指向pre
            cur.next = pre;
            // cur和cur都向前移一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    /**
     * 迭代法2：head遍历，不需要cur，节省空间
     * 1 先获取head.next
     * 2 每次head.next都执行pre
     * 3 pre和head向后移一位
     * 4 cur==null时，pre指向最后一个结点，返回pre
     */
    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 递归解法：
     * 1 递归结束条件：head=null或者head.next=null
     * 2 lastNode是单链表最后一个结点，每次递归返回都是它
     * 2 head此时指向倒数第二个节点
     * 3 head.next.next=head，让最后一个结点开始反转
     * 4 head.next防止链表循环
     */
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode LastNode = reverseList3(head.next);
        head.next.next = head;
        head.next = null;
        return LastNode;
    }
}

21 合并两个有序链表

题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Leet21 {
    /**
     * 递归法
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /**
     * 迭代法：速度最快
     */
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        // 记录返回值的头结点的pre哨兵
        ListNode resultPre = new ListNode(-1);
        ListNode pre = resultPre;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            // 移动pre指向较小值
            pre = pre.next;
        }
        // pre.next指向还未为空的链表，因为l1和l2都是有序的
        pre.next = (l1 == null) ? l2 : l1;
        return resultPre.next;
    }
}

141 环形链表

题目：判断一个链表是否有环，有就返回ture，无就返回false

public class Leet141 {
    /**
     * set法
     */
    public boolean hasCycle1(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    /**
     * 快慢指针
     */
    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        // 慢指针指向头结点
        ListNode slow = head;
        // 快指针指向头结点的第二个节点
        ListNode fast = head.next;
        while (slow != fast) {
            // 无环形时，快指针会先到底
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

哈希表

217 存在重复数字

题目：给定一个整数数组，判断是否存在重复元素。如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false

public class Leet217 {
    /**
     * 两次遍历法：时间超时
     */
    public boolean containsDuplicate1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 排序法
     */
    public boolean containsDuplicate2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
    /**
     * Set法
     */
    public boolean containsDuplicate3(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if(set.contains(num)){
                return true;
            }
            set.add(num);
        }
        return false;
    }
}

389 找不同

题目：给定两个字符串 s 和 t，它们只包含小写字母。字符串 t由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

/**
 * 389 找不同
 */
public class Leet389 {
    /**
     * 异或法：
     */
    public char findTheDifference(String s, String t) {
        // 从t的最后一个数开始异或
        char cur = t.charAt(t.length() - 1);
        for (int i = 0; i < s.length(); i++) {
            cur ^=s.charAt(i);
            cur ^=t.charAt(i);
        }
        return cur;
    }
}

队列

993 二叉树的堂兄弟结点

题目：在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

public class Leet993 {
    // 值和深度
    Map<Integer, Integer> depth;
    // 父亲的值和父节点
    Map<Integer, TreeNode> parent;

    public boolean isCousins(TreeNode root, int x, int y) {
        depth = new HashMap<>();
        parent = new HashMap<>();
        dfs(root, null);
        return (depth.get(x) == depth.get(y)) && (parent.get(x) != parent.get(y));

    }

    // 深度优先遍历
    public void dfs(TreeNode node, TreeNode par) {
        // 如果当前节点不为空
        if (node != null) {
            // 在写这两个
            depth.put(node.val, par == null ? 0 : depth.get(par.val) + 1);
            parent.put(node.val, par);
            // 先写这两个
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }
}

225 队列实现栈

题目：使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

/**
 * 225 队列实现栈
 *  用两个队列实现：会超时，不推荐学
 */
public class Leet225_1 {
    LinkedList<Integer> q1;
    LinkedList<Integer> q2;

    // 构造器
    public Leet225_1() {
        this.q1 = new LinkedList<>();
        this.q2 = new LinkedList<>();
    }

    // 进栈
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q1.offer(q2.poll());
        }
        LinkedList<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

    // 出栈
    public int pop() {
        return q1.poll();
    }

    // 栈顶元素
    public int top() {
        return q1.peek();
    }
    // 判空
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * 225 用队列实现栈
 *  单个队列法：单个队列入队尾，队尾前的数重新入队尾
 */
public class Leet225_2 {
    LinkedList<Integer> queue;

    public Leet225_2() {
        this.queue = new LinkedList<>();
    }

    // 进栈
    public void push(int x) {
        // 先获得之前队列的长度
        int length = queue.size();
        // 再入队尾
        queue.offer(x);
        // 遍历队尾前面的数，重新入队尾
        for (int i = 0; i < length; i++) {
            queue.offer(queue.poll());
        }
    }

    // 出栈
    public int pop() {
        return queue.poll();
    }

    // 栈顶元素
    public int top() {
        return queue.peek();
    }

    // 判空
    public boolean empty() {
        return queue.isEmpty();
    }
}