Java Advanced

Note

The following content is based on Java JDK 8. Changes in higher versions are possible.

Faster Input and Output

Scanner and System.out.print work well initially, but they become inefficient when handling larger inputs. Therefore, we need methods to improve I/O speed.

Using Kattio + StringTokenizer for Input

One of the most common methods is using Kattio.java from Kattis to improve I/O efficiency.¹ This method wraps StringTokenizer and PrintWriter in a class for convenience. When solving problems (if allowed by the contest/organizer), this template can be used directly.

Below is the I/O template that should be included in the code. Since the original Kattio from Kattis includes some less commonly used features, the template below has been adjusted (the original Kattio uses the MIT license).

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // Standard IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // File IO
    public Kattio(String intput, String output) throws IOException {
        super(output);
        r = new BufferedReader(new FileReader(intput));
    }
    // Returns null if no more input
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

The code below briefly demonstrates the usage of Kattio:

class Test {
    public static void main(String[] args) {
        Kattio io = new Kattio();
        // String input
        String str = io.next();
        // int input
        int num = io.nextInt();
        // Output
        io.println("Result");
        // Ensure to close the IO stream to guarantee output is written correctly
        io.close();
    }
}

Using StreamTokenizer for Input

In some cases, using StringTokenizer may cause MLE (Memory Limit Exceeded). In such situations, we need to use StreamTokenizer for input.

import java.io.*;
public class Main {
    // IO code
    public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in), 32768));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static double nextDouble() throws IOException { in.nextToken(); return in.nval; }
    public static float nextFloat() throws IOException { in.nextToken(); return (float)in.nval; }
    public static int nextInt() throws IOException { in.nextToken(); return (int)in.nval; }
    public static String next() throws IOException { in.nextToken(); return in.sval; }
    public static long nextLong() throws Exception { in.nextToken(); return (long)in.nval;}

    // Usage example
    public static void main(String[] args) throws Exception {
        int n = nextInt();
        out.println(n);
        out.close();
    }
}

Analysis and Comparison Between Kattio + StringTokenizer and StreamTokenizer Methods

1. StreamTokenizer uses less memory compared to StringTokenizer. When a Java standard solution MLE, you can try StreamTokenizer. However, StreamTokenizer loses precision and may cause issues when reading certain data.
   • The source code of StreamTokenizer has a Type that determines the type based on input content. If the input is a string starting with a number, like 123oi, it will forcibly treat it as a double type. Thus, reading a String type as a double will throw an exception.
   • StreamTokenizer loses precision when reading numbers larger than 1e14.
2. When using PrintWriter, ensure to close() the output stream at the end of the program or use flush() to clear the buffer when output is needed. Otherwise, content will not be written to the console/file.
3. Kattio inherits from the PrintWriter class, so its objects have the functionality of PrintWriter. Therefore, it can directly call PrintWriter functions for output, while modifying StringTokenizer as its member variable. The second method, Main, uses both StreamTokenizer and PrintWriter as member variables, resulting in slight differences in usage.

In summary, in most cases, StringTokenizer is superior to StreamTokenizer. In extreme MLE situations, you can try StreamTokenizer. However, StreamTokenizer cannot handle data beyond the int range.

BigInteger and Number Theory

BigInteger is a high-precision calculation class provided by Java, which can conveniently solve high-precision problems.

Initialization

Common ways to create BigInteger are as follows:

import java.io.PrintWriter;
import java.math.BigInteger;

class Main {
    static PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] args) {
        BigInteger a = new BigInteger("12345678910");  // Create a BigInteger object from a string in decimal
        out.println(a);  // a's value is 12345678910 
        BigInteger b = new BigInteger("1E", 16);  // Create a BigInteger object from a string in a specified base
        out.println(b);  // b's value is 30 
        out.close();
    }
}

Basic Operations

In the following, this represents the current BigInteger:

Function Name	Function
abs()	Returns the absolute value of this
negate()	Returns the opposite of this
add(BigInteger val)	Returns the sum of this and val
subtract(BigInteger val)	Returns the difference between this and val
multiply(BigInteger val)	Returns the product of this and val
divide(BigInteger val)	Returns the quotient of this divided by val
remainder(BigInteger val)	Returns the remainder of this divided by val
mod(BigInteger val)	Returns the value of this modulo val
pow(int val)	Returns this raised to the power of val
and(BigInteger val)	Returns the bitwise AND of this and val
or(BigInteger val)	Returns the bitwise OR of this and val
not()	Returns the bitwise NOT of this
xor(BigInteger val)	Returns the bitwise XOR of this and val
shiftLeft(int n)	Returns this shifted left by n bits
shiftRight(int n)	Returns this shifted right by n bits
max(BigInteger val)	Returns the larger of this and val
min(BigInteger val)	Returns the smaller of this and val
bitCount()	Returns the number of 1s in the binary representation of this, excluding the sign bit
bitLength()	Returns the length of the binary representation of this, excluding the sign bit
getLowestSetBit()	Returns the position of the rightmost set bit in this
compareTo(BigInteger val)	Compares the values of this and val
toString()	Returns the decimal string representation of this
toString(int radix)	Returns the string representation of this in base radix

Usage examples:

