1, Overview of classes and interfaces

Advantages and functions of Java collection framework

• Using a mature collection framework helps us write efficient and stable code conveniently and quickly
• Learning the data structure knowledge behind it will help us understand the advantages, disadvantages and usage scenarios of each collection

2, Collection interface

1. Collection common methods

• Put elements into the collection and return the number of elements in the collection

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        System.out.println(collection.size()); // 2

        // Simple basic types cannot be placed in angle brackets. They must be class types
        Collection<Integer> collection1 = new ArrayList<>();
        collection1.add(10);
    }
}

• Delete all elements in the collection and judge whether there are no elements in the collection

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        System.out.println(collection); // [hello, world]
        collection.clear();
        System.out.println(collection); // []

        System.out.println(collection.isEmpty()); // true
    }
}

• Returns an array containing all the elements in the collection

Casting as a whole is not recommended

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        Object[] objects = collection.toArray();
        System.out.println(Arrays.toString(objects)); // [hello, world]
    }
}

• If the element e appears in the collection, delete one of them

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        collection.remove("world");
        System.out.println(collection); // [hello]
    }
}

2. Map interface

Method signature	explain
V get(Object k)	Find the corresponding v according to the specified k
V getOrDefault(Object k, V defaultValue)	Find the corresponding v according to the specified k, and replace it with the default value
V put(K key, V value)	Put the specified k-v into the Map
boolean containsKey(Object key)	Determine whether the key is included
boolean containsValue(Object value)	Judge whether value is included
Set<Map.Entry<K, V>> entrySet()	Returns all key value pairs
boolean isEmpty()	Judge whether it is empty
int size()	Returns the number of key value pairs

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("Timely rain", "Song Jiang");
        map.put("Leopard head", "Lin Chong");

        System.out.println(map.isEmpty()); // false
        System.out.println(map.size()); // 2

        String ret = map.get("Timely rain");
        System.out.println(ret); // Song Jiang
        // No default values were found
        System.out.println(map.getOrDefault("monk who doesn't follow the rituals", "lu zhishen")); // lu zhishen

        System.out.println(map.containsKey("Leopard head")); // true
        System.out.println(map.containsValue("Lin Chong")); // true

        // Not in order
        System.out.println(map); // {leopard head = Lin Chong, timely rain = Song Jiang}

        Set<Map.Entry<String, String>> entrySet = map.entrySet(); // Assemble k v as a whole

        for (Map.Entry<String, String> entry : entrySet) {
            System.out.println("key: "+entry.getKey()+" value:"+entry.getValue());
        }
    }
}

3, Preliminary knowledge - Generic

Class myarraylist < E > represents that this class is a generic class. At this time, this e is just a placeholder

public class Test {
    public static void main(String[] args) {
        // Parameterize the type
        MyArrayList<String> myArrayList1 = new MyArrayList<>();
        MyArrayList<Integer> myArrayList2 = new MyArrayList<>();
        MyArrayList<Boolean> myArrayList3 = new MyArrayList<>();
    }

Meaning of generics:
1. Automatically check the type
2. Automatic forced class conversion of type

class MyArrayList<E> {
    private E[] elem;
    private int usedSize;
    public MyArrayList() {
        this.elem = (E[])new Object[10];
    }
    public void add(E val) {
        this.elem[usedSize] = val;
        usedSize++;
    }
    public E get(int pos) {
        return this.elem[pos];
    }
}

public class Test {
    public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();
        myArrayList.add("ABC");
        myArrayList.add("bit");
        String ret = myArrayList.get(1);
        System.out.println(ret); // bit

        MyArrayList<Integer> myArrayList1 = new MyArrayList<>();
        myArrayList1.add(11);
        myArrayList1.add(22);
        int ret2 = myArrayList1.get(1);
        System.out.println(ret2); // 22
    }
}

• The content in angle brackets in a generic type does not participate in the composition of types

Thoughts on Object [] forced type conversion

		// Premise: downward conversion of Object array
		String[] strings = new String[10];
        Object o1 = new String[10];
        Object[] o2 = new String[10];

JAVA improves six: generics

How are generics compiled?

Generics are a mechanism at compile time, the erasure mechanism (- > object)

