Hello, everyone! I am the third in my class. I have been brushing algorithms recently, and FOUND that I am not familiar with some APIS, so I have sorted out a wave of them.

A collection of

In the brush problem, we often use various data structures, such as stack implementation iteration, hash store key-value pairs, etc. Let’s take a look at common collections and related apis.

Class/interface describe methods
String string charAt toCharArray split substring indexOf lastIndexOf replace length
List The list of add remove get size subList
Stack The stack push pop peek isEmpty size
Queue The queue offer poll peek isEmpty size
Deque The bidirectional queue offerFirst offerLast pollFirst pollLast peekFirst peekLast isEmpty size
PriorityQueue Priority queue offer poll peek isEmpty size
Set add remove contains isEmpty size first(TreeSet) last(TreeSet)
Map put get getOrDefault containsKey containsValue keySet values isEmpty size

An array of

Arrays, of course, are the most familiar data structures.

Arrays

Arrays is a commonly used array utility class, which can complete functions such as sorting and copying.

  • Array.sort (int[] arr) Arrays.sort(int[] arr, int fromIndex, int toIndex)
Arrays.sort(int[] arr, int fromIndex, intToIndex, comparator);// Generics must be needed

Arrays.sort(arr, (o1, o2) -> o2 - o1);   // All arrays are sorted from largest to smallest like collections.sort ()

Arrays.sort(arr, 0.3, (o1, o2) -> o2 - o1);   // Sort from large to small, only sort [0, 3]
Copy the code
  • Copy: Array. CopyOf
int[] a = new int[5];
int[] newA = Array.copyOf(a, 5);
Copy the code

The list of

There are two main implementations of lists, sequential lists and linked lists.

A sequential list is essentially an array that can be dynamically expanded, implemented in Java as an ArrayList.

A LinkedList is a bidirectional list, which is implemented as a LinkedList in Java. LinkedList is a very powerful collection class in Java that can also be used as a two-way queue or stack.

Note that the expansion of the ArrayList requires copying the elements of the old array into the new array in O(n) time.

Basic method

  • structure
List<Integer> array = new ArrayList<>();    / / order form
// Set<Integer> a = new HashSet....
List<Integer> b = new ArrayList<>(a);     // Accept a collection container
Copy the code
  • get
get(int index)    // Return e -- array O(1), list O(n)
Copy the code

  • size

size()    // Return array/list length -- O(1)
Copy the code
  • add
add(E e)    // Add an element e -- O(1) to the end
add(int index, E e)    // Insert e -- O(n) into index
Copy the code
  • remove
.remove(int index)    // Delete the element in index, and return to delete the element e -- delete the last element O(1), the rest is O(n).
List.remove (list.size() -1);
Copy the code
  • subList
.subList(int from, int to)    // Return a fragment of the original array, but do not change it, changes will affect the original array -- O(1)
// List
      
        List, non-structural changes made to the original List and the returned List,
      
// Will affect each other. If you change the size of the sublist after calling sublist, the sublist will be invalidated and become unusable
Copy the code

A collection of tools

Collections is a collection utility class that provides methods for manipulating Collections.

  • The sorting
Collections.sort(list); Collections.sort(list, (o1, O2) -> o2-o1); Sort from largest to smallest, and the second argument is a comparatorCopy the code

Two implementations, ArrayList for finding, LinkedList for adding and deleting.

The comparison is as follows:

operation ArrayList LinkedList
get(int index) O(1) Order n, average n over 4 steps
add(E element) Worst case (expansion) O(n), average O(1) O(1)
add(int index, E element) Order n, average n over 2 steps Order n, average n over 4 steps
remove(int index) O(n) average n over 2 steps Order n, average n over 4 steps

The stack

The Stack interface is defined in Java, and the implementation class is Vector. Vector is a family collection class and is not recommended.

So what should we use?

The Deque interface implements the complete stack operation set, which has a familiar implementation class LinkedList.

  • structure
Deque<Integer> stack=new LinkedList<>();
Copy the code
  • push
push(E e);    // Push element e, return element e -- O(1)
Copy the code
  • pop
.pop();    // Unstack an element, return the unstack element e -- O(1)
Copy the code
  • peek
peek();    E -- O(1) e -- O(1)
Copy the code
  • isEmpty
isEmpty()    // Return true if the stack is empty, false otherwise -- O(1)
Copy the code
  • size
size()    // Return the number of elements in the stack -- O(1)
Copy the code

The queue

Queue S is a first-in, first-out structure, defined as Queue in Java and implemented as our old friend LinkedList.

  • structure
Queue<Integer> q = new LinkedList<>();
Copy the code
  • offer
offer(E e);    // Add element e to the end of the queue. Return true for success, false otherwise -- O(1)
Copy the code
  • poll
poll();    // Return the queue element e -- O(1)
Copy the code
  • peek
peek();    // Return e -- O(1)
Copy the code
  • isEmpty
isEmpty()    // Return true if the queue is empty, false otherwise -- O(1)
Copy the code
  • size
