Java 复习 JDK8 新特性 Lambda 和 Stream

参考自视频:https://www.bilibili.com/video/BV18b411t7Nc/

下面复习JDK8主打的两种新特性 Lambda 和 Stream

Lambda表达式

Lambda在一些动态语言中是一个匿名函数,在java中Lambda本质上是一个接口的实例化对象

格式 (o1, o2) -> Integer.compare(o1,o2)

  • 左边是形参列表(重写抽象方法的形参列表)
  • ->是Lambda操作符
  • 右边是Lambda方法体(重写抽象方法的方法体)

六种调用方式

  • Runnable runnable = () -> {System.out.println(“running”);}
  • Consumer<String> consumer = (String str) -> {System.out.println(str);}
  • Consumer<String> consumer = (str) -> {System.out.println(str);}
  • Consumer<String> consumer = str -> {System.out.println(str);}
  • Comparator<Integer> comparator = (o1, o2) -> return Integer.compare(o1, o2)
  • Comparator<Integer> comparator = (o1, o2) -> Integer.compare(o1, o2)

总结:是参数的类型可以省略,有自动推断机制,如果参数只有一个,那么括号可以省略,你把方法体应该用一对大括号来扩充,但是如果其中呢只有一条语句的话,括号可以省略,如果只有一条语句,并且是return语句,return这个关键词也可以省略。

这些都是建立在实现的接口中只有一个抽象方法(不会有歧义),这种类型的接口叫做函数式接口

函数式接口可以用FunctionalInterface注解进行修饰,类似Override注解的功能,在编译时期进行格式检查。

Lambda表达式一定依赖于函数式接口。

四大函数式接口

方法引用和构造器引用

方法引用本质上就是lambda表达式,只是一种更简便的方法,

使用要求:使用方法引用的前提是已有方法实现了接口抽象方法实现的功能,形参和返回值可以匹配上,有如下三种情况:

对象::非静态方法

Consumer <String> consumer = System.out::println;

Supplier<String> supplier = emp::getName;

类::静态方法

Comparator<Integer> comparator = Integer::compare;

Function<Double, Long> fun = Math::round;

类::实例方法(这种比较难)

BiPredicate<String, String> pre = String::equals;

Comparator<String> comparator = String::compareTo;

Function<Employee, String> func = Employee::getName;

构造器引用

Supplier<Employee> su = Employee::new;(调用空参数构造器)

Function<Integer, Employee> fun = Employee::new; (调用带一个参数integer的构造器)

BiFunction<Interger, String, Emplyee> fun2 = Employee::new;

数组引用(把数组看作一个特殊的类)

Function<Integer, String[]> fun = String[] :: new;

Stream API 真正把函数式编程风格引入到Java中,可以对集合数据进行操作,类似于SQL执行数据库查询。集合是数据在内存中,Stream是计算在CPU中

Stream不会自己存储元素,Stream也不会改变原有对象,Stream的计算是延迟的,

Stream的三个步骤,创建对象、中间操作、终止操作。

创建stream对象的方法

Collection接口中的default方法 stream 和 pararallStream

Arrays类的静态方法 stream

Stream类的静态方法 public static stream of (T…t)

创建无限流

Stream.iterate(0, t->t+2).limit(10).forEach(System.out::println) 输出前10个偶数,从0开始

Stream.generate(Math::random).limit(0).forEach(Sytem.out::println)输出10个随机数

中间操作

筛选和切片

fileter(Predicate p) 自定义筛选数据

limit(n) 截断流,取前n个数据

skip(n) 跳过前n个数据

distinct 筛选 利用流中元素的hashCode和equal方法去除重复元素。

映射

map(function fun)

Stream<String> stream = Arrays.asList("aa","bb","cc").stream();
stream.map(String::toUpperCase).forEach(System.out::println);

flatmap 扁平映射,把Stream套Stream的形式压成一层扁平的Stream

排序 sorted 自然排序和 sorted(Comparator comparator)定制排序

终止操作:

匹配和查找

allMatch anyMatch noneMatch 见面知意,参数一定是Predicate接口

findFirst、findAny、count、max(Comparator com)、min(Comparator com)

forEach(Consumer c) 内部迭代

归约 reduce(T identity, BinaryOperator)

System.out.println(Stream.iterate(1, x -> x + 1).limit(10).reduce(Integer::sum));

收集

collect(Collector c)

stream.collect(Collectors.toList()) stream.collect(Collectors.toSet())

Optional类 是用来避免空指针对程序对伤害。Optional可以理解为是一个容器或者是一个包装类,Optional有两种构造方法,一种是Optional.of(T) 一种是Optional.ofNullable()。为了避免在程序中出现空指针异常,使用orElse(备胎)方法获取Optional容器中的对象,如果是null就返回备胎,保证返回的对象不空。后面JDK9、10、11还会对这个类进行优化,可以暂且不用太关注。

java 高级复习

参考自 https://www.bilibili.com/video/BV1Qb411g7cz?from=search&seid=7373469111232659208

程序:是为了完成特定的目的,用某种语言编写的一种指令的集合

进程:是程序的一次运行后者是一个正在运行的程序,进程是资源分配的基本单位

线程:线程是进程的进一步细分,是程序内的一条执行路径。线程是调度和执行的单位,每个线程……

在java的虚拟机JVM中,每个线程都有自己的虚拟机栈和程序计数器,方法区和堆是进程独有的。即多个线程共享进程中的方法区和堆,这就存在安全隐患。

单核cpu上的多线程是假的多线程,只是一种快速的线程切换,同一个时刻只能执行一个线程。多核CPU才是真的多线程。

一个java应用程序至少有三个线程,main()主线程,gc()垃圾回收线程,异常处理线程。

并行(单核,时间片)与并发(多核)

单核CPU多线程实际比单线程慢,线程切换要花时间,但是多线程有他自己的优点,提高应用程序的响应,提高用户体验。提高计算机系统CPU的利用率。也可以改善程序结构,不用将冗长复杂的进程分为多个线程独立运行,利于理解和修改。

何时需要多线程 ?需要同时执行多个数据 (多功能的引用)或者需要一些等待的任务(加载图片) 或者一些后台运行的程序(垃圾回收)。

创建线程的两种方法:

方法一;继承Thread类并重写run方法,new出对象之后调用start方法。只能start一次,否则会出异常或者重新new一个对象再调用start方法。也可以用匿名子类。

    new Thread(){
        @Override
        public void run() {
            System.out.println("test");
        }
    }.start();

Thread.currentThread()一个静态方法,返回当前执行代码的线程。

yield()方法:释放当前线程的cpu执行,但是有可能下一时刻又拿到执行权。

join()方法:在线程A中调用线程B的join方法,线程A进入阻塞状态,直到线程B完全执行完以后,A结束阻塞状态。

sleep()方法:阻塞当前线程具体的时间

isAlive() 判断当前线程是否还存活。

线程有优先级1-10,默认是5