import java.io.PrintWriter;
import java.math.BigInteger;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static BigInteger a, b;

    static void abs() {
        out.println("abs:");
        a = new BigInteger("-123");
        out.println(a.abs());  // Output 123 
        a = new BigInteger("123");
        out.println(a.abs());  // Output 123 
    }

    static void negate() {
        out.println("negate:");
        a = new BigInteger("-123");
        out.println(a.negate());  // Output 123 
        a = new BigInteger("123");
        out.println(a.negate());  // Output -123 
    }

    static void add() {
        out.println("add:");
        a = new BigInteger("123");
        b = new BigInteger("123");
        out.println(a.add(b));  // Output 246 
    }

    static void subtract() {
        out.println("subtract:");
        a = new BigInteger("123");
        b = new BigInteger("123");
        out.println(a.subtract(b));  // Output 0 
    }

    static void multiply() {
        out.println("multiply:");
        a = new BigInteger("12");
        b = new BigInteger("12");
        out.println(a.multiply(b));  // Output 144 
    }

    static void divide() {
        out.println("divide:");
        a = new BigInteger("12");
        b = new BigInteger("11");
        out.println(a.divide(b));  // Output 1 
    }

    static void remainder() {
        out.println("remainder:");
        a = new BigInteger("12");
        b = new BigInteger("10");
        out.println(a.remainder(b));  // Output 2 
        a = new BigInteger("-12");
        b = new BigInteger("10");
        out.println(a.remainder(b));  // Output -2 
    }

    static void mod() {
        out.println("mod:");
        a = new BigInteger("12");
        b = new BigInteger("10");
        out.println(a.mod(b));  // Output 2 
        a = new BigInteger("-12");
        b = new BigInteger("10");
        out.println(a.mod(b));  // Output 8 
    }

    static void pow() {
        out.println("pow:");
        a = new BigInteger("2");
        out.println(a.pow(10));  // Output 1024 
    }

    static void and() {
        out.println("and:");
        a = new BigInteger("3");  // 11 
        b = new BigInteger("5");  // 101 
        out.println(a.and(b));  // Output 1 
    }

    static void or() {
        out.println("or:");
        a = new BigInteger("2");  // 10 
        b = new BigInteger("5");  // 101 
        out.println(a.or(b));  // Output 7 
    }

    static void not() {
        out.println("not:");
        a = new BigInteger("2147483647");  // 01111111 11111111 11111111 11111111 
        out.println(a.not());  // Output -2147483648 Binary: 10000000 00000000 00000000 00000000 
    }

    static void xor() {
        out.println("xor:");
        a = new BigInteger("6");  // 110 
        b = new BigInteger("5");  // 101 
        out.println(a.xor(b));  // 011 Output 3 
    }

    static void shiftLeft() {
        out.println("shiftLeft:");
        a = new BigInteger("1");
        out.println(a.shiftLeft(10));  // Output 1024 
    }

    static void shiftRight() {
        out.println("shiftRight:");
        a = new BigInteger("1024");
        out.println(a.shiftRight(8));  // Output 4 
    }

    static void max() {
        out.println("max:");
        a = new BigInteger("6");
        b = new BigInteger("5");
        out.println(a.max(b));  // Output 6 
    }

    static void min() {
        out.println("min:");
        a = new BigInteger("6");
        b = new BigInteger("5");
        out.println(a.min(b));  // Output 5 
    }

    static void bitCount() {
        out.println("bitCount:");
        a = new BigInteger("6");  // 110 
        out.println(a.bitCount());  // Output 2 
    }

    static void bitLength() {
        out.println("bitLength:");
        a = new BigInteger("6");  // 110 
        out.println(a.bitLength());  // Output 3 
    }

    static void getLowestSetBit() {
        out.println("getLowestSetBit:");
        a = new BigInteger("8");  // 1000 
        out.println(a.getLowestSetBit());  // Output 3 
    }

    static void compareTo() {
        out.println("compareTo:");
        a = new BigInteger("8");
        b = new BigInteger("9");
        out.println(a.compareTo(b));  // Output -1 
        a = new BigInteger("8");
        b = new BigInteger("8");
        out.println(a.compareTo(b));  // Output 0 
        a = new BigInteger("8");
        b = new BigInteger("7");
        out.println(a.compareTo(b));  // Output 1 
    }

    static void toStringTest() {
        out.println("toString:");
        a = new BigInteger("15");
        out.println(a.toString());  // Output 15 
        out.println(a.toString(16));  // Output f 
    }

    public static void main(String[] args) {
        abs();
        negate();
        add();
        subtract();
        multiply();
        divide();
        remainder();
        mod();
        pow();
        and();
        or();
        not();
        xor();
        shiftLeft();
        shiftRight();
        max();
        min();
        bitCount();
        bitLength();
        getLowestSetBit();
        compareTo();
        toStringTest();
        out.close();
    }
}

Mathematical Operations

In the following, this represents the current BigInteger:

Function Name	Function
gcd(BigInteger val)	Returns the greatest common divisor of the absolute values of this and val
isProbablePrime(int val)	Returns a boolean indicating whether this is prime
nextProbablePrime()	Returns the first prime greater than this
modPow(BigInteger b, BigInteger p)	Returns the value of this raised to the power b modulo p
modInverse(BigInteger p)	Returns the multiplicative inverse of this modulo p

Usage examples:

import java.io.PrintWriter;
import java.math.BigInteger;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static BigInteger a, b, p;

    static void gcd() {  // Greatest common divisor 
        a = new BigInteger("120032414321432144212100");
        b = new BigInteger("240231431243123412432140");
        out.println(String.format("gcd(%s,%s)=%s", a.toString(), b.toString(), a.gcd(b).toString()));  // gcd(120032414321432144212100,240231431243123412432140)=20 
    }

    static void isPrime() {  // Determines if the number is prime based on Miller-Rabin; higher parameter increases accuracy and complexity. Accuracy is (1-1/(val*2)) 
        a = new BigInteger("1200324143214321442127");
        out.println("a:" + a.toString());
        out.println(a.isProbablePrime(10) ? "a is prime" : "a is not prime");  // a is not prime 
    }

    static void nextPrime() {  // Finds the next prime after this number 
        a = new BigInteger("1200324143214321442127");
        out.println("a:" + a.toString());
        out.println(String.format("a nextPrime is %s", a.nextProbablePrime().toString()));  // a nextPrime is 1200324143214321442199 
    }

    static void modPow() {  // Fast exponentiation, faster than the normal version with internal mathematical optimizations 
        a = new BigInteger("2");
        b = new BigInteger("10");
        p = new BigInteger("1000");
        out.println(String.format("a:%s b:%s p:%s", a, b, p));
        out.println(String.format("a^b mod p:%s", a.modPow(b, p).toString()));//  24 
    }

    static void modInverse() {  // Modular inverse 
        a = new BigInteger("10");
        b = new BigInteger("3");
        out.println(a.modInverse(b));  // a ^ (p-2) mod p = 1 
    }

    public static void main(String[] args) {
        gcd();
        isPrime();
        nextPrime();
        modPow();
        modInverse();
        out.close();
    }
}

For Miller–Rabin related knowledge, refer to Miller–Rabin primality test.

Primitive Data Types and Wrapper Classes

Introduction

Since primitive types lack object-oriented features, Java provides corresponding wrapper classes for the eight primitive types to allow them to participate in object-oriented development. These are Byte, Double, Float, Integer, Long, Short, Character, and Boolean. The correspondence is as follows:

Primitive Data Type	Wrapper Class
byte	Byte
short	Short
boolean	Boolean
char	Character
int	Integer
long	Long
float	Float
double	Double

Differences

Here, int and Integer are used as examples:

1. Integer is the wrapper class for int, while int is a primitive data type in Java.
2. Integer must be instantiated before use, while int does not.
3. Integer actually corresponds to a reference; when new an Integer, an object is created, while int directly stores data.
4. The default value of Integer is null, and it can accept null and int type data. The default value of int is 0, and it cannot accept null type data.
5. Using == to determine equality between two Integer variables may lead to incorrect results; equals() must be used. For int, == can be used directly.

Boxing and Unboxing

Here, int and Integer are used as examples:

Integer is essentially an object, and int is a primitive type. Direct assignment between the two types is not possible. When conversion is needed, the primitive type should be converted to the wrapper type, which is called boxing. The reverse is called unboxing.

// Primitive type
int value1 = 1;
// Boxing to wrapper type
Integer integer = Integer.valueOf(value1);
// Unboxing to primitive type
int value2 = integer.intValue();

Java 5 introduced automatic boxing and unboxing:

Integer integer = 1;
int value = integer;

Note

Although JDK added automatic boxing and unboxing, please choose the appropriate type when declaring variables because the wrapper type Integer can accept null, while the primitive type int cannot accept null. Therefore, unboxing a wrapper type with a null value will throw an exception. The following code demonstrates this behavior.

Integer integer = Integer.valueOf(null);
integer.intValue();  // Throws java.lang.NumberFormatException

Integer integer = null;
integer.intValue();  // Throws java.lang.NullPointerException

Inheritance

Creating new designs based on existing designs is inheritance in object-oriented programming. In inheritance, new classes are not created out of thin air but are defined based on an existing class. Through inheritance, the new class automatically acquires all members of the base class, including member variables and methods, including members of all access attributes, whether public or private. Obviously, defining new classes through inheritance is much simpler, faster, and more convenient than writing a new class from scratch. Inheritance is an important means of supporting code reuse.

In Java, the keyword for inheritance is extends, and Java only supports single inheritance but can implement multiple interfaces.

In Java, all classes are subclasses of the Object class.

A subclass inherits from a parent class, and all parent class members, including variables and methods, become members of the subclass, except for constructors. Constructors are unique to the parent class because their names are the class names, so parent class constructors do not exist in the subclass. Apart from that, the subclass inherits all members of the parent class.

Each member has different access attributes. The subclass inherits all members of the parent class, but different access attributes cause the subclass to use these members differently: some parent class members directly become part of the subclass's external interface, while others are deeply hidden, even the subclass itself cannot directly access them.

The following table lists the access attributes of parent class members with different access attributes in the subclass:

Parent Member Access Attribute	Meaning in Parent Class	Meaning in Subclass
public	Open to all classes	Open to all classes
protected	Accessible only by other classes in the same package, itself, and subclasses	Accessible only by other classes in the same package, itself, and subclasses
Default (default)	Accessible only by other classes in the same package	If the subclass is in the same package as the parent class, accessible only by other classes in the same package; otherwise, equivalent to private, not accessible
private	Accessible only by itself	Not accessible

Polymorphism

In Java, when assigning an object to a variable, the object's type must match the variable's type. However, due to the concept of inheritance in Java, it can be redefined as a variable can hold its declared type or any subtype of that type.

If a type implements an interface, it can also be called a subtype of that interface.