Creating a Generic Array in Java
Considerations when using generic arrays:
An important difference between arrays and generics is how they enforce type checking. Specifically, arrays store and check type information at run time. However, generics check for type errors at compile time and have no type information at run time.

4, Preliminary knowledge - wrapper class

Basic data type	Packaging
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
boolean	Boolean

public class TestDemo {
    public static void main(String[] args) {
        String str = "123";
        int ret = Integer.valueOf(str);
        System.out.println(ret+1); // 124
    }
}

Boxing and unboxing

public class TestDemo {
    public static void main(String[] args) {
        Integer a = 123; //Packing [implicit]
        int b = a; //Unpacking [implicit]
        System.out.println(a+" " + b); // 123 123

        System.out.println("=============");

        Integer a2 = Integer.valueOf(123); //Display ground packing
        Integer a3 = new Integer(123); // Display ground packing

        int b2 = a2.intValue(); // Display unpacking
        double d = a2.doubleValue(); // Display unpacking
        int i = 10; // Display initialization
    }
}

One interview question:

public class TestDemo {
    public static void main(String[] args) {
        Integer a = 128;
        Integer b = 128;
        System.out.println(a == b); // false
    }
}

5, List

public class Test {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(20);

        ArrayList<String> list2 = new ArrayList<>();
    }
}

1. ArrayList implements the RandomAccess interface, indicating that ArrayList supports random access
2. ArrayList implements the Cloneable interface, which indicates that ArrayList can clone
3. ArrayList implements the Serializable interface, indicating that ArrayList supports serialization
4. Unlike vector, ArrayList is not thread safe and can be used in a single thread. Vector or CopyOnWriteArrayList can be selected in multiple threads
5. The bottom layer of ArrayList is a continuous space and can be dynamically expanded. It is a dynamic type sequential table

6, ArrayList use

1. Construction of ArrayList

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("hello");
        list.add("bit");
        list.add("haha");
        System.out.println(list);

        // Initialize list3 with another ArrayList
        ArrayList<String> list3 = new ArrayList<>(list);
    }
}

2. Traversal of ArrayList

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("hello");
        list2.add("bit");
        list2.add("haha");
        // ToString() overridden
        System.out.println(list2);
        System.out.println("================");
        for(int i = 0; i < list2.size(); i++) {
            System.out.print(list2.get(i)+" ");
        }
        System.out.println();
        System.out.println("==================");
        for (String s : list2) {
            System.out.print(s+" ");
        }
        System.out.println();
        System.out.println("========Iterator printing==========");
        Iterator<String> it = list2.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }

        System.out.println();
        System.out.println("========iterator  List Related printing==========");
        ListIterator<String> it2 = list2.listIterator();
        // Iterator<String> it2 = list2.listIterator();
        while (it2.hasNext()) {
            System.out.print(it2.next()+" ");
        }
    }
}

Difference between Iterator and ListIterator

• remove

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("hello");
        list2.add("bit");
        list2.add("haha");

        Iterator<String> it = list2.iterator();
        while (it.hasNext()) {
            String ret = it.next();
            if(ret.equals("hello")) {
                it.remove(); // You need to iterate out the elements in the collection using the next method before you can call the remove method
            }else {
                System.out.print(ret + " ");
            }
        }

        ListIterator<String> it2 = list2.listIterator();
        while (it2.hasNext()) {
            String ret = it2.next();
            if(ret.equals("hello")) {
                it2.remove(); // You need to iterate out the elements in the collection using the next method before you can call the remove method
            }else {
                System.out.print(ret + " ");
            }
        }
    }
}

• add
  Iterator does not have an add method

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        // CopyOnWriteArrayList<String> list2 = new CopyOnWriteArrayList<>(); //  Thread safe
        list2.add("hello");
        list2.add("bit");
        list2.add("haha");

        ListIterator<String> it2 = list2.listIterator();
        while (it2.hasNext()) {
            String ret = it2.next();
            if(ret.equals("bit")) {
                it2.add("gaobo"); // Next
            }else {
                System.out.print(ret + " ");
            }
        }
        System.out.println("=================");
        System.out.println(list2);
        // hello haha =================
        // [hello, bit, gaobo, haha]
    }
}