第二种创建线程的方法,实现Rnnable 接口,并重写run方法。

new Thread(new Runnable() {
@Override
public void run() {
System.out.println("test");
}
}).start();

两种方式优先选择Runnable的方式,应为实现的方式没有单继承的限制,更适合用来处理共享数据的问题。两种方法都需要重写run方法,将线程要执行的逻辑写在其中。

线程分为两类:守护线程和用户线程

线程的生命周期,状态:新建、就绪、运行、阻塞、死亡

线程的同步为了解决线程安全问题,原因在于操作共享数据为完成时,其他线程也进来操作数据。

同步代码块 synchronized(同步监视器){},同步监视器就是锁,任何一个类的对象都可以充当锁,要求多个线程共用同一个锁。解决了线程安全问题,但效率上有一点损失。在Runnable实现的方式可以用this(代表当前对象)作为锁。继承Thread的方法不可以,可以用类对象充当锁,Test.class。

同步方法如果一个操作共享数据的代码在一个方法中,直接用同步方法就可以。非静态同步方法的默认持有锁是this,Runnable方式好用,静态方法的同步监视器是当前的类对象,继承Thread方式好用。

用线程同步解决懒汉式单例模式的安全隐患。将getInstance方法直接声明为同步方法,但是效率不高。提高效率如下:

class SingleTon {
    private SingleTon(){}
    private static SingleTon instance;
    public static SingleTon getInstance(){
        if (instance == null) {
            synchronized (SingleTon.class){
                if (instance == null)
                    instance = new SingleTon();
            }
        }
        return instance;
    }
}

死锁,不同线程分别持有对方所需要的同步资源,都在等待对方释放资源,形成了死锁。

JDK5新增两种解决线程安全的方式,Lock锁。(ReentrantLock lock = new ReentrantLock();)也要保证里lock的唯一性。

lock.lock() lock.unlock() 夹住同步代码,可以结合try 和 finally

sychronized 和 lock的异同。两者都可以解决线程安全问题,sychronized自动释放锁,lock需要手动释放锁。lock的方式更灵活,其次是同步代码块,再是同步方法。

线程的通信涉及三个方法

wait()方法,当前方法进入阻塞状态,并释放锁

notify()方法,唤醒被wait的优先级最高的一个线程

notifyAll()方法,唤醒所有被wait的的线程

tip:三个方法必须用在同步代码块或者同步方法中,调用这三个方法必须由锁对象进行调用。这三个方法都定义在Object类中。

sleep方法和wait方法的异同:都可以时当前线程进入阻塞状态,两个方法声明的位置不同,sleep在Thread类中,wait在Object类中,sleep可以在任何需要的时候调用,wait必须在同步方法或者同步代码块中调用。如果两个方法都使用在同步代码中,wait方法会释放锁。

消费者和生产者问题的多线程设计

创建线程的方法三:实现Callable接口,结合FutureTask和Thread类。

     FutureTask futureTask = new FutureTask(new Callable() {
            @Override
            public Object call() throws Exception {
                return null;
            }
        });
        new Thread(futureTask).start();
        try {
            Object obj = futureTask.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }

Callable接口比Runnable方法好?

  • call方法有返回值,可以利用futureTask任务的get方法取得
  • call方法可以抛出异常,被外面的操作捕获,获取异常的信息
  • callable支持泛型

创建线程的方法四:线程池(避免频繁的创建和销毁线程,e.g. 安卓listview的item图片加载。实现重复利用) 好处:1.提高响应速度2.降低资源消耗3.便于线程管理

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        executorService.execute(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 100; i++) {
                    System.out.println(Thread.currentThread().getName() + " " + i);
                }
            }
        });
        executorService.shutdown();

创建多线程的四种方式

方法导致状态变化(多线程可以作为例子),状态变化导致某些方法执行(回调方法,安卓activity中很常见)

java 常用类

String 是一个final类,不能被继承。实现了serializable和comparable接口,可序列化,可比较。内部定义了final char[]进行存储字符串数据。String代表不可变的序列。

Stirng可以通过字面量的定义方式,String对象引用指向的内容是存在jvm方法区的常量池中。而常量池会维护其中常量的唯一性。重新赋值,连接操作,或者修改操作时,都是在常量池中进行新建一个字符串常量的。

String两种实例化方式的区别。new 的方式如果常量池中没有定义的话是创建了两个对象

        String a = "abc";
        String b = new String("abc");
        System.out.println(a == b); //false
        System.out.println(a.equals(b)); //true
        System.out.println(b.equals(a)); //true

常量和常量(final 修饰的变量)的拼接,结果在常量池且常量池中不会有相同的内容。

只要有一个变量,那么结果就在堆中。除非结果调用了intern方法,结果就在常量池中。

        String s1 = "a";
        String s2 = "b";
        String s3 = "ab";
        String s4 = "a"+"b";
        String s5 = s1 + "b";
        String s6 = "a" + s2;
        String s7 = s1 + s2;
        String s8 = (s1 + "b").intern();
        final String s9 = "a";
        String s10 = s9 + "b";
        System.out.println(s3 == s4); //true
        System.out.println(s3 == s5); //false
        System.out.println(s3 == s6); //false
        System.out.println(s3 == s7); //false
        System.out.println(s3 == s8); //true
        System.out.println(s3 == s10); //true

JVM内部结构是随着版本进行优化,也会有不同企业公司面对不同落地需求,优化虚拟机内部结构版本的JVM。有名的就是sun公司的java hotspot JVM

Jvm规范中将堆分别(青年区、老年区和永久区),其中永久区可以认为就是方法区。

JDK6 常量池在方法区,JDK7的常量池在堆里,JDK8常量池有回到永久区,但是永久区名称叫成元空间了。

字符串的常用方法很多,需要铭记一点String是不可变的,任何产生字符串改变的方法都不会改变原来的字符串,都是生成新的对象。

String与基本数据类型的转换,parseXXX与valueOf方法。

String与char数组类型转换 String.toCharArray() 与 new String(char [] arr))

String与Byte数组的转换 String.getBytes() —— new String(byte[]) 使用特定的字符集编码将字符串转换为byte数组,abc之类的就是ASCII值,如果字符串中出现了中文,utf-8会将中文转换为3为的byte,gbk转换成2位字节。

编码:字符串(看得懂)->字节(看不懂) 解码:字节->字符串

乱码的出现就是由于编码和解码的字符集不同。

String、StringBuffer 和 StringBuilder的区别。

  • StringBuffer类:可变的字符序列,线程安全,效率低。 底层用char[]实现
  • StringBuilder类:可变的字符序列,线程不安全,效率高。 底层用char[]实现
  • String类:不可变的字符序列,底层用char[]实现

StringBuffer默认初始化16个长度的char数组,或者初始化长度+16,每次扩容为原来的2倍+2,或者最小扩容数量。也可以在初始化的时候定制初始化长度。如果应用场景需要频繁修改字符串,StringBuffer的效率肯定高于String。