size()    // Return the number of elements in the queue -- O(1)
Copy the code

The bidirectional queue

A Queue has a subinterface, Dueue, which is a two-way Queue. Unlike a one-way Queue, it can enter or exit a Queue in two directions.

  • structure
Dueue<Integer> q = new LinkedList<>();
Copy the code
  • offFirst
offFirst(Object e)   // Add the specified element to the head of the queue -- O(1)
Copy the code
  • offLast
offLast(Object e)   // Add the specified element to the end of the queue -- O(1)
Copy the code
  • pollFirst
pollFirst()   // Get and delete the first element of the queue -- O(1)
Copy the code
  • pollLast
pollLast()   // Get and delete the last element of the queue -- O(1)
Copy the code
  • peekFirst
peekFirst()   // Get, but do not delete, the first element of the queue -- O(1)
Copy the code
  • peekLast
peekLast()   // Get, but do not delete, the last element of the queue -- O(1)
Copy the code

Priority queue

A priority queue is a special queue. The order in which the elements are stored is not the order in which they are added, but sorted by the size of the elements when they are added.

So the elements at the head of the queue are not in order, but in order of size.

The implementation in Java is PriorityQueue, with a tree at the bottom, taking the small root heap as an example. For any node, the value of that node is smaller than the value of its left and right children. The node at the top is the smallest. The big root heap is similar, with the largest node at the top

  • structure
    • Small root pile
Queue<Integer> minH = new PriorityQueue<>();    // Small root heap, default size 11 equivalent to new PriorityQueue<>(11)
Queue<Integer> minH = new PriorityQueue<>(100);  // Define a small root heap with a default size of 100. Adding elements to it expands, just to start specifying the size. Not size, capacity
Copy the code
    • Big root pile
Queue<Integer> maxH = new PriorityQueue<>((i1, i2) -> i2 - i1);    New PriorityQueue<>(11, (i1, i2) -> i2-i1)
Queue<Integer> maxH = new PriorityQueue<>(100, (i1, i2) -> i2 - i1);    // Define a large root heap with a default size of 100. Adding elements to it expands, just to start specifying the size
Copy the code
  • offer
offer(E e);    // Add element e to the heap and adjust the heap. Return true on success, false otherwise -- O(logN)
Copy the code
  • poll
poll();    // Eject the top element and resize the heap to return the queue element e -- O(logN)
Copy the code
  • peek
peek();    E -- O(1) e -- O(1)
Copy the code

Hash table

Hash represents a

data structure, implemented in Java as a HashMap.
,value>

  • structure
Map<Characters, Integer> map = new HashMap<>();
Copy the code
  • put
put(K key, V value);    // Add a 
      
        pair to the Map. Return value. Replace old value -- O(1) if there is a key in the Map
      ,>
Copy the code
  • get
get(K key);    // Return the value of the Map key. If this key is not present in Map, return null -- O(1)
Copy the code
  • getOrDefault
getOrDefault(K key, V defaultValue);    // Return the value of the Map key. If the key is not present in the Map, return defaultValue -- O(1)

// For example:
// Map<Character, Integer> map = new HashMap<>();
// if (...) // If k is found, the value of k in the Map is increased by 1. If you start with no k, you add 1 from 0. (equivalent to giving key an initial value in the Map)
    map.put('k', map.getOrDefault('k'.0) + 1);
Copy the code
  • containsKey
containsKey(Key key);    // Return true if key exists in Map, false otherwise -- O(1)

get(x) == null // Can be used instead
Copy the code
  • keySet
keySet();    // Return a Set containing all keys in the Map -- O(1)

// For example:
// We want to get all keys in Map
// Map<Character, Integer> map = new HashMap<>();
for (Character key : map.keySet()) {
    // Operate with each key
}
Copy the code
  • values
values(); // Return a Collection<v> containing all values -- O(1) // We want to get all values in Map // Map<Character, Integer> map = new HashMap<>(); for (Integer value : map.values()) { // Operate with each values }Copy the code
  • isEmpty
isEmpty()    // Return true if Map is empty, false otherwise -- O(1)
Copy the code
  • size
.size()    // Return the number of middle key pairs 
      
        in Map -- O(1)
      ,>
Copy the code

Set

A Set is a collection of no repeating elements, and a common implementation is a HashSet.

  • structure
Set<Integer> set = new HashSet<>();
List<Integer> list = newArrayList<>.... ; Set<Integer> set =new HashSet<>(list);
Copy the code
  • add
.add(E e);    // Add element E E to the set, true if successful, false if there is an element E in the set -- O(1)
Copy the code
  • remove
remove(E e);    // Remove element e from the set, return true if removed successfully; If there is no element e in the set, return false -- O(1)
Copy the code
  • contains
contains(E e);    // Return true if element e exists, false otherwise -- O(1)
Copy the code
  • isEmpty
isEmpty()    // Return true if the set is empty, false otherwise -- O(1)
Copy the code
  • size