3. ArrayList common operations

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        // The add method is placed at the last position of the array by default
        System.out.println(list2); // [a, b, c]
        
        list2.add(0, "hello");
        System.out.println(list2); // [hello, a, b, c]

        ArrayList<String> list3 = new ArrayList<>();
        list3.add("I'm testing List1");
        list3.add("I'm testing List2");
        list3.add("I'm testing List3");
        list2.addAll(list3); // [hello, a, b, c, I'm test List1, I'm test List2, I'm test List3]
        System.out.println(list2);
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        String ret = list2.remove(0);
        System.out.println(ret); // a
        System.out.println(list2); // [b, c]

		boolean flag = list2.remove("c");
        System.out.println(flag); // true
        System.out.println(list2); // [b]
    }
}

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        String ret = list2.get(0);
        System.out.println(ret); // a
        System.out.println(list2); // [a, b, c]

        String ret2 = list2.set(0, "p");
        System.out.println("The original string is:"+ret2); // The original string is: a
        System.out.println(list2); // [p, b, c]

        // Determine whether to include "p"
        System.out.println(list2.contains("p")); // true

        // Find subscript
        System.out.println(list2.indexOf("c")); // 2

        System.out.println(list2.lastIndexOf("c")); // 2

        // empty
        list2.clear();
        System.out.println(list2); // []
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        list2.add("f");
        list2.add("g");
        List<String> sub = list2.subList(1, 3);
        System.out.println(sub); // [b, c]

        sub.set(0, "bit");
        // The starting position of the intercepted [b, c] is given to sub
        System.out.println(sub); // [bit, c]
        System.out.println(list2); // [a, bit, c, f, g]
    }
}

4. Capacity expansion mechanism of ArrayList

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>(); // What is the initial size? The answer is 0
        list1.add("bit"); // When storing data elements for the first time, the sequence table is allocated a size of 10
        System.out.println(list1);
        ArrayList<String> list2 = new ArrayList<>(13); //The initial size is the specified 13
    }

Conclusion:

• If the ArrayList calls the construction method without parameters, the size of the sequence table is 0. The first time you add, the whole sequence table becomes 10
  When the 10 are full, start to expand the capacity by 1.5 times
• If the construction method of the given capacity is called, the size of the sequence table is the given capacity. Is it full or expanded by 1,5 times

5. Simulated implementation of ArrayList

import java.util.Arrays;

class MyArrayList<E> {
    private Object[] elementData;//array
    private int usedSize;//Represents the number of valid data

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public MyArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public MyArrayList(int capacity) {
        //Judge the parameters
        if(capacity > 0) {
            this.elementData = new Object[capacity];
        }else if(capacity == 0) {
            this.elementData = new Object[0];
        }else {
            throw new IllegalArgumentException("The initialized capacity cannot be negative");
        }
    }

    /**
     * Adding elements is equivalent to storing them in the last position of the array
     * @param e data
     * @return
     */
    public boolean add(E e) {
        //Determine a real capacity, forecast - > capacity expansion [put the empty and full checklists and capacity expansion together]
        ensureCapacityInternal(usedSize+1);
        elementData[usedSize] = e;
        usedSize++;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        //1. Calculate the required capacity
        int capacity = calculateCapacity(elementData,minCapacity);
        //2. Take the calculated capacity and see if it is full. So is the empty one. Give a clear capacity
        ensureExplicitCapacity(capacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // The if statement cannot be entered, and the array is not full
        if (minCapacity - elementData.length > 0)
            //Expanded capacity
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE =  Integer.MAX_VALUE-8;

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5x capacity expansion
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE> 0)
            //It means that the capacity you want is very large
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //1. Has the elementData array been previously sized
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10,minCapacity);
        }
        //2. After allocation, the value after + 1 is returned
        return minCapacity;
    }

    /**
     * Add an element to the index location
     * @param index
     * @param e
     */
    public void add(int index,E e) {
        //1. Check whether the subscript is legal
        rangeCheckForAdd(index);
        //2. Determine true capacity
        ensureCapacityInternal(usedSize+1);
        //3. Move data
        copy(index,e);
        usedSize++;
    }

    private void copy(int index,E e) {
        for (int i = usedSize-1; i >= index ; i--) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = e;
    }

    private void rangeCheckForAdd(int index) {
        if(index < 0 || index > size()) {
            throw new IndexOutOfBoundsException("index Illegal position, cannot insert!");
        }
    }

    /**
     * Gets the size of the sequential table
     * @return
     */
    public int size() {
        return this.usedSize;
    }

}