单线程效率:StringBuilder > StringBuffer > String

StringBuffer的一些方法返回值是this,可以实现方法链调用,这些方法对StringBuffer自身对象进行了修改,如append,delete等方法。返回值是String的方法则对本身不进行修改,如substring方法。

StringBuilder只是多数方法上加了sychronized 关键字。

java.util.Date 是 java.sql.Date的父类,后者和数据库交互的时候用,

java.util.Date转换为java.sql.Date类型的对象

simpledateformat类的构造函数,format和parse方法

jdk8 的localdatetime、instant和datetimeformatter这三个类关于时间日期操作更好用,符合人们认知和使用习惯

如果对象的引用需要能够用> >= < <=等进行比较时,需要使用Comparable接口,实现类需要重写compareTo方法,实现一种自然的排序。compareTo方法当前对象小返回负数,相等返回零,否则返回正数。这种比较方式实现(集成)在类的内部,类在定义的时候就需要制定,不够灵活。

Comparator接口也是一种比较器,可以实现定制排序。实现类需要实现compare方法。

        String [] arr = {"bac", "acd", "ddk", "bcd"};
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return -o1.compareTo(o2);
            }
        });
        System.out.println(Arrays.toString(arr));

两种方式对比,Comparable接口一旦制定,类在任何时候都可以比较。Comparator具有临时性。

System类代表系统,构造器是私有的,成员变量和方法基本都是静态的。如out,currentTimeMillions()、gc()……

Math类提供了一系列静态方法用于科学计算

BigInteger可以表示不可变的任意精度的整数。BigDecimal表示数字精度比较高的数字。

定义一组常量的时候,可以使用枚举类。

自定义枚举类可以利用final关键字实现,jdk5 以后可以使用enum关键字,更方便了。

enum Season{
    Spring("春天"),SUMMER("夏天"),AUTUMN("秋天"),WINTER("冬天");
    private String season;
    private Season(String season){
        this.season = season;
    }
}

注解 Annotation 注解是一种趋势

框架 = 注解 + 反射 + 设计模式

java中的注解

生成文档的相关注解如@author @version @param等

编译时进行格式检查 @Override @Deprecated @SuppressWarnings

如果方法上有@Override注解的话,编译过程会去校验方法的定义是否符合重写的规则,否则会报错,编译无法通过。@Deprecated 过时方法,但能用,为了兼容老代码。@SuppressWarnings 抑制编译器的一些警告,如变量没有使用,没有声明泛型等。

跟踪代码依赖性,代替配置文件的功能 servelet spring junit等框架提供的注解

注解可以认为是和类、接口、枚举并列的结构。也可以自定义。

注解具体实现什么功能?需要通过反射机制来完成。自定义的注解必须配合具体信息处理流程才有意义。

元注解是用来修饰其他注解的,主要有四种

Retention 表示所修饰注解的生命周期,取值Source表示在编译之前生效,class表示在会生成字节码文件(默认),runtime表示会被类加载器所加载到运行中,通过反射生效处理流程。

Target用于制定注解可以修饰的结构,不写默认都可以用,如类、接口、枚举、方法、构造器、变量、局部变量等

Documented表示所修饰的注解可以被解析到javadoc中

Inherited表明注解有继承性

通过反射可以获取注解信息,例子

Class clazz = Student.class;
Annotation [] annotations = clazz.getAnnotations();

jdk8 中关于注解的新特性

这里理解不是很深,后期再回来看看吧

集合框架

java从服务器数据库读取的list,为啥用json传,因为json是字符串,字符串是可序列化的。

集合框架分为collection接口 (collection又分为list接口 和set 接口)和map接口两个系列

list表示有序可重复集合,即动态数组,set表示无序不可重复集合

向实现collection接口的类对象中添加自定义类的时候,这个自定义类最好实现equals方法。因为很多方法都需要比较元素。

ArrayList.contains(), containsAll, romove, removeAll(删除交集),retainAll(求交集)方法比较的是对象的内容,调用equals方法。两个new的相同的字符串会返回true,如果自定义类没有重写eqauls方法,调用OBject类中的==比地址,则返回false。

数组和list的转换

  • Collection coll = Arrays.asList(12, 34, 56);
  • Object [] obj = coll.toArray();

Iterator迭代器接口(设计模式的一种,提供访问容器中各个元素的方式,而又不暴露容器的细节),通常使用hasNext方法和next方法结合使用。内部定义了Iterator在遍历的同时,remove删除当前元素。这比for循环靠谱,因为动态删除的时候数组的长度变了。

JDK 5 增强for循环,用于遍历集合对象(collection)和数组。底层就是用迭代器实现的。

for (Object obj : coll) {} 

List接口的三种实现类

  • ArrayList:作为List接口的主要实现类,线程不安全,效率高,底层用Object[]存储
  • LinkedList:底层使用双向链表进行存储,对频繁对插入和删除操作效率高
  • Vector:List接口的古老实现类,线程安全,效率低,底层用Object[]存储

ArrayList源码分析JDK7:

默认创建长度为10的Object[](饿汉),扩容每次为原来的1.5倍。建议new的时候制定容量,扩容移动数据会消耗资源。

JDK8中默认创建为{},第一次调用add操作的时候(懒汉),才创建长度为10的数据,后续其他操作 一致。

LinkdedList源码分析:定义了私有静态内部类Node,first和last属性,Node内部有prev和next两个引用,双向链表。

Vector默认创建10,扩容两倍,但是通常已经不用这个类了。

List常用方法,增删改查插长度遍历

注意list中remove方法的重载,以及list底层的Object数组,多态以及自动装箱。

ArrayList<Integer> al = new ArrayList<>();
al.add(1);
al.add(2);
al.add(3);
al.remove(2);
System.out.println(al); // 1,2
al.remove(new Integer(2));
System.out.println(al); //1

Set接口的主要实现类(无序,不可重复)

  • HashSet:作为Set的主要接口实现类, 线程不安全,可以存储null值
  • LinkedHashSet:作为HashSet的子类,遍历内部元素时,可以按照添加的顺序遍历‘
  • TreeSet类:可以按照添加元素制定的属性进行排序

Set接口没有额外定义新方法,都是Collection中的。

无序性理解:是不按照添加的顺序,不是随机性。底层虽然是用数组实现的,但是添加到数组中的位置是有hashcode决定的

不可重复性理解:保证添加的元素用hashcode和equal方法判断时,不能返回true

HashSet底层时用数组实现的,向其中添加元素时,首先算元素的Hashcode值,在通过散裂函数算存储的位置,如果该位置没有元素,添加成功。如果有元素,先比较hash值,不同则添加成功,相同再比较equals方法,false则添加成功。

多个元素通过链表进行存储,JDK7 和 JDK8中 (JDK8中旧的在原位)

向Set中添加的元素,需要重写hashcode方法和equals方法,相同元素一定要有相同的hashcode。

