初始化

1
2
3

String[] s = new String[3];    //初始化为null
int[] i = new int[3];          //初始化为0
boolean b = new boolean[3];    //初始化为false

字符

char

相等操作

c1 == c2;

运算

字符支持加减运算，但是不可以用 c = (char)('a' + (c - 'A'));，因为 Java 中字符（串）一旦声明就不能改变，这和 C/C++不一样。但是可以用新的变量保存字符：

1	new_c = (char)('a' + (old_c - 'A'));

string

常用函数

判断字符是否包含在字符串中

1	s.indexOf(c) != -1 //表示包含

判断字符串是否包含在字符串中

1	s1.contains(s2) //如果s2包含在s1中，则返回true

compareTo()比较

1	s1.compareTo(s2); //如果s1>s2，返回1；如果s1<s2，返回-1；如果相等，返回0

substring()截断：

1
2
3

s = s.substring(1,5);    //截取下标1~4

s = s.substring(5);   //截取下标为5~end

replace()替换

1	s = s.replace("-",""); //将全文的-变成无

equals()相等

1	s1.equals(s2);

split()分割

对于String s = "a b c d e f g"

分割单个空格

1	String[] sa = s.split(" ");

//a // //b // // // // //c // //d //e //f // // // // // //g //

分割多个连续空格

1	String[] sa = s.split("\\s+"); //正则

//a //b //c //d //e //f //g

字典序排序

1
2
3

char[] sc = s.toCharArray();
Arrays.sort(sc);
s = new String(sc);

常用转换

字符➡️字符串

将单个字符转为字符串

1	String st = String.valueOf('a');

将字符数组转为字符串

1	String s = String.valueOf(sa1);

或者

1	String s = new String(sa1);

字符串➡️字符

提取完整数组

1	char[] str = s.toCharArray();

提取字符串中某一下标的字符

1	char st = s.charAt(3);

字符➡️整数

1	int n = '5' - '0';

整数➡️字符串

1	String s = String.valueOf(3);

整数➡️字符

1 2	String s = String.valueOf(3); char c = s.charAt(0);

字符串➡️整数

使用Integer.parseInt(s)

1 2	String s = "12345"; int b = Integer.parseInt(s);

StringBuilder

String内容是不可变的，StringBuilder内容是可变的

StringBuilder处理字符串性能比String好

创建

1	StringBuilder sb = new StringBuilder();

插入

尾部插入

1	sb.append("wry");

中间插入

1	sb.insert(0,'w'); //在下标为0之前插入字符w

长度

1	int n = sb.length();

删除

1	sb.delete(6, 14); //删除下标为[6,14)

转换

StringBuilder转为String

1	String s = sb.toString();

String转为StringBuilder

1	StringBuilder sb = new StringBuilder(s);

数组

赋值

1	Arrays.fill(nums, Integer.MAX_VALUE); //对数组进行一次性赋值

自定义排序

Arrays.sort(logs, new Comparator<int[]>() {
	public int compare(int[] l1, int[] l2) {
		return l1[0]-l2[0];    //结果为1表示l1和l2调换
	} 
});

排序+去重

使用Stram 流

1	arr = Arrays.stream(arr).sorted().distinct().toArray();

判断相等

1 2	// 判断两个数组是否一样 Arrays.equals(arr1, arr2);

拷贝

深拷贝

1	System.arraycopy(原数组, 原数组起点, 新数组, 新数组起点, 长度);

list

List本质上就是动态数组

构建

对于单个List

1	List<String> l = new ArrayList<String>();

1	List<Integer> r = new ArrayList<Integer>();

不推荐 ArrayList<String> al = new ArrayList<String>();

对于嵌套List⭐

1	List<List<String>> ll = new ArrayList<>();

1	List<List<Integer>> result = new ArrayList<>();

初始化

// 将nums转为list
List<Integer> list = new ArrayList<>(nums);

// 将旧list的内容赋给新list（深拷贝）
List<Integer> list2 = new ArrayList<>(list1);

添加

对于单个List

1	list1.add(r); //r必须是list的<>内的类型，在尾部插入

对于嵌套List

1	res.add(new ArrayList<>(path));

搜索

1	list1.get(index); //获取list下标为index的数值

查找某个元素是否在其中