public class TestDemo {
    public static void main(String[] args) {

    }
}

7, Practice

1. Custom data type

Bittech has several students (student objects are placed in a List), and each student has a name (String), a class (String) and a double
At the end of an exam, each student got an exam score
Traverse the list set and print out the properties of the student object

class Student {
    private String name;
    private String  classes;
    private double score;
    public Student(String name, String classes, double score) {
        this.name = name;
        this.classes = classes;
        this.score = score;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getClasses() {
        return classes;
    }
    public void setClasses(String classes) {
        this.classes = classes;
    }
    public double getScore() {
        return score;
    }
    public void setScore(double score) {
        this.score = score;
    }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", classes='" + classes + '\'' +
                ", score=" + score +
                '}';
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<Student> students = new ArrayList<>();
        students.add(new Student("bit", "102-1", 10.9));
        students.add(new Student("zhangsan", "102-2", 70.9));
        students.add(new Student("lisi", "102-1", 50.9));
        System.out.println(students);
    }
}

2. Sorting using Collections

public static void main(String[] args) {
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(12);
        integers.add(53);
        integers.add(37);
        Collections.sort(integers); // [12, 37, 53]
        System.out.println(integers);
        Collections.reverse(integers);
        System.out.println(integers); // [53, 37, 12]
    }

3,Welcome to CVTE

Deletes the characters in the second string that appear in the first string
Example:
String str1 = "welcome to CVTE";
String str2 = "come";
Output: wl t CVTE

public class Test {
    // 2
    public static void main2(String[] args) {
        // Using ArrayList
        String str1 = "welcome to CVTE";
        String str2 = "come";
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!str2.contains(ch+"")) {
                list.add(ch);
            }
        }
        // System.out.println(list); // [w, l,  , t,  , C, V, T, E]
        for (char ch : list) {
            System.out.print(ch);
        }
    }

    // 1
    public static void main(String[] args) {
        String str1 = "welcome to CVTE";
        String str2 = "come";
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!str2.contains(ch+"")) {
                sb.append(ch);
            }
        }
        System.out.println(sb);
    }
}

5. Playing cards

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Card {
    private int rank; // number
    private String suit; // Decor

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public String toString() {
        return "[ "+this.suit+":"+this.rank+" ]";
    }
}

public class TestDemo {
    public static final String[] suits = {"♥","♠","♣","♦"};

    public static List<Card> budCard() {
        ArrayList<Card> cards = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                /*String suit = suits[i];
                int rank = j;
                Card card = new Card(rank, suit);
                cards.add(card);*/
                cards.add(new Card(j, suits[i]));
            }
        }
        return cards;
    }

    // exchange
    public static void swap(List<Card> cards, int i, int j) {
        Card tmp = cards.get(i);
        cards.set(i, cards.get(j));
        cards.set(j, tmp);
    }

    // shuffle the cards
    public static void shuffle(List<Card> cards) {
        int size = cards.size();
        for (int i = size - 1; i > 0; i--) {
            Random random = new Random();
            int rand = random.nextInt(i);
            swap(cards, i, rand);
        }
    }

    public static void main(String[] args) {
        List<Card> cards =  budCard();
        System.out.println("Buy cards"+cards);

        shuffle(cards);
        System.out.println("shuffle the cards"+cards);

        System.out.println("Unveiling: 3 people unveil 5 cards each in turn");

        ArrayList<List<Card>> hand = new ArrayList<>();

        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();

        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                Card card = cards.remove(0);
                hand.get(j).add(card);
            }
        }

        System.out.println("Card of the first person:"+hand1);
        System.out.println("The second person's card:"+hand2);
        System.out.println("The third person's card:"+hand3);
        System.out.println("Remaining cards:"+cards);
    }
}

6. Yang Hui triangle

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        // first line
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        ret.add(list1); // At this time, the data in the first row is put into ret
        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1); // Each line starts with 1
            List<Integer> preRow = ret.get(i-1); // previous line
            for (int j = 1; j < i; j++) {
                int num = preRow.get(j) + preRow.get(j-1);
                list.add(num);
            }
            list.add(1); // The ending is 1
            ret.add(list);
        }
        return ret;
    }
}