HashSet的底层是用HashMap来实现的。

LinkedHashSet作为HashSet的子类,在添加数据的同时,每个数据额外维护了两个prev和next指针(引用),对于比较频繁的遍历操作,效率高于HashSet,空间换时间。并且遍历顺序是按照添加顺序。

TreeSet中添加的元素,要求是相同类的对象。添加的对象必须有比较的方法,实现comparable接口或者定制comparator,定制的newTreeSet的时候传入。底层用红黑树进行实现。用campare/campareTo方法的返回值判断是不是唯一元素,不再用equals方法了。

List 和 Set 中都有很多方法涉及到重写equals方法,除了TreeSet.

一道有难度的题目,考察hashset中add方法的底层实现

public class HashSetTest {
    public static void main(String[] args) {
        HashSet<Person> hs = new HashSet<>();
        Person p1 = new Person(15, "Tom");
        Person p2 = new Person(15, "Amy");
        hs.add(p1);
        hs.add(p2);
        p1.setName("Jack");
        System.out.println(hs);
        hs.add(new Person(15, "Jack"));
        System.out.println(hs);
        hs.add(new Person(15, "Tom"));
        System.out.println(hs);

    }
}

class Person{
    private int age;
    private String name;

    Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person persino = (Person) o;
        return age == persino.age &&
                Objects.equals(name, persino.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

Map接口 双列数据,存储key-value对的数据。

Hashmap是map的主要实现类,非线程安全,可以存null的key和value,LinkedHashMap是hashMap的子类,提高了遍历的效率,且遍历顺序按照添加顺序。

Treemap内部元素按照key排序(自然、定制),底层用红黑树。

Hashtable古老的实现类,线程安全,效率低,不能存null,不常用了。有一个子类是Properties,配置文件,key value都是String

Hashmap JDK7 数组+链表 JDK8 数组+链表+红黑树

Map内部结构的理解:

key 无序,不可重复,value 无序,不可重复。key-value pair用Entry对象进行存储。key对象需要重写hashcode和equals方法。value要重写equals方法。

Hashmap的底层实现原理

初始化长度为16的Entry[] table.

put元素的时候,key.hashcode 散裂(& length-1) 确定位置,没冲突则装成Entry放入。冲突,则对比hashcode,在比key.equals(方法). 一样修改,不一样添加(头插法)。

每次扩容为原来的2倍。超过threshold并且索引位置不为空的时候扩容。

JDK8中Node[],而不是Entry[](本质一样,改个名罢了),首次put的时候才创建(懒汉),底层结构多了红黑树(数组+链表+红黑树)。当一个索引位置上元素个数大于8,且数组长度大于64,转换成红黑树,提高查找效率。五大常量:

  • DEFAULT_INITIAL_CAPACITY
  • DEFAULT_LOAD_FACTOR
  • threshold
  • TREEITY_THRESHOLD
  • MIN_TREEIFY_CAPACITY

LinkedHashMap就是把Node类改造了一下(继承),加了两个指针(引用)。

HashSet底层就是用Hashmap实现的,只存key,value统一指向一个静态的Object类的对象。

hashMap的遍历方法,keySet() / values() / entrySet() + iterator/增强for

面试题:负载因子的大小对Hashmap有什么影响?

负载因子表示Hashmap的数据密度。太大会怎样,太小会怎样?

treemap需要key是同一种类型的对象,并且要求该类实现comparable接口

Arrays是操作数组的工具类,Collectiions是操作集合和Map的工具类。

collection和collections的区别。

Collections常用方法包括reverse、shuffle、sort、swap、max、min(可以定制Comparator)、frequency、copy

        List src = Arrays.asList(new Integer[]{1,2,3});
        List des = Arrays.asList(new Object [src.size()]);
        Collections.copy(des, src);

Collections.sychronizedXxx方法返回线程安全的List、Set和Map,底层就是用同步代码块包裹了一下原来的方法。

数据结构的真实结构(数组、链表)和抽象结构(线性表(数组、链表、栈、队列)、树、图、其他),抽象结构都是在真实结构的基础上进行构建的。

泛型可以和集合框架结合,保证集合内部数据类型的一致性和类型检查,避免了强制转换带来的潜在异常。还可以用在Iterator、Comparator等接口,很方便。

Set<Map.Entry<String, Integer>> entrySet = hm.entrySet();

泛型必须是类,不能是基本数据类型,泛型不制定,则默认是java.lang.Object.

自定义泛型,继承的时候子类可以指明父类的泛型,子类就不是泛型类了。如果子类不指明,则子类还是泛型类。静态方法不能用泛型(从生命周期的角度很好理解),异常类也不能用泛型。

泛型方法:在方法中出现了泛型的结构,与类的泛型没有关系,类不是泛型类也没关系。泛型方法可以是静态的。

public <E> List<E> copy(E[] arr){} //public 后面的 <E> 是为了防止编译器认为E是一个类

例子:DAO(data access object)数据访问对象 就可以定义泛型,DAO中定义操作数据库表的共性操作的方法,T就可以是数据库中的表对于的类。

泛型在继承方面的体现。

类A是类B的父类,G<A>和G<B>不具有子父类关系,而是两个并列的结构。这会导致某些操作不太方便,因此引入通配符,二者的共同父类是G<?>

通配符: ?

public void print(List<?> list) {
Iterator <?> iterator = list.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println(obj);
}
}

像上面写不太好,不能再像list中添加任何元素了,除了null值。因为?具体表示什么类型不确定,只能读了,并且读出来的元素应该复制给Object类。

有限制的通配符。源码中很常见

?extends Person 实际上就是小于等于,这种方式添加数据不行

?super Persion 实际上就是大于等于,这种方式添加数据OK的

文件与IO流

文件File类,IO流主要有InputStream、OutputStream、Reader、Writer四个基本抽象类,任何其他的流操作都是在这四个类上继承而来的。

inputstream和outputstream是字节流,reader和writer是字符流

输入和输出都时相对与内存来说的

流可以分为节点流(例如直接作用在文件上)和处理流(作用在流上,如buffered)

流通常需要处理关闭close,否则可能会有内存泄露问题

FileReader作用于File节点,可以用char[]数组存读取的数据

FileWriter 文件不存在会自动创建,默认是覆盖模式,可以在File构造的时候制定为append模式。

FilieReader和FileWriter不能复制二进制文件(如图片等),因为是字符流

FileInputStream和FileOutputString可以复制二进制文件,字符文件当然也可以。读的过程用byte[]字节数组进行存储。

缓冲流是一种处理流,内置缓冲区,可以加速读写操作

BufferedInputStream、BufferedOutputStream、BufferedReader、BufferedWriter

字符流可以直接使用简单的方法,String line = br.readline(), 不包含换行符, bw.write(line) bw.newline()

转换流也是一种处理流,InputStreamReader和OutputStreamWriter,从后缀来看属于字符流,可以将字节输入流转换成字符流,将输出字符流转换成字节流。

转换流就设计到了编码解码

new InputStreamReader() 默认是用系统默认的字符集进行解码,当然可以显式地指定字符集。

字符集:

ASCII码(8位)、ISO8859-1(8位,欧洲)、GB2312(中文,最多两字节)、GBK(中文、最多两个字节,首位是0就是一个英文字母字节,是1就是两个字节中文)、

Unicode(所有语言的字符集,两个字节,实际没有落地) Unicode的问题,1.英文一个字节表示就够了,纯英文文件的话,文件有两倍大。2.如果英文的字符用一个字节进行编码,那么怎么区分一个字节字符和两个字节字符?3..如果英文采用首位0标识,那么能编码的字符数量就少了一半,不够用。

UTF-8(UCS transfer format)-8表示每8位传输。变长的字节编码方式,Unicode的一种实现方案,用前缀表示字符的长度,0xxxxxxx 、110xxxxx 10xxxxxx、1110xxxx 10xxxxxx 10xxxxxx、 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

ANSI编码标准,英文系统用 ISO8859-1 编码,中文系统默认用GBK。

标准输入输出流 默认是键盘输入控制台输出。可以通过方法重定向流,setIn,setOut。

System.in 是InputStream, 可以先包转换流,再包缓冲流,然后用readline读取System.out是PrintStream

打印流PrintStream和PrintWrite都是输出的,提供了一系列的重载的print()和println()方法。可以配合System.out实现输出的重定向

数据流DateinputStream和DateOutputStream是为了方便处理基本数据类型或者字符串。当然dos写到文件的数据对人来说通常是不可读,应该用dateinputstream进行配套对应读取。这两个类没什么意思

装饰设计模式和代理设计模式的区别。

对象流。 ObjectOutputStream,序列化 ObjectInputStream 反序列化。需要保证对象所属于的类是可序列化的。

对象序列化机制:允许把内存中的加了对象转化成平台无关的二进制流,从而允许把这种二进制流持久的保存在磁盘上或者通过网络,将这种二进制流传到另一个网络的一个节点上。当其他程序获得了,这种二进制流可以恢复成原来的java对象。

自定义类需要实现序列化Serializable接口,并提供serialVersionID值并且类中所有的属性都应该是可序列化(String和基本数据类型是可序列化的)才可以序列化。

serialVersionID理解: 就是一个类的标识,如果不显示指定,虽然会自动生成,但是如果你修改了类反序列化的时候可能不会保存,显式制定后再修改类反序列化的时候不会出问题。

static transit 成员变量不可序列化。

RandomAccessFile类,可以读可以写,写内容的时候可以从头覆盖,原来内容多可能留下来。

new RandomAccessFile(new File(), mode) mode可以是r rw rwd等

内部有位置指针seek(), 如果要实现插入的功能就比较麻烦了。多线程断点续传。

NIO(New IO、None-blocking IO)是面向缓冲区的,基于通道。是一种更加高效的读写文件的方式。Path类(可以当成File类的升级版)Paths类, Files类。

网络编程两个问题:如何定位主机以及主机上的应用?(IP和端口)如何进行可靠高效的数据传输?(网络通信协议)

IP区分主机,端口号区分应用

网络通信协议:OSI参考模型(理想7层,无法落地)TCP/IP参考模型(4层,应用层、传输层、网络层、数据链路层,实际实现的网络通信协议)

IPv4、IPv6、公网IP、私有IP。IP(不容易记忆)与域名(容易记忆,通过DNS服务器解析)

本地回路地址:127.0.0.1——-localhost

端口号和进程挂钩(程序/应用),同主机端口不能冲突。

在Java中ip和端口被封装在Socket类里面。

TCP和UDP是两个传输层协议,TCP建立连接三次握手,断开连接四次挥手,是可靠的

UDP不用建立连接,不可靠连接,效率比TCP快,e.g.直播

java开发中可以使用Socket做客户端,ServerSocket做服务器。

read是阻塞式方法,客户端可以调用socket.shutdown()方法通知服务器以及发送完数据了,不用再等了。

UDP的话用DatagramSocket和DatagramPacket类就行了。

URL 协议+主机名+端口+路径+参数 URL类 HttpURLConnection类

Java反射

反射是动态语言的关键,允许程序在执行期间取得类的任何内部信息。甚至是私有的结构都可以。java实际上是静态语言,有了反射,使java称为准动态语言。

反射机制和封装性的矛盾。实际上不矛盾,封装是设计上的思想,私有实际是内部使用,不推荐外部使用。

通过直接new和反射的方式都可以调用公共结构,应用场景各别是?

编译的时候无法确定要创建哪一个对象,可以用反射。WEB应用中很常见,因为用户的请求总是动态的,而服务器早就在运行态了。

对Class类的理解:类的加载过程,javac后会生成多个.class字节码文件,java.exe会对某一个类进行解释执行,将某个字节码文件加载到内存中。次过程为类的加载,加载到内存中的类称为运行时类,是Class类的一个实例。加载到内存中的运行时类,会缓冲一定时间,在此时间内,可以通过不同的方式获取此运行时类。

获取Class的实例的方式。方式三最常用,方式1写死了,方式2逻辑不对,先有对象