Object-type variables in Java are polymorphic variables. The term "polymorphism" (literally meaning many forms) refers to a variable being able to hold objects of different types (i.e., its declared type or any subtype).

Polymorphic variables:

1. Java object variables are polymorphic; they can hold more than one type of object.
2. They can hold objects of the declared type or objects of subclasses of the declared type.
3. Upcasting occurs when an object of a subclass is assigned to a variable of a parent class.

Generics

Generics refer to not setting the specific type of properties or method parameters in a class definition, but defining the type when using (or creating an object). Generics are essentially parameterized types, meaning the data type being operated on is specified as a parameter.

Generics provide a compile-time type safety detection mechanism, which allows illegal types to be detected at compile time.

Interfaces

Introduction

An interface in Java is an abstract type, a collection of abstract methods, usually declared with interface. A class implements an interface to inherit the abstract methods of the interface.

An interface is not a class. The way to write an interface is similar to a class, but they are different concepts. A class describes the properties and methods of an object. An interface contains the methods that a class must implement.

Unless the class implementing the interface is abstract, the class must define all methods in the interface.

An interface cannot be instantiated but can be implemented. A class that implements an interface must implement all methods described in the interface; otherwise, it must be declared as an abstract class. Additionally, in Java, an interface type can be used to declare a variable, which can become a null pointer or be bound to an object that implements this interface.

Differences from Classes

1. Interfaces cannot be used to instantiate objects.
2. Interfaces do not have constructors.
3. All methods in an interface must be abstract methods. After Java 8, non-abstract methods can be used in interfaces with the default keyword.
4. Interfaces cannot contain member variables, except for static and final variables.
5. Interfaces are not inherited by classes but are implemented by classes.
6. Interfaces support multiple inheritance; classes do not support multiple inheritance.

Declaration

[visibility] interface InterfaceName [extends other interface names] {
        // Declare variables
        // Abstract methods
}

Implementation

...implements InterfaceName[, other interface names, other interface names..., ...] ...

Lambda Expressions

Introduction

Lambda expressions, also known as closures, are the most important new feature in Java 8.

Lambda expressions allow functions to be passed as parameters to methods (functions as parameters passed into methods).

Using lambda expressions can make code more concise and compact.

Syntax

• Optional type declaration: No need to declare parameter types; the compiler can uniformly infer parameter values.
• Optional parameter parentheses: A single parameter does not require parentheses, but multiple parameters do.
• Optional curly braces: If the body contains a single statement, curly braces are not needed.
• Optional return keyword: If the body has a single expression returning a value, the compiler automatically returns the value; curly braces need to specify that the expression returns a value.

Lambda expressions are declared as follows:

// 1. No parameters, returns 5
() -> 5

// 2. Takes one parameter (numeric type), returns twice its value
x -> 2 * x

// 3. Takes 2 parameters (numbers) and returns their difference
(x, y) -> x – y

// 4. Takes 2 int integers and returns their sum
(int x, int y) -> x + y

// 5. Takes a String object and prints it to the console, returns nothing (looks like returning void)
(String s) -> System.out.print(s)

Taking a custom comparator for sorting a string array by length as an example, lambda expressions can be applied as follows.

import java.util.Arrays;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
        Arrays.sort(plants, (String first, String second) -> (first.length() - second.length()));
        for (String word : plants) {
            out.print(word + " ");
        }
        out.close();
    }
}

You can also use multiple statements in a lambda expression, as in the following example.

import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
        Arrays.sort(plants, (first, second) ->
        {
            // Parameter types not written; can be inferred from context
            int result = first.length() - second.length();
            return result;
        });
        for (String word : plants) {
            out.print(word + " ");
        }
        out.close();
    }
}

Here, -> is a derivation symbol, indicating that the preceding parentheses receive parameters and derive the return value (essentially passing a method).

Functional Interfaces

1. It is an interface that conforms to Java interface definitions.
2. An interface that contains only one abstract method.
3. Since there is only one unimplemented method, lambda expressions can automatically fill it in.

Functional interfaces are used as follows:

Output strings with length a multiple of 2

import java.io.PrintWriter;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
        Test test = s -> {  // Lambda expression as an instance of a functional interface
            if (s.length() % 2 == 0) {
                return true;
            }
            return false;
        };
        for (String word : plants) {
            if (test.check(word)) {
                out.print(word + " ");
            }
        }
        out.close();
    }
}

interface Test {
    public boolean check(String s);
}

Implement addition, subtraction, multiplication, and division

import java.io.PrintWriter;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static double calc(double a, double b, Calculator util) {
        return util.operation(a, b);
    }

    public static void main(String[] args) {
        Calculator util[] = new Calculator[4];  // Define an array of functional interfaces
        util[0] = (a, b) -> a + b;
        util[1] = (a, b) -> a - b;
        util[2] = (a, b) -> a * b;
        util[3] = (a, b) -> a / b;
        double a = 20, b = 15;
        for (Calculator c : util) {
            System.out.println(calc(a, b, c));
        }
        out.close();
    }
}

interface Calculator {
    public double operation(double a, double b);
}

Collection

Collection is an interface in Java implemented by multiple generic container interfaces. Here, Collection refers to data structures that store objects.

In Java, the element type of a Collection must be an object type, not a primitive data type.

The following usage is based on the polymorphic nature in Java, appearing in the form of implementing interfaces.

Common interfaces include List, Queue, Set, and Map.

Container Definition