size()    // Return the number of elements in the set -- O(1)
Copy the code
  • first
first()    // Return the minimum value in the set (maximum value if the comparator is given from large to small)
Copy the code
  • last
last()    // Return the maximum value in the set (minimum value if the comparator is given from large to small)
Copy the code

string

String

Immutable (equivalent to a read-only final modifier), each positional element is a char.

  • Initialize the

String copy initialization

String s = ``"abc"` `;Copy the code

Based on another string

// s = "abc"``String s2 = ``new` `String(s);
Copy the code

Based on the char []

// s = "abc";
// char[] c = s.toCharArray();
String s3 = new String(c);

// Can be offset
// public String(char value[], int offset, int count)
String s4 = new String(c, 1.2);    // [offset, offset + count) [)

// Change char[] to a string
char[] ch = {'a'.'b'.'c'};
String.valueOf(ch);
Copy the code
  • charAt
charAt(int index);    // Return index position char -- O(1)
Copy the code
  • length
length();    // Return the length of the string -- O(1)
Copy the code
  • substring
substring(int beginIndex, int endIndex);    // Return character fragment beginIndex, endIndex -- O(n)

substring(int beginIndex);    BeginIndex, end_of_String: ---- O(n)
Copy the code
  • indexOf
indexOf(String str)    // return the position at which STR first appeared (int), or -1 if not found. -- O(m * n) m is the length of the original string, and n is the length of STR
// if you are looking for a char c, STR can be represented as string.valueof (c) and passed as an argument.

s.indexOf(String str, int fromIndex);    // Start with fromIndex -- O(m * n)
Copy the code
  • lastIndexOf
lastIndexOf(String str);    // return the last occurrence of STR (int), -1 if not found. -- O(m * n) m is the length of the original string, and n is the length of STR
// if you are looking for a char c, STR can be represented as string.valueof (c) and passed as an argument.

lastIndexOf(String str, int fromIndex);    / / same as above,
[0 < -fromindex] -- O(m * n)
Copy the code
  • replace
replace(char oldChar, char newChar);    // Return a new String whose oldChar is all changed to newChar -- O(n)
Copy the code
  • toCharArray
toCharArray();   // Return char[] array. Programming String character arrays -- O(n)
Copy the code
  • trim
trim();    // Return a new string with whitespace removed -- O(n)
Copy the code
  • split
split(String regex);    // Mandatory String[], delimited by regex(regular expression). ---- O(n)

// For example
// If "/a/c" -> will become "" "" a" "" C"
String[] date = str.split("/");     // date[0]:1995 date[1]:12 date[2]:18 --- O(n)
Copy the code
  • toLowerCase, toUpperCase
s = s.toLowerCase();    // Return a new string all lowercase -- O(n)
s = s.toUpperCase();    // Return a new string all uppercase -- O(n)
Copy the code

StringBuilder

Since strings are so-called immutable classes, using STR + to concatenate strings is actually the JVM that creates the StringBuilder loop to concatenate strings, so StringBuilder is the best way to concatenate strings.

  • structure
StringBuilder sb = new StringBuilder();
Copy the code
  • charAt
charAt(int index); // Return index position char -- O(1)Copy the code
  • length
length(); // Return buffer string length -- O(1)Copy the code
  • apped
Append (String STR) // Concatenate String -- O(n)Copy the code
  • toString
toString(); // Return a string with the same content as the build or buffer -- O(n)Copy the code

mathematics

Maximum minimum value

The maximum and minimum values for each data type in Java are defined as follows:

fmax = Float.MAX_VALUE;

fmin = Float.MIN_VALUE;

dmax = Double.MAX_VALUE;

dmin = Double.MIN_VALUE;

bmax = Byte.MAX_VALUE;

bmin = Byte.MIN_VALUE;

cmax = Character.MAX_VALUE;

cmin = Character.MIN_VALUE;

shmax = Short.MAX_VALUE;

shmin = Short.MIN_VALUE;

imax = Integer.MAX_VALUE;

imin = Integer.MIN_VALUE;

lmax = Long.MAX_VALUE;

lmin = Long.MIN_VALUE;
Copy the code

Math

  • max
Math.max(long a, long b);    // Returns the greater of the two arguments
Copy the code
  • sqrt
Math.sqrt(double a);    // Find the arithmetic square root of the argument
Copy the code
  • abs
Math.abs(double a);  // Return an absolute value of the same type as the argument
Copy the code
  • pow
Math.pow(double a, double b);  // Return the second power of the first argument.
Copy the code
  • ceil
Math.ceil(double x);   // round up
Copy the code
  • floor
Math.floor(double x);  // round down
Copy the code
  • round
Math.round(double x);   // Round off
Copy the code


“Do simple things repeatedly, do repetitive things carefully, and do serious things creatively!” –

I am three points evil, a full stack of literary and military development.

Like, pay attention to not get lost, let’s see you next time!

Reference:

[1].java brush problem common API

[2].Java brush problem collection class