目录
一 输入输出
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
}
}
1.1 最常用的输入
已知行数读取数据
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
",fa,lch,rch);
}
// 注意：Java中没有%ld %l这种类型的控制字符，整型一律用%d
读取行数不确定的整型数据
1 A+B（1）
/*
输入：
1 5
10 20
输出：
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);
}
}
按行读取行数不确定的数字序列
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);
}
}
}
读取行数不确定的字符串序列并按行排序字符串
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()
大批量数量读取/写入模板
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
// 输入输出必须使用BufferedReader和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:构造模式串对应的next数组
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]; // 匹配失败
if(pp[size+1] == pp[i]) ++size; // 匹配成功
next[i] = size;
}
// step2:匹配
for(int i = 1,size = 0;i <= len2;++i){
while(size > 0 && pp[size+1] != ss[i]) size = next[size]; // 匹配失败
if(pp[size+1] == ss[i]) ++size; // 匹配成功
if(size == len1){
writer.write(i - size +" "); // 输出
size = next[size];
}
}
writer.flush(); // 将缓冲区写入的内容输出
writer.close();
buf.close();
}
}
Scanner使用注意点：
1）不要混用nextLine()方法与nextInt（）方法
字符串与数字混合输入的处理策略:
1)全部使用nextLine(),然后使用包装类型的parseInt()解析字符串
2)next()方法读取字符串(推荐)，比较方便
实例：
public class Main {
/*
读取：
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,p);
System.out.println(c);
}
}
二 字符串与数字
包装类的2属性
MIN_VALUE
MAX_VALUE
8种基本数据类型的默认值：
1）byte short int long 这四种基本数据类型数组默认值为0
2）float double 这两种数组默认值是0.0
3）char这种类型数组默认值为空格
4）boolean类型数组默认值为false
数值范围：
char 数值范围: -128 ~ 127
unsigned char 数值范围: 0 ~ 255
short 数值范围：32767 ~ -32768
int 数值范围：21 4748 3647 ~ -2147483648 // 2^31-1 ~ -2^31 即 2*10^10 (int能够表示10^10范围数据)
// 在Java中定义int变量为-2^31，使用库函数Math.abs(-2^31)其结果为依旧为-2^31，原因在于补码形式，整数比负数少表示一位
long 数值范围：922 3372 0368 5477 5807 ~ -9223372036854775808 // 9*10^18(能够表示10^18范围的数据)
byte 数值范围：127 ~ -128
float 数值范围：3.402823e+38 ~ 1.401298e-45
double 数值范围：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() // 基本的数据类型都可以
toString() // 转换成String类型用于打印
delete(start,end) // 删除位置区间为[start,end)的字符串
insert(start,value) // 从位置start(包括start)开始插入字符串
substring(start, end) // 返回位置区间[start,end)的字符串
toCharArray() // 转换成char [] 数组
void setCharAt(int index, char ch) // 设置指定位置字符
StringBuilder replace(int start, int end, String str)
StringBuilder reverse()
2-2 String类
int compareTo(String anotherString) // 比较两个字符串的大小
char charAt(int index) // 返回字符串类型
int length() // Returns the length of this string
String[] split(String regex) // 返回分割后的String数组
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) // 返回子串第一次出现的位置，如果没有返回-1，可用于替代KMP
char[] toCharArray() // 将字符串转换为char数组
String replaceAll(String regex, String replacement) // 找到字符串中所有的regex，替换为replacement.
Java中的regex(正则表达式的使用策略)
- 计算器类型的编程题采用regex对字符串进行规范化，更加方便处理。
1）split与match与repalceAll都是采用regex作为参数，即要求是合法的正则表达式。
2）在正则表达式中有些字符包含有特殊含义（如'?’，'+','|'），称为元字符，如果我们不想使用其特殊的含义可以在字符前加上 \
?Matches the preceding element zero or one time. For example,ab?cmatches only "ac" or "abc".+Matches the preceding element one or more times. For example,ab+cmatches "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|defmatches "abc" or "def".
注意点：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 ( ). |
|
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 Integer中常用方法（String与Integer的转化）
包装类中提供了以下属性：
包装类的2属性
MIN_VALUE
MAX_VALUE
--------------------------字符串转换为数字--------------------------------
// 注意下面都是静态方法。
static int parseInt(String s) // Parses the string argument as a signed decimal integer.
static int parseInt(String s, int radix) // 指定转化的进制数目
------------------------------------------------------------------------
static int reverse(int i) // 按照bit反转
static int reverseBytes(int i) // 按照字节翻转
---------------------------数字转化为字符串-----------------------------------
static String toString(int i)
static String toString(int i, int radix)
---------------------------非包装类的数字转化为String的方法---------------------
String.valueOf(T) // 使用String提供的静态方法，valueOf.
Integer位运算常用方法
static int bitCount(int i) // 返回1的数量
static int reverse(int i) // 逆转二进制
static int reverseBytes(int i)
static int rotateLeft(int i, int distance)
static int rotateRight(int i, int distance)
2-4 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中位操作符号
补码：
- 整数的补码与原码相同
- 负数的补码等于原码除符号位的其他所有位取反并加1
int a=129;
int b=128;
a & b // 与
a | b // 或
~a // 非
a^b // 异或
a<<3 // 左移运算符，在低位补0）
a>>3 // "有符号"右移运算 符，值为正，则在高位补0，如果值为负，则在高位补1.
a>>>3 // "无符号"右移运算符，采用0扩展机制
2-6 排序
常识：Java中提供Comparable 和 Comparator二种方式定义排序规则。
- Comparator时JUC包中定义的，通常配合JUC的一些工具类，是策略模式的体现。
- Comparable通常用于类的内部排序规则的制定，在类定义的时候可以去实现Comparable接口
2-6-1 基本数据类型的的排序(util中的Arrays)
int[] array = {10, 3, 6, 1, 4, 5, 9};
int[] array = new int[]{1,2}; //数组对象另外一种初始化方法
Arrays.sort(array); // 对数组进行升序排列，暂时没有找到直接对一维数组逆序排列的方法
-------------------------------------------------------
迂回策略：将int [] 转换为 Integer [],然后实现Comparator或者结合使用Arrays.sort()与Collections.reverse();
---------------------------------------------------------
/*关于List接口,ArrayList、LinkedList和Vector*/
// class Cmp implements Comparator<Integer> {
// @Override
// public int compare(Integer o1, Integer o2) {
// return o2-o1;
// }
// }
2-6-2 自定义数据类型的排序
- util工具包中的Collections提供了排序方法
- 一维/二维数组使用Arrays进行排序，实现list接口的容器类使用Collections进行排序
基本思想：实现用于比较的接口Comparable<T>
排序规则：
0 本身大于目标对象
=0 本身等于目标对象
<0 本身小于目标对象
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.
------------------------------------------------------------------------------------
在类中实现排序规则
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降序,这里o是o2,this是o1, o2 < o1
else{
return this.w-o.w; // w升序, o1 - o2 < 0 即 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);
使用函数式接口实现排序规则
static class Mydata{
int w;
int h;
public Mydata(int w, int h) {
this.w = w;
this.h = h;
}
}
// 本质上还是实现comparable接口，这里只是利用语法糖简化写法
Arrays.sort(data,(o1,o2)->{
if(o1.w == o2.w)
return o2.h-o1.h;
else
return o1.w-o2.w;
});
利用一维数组对象结合函数式接口(排序貌似要比前二种慢一点，50ms左右)
- 注意Java的数组也是对象，二维数组由多个一维数组对象组成，s直接继承Object
- 可以通过定义规则，对二维数组按照行排序。
Arrays.sort(envelopes,(o1,o2)->{
if(o1[0] == o2[0])
return o2[1]-o1[1];
else
return o1[0]-o2[0];
});
2-7 Math类常用方法
abs(T)
Math.ceil(double a) // 向上取整用
Math.floor(double a) // 向上取整用
2-8 Arrays工具包常用方法（操纵数组）
static int[] copyOfRange(int[] original, int from, int to) // 拷贝数组的一部分
2-9 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) //转化为小写
三 常用的数据结构
1.vector与ArrayList与LinkedList都实现List接口。
2.LinkList实现了List与deque接口，因此可以作为双端队列。
3.stack是vector的派生类。
4.Stack在vector基础上添加了新的方法可以同等看待。
5 线程安全性:只有Vector,Stack是线程安全的，虽然是线程安全的，实践中很少使用，都会采用juc包实现。
6 物理存储方式：ArrayList与Vector与stack是用数组来实现的，LinkedList使用链表来实现.物理存
储方式导致在增删改等操作效率上的差异性。
7 ArrayList,Vector除了在线程安全方面的差异性，扩容机制也不同， ArrayList以1.5倍的方式在扩
容、Vector 当扩容容量增量大于0时、新数组长度为原数组长度+扩容容量增量、否则新数组长度为原数组长
度的2倍。
3-0 C风格的数组对象定义以及操作
- Java数组索引不能接受long型变量（编译会报错）
length // 无括号，可以获取数组的长度
new int[]{1,2}; // 定义一个数组对象
int[] tmp = new int[0]; // 定义一个长度为0的数组对象，区别于null
int[][] res; // res[0],res[1]本质上是一个一维数组对象
Arrays常用方法
/* T 可以是8种基本数据类型*/
static void sort(T a);
static void sort(T [] a, int fromIndex, int toIndex) // 左闭右开
------------------------------------------------------------------------------
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) // 二分查找，如果查找不到返回<0的索引
static int binarySearch(T [] a, int fromIndex, int toIndex, T key)
------------------------------------------------------------------------------
Arrays.copyOfRange(T [] a,int fromIndex, int toIndex); // 拷贝a的[index1,index2)范围的数组，返回一个新的数组
------------------------------------------------------------------------------
Arrays.equals(T[] a, T[] a2); // 比较2个数组是否每个元素都相同，T可以任意基本类型
3-1 Class ArrayList
3-1-1 基本用法
---------------------------------------------------------------------
0 一维动态数组的定义
ArrayList<String> array = new ArrayList<String>();
----------------------------------------------------------------------
02 二维动态数组定义
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); //
for(int i = 0;i < 3;++i)
res.add(new ArrayList<Integer>());
注意：无法通过ArrayList<ArrayList<Integer>> [] res = new ArrayList<ArrayList<Integer>>()[3];
----------------------------------------------------------------------
03 二维数组另外一种定义方法（数组中每一个元素都是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的常用方法
peek() // 检索但不删除此队列的头，如果此队列为空，则返回 null
poll() // 检索并删除此队列的头，如果此队列为空，则返回 null
add(E e) // 将指定的元素插入到此队列中， true在成功后返回 IllegalStateException如果当前
isEmpty()
size()
toArray()
remove(int index) // tmp.remove(tmp.size()-1);
E set(int index, E element) // 设置指定元素值
get(int index) // 获指定位置元素
for ( 变量类型 变量名 : 数组名 ) // 变量名中存储的是容器中的元素，如果不需要容器的下标，可以考虑这种方式
3-1-2 Java的ArrayList与普通数组的转换
/*一维数组与ArrayList的转换*/
String[] array = (String[])list.toArray(new String[list.size()]); // ArrayList<Object>--->Obejct[]
int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray(); //ArrayList ---> int[]
/*int[][] 与ArrayList<int[]>的转换*/
List<int []> res = new ArrayList<>(); // int[] 在java中也是一个object
res.toArray(new int[res.size()][]); // ArrayList<int[]> => int[][]
public class NestedIterator implements Iterator<Integer> {
// 存储列表的当前遍历位置
private Deque<Iterator<NestedInteger>> stack;
public NestedIterator(List<NestedInteger> nestedList) {
stack = new LinkedList<Iterator<NestedInteger>>();
stack.push(nestedList.iterator());
}
@Override
public Integer next() {
// 由于保证调用 next 之前会调用 hasNext，直接返回栈顶列表的当前元素
return stack.peek().next().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
Iterator<NestedInteger> it = stack.peek();
if (!it.hasNext()) { // 遍历到当前列表末尾，出栈
stack.pop();
continue;
}
// 若取出的元素是整数，则通过创建一个额外的列表将其重新放入栈中
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 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 PriorityQueue的使用
add(E e) // Inserts the specified element into this priority queue.
peek() // 查看队列队首元素，没有返回null
poll() // 返回并删除队首元素，没有返回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.
优先队列比较符进行重载
/*https://blog.csdn.net/weixin_43664907/article/details/112919754*/
/*优先队列默认是小顶堆，可以自己传入排序方法。大顶堆就传相反的排序方法就好了*/
PriorityQueue<Integer> myq_big = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
比较器原则
真正正确的理解：
jdk官方默认是升序，是基于：
< return -1
= return 0
> return 1
如果要降序就必须完全相反：
< return 1
= return 0
> return -1
3-3 TreeMap的使用
getOrDefault(Object key, V defaultValue) // 根据key查找键值，如果没有则返回defaultValue
K ceilingKey(K key) // >= key的最大key
K floorKey(K key) // <= key的最大key
V get(Object key) // 根据key查找value,否则返回null
V replace(K key, V value) // 返回之前的键值对，并替换为新的键值对。
boolean replace(K key,V oldValue,V newValue) // 替换成功返回True
Map容器的遍历
/*----------方式1------------------------*/
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
/*---------lambda接口------------------------*/
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按照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();
}
}
使用迭代器遍历与删除元素(重要)
Iterator<Map.Entry<String,String>> iterator = map.entrySet().iterator();//返回所有的entry实体
while (iterator.hasNext()) {
Map.Entry<String, String> next1 = iterator.next();
String key = next1.getKey();
String value = next1.getValue();
System.out.println(key+" "+value);
}
//通过键来遍历
Iterator iterator1 = map.keySet().iterator();
while (iterator1.hasNext()) {
System.out.println(iterator1.next());
}
//通过值来遍历
// 在遍历的过程中可以通过it.remove()来删除元素
Iterator iterator2 = map.values().iterator();
while (iterator2.hasNext()) {
System.out.println(iterator2.next());
}
451. 根据字符出现频率排序
3-4 Stack类的使用（早期遗留代码，不推荐使用）
boolean empty() // Tests if this stack is empty.
E peek() //
E pop() //
E push(E item) //
3-5 LinkList（双向链表）与ArrayDeque（栈/队列）的使用
- LinkedList：Doubly-linked list implementation of the
ListandDequeinterfaces. Implements all optional list operations, and permits all elements (includingnull). - 物理存储方式：ArrayList与Vector与stack是用数组来实现的
- ArrayDeque采用循环数组实现，采用栈或者队列使用这个类 参考
总结：双向链表用LinkList，栈和队列使用ArrayDeque
// 01 双向链表相关的方法(LinkedList)
public E removeFirst()
public E removeLast()
public void addFirst(E e)
public boolean remove(Object o) // 删除某一元素，返回是否成功,操作效率为O(1)
boolean addFirst(E e) // 等同于 addLast(E).
// 02 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属于过时类，直接使用ArrayList<Deque>替代）
Stack Method Equivalent Deque Method
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()
- 双端队列/队列/栈，尽量用ArrayDeque取代LinkList
3-6 HashSet的使用
基本方法
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.
自定义的类使用hashset
/*这里通过toString()得到类的字符串表示，然后调用hashcode方法生成hash值*/
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) {
// 判断2个引用是否指向同一实例
if (this == o) return true;
// 判断2个引用指向的实例的类是否相同
if (o == null || getClass() != o.getClass()) return false;
// 同一类，比较成员属性是否相同。
Node node = (Node) o;
return x == node.x &&
y == node.y;
}
}
使用
Set<Node> visited = new HashSet<Node>();
3-7 TreeSet的使用
boolean add(E e)
E ceiling(E e) // 寻找 >= e 的第一个元素，没有返回null
void clear()
boolean isEmpty()
E floor(E e) // 寻找 <= e 的第一个元素, 没有则返回null
int size()
=======================自定义element的比较规则=====================
TreeSet(Comparator<? super E> comparator) // Constructs a new, empty tree set, sorted according to the specified comparator.
四 数学工具类的使用
java.util.Random
Random random = new Random();
int randomIndex = left + random.nextInt(right - left+1);
Math.random():默认产生大于等于0.0且小于1.0之间的随机double型随机数
- Random.nextInt()方法，是生成一个随机的int值，该值介于[0,n)的区间，也就是0到n之间的随机int值，包含0而不包含n。
五 Java8中比较好用的流处理API
定义：A sequence of elements supporting sequential and parallel aggregate operations(支持序列化以及并行聚合的元素序列)
特点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.(流管道中包含有流操作)
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.
流的生成
在 Java8中，集合接口有两个方法来生成流: 1) stream() − 为集合创建串行流。
统计符合条件的元素
List<String> strings = Arrays.asList("abc", "", "bc", "efg", "abcd","", "jkl");
count = strings.stream().filter(string->string.isEmpty()).count();
System.out.println("空字符串数量为: " + count);
count = strings.stream().filter(string -> string.length() == 3).count();
System.out.println("字符串长度为 3 的数量为: " + count);
过滤并返回符合条件的元素
filtered = strings.stream().filter(string ->!string.isEmpty()).collect(Collectors.toList());
--------------------------------------------------------------------
mergedString = strings.stream().filter(string ->!string.isEmpty()).collect(Collectors.joining(", "));
System.out.println("合并字符串: " + mergedString);
集合对象与数组的转换
//ArrayList<包装类> ---> 基本数据列[]
int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray();
六 Java中的语法糖使用
6-1 for Each循环：
| 遍历方式 | 特点 | 动机 |
|---|---|---|
| 普通for循环 | 适合支持随机访问数据结构，比如ArrayList | 实现RandomAccess接口的类实例，假如是随机访问的，使用普通for循环效率将高于使用foreach循环，比如ArryList。 |
| 增强for循环（forEach） | 底层使用的仍然是迭代器，可以看成不能改变结构的迭代器循环 | 循环中不能增加或者减少元素，可以修改对象引用的指定对象的值（会对遍历的对象引用以及基本数据类型进行复制） |
| 迭代器遍历 | 适合顺序访问的数据结构，比如LinkedList | 统一方法调用，只要实现iterator接口，都可以调用 |
使用注意点：
迭代器：遍历方便，删除方便；（Iterator只有3个方法：hasNext()、next()、remove(),迭代过程中删除不能使用提供的普通的remove方法,可能会触发fail fast机制。
普通for：遍历时可删除，可修改；
增强for：本质上依旧是迭代器，如果只是遍历并且不修改可以用for增强，但是如果想在遍历中增加和删除，仍然需要使用迭代器。
使用实例
map.forEach((k, v) -> System.out.println("key: " + k + " value" + v));
// lambda表达式中仍然不能引用外部变量，只能引用effective final的变量。
常识
n^2 10^4
nlogn 10^7
n 10^8
n^4 30
2^n 20
整型数据范围
Integer:-2147483648 ~ 2147483647 2x10^9 (2^10 = 1024)
Long: -9223372036854775808 ~ 9223372036854775807 9x10^18
参考资料