        //调用运行时类的属性
        Class clazz1 = Person.class;
        //通过运行时类的对象的getClass方法
        Person p = new Person("Amy", 20);
        Class clazz2 = p.getClass();
        //调用Class的静态方法
        Class class3 = Class.forName("java.lang.String");
        //使用类的加载器 Test是当前类
        ClassLoader classLoader = Test.class.getClassLoader();
        Class class4 = classLoader.loadClass("java.lang.String");

Class的实例可以是那些结构,类、接口、注解、数组、基本数据类型、void、枚举

如果程序主动使用某个类,如果该类还未被加载到内存中,则系统会通过如下三个步骤对内进行初始化。Load、Link、Initialize。

可以用ClassLoder系统类加载器加载配置文件,和Property的文件流加载方式的功能一样,默认路径在工程下的src目录。

Class的方法,newInstance()调用空参数构造函数(有权限 public)创建对象。

通常在javabean中要求提供一个public的空参构造器,便于通过反射,创建运行时的类,同时便于子类继承时,子类调用super()。

运行时类的属性结构:

getFields():获取当前类和父类中声明为public的属性

getDeclaredFields(): 多去当前类中声明的所有属性

getMethods(): 获取当前运行时类和父类中声明的所有public方法

getDeclaredMethods():获取当前类中声明所有方法

获取方法声明的注解(框架中很常用): method.getAnnotations()

还可以获得运行时类的带有泛型的父类的泛型,在DAO有用到

class StudenDao extends Dao<Student>{}

获得运行时类的注解 clazz.getAnnotations() 注解应该是RUNTIME

获取运行时类实现的接口 clazz.getInterfaces() 在动态代理中可以用。

通过反射操作实例的属性:field.set(对象,name)

Class clazz = Person.class;
Person p = new Person();
Field field = clazz.getDeclaredField("name");
field.setAccessible(true);
name.set(p, "Tome");

通过反射调用实例的方法:field.set(对象,name)

Class clazz = Person.class;
Person p = new Person();
Method show = clazz.getDeclaredMethod("show");
show.setAccessible(true);
show.invoke(p);

创建类的对象的方式:

  • new + 构造器
  • XXX XXXs XXXFactory XXXBuilder中的静态方法
  • 反射

动态代理

静态代理:代理类和被代理费都要实现同一套的接口,所有的功能都由代理类来完成,当代理内完成不了的时候就用被代理类的方法。如房屋中介和租房子的人,他们时都要实现找房子的这个接口,而房屋中介就是代理类,租房子的人就是被代理类。又比如明星和经纪人的关系,他们都要实现明星这个结果,你的明星所有的事物都是由机器人来完成的,当明天要上课的时候,直接就调用明星的唱歌方法。

静态的意思就是,房屋中介和租房子的人在编译之前就应该写好两个类的代理关系,明星和经纪人也是一样的,如果一个工程上的代理的代理对的关系比较多,那么工程下的类的数目就会变得非常多。

下面这个动态代码挺有意思的


import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;

public class ProxyTest {
    public static void main(String[] args) {
        SuperMan superMan = new SuperMan();
        Human proxy = (Human) ProxyFactory.getProxyInstance(superMan);
        proxy.eat("beef");
        System.out.println(proxy.getBelief());
    }
}

interface Human{
    String getBelief();
    void eat(String food);
}

class SuperMan implements Human{

    @Override
    public String getBelief() {
        return "help others";
    }

    @Override
    public void eat(String food) {
        System.out.println("eat " + food);
    }
}

class ProxyFactory{
    public static Object getProxyInstance(Object obj) {
        MyInvocationHandler myInvocationHandler = new MyInvocationHandler();
        myInvocationHandler.bind(obj);
        return Proxy.newProxyInstance(obj.getClass().getClassLoader(), obj.getClass().getInterfaces(),myInvocationHandler);
    }
}

class MyInvocationHandler implements InvocationHandler{
    private Object obj;
    public void bind(Object obj) {
        this.obj = obj;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("代理中");
        return method.invoke(obj, args);
    }
}

输出:

代理中
eat beef
代理中
help others

动态代理和AOP(Aspect Orient Programming, 面向切片编程)

上面代码中的invoke方法的System.out.println(“代理中”);可以简单理解为一个切片。

Java 基础复习

https://www.bilibili.com/video/BV1Qb411g7cz?from=search&seid=7373469111232659208 参考的视频,整理出有用的一些点。

三种注释方式

变量的类型 基本数据类型 引用数据类型(数组、类、接口)

数组是数组引用类型的,操作数组的类是Arrays,里面实现了很多有用的方法

数组的静态初始化和动态初始化 new int[10]; / new int [] {1,2,3};

二维动态初始化必须指定第一维度大小 new int [10][];

jvm 中创建数组基本的堆栈结构变化

数组创建默认初始值 0/ false/ null

自动类型提升,强制类型转换

位运算中左移<< 右移>>(正数补0负数补1)是乘二除以二对关系(除二下取整数) 无符号右移>>>都补0

用异或运算实现两个数交换的骚操作,异或运算(或位运算)的一些性质对算法题有点帮助,如hashmap 里面hash值存入那个位置用的是(length-1)加&为运算,而length始终是2的幂。

局部变量在栈区,new 出来的东西在堆区

… 表示可变个数的形参, 接受0,1,2,…个参数,实际就是当做数组来处理。也可以直接传一个数组进去。 public void accept(String … agrs) {}

赋值的值传递,区别基本数据类型的传值和引用数据类型传地址

引用数据类型中的string字符串类型是比较特殊,由双引号表示的一个字符串,在内存中是存在一个常量池中,底层应该是用差数组来实现的,然后string在账中的变量存储的实际上就是一个地址值,之所以叫常量池,就是因为是不允许更改的,所以你新建一个string类型的字符串,实际上就是在常量池中又创建了一个字符串。所以字符串作为函数的形参的时候会和其他引用类型的变量体现出不一样的特性。但是作为参数的时候仍然符合直传递的一个特性。

封装性,private私有化不对外界暴露的成员变量、方法、初始化方法(e.g.单例模式)

private (类内可用)、缺省(同一个包可用)、protected(不同包的子类可用)、public 四种权限

可以用来修饰 属性、方法、构造器和内部类,修饰类(不包括内部类)只能用public和缺省。

类的属性初始化顺序