1	list.contains(s); //查找s这个元素是否在list中

数组➡️List

Arrays. asList 将数组转化成 List 集合，但是得到的 List 的长度是不可改变的。

1	res.add(Arrays.asList(x,y)); //在嵌套list（res）中加入一个由x、y两个元素构成的list

注意：
（1）该方法适用于对象型数据的数组（String、Integer...）
（2）该方法不建议使用于基本数据类型的数组（byte, short, int, long, float, double, boolean）
（3）该方法将数组与 List 列表链接起来：当更新其一个时，另一个自动更新
（4）不支持 add ()、remove ()、clear () 等方法

动态数组 ArrayList

构建

1	ArrayList<Integer> al = new ArrayList<Integer>();

添加

1	al.add(2); //将整数2加入动态数组

定点添加

1	al.add(2,1); //将整数1加入动态数组的2的位置（作为第三个元素）（第一个是index，第二个是元素值）

替换

1	al.set(2,3); // 将下标为2的元素替换为数字3

删除

1	al.remove(1); //删掉第二个元素

输出

1	res = al.get(1); //获取下标为1的元素的值

长度

1	int l = al.size();

排序

升序排序（从小到大）

1	Collections.sort(list);

降序排序（从大到小）🌟

Collections.sort(list, new Comparator<Integer>() {
	public int compare(Integer n1, Integer n2) {
		return n2-n1;     //如果return>0则对调
	}
});

Deque双端队列

两端都可以进出，FIFO（先进先出）

构造

注意：ArrayDeque<>比 LinkedList 更快力扣

1	Deque<Integer> dq = new LinkedList<>();

操作

端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

	第一个元素 (头部)		最后一个元素 (尾部)
	抛出异常	特殊值	抛出异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

Deque与Queue的对照

Queue方法	等效Deque方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

堆栈方法	等效Deque方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

但是Java没有栈，只能用Deque双端队列代替。

需要多次使用的方法：

//创建
Deque<String> dq = new LinkedList<>();

//增加
dq.addLast(st);

//弹出并返回
String temp = dq.pollLast();

Stream流

Stream流是Java8开始有的一个很装逼的功能，可以对流直接进行操作。

46使用了：

List<List<Integer>> res = new ArrayList<>();
int[] nums;

res.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));

请注意，这里的res存的时Integer的集合(列表)，但是num时int类型的，曾经说到过int转为Integer可以用：

1	Integer b = Integer.valueOf(a);

但是这个方法很不好，而Java8的流操作可以处理：

Arrays.stream(nums)表示将数组nums转为流
.boxed()表示将流的类型提升，比如int变成Integer等等
.collect(Collectors.toList())基本是流操作必备的结尾，表示将流转为List集合类型

此外，流操作还有很多其他的用法：

全面吃透JAVA Stream流操作，让代码更加的优雅 (baidu.com)

开始管道

主要负责新建一个Stream流，或者基于现有的数组、List、Set、Map等集合类型对象创建出新的Stream流。

中间管道⭐

负责对Stream进行处理操作，并返回一个新的Stream对象，中间管道操作可以进行叠加。

终止管道

顾名思义，通过终止管道操作之后，Stream流将会结束，最后可能会执行某些逻辑处理，或者是按照要求返回某些执行后的结果数据。

数组转为 list

1	List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());

链表

Java语言使用链表格式：

class MyLinkedList {
    static class Node {
        int val;
        Node pre;
        Node next;
        public Node() {
        }
        public Node(int val) {
            this.val = val;
        }
    }

    Node head;
    int size=0;

    public MyLinkedList() {
        head = new Node();
        head.next = head;
        head.pre = head;
    }
    
    public int get(int index) {
        Node node = head;
        //......
    }
    //......
}

//调用
MyLinkedList linkedList = new MyLinkedList();
linkedList.get(1);

HashMap（散列表）

创建

1	HashMap<String,Integer> hash = new HashMap<String,Integer>();

添加键值对

key 如果已经存在，则 value 会直接覆盖。

1	hash.put("abc",2);

删除键值对

1	hash.remove("abc");

查找值

1	hash.get("abc"); //输出2

更新值

1	hash.replace("abc",3); //以后hash里面"abc"对应的value就是3

1	hash.replace("abc",2,3); //只对hash键值对为"abc"-2的修改value为3，如果键值对不符合则返回false