When defining generic container classes, the data type must be specified at definition time. If the data type is not specified and data is arbitrarily added as Object type, it may compile in Java 8 but with many warning risks.

For example, the following definition is safe; the container only accepts Integer type.

List<Integer> list1 = new LinkedList<>();

The following definition will produce warnings.

List list = new ArrayList<>();
list.add(1);
list.add(true);
list.add(1.01);
list.add(1L);
list.add("I am String");

Therefore, if there is no special requirement, the second behavior is not recommended, as the compiler cannot help check whether the stored data is safe. When retrieving data with list.get(index), the data type cannot be determined (the retrieved data type is Object), and it must be manually cast back to the original type, which may easily cause incorrect casting exceptions.

If the type is specified, such as List<Integer>, the compiler will check the data type being added, allowing only integer data. When declaring collection variables, only wrapper types like List<Integer> or custom Class can be used, not primitive types like List<int>.

List

ArrayList

ArrayList is an array that can dynamically grow as needed, with a default initial length of 10. If the current length is exceeded, it expands by \(\dfrac{3}{2}\).

Initialization

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();  // Create a self-incrementing array named list1 with default initial length (10)
        List<Integer> list2 = new ArrayList<>(30);  // Create a self-incrementing array named list2 with initial length 30
        List<Integer> list3 = new ArrayList<>(list2);  // Create a self-incrementing array named list3, using elements and size from list2 as initial values
    }
}

LinkedList

LinkedList is a doubly linked list.

Initialization

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        List<Integer> list1 = new LinkedList<>();  // Create a doubly linked list named list1 
        List<Integer> list2 = new LinkedList<>(list1);  // Create a doubly linked list named list2, adding all elements from list1 
    }
}

Common Methods

In the following, this represents the current List<Integer>:

Function Name	Function
size()	Returns the length of this
add(Integer val)	Inserts val at the end of this
add(int idx, Integer e)	Inserts element e at position idx in this
get(int idx)	Returns the value at position idx in this, throws an exception if out of bounds
set(int idx, Integer e)	Modifies the value at position idx in this to e

Usage examples and differences:

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static List<Integer> array = new ArrayList<>();
    static List<Integer> linked = new LinkedList<>();

    static void add() {
        array.add(1);  // Time complexity O(1) 
        linked.add(1);  // Time complexity O(1) 
    }

    static void get() {
        array.get(10);  // Time complexity O(1) 
        linked.get(10);  // Time complexity O(11) 
    }

    static void addIdx() {
        array.add(0, 2);  // Worst-case time complexity O(n)
        linked.add(0, 2);  // Worst-case time complexity O(n)
    }

    static void size() {
        array.size();  // Time complexity O(1)
        linked.size();  // Time complexity O(1)
    }

    static void set() {  // This method returns the original value at that position
        array.set(0, 1);  // Time complexity O(1)
        linked.set(0, 1);  // Worst-case time complexity O(n)
    }

}

Traversal

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static List<Integer> array = new ArrayList<>();
    static List<Integer> linked = new LinkedList<>();

    static void function1() {  // Simple traversal
        for (int i = 0; i < array.size(); i++) {
            out.println(array.get(i));  // Traverse self-incrementing array, complexity O(n)
        }
        for (int i = 0; i < linked.size(); i++) {
            out.println(linked.get(i));  // Traverse doubly linked list, complexity O(n^2) because LinkedList's get(i) complexity is O(i)
        }
    }

    static void function2() {  // Enhanced for loop traversal 
        for (int e : array) {
            out.println(e);
        }
        for (int e : linked) {
            out.println(e);  // Complexity O(n) for both 
        }
    }

    static void function3() {  // Iterator traversal 
        Iterator<Integer> iterator1 = array.iterator();
        Iterator<Integer> iterator2 = linked.iterator();
        while (iterator1.hasNext()) {
            out.println(iterator1.next());
        }
        while (iterator2.hasNext()) {
            out.println(iterator2.next());
        }  // Complexity O(n) for both 
    }

}

Note

Do not delete elements from a List during for or foreach traversal; otherwise, an exception will be thrown.

The reason is simple: list.size() changes, but the number of iterations already completed in the loop does not change accordingly. The data originally expected at the next index becomes the data at the current index due to the deletion operation. When the next loop runs, the operation will be on the data originally expected at the next-next index, ultimately causing the operated data to not meet expectations.

Queue

LinkedList

LinkedList can be used to implement a regular queue, with the underlying structure being a linked list simulating a queue.

Initialization

Queue<Integer> q = new LinkedList<>();

LinkedList implements both the List interface and the Deque interface, and Deque inherits from Queue, so LinkedList can implement both List and Queue.

ArrayDeque

ArrayDeque can be used to implement a regular queue, with the underlying structure being an array simulating a queue.

Initialization

Queue<Integer> q = new ArrayDeque<>();

ArrayDeque implements the Deque interface, and Deque inherits from Queue, so ArrayDeque can implement Queue.

Differences Between LinkedList and ArrayDeque in Implementing Queue Interface