  • 默认初始化
  • 显式初始化 / 代码块(谁写在前先执行谁)
  • 构造器初始化(默认构造器的权限同类的权限)

this表示当前对象,可以修饰或者调用成员变量,属性以及构造器

this(形参列表),不能调用自己,并且必须在构造器的首行调用

package 表示类或接口所属的包,包名的命名规则和标识符相同,每.表示一层dir,同包名不能命名同名的类或者接口。import导入包名+类名,*导入包下的所有类。

java.lang包下的类可以不import,同包下的调用不用写import。异包同类只能用全类名的方式调用。import static java.lang.Math.*; import + static 调用类中的静态结构(属性或者方法)这个不常用。

继承可以避免冗余代码,易于功能扩展,是多态的基础。java中只允许单继承和多层继承。java.lang.Object是所有类的直接或者间接父类。子类可以重写覆盖父类方法

区别方法的重载和重写

重写时函数名参数列表都要相同,权限修饰符不小于父类被重写方法,父类private方法不可以被重写。返回值类型是void和基本数据类型是,重写方法也一致,如果是引用数据类型A,则重写方法的返回值可以是A或者A的子类,父类方法的异常也一样,重写方法抛出的异常也是一样或者子类。

super和this有点类似,可以修饰类的属性、方法和构造器。可以在子类的构造函数的第一行调用super(形参类表)的方式调用父类的构造器,和this()只能二选一。不写就会有默认的super(),子类不显示写构造方法就会自动调用父类的空参数构造器。

一个类如果有n个构造器,最多n-1的首行是this,至少一行是super。默认不写就是super。

子类的实例化过程,子类一定会直接或者间接的调用父类的构造器(n-1与1的关系),父类进而调用祖父类的,直到object。所以子类对象会继承所有父类的属性和方法。

多态,父类引用可以指向子类对象,父类引用只可以调用父类的方法,如果子类重写了该方法,则调用子类重写的。适用于方法,不适用于同名属性。

多态体现在执行的时候,属于一种动态绑定,是编译时期无法进行确定的。重载属于静态绑定,编译时期就可以确定,重写则无法在编译时期确定,解释运行时才可以确定,属于晚绑定。

instanceof关键字的使用,避免向下转型的时候出现异常

Object是所有类的直接或者间接父类,其中定义的属性(没有定义属性)和方法具有通用性

== 与 equals()的区别

==是一种运算符号

如果两边是基本数据类型,比较两边数值是否相同,int可以和double,char可以和int进行比较,除了布尔类型不能比较。

如果两边是应用类型的变量,则比较地址值是否相同,即是否是同一个对象。

equals是一种方法,不能使在基本数据类型上,在Objejct中类的定义是return(this == obj); 和==没有区别。

但是某个类重写了equals方法,则根据多态的动态绑定,执行的语句是重写的函数体。注意字符串和常量池的问题。equals中用getclass 比较会更严格 和 instance of 会存在漏洞(导致不同类对象,存在继承关系,返回的结果是true)。

to String 方法在object中默认返回类名和哈希值,子类可以重写,在print的时候被调用

基本数据类型和包装类,六种是number子类,自动装箱和拆箱

自动装箱与integer 缓存 -128-127

static关键字,静态变量随类加载,在JVM的方法区中的静态域里面放着

静态方法,随类加载。静态只能调用静态,非静态方法内部随便调用。

单例模式要求,私有化成员函数,唯一实例为静态,getInstance函数对外暴露,也为静态方法,分为懒汉式(类加载快但需要同步处理)和饿汉式(类加载慢但线程安全)两种方式。

main方法是程序入口,是一个静态方法,args参数接受的实际是命令行参数。

代码块(初始化块),不常用,就是一个大括号包裹的代码块,分静态和非静态。静态代码块随着类的加载而执行 (可存在多个,依声明顺序执行) 。非静态代码块随着对象的创建而执行,因此可以实现初始化功能。

类的属性初始化顺序:默认初始化、(显式初始化、 代码块(谁写在前面先执行谁))、构造函数

类的加载顺序,先加载父类(静态代码快)再加载子类(静态代码块),然后new 对象时先调用父类的非静态代码块和构造方法,再是子类的。

final关键字,可以修饰类,方法和变量。

修饰类则此类不能被其他类继承,不能有子类了。(e.g. String System StringBuffer类)

修饰方法则不能被重写,如getClass方法。

修饰属性就变成常量了,不能再修改。如果是属性只能用显式初始化/代码块/构造器中初始化

修饰局部变量,尤其是修饰形参时,不能再修改

static fianl 修饰属性,表示一个全局常量。

abstract 可以修饰类和方法。

abstract修饰类的时候,该类不能实例化,该类的非抽象子类可以实例化。

abstract修饰方法,e.g. public abstract void test(); 有抽象方法的类一定是抽象类。抽象类不一定有抽象方法。

若子类重写了父类的所有的抽象方法才可以实例化,否则子类也是抽象类。

abstract 不能和static、private 和 final共用。

抽象类的匿名子类对象

Person p = new Person(){
    @override
    public void eat(){
        System.out.println("吃饱饱");
    }
};

模版设计模式是抽象类的一种应用场景,实际中很多地方用到。

接口interface是和类class并列的一种结构,克服了类只能单继承的缺点,一个类可以实现多个接口。接口是一种规范,是多态的体现。

如果说类的继承是 is a 的关系, 实现接口更像 has a / can do 的关系,即具有某种特性或者功能。

interface中只能定义public final static 常量 和public abstract 抽象方法,不能有构造方法(JDK7 及之前)。

java类通过implement关键字取实现某个接口,该类需要重写interface中所有的抽象方法,否则该类退化为一个抽象类。接口之间可以多继承。应用场景e.g.JDBC面向接口编程。

接口的匿名实现对象和抽象类的匿名子类的书写形式差不多。

抽象类和接口的区别?…抽象类有构造器,接口没有。单继承与多实现。

接口与代理模式和工厂模式

一个类继承的类和实现的接口中有同名属性,类中调用要明确指出调用哪一个,如super. x 或者A. x

接口在JDK8中还可以有静态方法和默认方法

静态方法只能通过接口.静态方法名调用,接口实现类的对象无法调用,内部也访问不到,有点像把接口弄成工具类的意思。

默认方法就是一个普通的方法, 只可以通过实现类的对象进行调用。如果子类重写了,则调用重写的方法(多态)

interface Test{
    public final static int x = 0;
    public abstract void test();
    public static void test1(){}
    public default void test2(){}
}

如果父类和接口的默认方法出现同名,而子类没有重写,则优先调用父类的同名方法,类优先原则

如果两个接口有同名的默认方法,一个类实现这两个接口,并且没有重写,则调用该方法会报错,因为不知道调用哪个。如果非要调用:接口名.super.方法名()。

这里的知识点有点琐碎,看看得了。

内部类分为:成员内部类(静态、非静态),代码块内部类,局部内部类

以成员内部类为例,类内可以定义属性方法构造器等, 可以用final修饰,表示类不能被继承 ,abstract修饰表示不能实例化。

同时作为一个成员,可以调用外部来的一些属性和方法,可以被权限修饰符修饰

使用内部类使用频率很低,稍作了解。

局部内部类中调用局部变量时,局部变量应该声明成final,在安卓开发中比较常见。

Error不能显式处理,JVM内部出错,如栈溢出(无限递归),OOM(堆溢出)等

Exception分为编译时异常和运行时异常。常见运行时如角标越界,空指针,除零异常,类转换异常等。

两种处理方式,try-catch-finally (finally可选)和 throws。catch中的异常声明要按照先子后夫的顺序,否则unreachable。e.getMessage() e.printStacktrace()两个常用方法。

finally中的语句是一定会被执行的代码,即使catch里面又有异常或者代码在之前return了。fianlly里面有return会return final 里面的值。一般在finally写一些关闭资源的操作。

通常值处理编译时异常,否则无法通过编译,出现运行时异常的话,就是代码有问题,需要debug该代码了。

throws 是向上级抛异常,写在函数的参数列表后面。

子类重写父类方法是抛出的异常不能大于父类抛出的异常。

几个具有顺序依赖的方法要执行,而各个方法都可能抛出异常,这是各个方法不能各自用trycatch,而要throws,然后整体进行trycatch处理。

手动抛出异常关键字 throw new Exception(“msg”); 也可以自定义异常类等。

华为2020.5.13 实习笔试

第一题 给定两个年月日,第一个日期给了星期几,推断第二个日期是星期几。

思路:将日期转化为公元0000年起的绝对天数,注意闰年的判断等。然后再相减两个日期,在做一些mod7运算和负数处理就可以了。

第二题 给定一组站台和路灯的坐标,路灯可以调整亮度且所有路灯的亮度一致,所有站台被照亮之后的最小亮度值。

思路:将路灯的坐标进行一下排序,然后便利站台列表,找出和站台距离最近的那个路灯的距离,并且求所有站台最近路灯距离的最大值,作为最终的最小亮度值。可能涉及二分查找等。

第三题:有特定数量的书和特定数量的读者,每个读者都有喜欢的数的列表,若要满足所有读者的需求,书本数量的最小值是多少。

思路:可以将问题转化为二部图进行求解。

LeetCode 50 pow(x,n) 与 java中的数组越界问题

这题参考了leetcode官方题解中的迭代法思路,主要是结合了二进制位运算的优势以及结合二进制表示数的特点进行求解。

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        long N = n;
        boolean isPos = N > 0 ? true : false;
        N = Math.abs(N);
        double res = 1;
        double tmp = x;
        for(int i = 0; i < 32; i ++) {
            long addOrNot = N & 1;
            if (addOrNot == 1) res *= tmp;
            tmp *= tmp;
            N >>= 1;    
       }
       return isPos ? res : 1.0 / res;
    }