查找键值对数量

1	hash.size()

判断是否为空

1	hash.isEmpty() //如果为空返回true

判断是否有某个key

1	hash.containsKey("abc") //如果有则返回true

判断是否有某个value

1	hash.containsValue(3) //如果有则返回true

遍历⭐

//方法一、forEach
hash.forEach((key,value)-> {
    //对于每一组key和value的操作
    String s = value.toString() + key;
    res.add(s);
});    //不要忘记分号

//方法二、最推荐，遍历entey获取key和value
for (Map.Entry<String,Integer> entry : hash.entrySet()) {  //entrySet()返回hashMap中所有映射项的集合集合视图。
    String key = entry.getKey();
    Integer value = entry.getValue();
}

//方法三、单独取出key和value
for (String key : hash.KeySet()) {    //keySet()返回hashMap中所有key组成的集合视图。
    //对key操作
}
for (String value : hash.values()) {    //values()返回hashMap中所有value组成的集合视图。
    //对key操作
}

删除所有键值对

1	hash.clear();

获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值

1	value = hash.getOrDefault(key,defaultvalue); //如果key存在，则相当于get()；如果key不存在，则返回的是defaultvalue

🌟如果 key 存在，则将原始值+1；如果 key 不存在，则加入（value 设置为 1）

1	hash.put(key, hash.getOrDefault(key,0)+1)

Set 集合

时间复杂度 \(n\)

Set 表示唯一对象的集合。集合中元素的排序是不相关的。

HashSet

HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

HashSet 允许有 null 值。

HashSet 是无序的，即不会记录插入的顺序。

HashSet 实现了 Set 接口。（这就是为什么这个解法可以使用 Set<Long> set = new HashSet<>();）

Set 对象的创建：

1	Set<Long> set = new HashSet<>();

Set 对象的添加操作：

1	set.add(6);

Set 对象的判断是否存在操作：

1	set.contains(k) //判断k这个值在set中是否存在，存在则返回true

Set 判断一个 set 集合是否包含在另一个集合中：

1	set1.containsAll(set2) //set2是否是set1的子集

合并 set

1	set1.addAll(set2); // 将set2中的所有元素加入set1中

删除

1	set.remove(6); // 删除6这个元素

Set 清空功能

1	set.clear();

小根堆

时间复杂度：\(O(log(n))\)

创建：

1	PriorityQueue<Long> q = new PriorityQueue<>();

添加操作：

q.add(5);

判断是否为空：

1	q.isEmpty() //如果是空则返回true

弹出操作（弹出最小的数，并返回此数）：

1	long t = q.poll();

大根堆

创建

1 2	//如果b>a，则返回正值，表示顺序要替换 PriorityQueue<Integer> q = new PriorityQueue<Integer>((a,b)->b-a);

复杂构建

//如果a[1]-a[0]大的放在根节点
PriorityQueue<int[]> q = new PriorityQueue<int[]>((a,b)->{
	int x = a[1]-a[0];
	int y = b[1]-b[0];
	return y-x;   
});

添加

1
2
3

q.add(5);
//或者
q.offer(5);

弹出

1	q.poll(); //弹出最大（最小）的元素

长度函数

length：数组长度
length()：字符串长度
size()：列表长度
int转为Integer
1
2
int a;
Integer b = Integer.valueOf(a);

数组的排序

1	Arrays.sort(nums); //原地修改nums数组

位运算

操作符	描述	例子
＆	如果相对应位都是 1，则结果为 1，否则为 0	（A＆B），得到 12，即 00001100
\|	如果相对应位都是 0，则结果为 0，否则为 1	（A\|B）得到 61，即 00111101
^	如果相对应位值相同，则结果为 0，否则为 1	（A^B）得到 49，即 00110001
〜	按位取反运算符翻转操作数的每一位，即 0 变成 1，1 变成 0。	（〜A）得到-61，即 11000011
<<	按位左移运算符。左操作数按位左移右操作数指定的位数。	A<<2 得到 240，即 11110000
>>	按位右移运算符。左操作数按位右移右操作数指定的位数。	A>>2 得到 15 即 1111
>>>	按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。	A>>>2 得到 15 即 00001111

并查集

模板题： #1971

模板代码