1. Data Structure: In terms of data structure, both ArrayDeque and LinkedList implement the Java Deque double-ended queue interface. However, ArrayDeque does not implement the Java List interface, so it does not have behavior based on index positions.
2. Thread Safety: Neither ArrayDeque nor LinkedList consider thread synchronization and do not guarantee thread safety.
3. Underlying Implementation: In terms of underlying implementation, ArrayDeque is based on a dynamic array, while LinkedList is based on a doubly linked list.
4. Traversal Speed: ArrayDeque is a contiguous memory space, and based on the principle of locality, it can better hit CPU cache lines, while LinkedList is discrete memory space, which is not friendly to cache lines.
5. Operation Speed: Both ArrayDeque and LinkedList have \(O(1)\) time complexity for stack and queue behaviors. ArrayDeque's push and enqueue operations may trigger expansion, but from an amortized analysis perspective, it is still \(O(1)\) time complexity.
6. Extra Memory Consumption: ArrayDeque has idle space outside the head and tail pointers of the array, while LinkedList adds predecessor and successor pointers to nodes.

PriorityQueue

PriorityQueue is a priority queue, defaulting to a min-heap.

Initialization

Queue<Integer> q1 = new PriorityQueue<>();  // Min-heap
Queue<Integer> q2 = new PriorityQueue<>((x, y) -> {return y - x;});  // Max-heap

Common Methods

In the following, the queue is defined as Queue<Integer>.

Function Name	Function
size()	Returns the current queue length
add(Integer val)	Inserts val into the queue; if insertion violates capacity limits, throws an exception
offer(Integer val)	Inserts val into the queue; if insertion violates capacity limits, insertion fails but does not throw an exception
isEmpty()	Determines if the queue is empty; returns true if empty
peek()	Returns the head element; returns null if the queue is empty
poll()	Returns and removes the head element; returns null if the queue is empty

Usage examples and differences:

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Queue<Integer> q1 = new LinkedList<>();
    static Queue<Integer> q2 = new PriorityQueue<>();

    static void add() {  // No functional difference between add and offer; difference is whether an exception is thrown 
        q1.add(1);  // Time complexity O(1) 
        q2.add(1);  // Time complexity O(logn) 
    }

    static void isEmpty() {
        q1.isEmpty();  // Time complexity O(1) 
        q2.isEmpty();  // Space complexity O(1) 
    }

    static void size() {
        q1.size();  // Time complexity O(1) 
        q2.size();  // Returns the length of q2 
    }

    static void peek() {
        q1.peek();  // Time complexity O(1) 
        q2.peek();  // Time complexity O(logn) 
    }

    static void poll() {
        q1.poll();  // Time complexity O(1) 
        q2.poll();  // Time complexity O(logn) 
    }
}

Traversal

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Queue<Integer> q1 = new LinkedList<>();
    static Queue<Integer> q2 = new PriorityQueue<>();

    static void test() {
        while (!q1.isEmpty()) {  // Complexity O(n) 
            out.println(q1.poll());
        }
        while (!q2.isEmpty()) {  // Complexity O(nlogn) 
            out.println(q2.poll());
        }
    }

}

Deque

Deque is a double-ended queue in Java, commonly used for queue operations and stack operations.

Main Functions

In the following, the queue is defined as Deque<Integer>.

Function Name	Function
addFirst(Integer val)	Inserts val at the head; if insertion violates capacity limits, throws an exception
offerFirst(Integer val)	Inserts val at the head; if insertion violates capacity limits, insertion fails but does not throw an exception
removeFirst()	Returns and removes the head element; throws an exception if the queue is empty
pollFirst()	Returns and removes the head element; returns null if the queue is empty
peekFirst()	Returns the head element; returns null if the queue is empty
push(Integer val)	Inserts val at the head, equivalent to addFirst
pop()	Returns and removes the head element, equivalent to removeFirst
remove()	Removes the head element, equivalent to removeFirst
poll()	Removes the head element, equivalent to pollFirst
addLast(Integer val)	Inserts val at the tail; if insertion violates capacity limits, throws an exception
offerLast(Integer val)	Inserts val at the tail; if insertion violates capacity limits, insertion fails but does not throw an exception
removeLast()	Returns and removes the tail element; throws an exception if the queue is empty
pollLast()	Returns and removes the tail element; returns null if the queue is empty
peekLast()	Returns the tail element; returns null if the queue is empty
add(Integer val)	Inserts val at the tail, equivalent to addLast
offer(Integer val)	Inserts val at the tail, equivalent to offerLast

Stack Operations

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static Deque<Integer> stack = new ArrayDeque<>();
    static int[] a = {1, 2, 3, 4, 5};

    public static void main(String[] args) {
        for (int v : a) {
            stack.push(v);
        }
        while (!stack.isEmpty()) { //Output 5 4 3 2 1
            System.out.println(stack.pop()); 
        }
    }
}

Double-ended Queue Operations

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static Deque<Integer> deque = new ArrayDeque<>();

    static void insert() {
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addLast(3);
        deque.addLast(4);
    }

    public static void main(String[] args) {
        insert();
        while (!deque.isEmpty()) { //Output 2 1 3 4
            System.out.println(deque.poll());
        }
        insert();
        while (!deque.isEmpty()) { //Output 4 3 1 2
            System.out.println(deque.pollLast());
        }
    }
}

Set

Set is a data structure that keeps elements in a container unique.

HashSet

A Set that inserts elements at random positions.

Initialization

Set<Integer> s1 = new HashSet<>();

LinkedHashSet

A Set that maintains insertion order.

Initialization

Set<Integer> s2 = new LinkedHashSet<>();

TreeSet

A Set that keeps elements in order, default ascending.

Initialization

Set<Integer> s3 = new TreeSet<>();
Set<Integer> s4 = new TreeSet<>((x, y) -> {return y - x;});  // Descending 

