catalogue
- One input output
- Class BufferedReader
- Two strings and numbers
- Three common data structures
- IV. use of mathematical tools
- Five easy-to-use stream processing API s in Java 8
- Vi. use of syntax sugar in Java
One input output
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
}
}
1.1 most commonly used inputs
Read data with a known number of rows
Scanner input = new Scanner(System.in);
int n,root;
n = input.nextInt();
root = input.nextInt();
int fa,lch,rch;
for(int i = 0;i < n;++i){
fa = input.nextInt();
lch = input.nextInt();
rch = input.nextInt();
left[fa] = lch;
right[fa] = rch;
// System.out.printf("%d %d %d\n",fa,lch,rch);
}
// Note: there is no control character of% LD% L in Java, and all integers use% d
Read integer data with uncertain number of rows
1 A+B(1)
/*
Input:
1 5
10 20
Output:
6
30
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(a+b);
}
}
Read a sequence of numbers with an uncertain number of rows by row
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
int sum = 0;
String a = sc.nextLine();
String[] as = a.split(" ");
for(int i=0;i<as.length;i++){
sum = sum + Integer.parseInt(as[i]);
}
System.out.println(sum);
}
}
}
Reads a string sequence with an uncertain number of lines and sorts the strings by line
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
String a = sc.nextLine();
String[] as = a.split(",");
Arrays.sort(as);
for(int i=0;i<as.length-1;i++){
System.out.print(as[i]+',');
}
System.out.println(as[as.length-1]);
}
}
}
Class BufferedReader
String readLine()
Mass read / write templates
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
// Input and output must use BufferedReader and BufferedWrite
BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int len1 = Integer.parseInt(buf.readLine());
String P = buf.readLine();
int len2 = Integer.parseInt(buf.readLine());
String S = buf.readLine();
P = " "+P;
S = " "+S;
char[] pp = P.toCharArray();
char[] ss = S.toCharArray();
// step1: construct the next array corresponding to the pattern string
int[] next = new int[len1+1];
next[1] = 0;
for(int i = 2,size = 0;i <= len1;++i){
while(size > 0 && pp[size+1] != pp[i]) size = next[size]; // Matching failed
if(pp[size+1] == pp[i]) ++size; // Match successful
next[i] = size;
}
// Step 2: Match
for(int i = 1,size = 0;i <= len2;++i){
while(size > 0 && pp[size+1] != ss[i]) size = next[size]; // Matching failed
if(pp[size+1] == ss[i]) ++size; // Match successful
if(size == len1){
writer.write(i - size +" "); // output
size = next[size];
}
}
writer.flush(); // Output the contents written to the buffer
writer.close();
buf.close();
}
}
Precautions for using Scanner:
1)Don't mix nextLine()Method and nextInt()method Processing strategy of mixed input of string and number: 1)All use nextLine(),Then use the package type parseInt()Parse string 2)next()Method to read a string(recommend)，More convenient
example:
public class Main {
/*
Read:
10 5
oxxoooxxxo
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int p = sc.nextInt();
String c = sc.next();
System.out.printf("%d %d\n",n,p);
System.out.println(c);
}
}
Two strings and numbers
2 Properties of wrapper class
MIN_VALUE
MAX_VALUE
8 Default values for basic data types:
1)byte short int long The default value of these four basic data type arrays is 0
2)float double The default value of these two arrays is 0.0
3)char The default value of this type of array is space
4)boolean The default value of type array is false
Value range:
char Numerical range: -128 ~ 127
unsigned char Numerical range: 0 ~ 255
short Value range: 32767 ~ -32768
int Value range: 21 4748 3647 ~ -2147483648 // 2 ^ 31-1 ~ - 2 ^ 31, i.e. 2*10^10 (int can represent 10 ^ 10 range data)
// In Java, the int variable is defined as - 2 ^ 31. Using the library function Math.abs(-2^31), the result is still - 2 ^ 31. The reason is that in the form of complement, integers represent one bit less than negative numbers
long Value range: 922 3372 0368 5477 5807 ~ -9223372036854775808 // 9 * 10 ^ 18 (data that can represent the range of 10 ^ 18)
byte Value range: 127 ~ -128
float Value range: 3.402823e+38 ~ 1.401298e-45
double Value range: 1.797693e+308 ~ 4.900000e-324
byte 8 bit 0 Byte
short 16 bit 0 Short
int 32 bit 0 Integer
long 64 bit 0L Long
float 32bit 0.0f Float
double 64bit 0.0d Double
char 16 bit / Character
boolean / false Boolean
2-1 StringBuilder
append() // Basic data types are OK toString() // Convert to String type for printing delete(start,end) // Delete the string whose position interval is [start, end] insert(start,value) // Insert the string from the position start (including start) substring(start, end) // Returns the string of the position interval [start, end] toCharArray() // Convert to char [] array void setCharAt(int index, char ch) // Sets the character for the specified position StringBuilder replace(int start, int end, String str) StringBuilder reverse()
2-2 String class
int compareTo(String anotherString) // Compare the size of two strings char charAt(int index) // Return string type int length() // Returns the length of this string String[] split(String regex) // Returns the split String array String substring(int beginIndex, int endIndex) boolean isEmpty() boolean equals(Object anObject) // Compares this string to the specified object. boolean equalsIgnoreCase(String anotherString) // ignoring case considerations. public boolean matches(String regex) int indexOf(String str) // Returns the position where the substring first appears. If - 1 is not returned, it can be used to replace KMP char[] toCharArray() // Convert string to char array String replaceAll(String regex, String replacement) // Find all regex in the string and replace with replacement
Regex in Java (usage strategy of regular expressions)
- For calculator type programming problems, regex is used to normalize the string, which is more convenient to process.
1)split And match And repalceAll All adopt regex As a parameter, it is required to be a legal regular expression. 2)Some characters in regular expressions contain special meanings (such as'?'，'+','|')，It is called metacharacter. If we don't want to use its special meaning, we can add it before the character \\
- ?Matches the preceding element zero or one time. For example, ab?c matches only "ac" or "abc".
- +Matches the preceding element one or more times. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".
- |The choice (also known as alternation or set union) operator matches either the expression before or the expression after the operator. For example, abc|def matches "abc" or "def".
Note: In the POSIX standard, Basic Regular Syntax (BRE) requires that the metacharacters ( ) and { } be designated \(\) and \{\}, whereas Extended Regular Syntax (ERE) does not.
| ^ | Matches the starting position within the string. In line-based tools, it matches the starting position of any line. |
|---|---|
| . | Matches any single character (many applications exclude newlines, and exactly which characters are considered newlines is flavor-, character-encoding-, and platform-specific, but it is safe to assume that the line feed character is included). Within POSIX bracket expressions, the dot character matches a literal dot. For example, a.c matches "abc", etc., but [a.c] matches only "a", ".", or "c". |
| [ ] | A bracket expression. Matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z].The - character is treated as a literal character if it is the last or the first (after the ^, if present) character within the brackets: [abc-], [-abc]. Note that backslash escapes are not allowed. The ] character can be included in a bracket expression if it is the first (after the ^) character: []abc]. |
| [^ ] | Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". Likewise, literal characters and ranges can be mixed. |
| $ | Matches the ending position of the string or the position just before a string-ending newline. In line-based tools, it matches the ending position of any line. |
| ( ) | Defines a marked subexpression. The string matched within the parentheses can be recalled later (see the next entry, \*n*). A marked subexpression is also called a block or capturing group. BRE mode requires \( \). |
| \n | Matches what the nth marked subexpression matched, where n is a digit from 1 to 9. This construct is vaguely defined in the POSIX.2 standard. Some tools allow referencing more than nine capturing groups. Also known as a backreference. |
| * | Matches the preceding element zero or more times. For example, ab*c matches "ac", "abc", "abbbc", etc. [xyz]* matches "", "x", "y", "z", "zx", "zyx", "xyzzy", and so on. (ab)* matches "", "ab", "abab", "ababab", and so on. |
| {m,n} | Matches the preceding element at least m and not more than n times. For example, a{3,5} matches only "aaa", "aaaa", and "aaaaa". This is not found in a few older instances of regexes. BRE mode requires \{\*m\*,\*n\*\}. |
2-3 common methods in Integer (conversion between String and Integer)
The following properties are provided in the wrapper class:
2 Properties of wrapper class MIN_VALUE MAX_VALUE --------------------------Convert string to number-------------------------------- // Note that the following are static methods. static int parseInt(String s) // Parses the string argument as a signed decimal integer. static int parseInt(String s, int radix) // Specifies the number of hexadecimals to convert ------------------------------------------------------------------------ static int reverse(int i) // Reverse according to bit static int reverseBytes(int i) // Flip by byte ---------------------------Convert numbers to strings----------------------------------- static String toString(int i) static String toString(int i, int radix) ---------------------------Non packaged numbers are converted to String Method of--------------------- String.valueOf(T) // Use the static method provided by String, valueOf
Common methods of Integer bit operation
static int bitCount(int i) // Returns the number of 1 static int reverse(int i) // Reverse binary static int reverseBytes(int i) static int rotateLeft(int i, int distance) static int rotateRight(int i, int distance)
2-4 use of BigDecimal
BigDecimal bignum1 = new BigDecimal("10");
BigDecimal bignum2 = new BigDecimal("5");
BigDecimal bignum3 = null;
bignum3 = bignum1.add(bignum2);
bignum3 = bignum1.subtract(bignum2);
bignum3 = bignum1.multiply(bignum2);
bignum3 = bignum1.divide(bignum2);
2-5 Java median operator symbols
Complement:
- The complement of an integer is the same as the original code
- The complement of a negative number is equal to all the bits of the original code except the sign bit, which are reversed and plus 1
int a=129; int b=128; a & b // And a | b // or ~a // wrong a^b // XOR a<<3 // Shift left operator, fill 0 in low order) a>>3 // "Signed" shift right operator. If the value is positive, 0 will be filled in the high order. If the value is negative, 1 will be filled in the high order a>>>3 // "Unsigned" shift right operator, using 0 extension mechanism
2-6 sorting
Common sense: Java provides two ways to define sorting rules: Comparable and Comparator.
- Comparator is defined in the JUC package and usually cooperates with some tool classes of JUC, which is the embodiment of the policy pattern.
- Comparable is usually used to formulate the internal sorting rules of a class. You can implement the comparable interface when defining a class
The difference between Comparable and Comparator
2-6-1 sorting of basic data types (arrays in util)
int[] array = {10, 3, 6, 1, 4, 5, 9};
int[] array = new int[]{1,2}; //Another initialization method for array objects
Arrays.sort(array); // The array is arranged in ascending order. For the time being, there is no method to directly arrange the one-dimensional array in reverse order
-------------------------------------------------------
Detour strategy: turn int [] Convert to Integer [],Then implement Comparator Or in combination Arrays.sort()And Collections.reverse();
---------------------------------------------------------
/*For the List interface, ArrayList, LinkedList, and Vector*/
// class Cmp implements Comparator<Integer> {
// @Override
// public int compare(Integer o1, Integer o2) {
// return o2-o1;
// }
// }
2-6-2 sorting of user-defined data types
- Collections in the util toolkit provides a sort method
- One dimensional / two-dimensional Arrays are sorted by Arrays, and the container class implementing the list interface is sorted by Collections
Basic idea: implement the interface for comparison Comparable<T>
Collation:
0 Itself is larger than the target object
=0 Itself is equal to the target object
<0 Itself is smaller than the target object
public interface Comparable<T> {
public int compareTo(T o);
}
Arrays:
void sort(Comparator<? super E> c) // Sorts this list according to the order induced by the specified Comparator.
------------------------------------------------------------------------------------
Implement collation in class
static class Mydata implements Comparable<Mydata>{
int w;
int h;
public Mydata(int w, int h) {
this.w = w;
this.h = h;
}
@Override
public int compareTo(Mydata o) {
if(this.w == o.w)
return o.h-this.h; // h in descending order, where o is o2,this is O1, O2 < O1
else{
return this.w-o.w; // w in ascending order, O1 - O2 < 0, i.e. O1 > O2
}
}
}
ArrayList<Mydata> data = new ArrayList<Mydata>();
for(int i = 0;i < len1;++i){
data.add(new Mydata(envelopes[i][0],envelopes[i][1]));
Collections.sort(data);
Implementing sorting rules using functional interfaces
static class Mydata{
int w;
int h;
public Mydata(int w, int h) {
this.w = w;
this.h = h;
}
}
// In essence, it still implements the comparable interface. Here, we only use syntax sugar to simplify the writing method
Arrays.sort(data,(o1,o2)->{
if(o1.w == o2.w)
return o2.h-o1.h;
else
return o1.w-o2.w;
});
Using one-dimensional array objects and functional interfaces (sorting seems to be a little slower than the first two, about 50ms)
- Note that Java arrays are also objects. Two dimensional arrays are composed of multiple one-dimensional array objects, which s directly inherit objects
- You can sort two-dimensional arrays by rows by defining rules.
Arrays.sort(envelopes,(o1,o2)->{
if(o1[0] == o2[0])
return o2[1]-o1[1];
else
return o1[0]-o2[0];
});
2-7 common methods of math class
abs(T) Math.ceil(double a) // Round up Math.floor(double a) // Round up
2-8 common methods of arrays Toolkit (manipulating arrays)
static int[] copyOfRange(int[] original, int from, int to) // Copy part of an array
2-9 common functions of character
static boolean isDigit(char ch) static boolean isLetterOrDigit(char ch) // letter static boolean isLetter(char ch) // static boolean isLowerCase(char ch) static char toLowerCase(char ch) //Convert to lowercase
Three common data structures
1.vector And ArrayList And LinkedList All realized List Interface. 2.LinkList Realized List And deque Interface, so it can be used as a double ended queue. 3.stack yes vector A derived class of. 4.Stack stay vector Based on the new method, it can be treated equally. 5 Thread safety:only Vector,Stack It is thread safe. Although it is thread safe, it is rarely used in practice and will be adopted juc Package implementation. 6 Physical storage method: ArrayList And Vector And stack It is implemented with arrays, LinkedList Use linked list to achieve.Physical storage Storage methods lead to differences in operation efficiency such as addition, deletion and modification. 7 ArrayList,Vector In addition to the differences in thread safety, the capacity expansion mechanism is also different, ArrayList With 1.5 The way of multiplication is expanding Rong Vector When the expansion capacity increment is greater than 0, the length of the new array is the length of the original array+Expansion capacity increment, otherwise the length of the new array is the original number Twice the degree.
3-0 C style array object definition and operation
Why use length to get the length of a Java array
- Java array index cannot accept long variables (compilation will report errors)
length // Without parentheses, you can get the length of the array
new int[]{1,2}; // Define an array object
int[] tmp = new int[0]; // Define an array object with length 0, which is different from null
int[][] res; // res[0],res[1] is essentially a one-dimensional array object
Common methods of Arrays
/* T It can be 8 basic data types*/ static void sort(T a); static void sort(T [] a, int fromIndex, int toIndex) // Left closed right open ------------------------------------------------------------------------------ static void fill(T [] a, T val) static void fill(T [] a, int fromIndex, int toIndex, T val) ------------------------------------------------------------------------------- static int binarySearch(T [] a, T key) // Binary search, if the index < 0 is not found static int binarySearch(T [] a, int fromIndex, int toIndex, T key) ------------------------------------------------------------------------------ Arrays.copyOfRange(T [] a,int fromIndex, int toIndex); // Copy the array of the [index1,index2) range of a and return a new array ------------------------------------------------------------------------------ Arrays.equals(T[] a, T[] a2); // Compare whether each element of the two arrays is the same. T can be of any basic type
3-1 Class ArrayList
3-1-1 basic usage
---------------------------------------------------------------------
0 Definition of one-dimensional dynamic array
ArrayList<String> array = new ArrayList<String>();
----------------------------------------------------------------------
02 Two dimensional dynamic array definition
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); //
for(int i = 0;i < 3;++i)
res.add(new ArrayList<Integer>());
Note: unable to pass ArrayList<ArrayList<Integer>> [] res = new ArrayList<ArrayList<Integer>>()[3];
----------------------------------------------------------------------
03 Another definition method of two-dimensional array (each element in the array is ArrayList)
ArrayList<Integer>[] dp = new ArrayList[len1];
for(int i = 0;i < len1;++i){
dp[i] = new ArrayList<Integer>();
dp[i].add(nums[i]);
}
-------------------------------------------------------------------------
04 ArrayList Common methods of
peek() // Retrieves but does not delete the header of this queue, and returns null if the queue is empty
poll() // Retrieve and delete the header of this queue, and return null if the queue is empty
add(E e) // Insert the specified element into this queue. true returns IllegalStateException after success. If the current
isEmpty()
size()
toArray()
remove(int index) // tmp.remove(tmp.size()-1);
E set(int index, E element) // Sets the value of the specified element
get(int index) // Get the specified location element
for ( Variable type variable name : Array name ) // The elements in the container are stored in the variable name. This method can be considered if the subscript of the container is not required
3-1-2 conversion between ArrayList and ordinary array in Java
/*Conversion between one-dimensional array and ArrayList*/ String[] array = (String[])list.toArray(new String[list.size()]); // ArrayList<Object>--->Obejct[] int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray(); //ArrayList ---> int[] /*int[][] Conversion to ArrayList < int [] >*/ List<int []> res = new ArrayList<>(); // int [] is also an object in java res.toArray(new int[res.size()][]); // ArrayList<int[]> => int[][]
Implementation principle and implementation of enhanced for loop in Java
For the understanding of iterators, refer to this topic
public class NestedIterator implements Iterator<Integer> {
// Stores the current traversal location of the list
private Deque<Iterator<NestedInteger>> stack;
public NestedIterator(List<NestedInteger> nestedList) {
stack = new LinkedList<Iterator<NestedInteger>>();
stack.push(nestedList.iterator());
}
@Override
public Integer next() {
// Because it is guaranteed that hasNext will be called before calling next, the current element of the stack top list will be returned directly
return stack.peek().next().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
Iterator<NestedInteger> it = stack.peek();
if (!it.hasNext()) { // Traverse to the end of the current list and get out of the stack
stack.pop();
continue;
}
// If the extracted element is an integer, it is put back on the stack by creating an additional list
NestedInteger nest = it.next();
if (nest.isInteger()) {
List<NestedInteger> list = new ArrayList<NestedInteger>();
list.add(nest);
stack.push(list.iterator());
return true;
}
stack.push(nest.getList().iterator());
}
return false;
}
}
3-1-3 common methods of collections
static void sort(List<T> list) static void sort(List<T> list, Comparator<? super T> c) static void rotate(List<?> list, int distance) static void reverse(List<?> list) static <T> void fill(List<? super T> list, T obj) static boolean disjoint(Collection<?> c1, Collection<?> c2)
3-2 use of PriorityQueue
add(E e) // Inserts the specified element into this priority queue. peek() // Viewing the queue header element, no null is returned poll() // Return and delete the queue head element, without returning null remove() // Removes all of the elements from this priority queue size() // Returns the number of elements in this collection. clear() // Removes all of the elements from this priority queue.
Priority queue comparator overloaded
/*https://blog.csdn.net/weixin_43664907/article/details/112919754*/
/*By default, the priority queue is a small top heap, and you can pass in the sorting method yourself. Just pass the opposite sorting method to the large top heap*/
PriorityQueue<Integer> myq_big = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
Comparator principle
Truly correct understanding: jdk The official default is ascending, which is based on: < return -1 = return 0 > return 1 If the order is to be descending, it must be exactly the opposite: < return 1 = return 0 > return -1
3-3 use of treemap
getOrDefault(Object key, V defaultValue) // Find the key value according to the key. If not, return defaultValue K ceilingKey(K key) // >=Maximum key of key K floorKey(K key) // < = maximum key of key V get(Object key) // Find value according to key, otherwise null will be returned V replace(K key, V value) // Returns the previous key value pair and replaces it with a new key value pair. boolean replace(K key,V oldValue,V newValue) // Replace successfully returns True
Traversal of Map container
Internal interface of Map Map.Entry
/*----------Mode 1------------------------*/
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
/*---------lambda Interface------------------------*/
map.forEach((k, v) -> System.out.println("key: " + k + " value" + v));
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
TreeMap is sorted by value
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap();
for(int i = 0;i < s.length();++i){
char c = s.charAt(i);
map.put(c,map.getOrDefault(c,0)+1);
}
List<Map.Entry<Character, Integer>> list = new ArrayList<Map.Entry<Character,Integer>>(map.entrySet());
Collections.sort(list,(o1,o2)->{
return o2.getValue().compareTo(o1.getValue());
});
StringBuilder tmp = new StringBuilder();
for(Map.Entry<Character,Integer> v: list){
char c = v.getKey();
for(int k = 0;k < v.getValue();++k){
tmp.append(c);
}
}
return tmp.toString();
}
}
Traversing and deleting elements using iterators (important)
Iterator<Map.Entry<String,String>> iterator = map.entrySet().iterator();//Return all entry entities
while (iterator.hasNext()) {
Map.Entry<String, String> next1 = iterator.next();
String key = next1.getKey();
String value = next1.getValue();
System.out.println(key+" "+value);
}
//Traversal by key
Iterator iterator1 = map.keySet().iterator();
while (iterator1.hasNext()) {
System.out.println(iterator1.next());
}
//Traversal by value
// In the process of traversal, you can delete elements through it.remove()
Iterator iterator2 = map.values().iterator();
while (iterator2.hasNext()) {
System.out.println(iterator2.next());
}
451. Sort according to the occurrence frequency of characters
3-4 use of stack class (early legacy code, not recommended)
boolean empty() // Tests if this stack is empty. E peek() // E pop() // E push(E item) //
3-5 Use of LinkList and ArrayDeque
- LinkedList: Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
- Physical storage: ArrayList, Vector and stack are implemented by arrays
- ArrayDeque is implemented by circular array, and this class is used by stack or queue reference resources
Summary: LinkList is used for bidirectional linked list, and ArrayDeque is used for stack and queue
// 01 two way linked list related methods (LinkedList) public E removeFirst() public E removeLast() public void addFirst(E e) public boolean remove(Object o) // Delete an element and return whether it is successful. The operation efficiency is O(1) boolean addFirst(E e) // Equivalent to addLast(E) // 02 related methods of deque / queue / stack ArrayDeque<Node> deque = new ArrayDeque<Node>(); void offerFirst(E e) / E pollFirst() void offerLast(E e) / E pollLast() peekFirst()/peekLast() int size() boolean isEmpty() ================================================= Queue Method Equivalent Deque Method add(e) addLast(e) offer(e) offerLast(e) remove() removeFirst() poll() pollFirst() element() getFirst() peek() peekFirst() ================================================== Comparison of Stack and Deque methods (stack It belongs to the obsolete category and can be used directly ArrayList<Deque>(substitute) Stack Method Equivalent Deque Method push(e) addFirst(e) pop() removeFirst() peek() peekFirst()
- Double ended queue / queue / stack, try to replace LinkList with ArrayDeque
3-6 use of HashSet
Basic method
boolean add(E e) Adds the specified element to this set if it is not already present. void clear() Removes all of the elements from this set. boolean contains(Object o) Returns true if this set contains the specified element. boolean isEmpty() Returns true if this set contains no elements. boolean remove(Object o) Removes the specified element from this set if it is present. int size() Iterator<E> iterator() Returns an iterator over the elements in this set.
Custom classes use hashset
/*Here we get the string representation of the class through toString(), and then call the hashcode method to generate the hash value.*/
class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return x+"@"+y;
}
@Override
public int hashCode() {
return toString().hashCode();
}
@Override
public boolean equals(Object o) {
// Judge whether two references point to the same instance
if (this == o) return true;
// Judge whether the classes of the instances pointed to by the two references are the same
if (o == null || getClass() != o.getClass()) return false;
// For the same class, compare whether the member properties are the same.
Node node = (Node) o;
return x == node.x &&
y == node.y;
}
}
use
Set<Node> visited = new HashSet<Node>();
3-7 use of TreeSet
boolean add(E e) E ceiling(E e) // Looking for the first element of > = e does not return null void clear() boolean isEmpty() E floor(E e) // Find the first element of < = e, and return null if there is no int size() =======================custom element Comparison rules for===================== TreeSet(Comparator<? super E> comparator) // Constructs a new, empty tree set, sorted according to the specified comparator.
IV. use of mathematical tools
java.util.Random
Random random = new Random(); int randomIndex = left + random.nextInt(right - left+1); Math.random():The default value is greater than or equal to 0.0 And less than 1.0 Random between double Type random number
- Random.nextInt() method generates a random int value, which is an interval between [0,n), that is, a random int value between 0 and N, including 0 but not n.
Five easy-to-use stream processing API s in Java 8
API for stream interface of Java
definition: A sequence of elements supporting sequential and parallel aggregate operations(Element sequences that support serialization and parallel aggregation) Feature 1: To perform a computation, stream operations are composed into a stream pipeline. A stream pipeline consists of a source (which might be an array, a collection, a generator function, an I/O channel, etc), zero or more intermediate operations (which transform a stream into another stream, such as filter(Predicate)), and a terminal operation (which produces a result or side-effect, such as count() or forEach(Consumer)). Streams are lazy; computation on the source data is only performed when the terminal operation is initiated, and source elements are consumed only as needed.(The flow pipeline contains flow operations) Collections and streams, while bearing some superficial similarities, have different goals. Collections are primarily concerned with the efficient management of, and access to, their elements. By contrast, streams do not provide a means to directly access or manipulate their elements, and are instead concerned with declaratively describing their source and the computational operations which will be performed in aggregate on that source. However, if the provided stream operations do not offer the desired functionality, the BaseStream.iterator() and BaseStream.spliterator() operations can be used to perform a controlled traversal.
Implementation mechanism of Linux pipeline
Stream generation
stay Java8 In, the collection interface has two methods to generate streams: 1) stream() − Create a serial stream for the collection.
Count eligible elements
List<String> strings = Arrays.asList("abc", "", "bc", "efg", "abcd","", "jkl");
count = strings.stream().filter(string->string.isEmpty()).count();
System.out.println("The number of empty strings is: " + count);
count = strings.stream().filter(string -> string.length() == 3).count();
System.out.println("The number of strings with length 3 is: " + count);
Filter and return qualified elements
filtered = strings.stream().filter(string ->!string.isEmpty()).collect(Collectors.toList());
--------------------------------------------------------------------
mergedString = strings.stream().filter(string ->!string.isEmpty()).collect(Collectors.joining(", "));
System.out.println("Merge string: " + mergedString);
Conversion of collection object and array
//ArrayList < wrapper class > -- > basic data column [] int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray();
Vi. use of syntax sugar in Java
6-1 for Each cycle:
| Traversal mode | characteristic | motivation |
|---|---|---|
| Normal for loop | It is suitable for supporting random access data structures, such as ArrayList | For class instances that implement the RandomAccess interface, if they are accessed randomly, the efficiency of using ordinary for loops will be higher than that of using foreach loops, such as ArryList. |
| Enhanced for loop (forEach) | The bottom layer still uses iterators, which can be regarded as iterator loops that can not change the structure | Elements cannot be added or reduced in the loop. You can modify the value of the specified object referenced by the object (the traversed object reference and basic data type will be copied) |
| Iterator traversal | Data structures suitable for sequential access, such as LinkedList | Unified method calls can be called as long as the iterator interface is implemented |
Precautions for use:
Iterator: easy to traverse and delete; ( Iterator There are only three ways: hasNext(),next(),remove(),You cannot use the provided generic during the iteration remove method,May trigger fail fast Mechanism. ordinary for: It can be deleted and modified during traversal; enhance for: Essentially, it is still an iterator. It can be used if it is only traversal and not modified for Enhanced, but if you want to add and remove in traversal, you still need to use iterators.
Use example
map.forEach((k, v) -> System.out.println("key: " + k + " value" + v));
// External variables cannot be referenced in lambda expressions. Only variables of effective final can be referenced.
common sense
n^2 10^4 nlogn 10^7 n 10^8 n^4 30 2^n 20
Integer data range
Integer:-2147483648 ~ 2147483647 2x10^9 (2^10 = 1024) Long: -9223372036854775808 ~ 9223372036854775807 9x10^18
reference material