```java
class Solution {

    public int find(int[] bc, int x) {
        if (bc[x]!=x) {   
            bc[x] = find(bc,bc[x]);   
        }
        return bc[x];    
    }

    public void union(int[] bc, int x, int y) {
	    int rootx = find(bc,x);
	    int rooty = find(bc,y);
        if (rootx==rooty) {
            return ;
        }
        else {
            bc[rootx] = rooty;
        }
    }
    
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        int[] bc = new int[n];
        for (int i=0;i<n;i++) {
            bc[i] = i;        // 初始每个节点的根就是自己
        }
        //...
    }
}

有序集合 TreeSet⭐

时间复杂度 \(log(n)\)

TreeSet 是一个有序集合，它扩展了 AbstractSet 类并实现了 NavigableSet 接口。

它存储唯一的元素
它不保留元素的插入顺序
它按升序对元素进行排序
它不是线程安全的

title: 排序原理
TreeSet 存储对象的时候，可以排序，但是需要指定排序的算法  
- Integer 能排序 (有默认顺序)，String 能排序 (有默认顺序)，自定义的类存储的时候出现异常 (没有顺序)  
	- 对于数字直接是按从小到大顺序排序
	- 对于字符串需要使用iterator()进行排序
		```java
		public class TreeSetTest {
		    public static void main(String[] args) {
		        Set ts = new TreeSet();
		        ts.add("abc");
		        ts.add("xyz");
		        ts.add("rst");
		        Iterator it = ts.iterator();    //重点
		        while (it.hasNext()) {
		            System.out.print(it.next());
		            System.out.print(" ");
		        }
		    }
		}
		//abc rst xyz

如果想把自定义类的对象存入 TreeSet 进行排序，那么必须实现 Comparable 接口
在类上 implement Comparable
重写 compareTo() 方法
在方法内定义比较算法, 根据大小关系，返回正数负数或零
在使用TreeSet存储对象的时候，add()方法内部就会自动调用compareTo()方法进行比较，根据比较结果使用二叉树形式进行存储
1
2
3
4
5

## 创建

```java
TreeSet<Integer> set = new TreeSet<>();

添加

1	set.add(2);

删除

1	set.remove(3); //将元素3删除

清空

1	set.clear();

查询元素数量

1	set.size();

判空

1	set.isEmpty();

判断存在

1	set.contains(3); //判断3元素是否存在

返回首个元素

1	set.first();

返回最后元素

1	set.last()

返回小于指定值的 TreeSet 的元素

1	set.headSet(2); //返回小于2的

返回大于指定值的 TreeSet 的元素

1	set.tailSet(2); //返回大于2的

迭代器 iterator () 遍历🌟

返回类型为 Iterator ，它以升序返回 TreeSet 元素。

例子：

import java.util.*;
 
public class IteratorOfTreeSet {
    public static void main(String[] args) {
        TreeSet <String> tree_set = new TreeSet<String>();
        tree_set.add("C");
        tree_set.add("C++");
        tree_set.add("JAVA");
        tree_set.add("PHP");
        tree_set.add("SFDC");

        System.out.println("TreeSet: " + tree_set);
        
        System.out.println("tree_set.iterator(): ");
        for (Iterator itr = tree_set.iterator(); itr.hasNext();)
            System.out.println(itr.next());
    }
}

//TreeSet: [C, C++, JAVA, PHP, SFDC]
//
//tree_set.iterator():
//C
//C++
//JAVA
//PHP
//SFDC

二分查找

模拟 C++的 lower_bound() 和 `upper_bound()

大于等于target

// 能找到 k 最好，找不到就找稍微大一点的  
public static int findBigger (int k) {  
	int l=0,r=nums.length-1;  
	while (l<r) {  
		int m = (l + r) / 2;  
		if (nums[m]<k) {  
			l = m+1;  
		}  
		else {  
			r = m;  
		}  
	}  
	return l;  
}

小于等于target

// 能找到k最好，找不到就找稍微小一点的  
public static int findSmaller(int k) {  
	int l=0, r=nums.length-1;  
	while (l<r) {  
		int m = (l + r + 1) / 2; // 向上取整  
		if (nums[m]<=k) {  
			l = m;  
		}  
		else {  
			r = m - 1;  
		}  
	}  
	return l;  
}