More Usage of TreeSet

These methods are newly created and implemented by TreeSet. We cannot call the following methods using the Set interface, so we create them as follows:

TreeSet<Integer> s3 = new TreeSet<>();
TreeSet<Integer> s4 = new TreeSet<>((x, y) -> {return y - x;});  // Descending 

In the following table, this represents the current TreeSet<Integer>.

Function Name	Function
first()	Returns the first element in this; returns null if none
last()	Returns the last element in this; returns null if none
floor(Integer val)	Returns the first element in this less than or equal to val; returns null if none
ceiling(Integer val)	Returns the first element in this greater than or equal to val; returns null if none
higher(Integer val)	Returns the first element in this greater than val; returns null if none
lower(Integer val)	Returns the first element in this less than val; returns null if none
pollFirst()	Returns and removes the first element in this; returns null if none
pollLast()	Returns and removes the last element in this; returns null if none

Code example:

import java.util.TreeSet;

public class Main {
    static int[] a = {4,7,1,2,3,6};

    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int v:a) {
            set.add(v);
        }
        Integer a2 = set.first();
        System.out.println(a2); //Returns 1
        Integer a3 = set.last();
        System.out.println(a3); //Returns 7
        Integer a4 = set.floor(5);
        System.out.println(a4); //Returns 4
        Integer a5 = set.ceiling(6);
        System.out.println(a5); //Returns 6
        Integer a6 = set.higher(7);
        System.out.println(a6); //Returns null
        Integer a7 = set.lower(2);
        System.out.println(a7); //Returns 1
        Integer a8 = set.pollFirst();
        System.out.println(a8); //Returns 1
        Integer a9 = set.pollLast();
        System.out.println(a9); //Returns 7
    }
}

Set Common Methods

Function Name	Function
size()	Returns the current set size
add(Integer val)	Inserts val into the set
contains(Integer val)	Determines if the set contains element val
addAll(Collection e)	Adds all elements from container e into the current set
retainAll(Collection e)	Deletes elements from the current set that do not appear in container e, i.e., finds the intersection of the current set and e
removeAll(Collection e)	Deletes elements from the current set that appear in container e, i.e., finds the difference between the current set and e

import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Set<Integer> s1 = new HashSet<>();
    static Set<Integer> s2 = new LinkedHashSet<>();

    static void add() {
        s1.add(1);
    }

    static void contains() {  // Determines if the set contains element with value 2; returns true if yes, false otherwise 
        s1.contains(2);
    }

    static void test1() {  // Union of s1 and s2 
        Set<Integer> res = new HashSet<>();
        res.addAll(s1);
        res.addAll(s2);
    }

    static void test2() {  // Intersection of s1 and s2 
        Set<Integer> res = new HashSet<>();
        res.addAll(s1);
        res.retainAll(s2);
    }

    static void test3() {  // Difference: s1 - s2 
        Set<Integer> res = new HashSet<>();
        res.addAll(s1);
        res.removeAll(s2);
    }
}

Traversal

import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Set<Integer> s1 = new HashSet<>();
    static Set<Integer> s2 = new LinkedHashSet<>();

    static void test() {
        for (int key : s1) {
            out.println(key);
        }
        out.close();
    }
}

Map

Map is a data structure that maintains key-value pairs <Key, Value>, where Key is unique.

HashMap

A Map that inserts elements at random positions.

Initialization

Map<Integer, Integer> map1 = new HashMap<>();

LinkedHashMap

A Map that maintains insertion order.

Initialization

Map<Integer, Integer> map2 = new LinkedHashMap<>();

TreeMap

A Map that keeps keys in order, default ascending.

Initialization

Map<Integer, Integer> map3 = new TreeMap<>();
Map<Integer, Integer> map4 = new TreeMap<>((x, y) -> {return y - x;});  // Descending

Common Methods

In the following, this represents the current Map<Integer, Integer>:

Function Name	Function
put(Integer key, Integer value)	Inserts <key, value> into this
size()	Returns the size of this
containsKey(Integer key)	Determines if this contains an element with key key
get(Integer key)	Returns the value corresponding to the element with key key in this
keySet()	Returns all keys in this as a set

Usage examples:

import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    static Map<Integer, Integer> map1 = new HashMap<>();
    static Map<Integer, Integer> map2 = new LinkedHashMap<>();
    static Map<Integer, Integer> map3 = new TreeMap<>();
    static Map<Integer, Integer> map4 = new TreeMap<>((x,y)->{return y-x;});

    static void put(){  // Returns the element with key 1 and value 1
        map1.put(1, 1);
    }
    static void get(){  // Returns the value for key 1
        map1.get(1);
    }
    static void containsKey(){  // Determines if there is a key-value pair with key 1
        map1.containsKey(1);
    }
    static void KeySet(){
        map1.keySet();
    }
}

Traversal

import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    static Map<Integer, Integer> map1 = new HashMap<>();

    static void print() {
        for (int key : map1.keySet()) {
            out.println(key + " " + map1.get(key));
        }
    }
}

Of course, the key and value types can also be changed. For example, Map can also be defined as:

Map<String, Set<Integer>> map = new HashMap<>();

Arrays

Arrays is a utility class in java.util for array operations. Methods are static and can be called directly using the class name.

Arrays.sort()