解体的时候需要注意一个取绝对值的时候的越界问题,因为n如果取了最小值,即32位的,不管取绝对值也好,前面添加符号也好,都是原来的最小值,因此会对逻辑产生影响。因此采用long类型的变量来避免额外的错误。

        int i = Integer.MIN_VALUE;
        System.out.println(i);
        System.out.println(-i);
        System.out.println(Math.abs(i));

对应输出结果为

leetcode 39 & 40 组合总数

回溯法解决

两道题的思路都是类似的,用回溯来解决问题。

39题由于数值数字没有重复的,并且每个数字可以用零到无数次,所以是一个比较简单的回溯。

40题的数字是有出现重复的,并且每个数字只可以用一次或者不用, ,所以需要先对待用的数字进行排序, 然后再在loop循环里面,排除重复的情况。

39题代码

class Solution:
    
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        def backtrace(index, tmp, target):
            if target <= 0:
                if target == 0:
                    self.res.append(tmp.copy())
            else:
                for i in range(index, len(candidates)):
                    tmp.append(candidates[i])
                    backtrace(i, tmp, target - candidates[i])
                    tmp.pop()
        backtrace(0, [], target)
        return self.res

40题代码

class Solution(object):
    def combinationSum2(self, candidates, target):
        self.res = []
        candidates.sort()
        def backtrace(index, tmp, target):
            if target == 0:
                self.res.append(tmp[:])
            elif target > 0:
                for i in range(index, len(candidates)):
                    if i > index and candidates[i] == candidates[i-1]: continue
                    tmp.append(candidates[i])
                    backtrace(i + 1, tmp, target - candidates[i])
                    tmp.pop()
        
        backtrace(0, [], target)
        return self.res

参考链接:https://www.bilibili.com/video/BV1V4411h7dU/

编程题:带障碍的机器人的最短路径

题目:输入为一个正数n以及一个block数组表示障碍所在的坐标x,y,机器人从左上角0,0开始,每一步只能走上下左右的位置,并且每走一步就会放block数组里面的一个障碍,如果机器人已经经过这个位置障碍就不放置,没有经过这个位置block就放置,直到block放置完成为止,如果机器人能够到达右下角就返回机器人所经过格子的最少个数,否则返回-1。

很明显,这道题就是要使用,bfs广度优先搜索,问题 就是在block数组如何限制下一步选择? 选用bfs带有step的函数模板,然后在每一个step,将status数组里面的block所在的位置设为无法到达,那么问题就解决了。

import java.util.ArrayList;
import java.util.LinkedList;

class Position{
    public int x;
    public int y;
    public Position(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Test9 {
    public int solution() {
        int n = 5;
        int [][] block = {{0,1}, {1,1}, {2,1}, {3,1}, {4,3}, {3,3}};
        int blockCount = block.length;
        int [][] status = new int[n][n];
        if (n == 1) return 1;

        LinkedList<Position> q = new LinkedList<Position>();
        int step = 0;
        int x = 0, y = 0;
        status[x][y] = 1;
        q.add(new Position(x, y));

        while (!q.isEmpty()) {
            int roundCount = q.size();
            for (int i = 0; i < roundCount; i++) {
                Position cur = q.poll();
                if (step < blockCount && status[block[step][0]][block[step][1]] == 0)
                    status[block[step][0]][block[step][1]] = 2;
                if(cur.x == n - 1 && cur.y == n - 1) return step + 1;
                for (Position p: getNextPosition(cur, status, n)){
                    status[p.x][p.y] = 1;
                    q.add(p);
                }
            }
            step ++;
        }
        return -1;
    }
    
    public ArrayList<Position> getNextPosition(Position cur, int[][] status, int n) {
        ArrayList<Position> al = new ArrayList<>();
        int x = cur.x, y = cur.y;
        if (x + 1 < n &&  status[x + 1][y] == 0) al.add(new Position(x + 1, y));
        if (y + 1 < n &&  status[x][y + 1] == 0) al.add(new Position(x, y + 1));
        if (x - 1 >= 0 &&  status[x - 1][y] == 0) al.add(new Position(x - 1, y));
        if (y - 1 >= 0 &&  status[x][y - 1] == 0) al.add(new Position(x, y - 1));
        return al;
    }

    public void printStatus(int [][] status) {
        for (int i = 0; i < status.length; i++) {
            for (int j = 0; j < status[0].length; j++) {
                System.out.print(status[i][j] + " ");
            }
            System.out.println();
        }
    }
}

下面为测试用例的调试结果,更加直观,1表示bfs访问到的节点,2表示每一个时间步放置的障碍。

KMP 算法

首先贴出本人写的KMP算法,本人习惯next数组的第一位存的是-1,下面是代码:

def KMP(txt, pat):
    if pat == "": return 0
    def get_next_arr(pat):
        next_arr, j, k =[-1], 0, -1
        while j < len(pat) - 1:
            if k == -1 or pat[j] == pat[k]:
                k, j = k + 1, j + 1
                next_arr.append(k)
            else:
                k = next_arr[k]
        return next_arr

    next_arr = get_next_arr(pat)

    i, j = 0, 0
    while i < len(txt) and j < len(pat):
        if j == -1 or txt[i] == pat[j]:
            i, j = i + 1, j + 1
        else:
            j = next_arr[j]
    if j == len(pat):
        return i - j
    return -1

KMP代码关键有两个部分

首先是求解next数组,next数组记录的内容是pat中字串的最长相同前后缀的长度,这个数据需要先求出来,方便后续的字符串匹配处理。next数组求解过程中的k=next[k]这个步骤不太好理解,详细可以参考文章,或者视频

第二点就是在匹配主串的过程,其中需要借助next数组进行巧妙的指针变化,主串的指针可以实现不回退。 KMP算法的时间复杂度是O(n+m)

彻底理解原码、反码和补码

本科时从计算机组成原理这门课程上学习计算机的编码方式,原码反码和补码,始终是很混乱,也可以说学了就忘忘了再看看了又忘,。从网上的一些博客也好,也很难找到一种特别具象化形象的理解方式,因此本人制作了一个较为具象化的视频来讲解原码反码和补码的区别以及计算机为什么最终采用补码作为编码方式。视频如下:

https://www.bilibili.com/video/BV1Yk4y1r7D4/