Arrays.sort() is a method for sorting arrays. The main overloaded methods are as follows:

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static int[] a = new int[10];
    static Integer[] b = new Integer[10];
    static int firstIdx, lastIdx;

    public static void main(String[] args) {
        Arrays.sort(a);  // 1 
        Arrays.sort(a, firstIdx, lastIdx);  // 2 
        Arrays.sort(b, new Comparator<Integer>() {  // 3 
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        Arrays.sort(b, firstIdx, lastIdx, new Comparator<Integer>() {  // 4 
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        // Since Java 8 has Lambda expressions, the third and fourth overloads can also be written as 
        Arrays.sort(b, (x, y) -> {  // 5 
            return y - x;
        });
        Arrays.sort(b, (x, y) -> {  // 6 
            return y - x;
        });
    }
}

Meanings of the numbered overloaded methods:

1. Sorts array a in ascending order by default.
2. Sorts a specified range of array a in ascending order by default, sorting interval is left-closed right-open [firstIdx, lastIdx).
3. Sorts array a in a custom manner; second parameter - first parameter is descending, first parameter - second parameter is ascending. When using a custom comparator, the array element type must be an object type.
4. Sorts a specified range of array a in a custom manner, sorting interval is left-closed right-open [firstIdx, lastIdx). When using a custom comparator, the array element type must be an object type.
5. Same as 3, optimized code length with Lambda expression.
6. Same as 4, optimized code length with Lambda expression.

Arrays.sort() Underlying Function

1. When the parameter array element type of Arrays.sort is a primitive data type (byte, short, char, int, long, double, float), it defaults to DualPivotQuicksort (dual-pivot quicksort), with worst-case complexity up to \(O(n^2)\).
2. When the parameter array element type of Arrays.sort is a non-primitive data type, it defaults to legacyMergeSort and TimSort (merge sort), with complexity \(O(n\log n)\).

This can be verified with the following code:

Codeforces 1646B - Quality vs Quantity

There are \(n\) integers, you need to divide them into two groups. Is it possible for one group to have a smaller length than the other while having a greater sum?

Example Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static class FastReader {
        StringTokenizer st;
        BufferedReader br;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static PrintWriter out = new PrintWriter(System.out);
    static FastReader in = new FastReader();

    static void solve() {
        int n = in.nextInt();
        // Changing the array type from Integer to int here will cause TLE
        Integer[] a = new Integer[n + 10];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a, 1, n + 1);
        long left = a[1];
        long right = 0;
        int x = n;
        for (int i = 2; i < x; i++, x--) {
            left = left + a[i];
            right = right + a[x];
            if (right > left) {
                out.println("YES");
                return;
            }
        }
        out.println("NO");
    }

    public static void main(String[] args) {
        int t = in.nextInt();
        while (t-- > 0) {
            solve();
        }
        out.close();
    }
}

Arrays.binarySearch()

Arrays.binarySearch() is a method for binary search on a continuous interval of an array. The prerequisite is that the array must be sorted, with time complexity \(O(\log_n)\). The main overloaded methods are as follows:

import java.util.Arrays;

public class Main {
    static int[] a = new int[10];
    static Integer[] b = new Integer[10];
    static int firstIdx, lastIdx;
    static int key;

    public static void main(String[] args) {
        Arrays.binarySearch(a, key);  // 1 
        Arrays.binarySearch(a, firstIdx, lastIdx, key);  // 2 
    }
}

Source code:

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Meanings of the numbered overloaded methods:

1. Performs a binary search for key in array a. If found, returns its index. If not found, returns a negative number.
2. Performs a binary search for key in array a, searching interval is left-closed right-open [firstIdx,lastIdx). If found, returns its index. If not found, returns a negative number.

Arrays.fill()

Arrays.fill() method assigns the same value to consecutive positions in an array. It accepts parameters: array, fromIndex, toIndex, and the value to fill. After execution, all elements in the left-closed right-open interval [firstIdx,lastIdx) will have the filled value.

Collections

Collections is a utility class in java.util for collection operations. Methods are static and can be called directly using the class name.

Collections.sort()

Collections.sort() underlying principle is to convert all elements into an array and call Arrays.sort(). After sorting, it assigns back to the original collection. Since element types in Java Collection are all object types, it always uses merge sort.

This method cannot sort a specified interval of a collection.

Underlying source code:

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Collections.binarySearch()

Collections.binarySearch() performs binary search on a specified interval in a collection, with the same functionality as Arrays.binarySearch().

Collections.binarySearch(list, key);

This method cannot search a specified interval.

Collections.swap()

Collections.swap() swaps elements at two specified positions in a collection.

 Collections.swap(list, i, j);

Miscellaneous

Numerical Comparison Issues

In Java, if it's purely a numeric type, -0.0 = 0.0. If it's an object type, then -0.0 != 0.0. This can cause trouble when trying to count slopes with a Set. The provided solution is to add 0.0 to all slopes before adding them to the Set.

import java.io.PrintWriter;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    static void A() {
        Double a = 0.0;
        Double b = -0.0;
        out.println(a.equals(b));  // false 
    }

    static void B() {
        Double a = 0.0;
        Double b = -0.0 + 0.0;
        out.println(a.equals(b));  // true 
    }

    static void C() {
        double a = 0.0;
        double b = -0.0;
        out.println(a == b);  // true 
    }


    public static void main(String[] args) {
        A();
        B();
        C();
        out.close();
    }
}

References

---

1. Input & Output - USACO Guide ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用