Java刷题

Java

2024年 Java 面试八股文（20w字）_java八股文2023-CSDN博客

SQL

SQL 50 题（MySQL 版，包括建库建表、插入数据等完整过程，适合复习 SQL 知识点）_sql50题-CSDN博客

SQL常见语句及用法_sql语句大全及用法-CSDN博客

SQL中的 聚合函数 ,where ,having_where后面可以跟聚合函数吗-CSDN博客

Spring

面试被问了几百遍的 IOC 和 AOP ，一篇文章带你搞清楚！！！_ioc和aop的原理面试-CSDN博客

Sentinel

sentinel （史上最全）-CSDN博客

Gradle&Maven

gradle中的build script详解_gradle buildscript-CSDN博客

[Gradle和Maven的区别-CSDN博客](https://blog.csdn.net/weixin_45626288/article/details/131973787?ops_request_misc={"request_id"%3A"172024305816800185819613"%2C"scm"%3A"20140713.130102334.."}&request_id=172024305816800185819613&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-131973787-null-null.142^v100^pc_search_result_base8&utm_term=gradle maven&spm=1018.2226.3001.4187)

线程池和锁

面试+基础-----详细解读多线程（线程池、锁、死锁…）_多线程井发、死锁问题、线程池原理等-CSDN博客

Java 多线程：彻底搞懂线程池_java线程池-CSDN博客

Netty

【硬核】肝了一月的Netty知识点-CSDN博客

超详细Netty入门，看这篇就够了！_netty框架-CSDN博客

JUnit

JUnit详解-CSDN博客

Pytest

Python测试框架之pytest详解_pytest框架详解-CSDN博客

Docker

docker入门，这一篇就够了。-CSDN博客

docker run [可选参数] image 命令 #启动容器（无镜像会先下载镜像）
#参数说明
–name = “Name” 容器名字
-c 后面跟待完成的命令
-d 以后台方式运行并且返回ID，启动守护进程式容器
-i 使用交互方式运行容器，通常与t同时使用
-t 为容器重新分配一个伪输入终端。也即启动交互式容器
-p 指定容器端口 -p 容器端口:物理机端口 映射端口
-P 随机指定端口
-v 给容器挂载存储卷

JVM

[JAVA内存分配原理解析–栈、堆、常量池_堆,栈,常量池详解-CSDN博客](https://blog.csdn.net/gb702250823/article/details/92801716?ops_request_misc={"request_id"%3A"171151029816800225558425"%2C"scm"%3A"20140713.130102334.."}&request_id=171151029816800225558425&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-92801716-null-null.142^v100^pc_search_result_base2&utm_term=java 常量池 栈 堆&spm=1018.2226.3001.4187)

java的垃圾回收(GC)详解_java gc-CSDN博客

Java - 类加载器_java类加载器-CSDN博客

常用数据结构和库

java刷题前常用的数据结构及方法_java刷题常用方法-CSDN博客

ACM模式

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
    
    }
}

输入输出

1、输入整数、字符串数组
第一行输入n, m

第二行输入n个整数

第三行输入m个字符串

//导入包
import java.util.Scanner;
import java.util.Arrays;

public class MyScanner {
public static void main(String[] args) {
	
	//创建对象
	Scanner sc = new Scanner(System.in);		
	System.out.println("输入数据:");	
	//多行输入
	int n = sc.nextInt();
	int m = sc.nextInt();
	int[] arr = new int[n];	
	String[] str = new String[m];
	
	//int等基本数据类型的数组,用nextInt()，同行或不同都可以
	for(int i=0; i<n; i++) {
		arr[i] = sc.nextInt();
	}
	//String字符串数组, 读取用next()，以空格划分
	for(int i=0; i<m; i++) {
		str[i] = sc.next();
	}
	
    //调用方法进行操作
	TestSc(n, m, arr);
	TestStr(str);
	
	System.out.println("Test01 End");
	
	//关闭
	sc.close();
}

public static void TestSc(int n, int m, int[] arr) {
	System.out.println("数据n：" + n + ", 数据m：" + m);
	System.out.println(Arrays.toString(arr));
}

public static void TestStr(String[] str) {
	System.out.println(Arrays.toString(str));
}
}

若输入的字符串中想要包含空格，使用scanner.nextLine()换行后用scanner.nextLine()进行读入，见情形7.

2、输入二维数组
第一行输入n, m

第二行开始输入二维数组。

import java.util.Arrays;
import java.util.Scanner;

public class MyScanner2 {
public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);		
	System.out.println("输入数据:");	
 
	//二维数组
	int n = sc.nextInt();
	int m = sc.nextInt();
	int[][] arr2 = new int[n][m];	
	System.out.println("Test02 输入二维数组数据：");
 
	//可以直接读入
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			arr2[i][j] = sc.nextInt();
		}
	}
 
	TestSc(n, m, arr2);
	//关闭
	sc.close();
}

public static void TestSc(int n, int m, int[][] arr) {
	System.out.println("数据n：" + n + ", 数据m：" + m);
	for(int i=0; i<n; i++) {
		System.out.println(Arrays.toString(arr[i]));
	}
	System.out.println("数组行数： arr.length= "+ arr.length);
	System.out.println("数组列数： arr[0].length= "+ arr[0].length);
}
}

3、输入字符串
输入字符串，用空格隔开。

next()和nextLine()区别。

import java.util.Scanner;
/*
*next()读取到空白停止，在读取输入后将光标放在同一行中。
*nextLine()读取到回车停止 ，在读取输入后将光标放在下一行。
*/

public class MyScanner3 {
public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);		
	System.out.println("输入字符串:");		
	
	//next():只读取输入直到空格。
	String str = sc.next();
 
	//nextLine():读取输入，包括单词之间的空格和除回车以外的所有符号
	String str2 = sc.nextLine();
 
	System.out.println("str：" + str);
	System.out.println("str2：" + str2);
	
	//关闭
	sc.close();
}
}

4、输入字符串分割为数组
先用scanner.nextLine()读入字符串，再将字符串分割为字符数组或字符串数组。

import java.util.*;

public class MyScanner4 {
public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);	
	System.out.println("输入字符串数组：");
	
	String str;
	str = sc.nextLine();
	
	char[] ch = new char[str.length()];
	for(int i=0; i<str.length(); i++) {
		//用charAt();进行定位分隔
		ch[i] = str.charAt(i);
		System.out.println(ch[i] + " ");
	}
	System.out.println("END");
	
	//读入字符串后,用空格分隔为数组
	String[] strs = str.split(" ");
	System.out.println(Arrays.toString(strs));
 
}
}

5、连续输入数字和字符串
区别于情形1，对于不能采用for循环的方式获取String。采用情形5,6用来处理。

采用while(scanner.hasNext()) 循环，实现连续输入。

格式：数字，空格，字符串。

或： 数字，回车，字符串

import java.util.Scanner;

public class MyScanner5 {
public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	while(sc.hasNext()) {					
		int n = sc.nextInt();
		String str = sc.next();
		Tes(n, str);
	}
		
	sc.close();
}

public static void Tes(int n, String str) {
	System.out.println("n = " + n);
	System.out.println("str = " + str);	
	System.out.println("str.length = " + str.length());
}
}

6、换行输入数字和字符串
也采用scanner.nextLine()，将光标移到下一行。再继续读入字符串。

第一行输入整数n，m，第二行开始输入字符串。或

第一行输入整数n，第二行输入m，第三行开始输入字符串。

import java.util.*;

public class MyScanner6 {
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	
	//注意！！！光标换到下一行
	sc.nextLine();
	
	String s = sc.nextLine();
	String str = sc.nextLine();
	
	System.out.println("n = " + n + " , m = " + m);
	System.out.println("s = " + s);
	System.out.println("str = " + str);
			
	sc.close();
}
}

7、换行输入数字和字符串(需要包含空格)
采用scanner.nextLine()，将光标移到下一行。再继续读入字符串。

第一行输入n，

第二行开始输入n行字符串，字符串中包含空格。

import java.util.Scanner;
public class MyScanner7 {
public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	int n = sc.nextInt();
	String[] strs = new String[n]; 
	
	sc.nextLine();
	
	for(int i=0; i<n; i++) {
		String str = sc.nextLine();
		strs[i] = str;			
	}
	
	Tes2(strs);
	System.out.println("End");		
	sc.close();
}
public static void Tes2(String[] strs) {
	for(int i=0; i<strs.length; i++) {
		String str = strs[i];
		System.out.println(str);
	}
}
}

int 转Integer

int num=1;

Integer i = Integer.valueOf(num);

Integer转int

int num = integer.intValue();

int到String数据类型的转换

int num;

Integer.toString(num);

或者String.valueOf(num);

public class HelloWorld {
  public static void main(String[] args) {
   // 引号带上数据
    int num=100;
    String a=""+num;
    System.out.println(a);
   // 直接类型转换
    Integer num2=100;
    String b=Integer.toString(num2);
    System.out.println(b);
    
    
    // 字符串定义
    String c=String.valueOf(num2);
    System.out.println(c);
}
}

String到int类型的转换

String s = "100"

int d = Integer.parseInt(s);
    // parseInt
    // 加上static的方法，方法属于类，需要使用类名进行调用，没有加上static的，方法属于对象，可以new一个对象再调用
    int e=Integer.parseInt(s);
    System.out.println(e);

ArrayList动态转换为Array数组

String [] array=list.toArray(new String[size]);

除此之外，ArrayList还有以下的常用的方法：

void add(int index, E element) 将指定元素插入此列表中的指定位置。
boolean add(E e)将指定的元素追加到此列表的末尾。
boolean contains(Object o)如果此列表包含指定的元素，则返回 true 。
E get(int index) 返回此列表中指定位置的元素。
int indexOf(Object o) 返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
boolean isEmpty() 如果此列表不包含任何元素，则返回 true 。
int lastIndexOf(Object o)返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。
E remove(int index) 删除此列表中指定位置的元素。
boolean remove(Object o)从该列表中删除指定元素的第一个匹配项（如果存在）
E set(int index, E element) 用指定的元素替换此列表中指定位置的元素。
int size() 返回此列表中的元素数。

Array数组转为ArrayList

List<String>list= Arrays.asList(array)

Arrays的常用方法

//创建数组
int nums[]=new int[100];
//获取长度
nums.length;

Arrays.toString(nums)
Arrays.sort(nums)//升序
Arrays.fill(nums)//初始化数组的时候会用到（比如全部给-1）
Arrays.equal(nums)
Arrays.copyof(nums)
Arrays.compare(nums)
Arrays.binarySearch(nums)

Arrays.sort()重写Comparator:

//合并区间的例子
Arrays.sort(nums,new Comparator<int []>(){
    public int compare(int[]nums1, int[]nums2){
        return nums1[0]-nums2[0];
    }
});

ArrayList的常用用法

Array：只可存储基本数据类型和对象。被设置为固定大小。所包含的方法没有ArrayList多
ArrayList：只能存储对象。是一个可变数组，大小可自动调整。有很多操作方法：addAll、removeAll、iteration等。

//添加元素
ArrayList list = new ArrayList();
list.add("迪丽热巴");
ArrayList<String> sites = new ArrayList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        sites.remove(3); // 删除第四个元素
//计算大小
sites.size();
//排序
Collections.sort(sites);
//是否包含
sites.contains();
//addAll()
这个方法括号中类型是list，拼接
    
void add(int index, E element) 将指定元素插入此列表中的指定位置。
boolean add(E e)将指定的元素追加到此列表的末尾。
boolean contains(Object o)如果此列表包含指定的元素，则返回 true 。
E get(int index) 返回此列表中指定位置的元素。
int indexOf(Object o) 返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
boolean isEmpty() 如果此列表不包含任何元素，则返回 true 。
int lastIndexOf(Object o)返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。
E remove(int index) 删除此列表中指定位置的元素。
boolean remove(Object o)从该列表中删除指定元素的第一个匹配项（如果存在）
E set(int index, E element) 用指定的元素替换此列表中指定位置的元素。
int size() 返回此列表中的元素数。

Collections类

对list进行反转

Collections.reverse(list)
Collections.sort(numbers); //List列表按照升序排列
Collections.binarySearch(numbers, 3); //numbers是List且按升序排列
Collections.swap(numbers, 2,4); //交换numbers的list的Index为2、4的数字

String类

String获取长度是.length()（要加括号）

String、StringBuilder类超详细笔记_stringbuilder可以用equalsignorecase-CSDN博客

重要：char charAt​(int index) 返回指定索引处的 char值。
int indexOf​(String ch) 返回指定字符第一次出现的字符串中的索引。
    String s = String.valueOf('c'); //效率最高的方法
- boolean isEmpty() ，当且仅当， length()是 0 返回 true
int lastIndexOf​(int ch) 返回指定字符最后一次出现的字符串中的索引。
int length() 返回此字符串的长度。
    String trim() 去除两端的空格
String replace​(CharSequence target, CharSequence replacement) 将此字符串中与文字目标序列匹配的每个子字符串替换为指定的文字替换序列。
String replaceAll​(String regex, String replacement) 将给定替换的给定 regular expression匹配的此字符串的每个子字符串替换。
String[] split​(String regex) //将此字符串拆分为给定 regular expression的匹配 项 。（如果有多个空格，则会在Arrays中有空的""出现）
boolean startsWith​(String prefix) 测试此字符串是否以指定的前缀开头。
String substring​(int beginIndex) 返回一个字符串，该字符串是此字符串的子字符串。
char[] toCharArray() 将此字符串转换为新的字符数组。
String toLowerCase() 使用默认语言环境的规则将此 String所有字符转换为小写。
String toUpperCase() 使用默认语言环境的规则将此 String所有字符转换为大写。
比较大小的话
    String c= "123";
	String b = "123";
	c.compareTo(b);
或者
    c.equals(b);

字符类Chracter

//char转Character
Character.valueOf('I');
Character.compare(char x, char y) 以数字方式比较两个 char值。
Character.equals(Object obj) 将此对象与指定的对象进行比较。
Character.isDigit(char ch) 确定指定的字符是否为数字。
Character.isLetter(char ch) 确定指定的字符是否为字母。
Character.isLowerCase(char ch) 确定指定的字符是否为小写字符。
Character.isUpperCase(char ch) 确定指定的字符是否为大写字符。
Character.toString(char c) 返回表示指定的 char的 String对象。
Character.valueOf(char c) 返回表示指定的 char值的 Character实例。
Character.toLowerCase("A"); 转为小写
Character.toUpperCase("a"); 转为大写
//char数组转String
char[] data = new char[] {'a','b','c'};
String str = new String(data);
System.out.println(str);  //输出abc

字符串构造器StringBuilder

Java-修改 String 指定位置的字符最全方法总结（StringBuilder 和 StringBuffer 的使用以及区别）_string替换指定位置字符-CSDN博客

String、StringBuffer与StringBuilder之间区别_string stringbuffer stringbuilder区别-CSDN博客

可变字符串，StringBuilder对象的内容可以修改。

1. StringBuilder类的常用方法

   1. append()方法
      使用append()方法可实现字符串的拼接操作，返回拼接后的StringBuilder对象。

   2. reverse()方法
      使用reverse()方法可实现StringBuilder字符串的反转操作。

   3. delete(int start, int end)方法
      删除字符串中指定索引范围为 [start,end) 的所有内容。

      Java中大多数范围均为左闭右开区间。

      StringBuilder sb = new StringBuilder("hello");
      sb.append("world");
      sb.delete(5,8);  //删除索引范围为[5,8)内的所有内容，即从w开始删除到l之前
      System.out.println(sb);  //输出hellold

   4. insert(int start, 任意数据类型)方法
      在索引start处开始插入任意数据类型的内容。插入内容的起始索引是start。

      StringBuilder sb1 = new StringBuilder("hello");
      sb1.insert(2,77);
      System.out.println(sb1);  //输出he77llo
      sb1.insert(3,"ooo");
      System.out.println(sb1);  //输出he7ooo7llo

   5. setCharAt(index,character)

      sb.setCharAt(j,Character.toUpperCase(sb.charAt(j)));

2. StringBuilder与String的相互转换
   1）String转为StringBuilder
   ① 构造方法StringBuilder(String str)

StringBuilder sb = new StringBuilder("hello"); 

② 字符串拼接方法append(String str)

StringBuilder sb = new StringBuilder();
sb.append("123");

2）StringBuilder转为String
通过StringBuilder对象调用toString()方法

String str = sb.toString();
String、StringBuilder、StringBuffer的区别
String为不可变字符串类，StringBuilder、StringBuffer为可变字符串类。
StringBuilder类性能较高，但存在线程安全问题; StringBuffer类线程安全，但性能较差。

双链表LinkedList

boolean isEmpty()
int size()
boolean contains(Object o) // 判断链表中是否存在元素o 复杂度O(N)
void addFirst(E e)
E removeFirst() //删除，返回的是删除的元素
E getFirst/Last()
int indexOf( E e)
Collections.reverse(link); // 翻转链表

哈希表Hashmap

boolean containsKey(Object key)如果这个映射包含指定键映射，则返回true
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true 。
V get(Object key) 返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
V put(K key, V value) 将指定的值与此映射中的指定键相关联。
V remove(Object key) 从此映射中删除指定键的映射（如果存在）。
int size() 返回此映射中键 - 值映射的数量。
Collection<V> values() 返回此映射中包含的值的Collection视图。
Set<K> keySet() 返回此映射中包含的键的Set视图。
default V getOrDefault(Object key, V defaultValue) 返回指定键映射到的值，如果此映射不包含键的映射，则返回 defaultValue 。这个方法继承自Map接口
default V putIfAbsent(K key, V value) 如果key存在则什么都不做，否则put()，并且返回当前值
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射的Set视图。
    
/* 初始化哈希表 */
Map<Integer, String> map = new HashMap<>();

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");   
map.put(15937, "小啰");   
map.put(16750, "小算");   
map.put(13276, "小法");
map.put(10583, "小鸭");

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
String name = map.get(15937);

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);

/* 遍历哈希表 */
// 遍历键值对 key->value
for (Map.Entry <Integer, String> kv: map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// 单独遍历键 key
for (int key: map.keySet()) {
    System.out.println(key);
}
// 单独遍历值 value
for (String val: map.values()) {
    System.out.println(val);
}

哈希集合HashSet

[【Java 基础篇】Java Set 详解-CSDN博客](https://blog.csdn.net/qq_21484461/article/details/131383848?ops_request_misc={"request_id"%3A"171015290416800180682690"%2C"scm"%3A"20140713.130102334.."}&request_id=171015290416800180682690&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-131383848-null-null.142^v99^pc_search_result_base2&utm_term=Java set&spm=1018.2226.3001.4187)

不能保证集合迭代的顺序

boolean add(E e) 如果指定的元素尚不存在，则将其添加到此集合中。
boolean remove(Object o) 如果存在，则从该集合中移除指定的元素。
boolean contains(Object o) 如果此set包含指定的元素，则返回 true 。

栈 Stack

栈，后进先出

/* 初始化栈 */
Stack<Integer> stack = new Stack<>();

/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* 访问栈顶元素 */
int peek = stack.peek();

/* 元素出栈 */
int pop = stack.pop();

/* 获取栈的长度 */
int size = stack.size();

/* 判断是否为空 */
boolean isEmpty = stack.isEmpty();

队列Queue、双端队列Deque（都可用LinkedList来实例化，因为二者都是接口）

队列，先进先出，Queue和Deque都是接口，而LinkedList类继承了这两个队列，可以是用LinkedList来实例化Queue或者Deque，可以作为单向队列或者双向队列来使用。

Queue q = new LinkedList<>();
void add(int index, E element) 将指定元素插入此列表中的指定位置。
E element() 检索但不删除此列表的头部（第一个元素）。
E get(int index) 返回此列表中指定位置的元素。
int indexOf(Object o) 返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
int lastIndexOf(Object o) 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。
boolean offer(E e) 将指定的元素添加为此列表的尾部（最后一个元素）。
E peek() 检索但不删除此列表的头部（第一个元素）
E poll() 检索并删除此列表的头部（第一个元素）。
E set(int index, E element) 用指定的元素替换此列表中指定位置的元素。
/* 翻转队列 */
Collections.reverse(queue) 
/* 获取队列的长度 */
int size = queue.size();
/* 判断队列是否为空 */
boolean isEmpty = queue.isEmpty();

双端队列

/* 初始化双向队列 */
Deque<Integer> deque = new LinkedList<>();

/* 元素入队 */
deque.offerLast(2);   // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // 添加至队首
deque.offerFirst(1);

/* 访问元素 */
int peekFirst = deque.peekFirst();  // 队首元素
int peekLast = deque.peekLast();    // 队尾元素

/* 元素出队 */
int popFirst = deque.pollFirst();  // 队首元素出队
int popLast = deque.pollLast();    // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
boolean isEmpty = deque.isEmpty();

…

LinkedList可以作为堆栈使用，并且在类中实现了对应的方法
E pop() 弹出此列表所代表的堆栈中的元素。
void push(E e) 将元素推送到此列表所表示的堆栈上。

优先队列(作为堆来用)

默认小顶堆，但如果是数据结构就还是要重写comparator

import java.util.PriorityQueue;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//读
minHeap.peek();
minHeap.poll();(会弹出)
//添加
minHeap.add();
minHeap.offer();
//优先队列自然排序示例
Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);//容量为7
//优先队列使用示例
Queue<Customer> customerPriorityQueue = new PriorityQueue<>(idComparator);
//匿名Comparator实现
public static Comparator<Customer> idComparator = new Comparator<Customer>(){
    public int compare(Customer c1, Customer c2) {
        return (int) (c1.getId() - c2.getId());//这是小顶堆，反着写就是大顶堆
        }
    };
//或者实现Comparator接口也行
class idComparator implements Comparator{
    @Override
    public int compare(Customer c1, Customer c2){
        return (int)(c1.getId()-c2.getId)());
    }
}

/* 初始化堆 */
// 初始化小顶堆
Queue<Integer> minHeap = new PriorityQueue<>();
// 初始化大顶堆（使用 lambda 表达式修改 Comparator 即可）
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

/* 元素入堆 */
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);

/* 获取堆顶元素 */
int peek = maxHeap.peek(); // 5

/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
peek = maxHeap.poll(); // 5
peek = maxHeap.poll(); // 4
peek = maxHeap.poll(); // 3
peek = maxHeap.poll(); // 2
peek = maxHeap.poll(); // 1

/* 获取堆大小 */
int size = maxHeap.size();

/* 判断堆是否为空 */
boolean isEmpty = maxHeap.isEmpty();

/* 输入列表并建堆 */
minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));

数学库

Math.ceil(3.3); //向上取整
Math.floor(3.3); //向下取整
Math.round(3.4); //四舍五入
Math.pow(3,2) //幂运算
Math.abs(-1); //绝对值 
Math.max(9999,10000);
Math.min(9999,10000);
Math.ramdom(); //返回0-1的随机数，左闭右开
Math.sqrt(3.644); //开方

算法

排序

import java.util.Arrays;

public class MergeSort{

    public static void mergeSort(int[]arr, int l, int r){
        if (l>=r)return ;
        int mid = l+(r-l)/2;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }

    public static void merge(int[] arr, int l ,int mid,int r){
        int temp[] = new int[r-l+1];
        int left = l;
        int right = mid+1;
        int start = 0;
        while(left<=mid&& right<=r){
            if (arr[left]<arr[right]){
                temp[start++] = arr[left++];
            }else{
                temp[start++] = arr[right++];
            }
        }
        while(left<=mid){
            temp[start++] = arr[left++];
        }
        while(right<=r){
            temp[start++] = arr[right++];
        }
        for(int i=0;i<temp.length;i++){
                arr[l+i] = temp[i];
        }

     }
     public static void main(String[] args){
        int nums[] = new int[]{
            1,4,2,6,9,3,5,8,7
        };
        mergeSort(nums,0,nums.length-1);
        System
        .out.println(Arrays.toString(nums));
     }
}

图

邻接矩阵

/* 基于邻接矩阵实现的无向图类 */
class GraphAdjMat {
    List<Integer> vertices; // 顶点列表，元素代表“顶点值”，索引代表“顶点索引”
    List<List<Integer>> adjMat; // 邻接矩阵，行列索引对应“顶点索引”

    /* 构造方法 */
    public GraphAdjMat(int[] vertices, int[][] edges) {
        this.vertices = new ArrayList<>();
        this.adjMat = new ArrayList<>();
        // 添加顶点
        for (int val : vertices) {
            addVertex(val);
        }
        // 添加边
        // 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
        for (int[] e : edges) {
            addEdge(e[0], e[1]);
        }
    }

    /* 获取顶点数量 */
    public int size() {
        return vertices.size();
    }

    /* 添加顶点 */
    public void addVertex(int val) {
        int n = size();
        // 向顶点列表中添加新顶点的值
        vertices.add(val);
        // 在邻接矩阵中添加一行
        List<Integer> newRow = new ArrayList<>(n);
        for (int j = 0; j < n; j++) {
            newRow.add(0);
        }
        adjMat.add(newRow);
        // 在邻接矩阵中添加一列
        for (List<Integer> row : adjMat) {
            row.add(0);
        }
    }

    /* 删除顶点 */
    public void removeVertex(int index) {
        if (index >= size())
            throw new IndexOutOfBoundsException();
        // 在顶点列表中移除索引 index 的顶点
        vertices.remove(index);
        // 在邻接矩阵中删除索引 index 的行
        adjMat.remove(index);
        // 在邻接矩阵中删除索引 index 的列
        for (List<Integer> row : adjMat) {
            row.remove(index);
        }
    }

    /* 添加边 */
    // 参数 i, j 对应 vertices 元素索引
    public void addEdge(int i, int j) {
        // 索引越界与相等处理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        // 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) == (j, i)
        adjMat.get(i).set(j, 1);
        adjMat.get(j).set(i, 1);
    }

    /* 删除边 */
    // 参数 i, j 对应 vertices 元素索引
    public void removeEdge(int i, int j) {
        // 索引越界与相等处理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        adjMat.get(i).set(j, 0);
        adjMat.get(j).set(i, 0);
    }

    /* 打印邻接矩阵 */
    public void print() {
        System.out.print("顶点列表 = ");
        System.out.println(vertices);
        System.out.println("邻接矩阵 =");
        PrintUtil.printMatrix(adjMat);
    }
}

邻接表的BFS

/* 广度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希表，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    visited.add(startVet);
    // 队列用于实现 BFS
    Queue<Vertex> que = new LinkedList<>();
    que.offer(startVet);
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    while (!que.isEmpty()) {
        Vertex vet = que.poll(); // 队首顶点出队
        res.add(vet);            // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (Vertex adjVet : graph.adjList.get(vet)) {
            if (visited.contains(adjVet))
                continue;        // 跳过已被访问的顶点
            que.offer(adjVet);   // 只入队未访问的顶点
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}

邻接表的DFS

/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.add(vet);     // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (Vertex adjVet : graph.adjList.get(vet)) {
        if (visited.contains(adjVet))
            continue; // 跳过已被访问的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希表，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    dfs(graph, visited, res, startVet);
    return res;
}

Floyd

public class MatrixUDG {

    private int mEdgNum;        // 边的数量
    private char[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵
    private static final int INF = Integer.MAX_VALUE;   // 最大值

    ...
}
/*
 * floyd最短路径。
 * 即，统计图中各个顶点间的最短路径。
 *
 * 参数说明：
 *     path -- 路径。path[i][j]=k表示，"顶点i"到"顶点j"的最短路径会经过顶点k。
 *     dist -- 长度数组。即，dist[i][j]=sum表示，"顶点i"到"顶点j"的最短路径的长度是sum。
 */
public void floyd(int[][] path, int[][] dist) {

    // 初始化
    for (int i = 0; i < mVexs.length; i++) {
        for (int j = 0; j < mVexs.length; j++) {
            dist[i][j] = mMatrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
            path[i][j] = j;                // "顶点i"到"顶点j"的最短路径是经过顶点j。
        }
    }

    // 计算最短路径
    for (int k = 0; k < mVexs.length; k++) {
        for (int i = 0; i < mVexs.length; i++) {
            for (int j = 0; j < mVexs.length; j++) {

                // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
                int tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                if (dist[i][j] > tmp) {
                    // "i到j最短路径"对应的值设，为更小的一个(即经过k)
                    dist[i][j] = tmp;
                    // "i到j最短路径"对应的路径，经过k
                    path[i][j] = path[i][k];
                }
            }
        }
    }

    // 打印floyd最短路径的结果
    System.out.printf("floyd: \n");
    for (int i = 0; i < mVexs.length; i++) {
        for (int j = 0; j < mVexs.length; j++)
            System.out.printf("%2d  ", dist[i][j]);
        System.out.printf("\n");
    }
}

迪杰斯特拉

public class MatrixUDG {
 
    private int mEdgNum;        // 边的数量
    private char[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵
    private static final int INF = Integer.MAX_VALUE;   // 最大值
 
    ...
}
/*
 * Dijkstra最短路径。
 * 即，统计图中"顶点vs"到其它各个顶点的最短路径。
 *
 * 参数说明：
 *       vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
 *     prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
 *     dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
 */
public void dijkstra(int vs, int[] prev, int[] dist) {
    // flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取
    boolean[] flag = new boolean[mVexs.length];
 
    // 初始化
    for (int i = 0; i < mVexs.length; i++) {
        flag[i] = false;          // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = mMatrix[vs][i];  // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }
 
    // 对"顶点vs"自身进行初始化
    flag[vs] = true;
    dist[vs] = 0;
 
    // 遍历mVexs.length-1次；每次找出一个顶点的最短路径。
    int k=0;
    for (int i = 1; i < mVexs.length; i++) {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
        int min = INF;
        for (int j = 0; j < mVexs.length; j++) {
            if (flag[j]==false && dist[j]<min) {
                min = dist[j];
                k = j;
            }
        }
        // 标记"顶点k"为已经获取到最短路径
        flag[k] = true;
 
        // 修正当前最短路径和前驱顶点
        // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
        for (int j = 0; j < mVexs.length; j++) {
            int tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j]));
            if (flag[j]==false && (tmp<dist[j]) ) {
                dist[j] = tmp;
                prev[j] = k;
            }
        }
    }
 
    // 打印dijkstra最短路径的结果
    System.out.printf("dijkstra(%c): \n", mVexs[vs]);
    for (int i=0; i < mVexs.length; i++)
        System.out.printf("  shortest(%c, %c)=%d\n", mVexs[vs], mVexs[i], dist[i]);
}

Leetcode 133.克隆图

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    Map<Node,Node>visitedMap=new HashMap();
    public Node cloneGraph(Node node) {
        if (node==null)return null;
        if (!visitedMap.containsKey(node)){
            int val = node.val;
            Node temp = new Node(val,new ArrayList());
            visitedMap.put(node,temp);
        }else{
            return visitedMap.get(node);
        }
        Node ans = visitedMap.get(node);
        for (Node node1:node.neighbors){
            ans.neighbors.add(cloneGraph(node1));
        }
        return ans;
    }

}

Leetcode 399.除法求值(并查集，一遍查询一边修改)

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationsSize = equations.size();

        UnionFind unionFind = new UnionFind(2 * equationsSize);
        // 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
        Map<String, Integer> hashMap = new HashMap<>(2 * equationsSize);
        int id = 0;
        for (int i = 0; i < equationsSize; i++) {
            List<String> equation = equations.get(i);
            String var1 = equation.get(0);
            String var2 = equation.get(1);

            if (!hashMap.containsKey(var1)) {
                hashMap.put(var1, id);
                id++;
            }
            if (!hashMap.containsKey(var2)) {
                hashMap.put(var2, id);
                id++;
            }
            unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
        }

        // 第 2 步：做查询
        int queriesSize = queries.size();
        double[] res = new double[queriesSize];
        for (int i = 0; i < queriesSize; i++) {
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);

            Integer id1 = hashMap.get(var1);
            Integer id2 = hashMap.get(var2);

            if (id1 == null || id2 == null) {
                res[i] = -1.0d;
            } else {
                res[i] = unionFind.isConnected(id1, id2);
            }
        }
        return res;
    }

    private class UnionFind {

        private int[] parent;

        /**
         * 指向的父结点的权值
         */
        private double[] weight;


        public UnionFind(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1.0d;
            }
        }

        public void union(int x, int y, double value) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            parent[rootX] = rootY;
          	// 关系式的推导请见「参考代码」下方的示意图
            weight[rootX] = weight[y] * value / weight[x];
        }

        /**
         * 路径压缩
         *
         * @param x
         * @return 根结点的 id
         */
        public int find(int x) {
            if (x != parent[x]) {
                int origin = parent[x];
                parent[x] = find(parent[x]);
                weight[x] *= weight[origin];
            }
            return parent[x];
        }

        public double isConnected(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return weight[x] / weight[y];
            } else {
                return -1.0d;
            }
        }
    }
}

Leetcode 207.课程表

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int numOfRelations = prerequisites.length;
        int inDegree[] = new int[numCourses];
        Map<Integer,List<Integer>>map = new HashMap();
        for (int i=0;i<numOfRelations;i++){
            int pre = prerequisites[i][0];
            int after = prerequisites[i][1];
            inDegree[after]++;
            List<Integer>list = map.getOrDefault(pre,new ArrayList<Integer>());
            list.add(after);
            map.put(pre,list);
        }
        Queue<Integer>q = new LinkedList();
        for (int i=0;i<numCourses;i++){
            if (inDegree[i]==0)q.add(i);
        }
        while(!q.isEmpty()){
            int pre = q.poll();
            List<Integer>after = map.get(pre);
            if (after!=null)
            for (int num:after){
                inDegree[num]--;
                if (inDegree[num]==0)q.add(num);
            }
        }
        for (int i=0;i<numCourses;i++){
            if (inDegree[i]!=0)return false;
        }
        return true;
    }
}

Leetcode 210.课程表2

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int numOfRelations = prerequisites.length;
        int inDegree[] = new int[numCourses];
        Map<Integer,List<Integer>>map = new HashMap();
        for (int i=0;i<numOfRelations;i++){
            int after = prerequisites[i][0];
            int pre = prerequisites[i][1];
            inDegree[after]++;
            List<Integer>list = map.getOrDefault(pre,new ArrayList<Integer>());
            list.add(after);
            map.put(pre,list);
        }
        Queue<Integer>q = new LinkedList();
        for (int i=0;i<numCourses;i++){
            if (inDegree[i]==0)q.add(i);
        }
        int ans[]=new int[numCourses];
        int start = 0;
        while(!q.isEmpty()){
            int pre = q.poll();
            ans[start] = pre;
            start++;
            List<Integer>after = map.get(pre);
            if (after!=null){    
                for (int num:after){
                inDegree[num]--;
                if (inDegree[num]==0)q.add(num);
                }
            }
            
        }
        for (int i=0;i<numCourses;i++){
            if (inDegree[i]!=0)return new int[]{};
        }
        return ans;
    }
    
}

Leetcode 909.蛇梯棋

class Solution {
    public int snakesAndLadders(int[][] board) {
        // edge condition
        if(board == null || board.length == 0 || board[0] == null || board[0].length == 0){
            return 0;
        }

        // Preparation
        int rowNum = board.length;
        int colNum = board[0].length;

        boolean isRight = true;

        // 扁平化
        int[] nums = new int[rowNum * rowNum + 1];
        int index = 1;

        for(int i = rowNum - 1; i >= 0; i--){
            if(isRight){
                for(int j = 0; j < colNum; j++){
                    nums[index++] = board[i][j];
                }
            }
            else{
                for(int j = colNum - 1; j >= 0; j--){
                    nums[index++] = board[i][j];
                }
            }

            isRight = !isRight;
        }

        // Queue
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);

        // <Index, steps>
        Map<Integer, Integer> distanceMap = new HashMap<>();
        distanceMap.put(1, 0);

        while(!queue.isEmpty()){
            int curIndex = queue.poll();
            int step = distanceMap.get(curIndex);

            // 走到左上角：答案
            if(curIndex == rowNum * rowNum){
                return step;
            }

            for(int i = 1; i <= 6; i++){
                int newIndex = curIndex + i;

                // isValid
                if(newIndex <= 0 || newIndex > rowNum * rowNum){
                    continue;
                }

                // 遇到蛇 或 梯子
                if(nums[newIndex] != -1){
                    newIndex = nums[newIndex];
                }

                // visited
                if(distanceMap.containsKey(newIndex)){
                    continue;
                }

                // 入 queue
                queue.offer(newIndex);
                
                // 当前点走过的距离
                distanceMap.put(newIndex, step + 1);
            }
        }

        return -1;
    }
}

回溯问题

/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

全排列问题

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

子集和问题

类似于全排列问题，我们可以把子集的生成过程想象成一系列选择的结果，并在选择过程中实时更新“元素和”，当元素和等于 target 时，就将子集记录至结果列表。

而与全排列问题不同的是，本题集合中的元素可以被无限次选取，因此无须借助 selected 布尔列表来记录元素是否已被选择。我们可以对全排列代码进行小幅修改，初步得到解题代码：

/* 回溯算法：子集和 I */
void backtrack(List<Integer> state, int target, int total, int[] choices, List<List<Integer>> res) {
    // 子集和等于 target 时，记录解
    if (total == target) {
        res.add(new ArrayList<>(state));
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < choices.length; i++) {
        // 剪枝：若子集和超过 target ，则跳过该选择
        if (total + choices[i] > target) {
            continue;
        }
        // 尝试：做出选择，更新元素和 total
        state.add(choices[i]);
        // 进行下一轮选择
        backtrack(state, target, total + choices[i], choices, res);
        // 回退：撤销选择，恢复到之前的状态
        state.remove(state.size() - 1);
    }
}

/* 求解子集和 I（包含重复子集） */
List<List<Integer>> subsetSumINaive(int[] nums, int target) {
    List<Integer> state = new ArrayList<>(); // 状态（子集）
    int total = 0; // 子集和
    List<List<Integer>> res = new ArrayList<>(); // 结果列表（子集列表）
    backtrack(state, target, total, nums, res);
    return res;
}

但这样的问题是，其在进行选取的时候，会造成重复，解决办法是先排序

• 在开启搜索前，先将数组 nums 排序。在遍历所有选择时，当子集和超过 target 时直接结束循环，因为后边的元素更大，其子集和一定超过 target 。
• 省去元素和变量 total ，通过在 target 上执行减法来统计元素和，当 target 等于 0 时记录解。

/* 回溯算法：子集和 I */
void backtrack(List<Integer> state, int target, int[] choices, int start, List<List<Integer>> res) {
    // 子集和等于 target 时，记录解
    if (target == 0) {
        res.add(new ArrayList<>(state));
        return;
    }
    // 遍历所有选择
    // 剪枝二：从 start 开始遍历，避免生成重复子集
    for (int i = start; i < choices.length; i++) {
        // 剪枝一：若子集和超过 target ，则直接结束循环
        // 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if (target - choices[i] < 0) {
            break;
        }
        // 尝试：做出选择，更新 target, start
        state.add(choices[i]);
        // 进行下一轮选择
        backtrack(state, target - choices[i], choices, i, res);
        // 回退：撤销选择，恢复到之前的状态
        state.remove(state.size() - 1);
    }
}

/* 求解子集和 I */
List<List<Integer>> subsetSumI(int[] nums, int target) {
    List<Integer> state = new ArrayList<>(); // 状态（子集）
    Arrays.sort(nums); // 对 nums 进行排序
    int start = 0; // 遍历起始点
    List<List<Integer>> res = new ArrayList<>(); // 结果列表（子集列表）
    backtrack(state, target, nums, start, res);
    return res;
}

N皇后问题（经典）

13.4 N 皇后问题 - Hello 算法 (hello-algo.com)

/* 回溯算法：n 皇后 */
void backtrack(int row, int n, List<List<String>> state, List<List<List<String>>> res,
        boolean[] cols, boolean[] diags1, boolean[] diags2) {
    // 当放置完所有行时，记录解
    if (row == n) {
        List<List<String>> copyState = new ArrayList<>();
        for (List<String> sRow : state) {
            copyState.add(new ArrayList<>(sRow));
        }
        res.add(copyState);
        return;
    }
    // 遍历所有列
    for (int col = 0; col < n; col++) {
        // 计算该格子对应的主对角线和次对角线
        int diag1 = row - col + n - 1;
        int diag2 = row + col;
        // 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
        if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 尝试：将皇后放置在该格子
            state.get(row).set(col, "Q");
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            // 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2);
            // 回退：将该格子恢复为空位
            state.get(row).set(col, "#");
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}

/* 求解 n 皇后 */
List<List<List<String>>> nQueens(int n) {
    // 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
    List<List<String>> state = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<String> row = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            row.add("#");
        }
        state.add(row);
    }
    boolean[] cols = new boolean[n]; // 记录列是否有皇后
    boolean[] diags1 = new boolean[2 * n - 1]; // 记录主对角线上是否有皇后
    boolean[] diags2 = new boolean[2 * n - 1]; // 记录次对角线上是否有皇后
    List<List<List<String>>> res = new ArrayList<>();

    backtrack(0, n, state, res, cols, diags1, diags2);

    return res;
}

2024.09.04蔚来

import java.util.Scanner;
public class Main {

    public static boolean getAns(int[][] matrix, int[][] ans, boolean flag) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        int currentX = 0;
        int currentY = 0;
        int steps[][] = new int[4][2];
        steps[0][0] = 0; steps[0][1] = 1;
        steps[1][0] = 1; steps[1][1] = 0;
        steps[2][0] = 0; steps[2][1] = -1;
        steps[3][0] = -1; steps[3][1] = 0;
        
        if (matrix[0][0] == 1) return false;
        ans[0][0] = 1;
        
        boolean visited[][] = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = false;
            }
        }
        return backtrace(matrix, visited, currentX, currentY, m, n, flag, steps, ans);
    }

    public static boolean backtrace(int[][] matrix, boolean[][] visited, int currentX, int currentY, int m, int n, boolean flag, int[][] steps, int[][] ans) {
        if (currentY < 0 || currentY >= n || currentX < 0 || currentX >= m) return false;
        for (int j = 0; j < 4; j++) {
            int tempCurrentX = currentX + steps[j][0];
            int tempCurrentY = currentY + steps[j][1];
            if (tempCurrentX < 0 || tempCurrentX >= m || tempCurrentY < 0 || tempCurrentY >= n || visited[tempCurrentX][tempCurrentY] || matrix[tempCurrentX][tempCurrentY] == 1) {
                continue;
            } else {
                if (tempCurrentX == m - 1 && tempCurrentY == n - 1) {
                    flag = true;
                    ans[tempCurrentX][tempCurrentY] = 1;
                    return true;
                }
                visited[tempCurrentX][tempCurrentY] = true;
                ans[tempCurrentX][tempCurrentY] = 1;
                if (backtrace(matrix, visited, tempCurrentX, tempCurrentY, m, n, flag, steps, ans)) {
                    return true;
                }
                ans[tempCurrentX][tempCurrentY] = 0;
                visited[tempCurrentX][tempCurrentY] = false;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        boolean flag = false;
        int matrix[][] = new int[3][3];
        matrix[0][1] = 1;
        matrix[0][2] = 1;
        int ans[][] = new int[3][3];
        flag = getAns(matrix, ans, flag);
        if (flag) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    System.out.print(ans[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("No path found.");
        }
    }
}

Leetcode 77.组合

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }

    public void dfs(int cur, int n, int k) {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.size() == k) {
            ans.add(new ArrayList<Integer>(temp));
            return;
        }
        // 考虑选择当前位置
        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
}

动态规划

记忆化搜索

/* 记忆化搜索 */
int dfs(int i, int[] mem) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // 若存在记录 dp[i] ，则直接返回之
    if (mem[i] != -1)
        return mem[i];
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1, mem) + dfs(i - 2, mem);
    // 记录 dp[i]
    mem[i] = count;
    return count;
}

/* 爬楼梯：记忆化搜索 */
int climbingStairsDFSMem(int n) {
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    int[] mem = new int[n + 1];
    Arrays.fill(mem, -1);
    return dfs(n, mem);
}

01背包

暴力搜索 O(2^n)

/* 0-1 背包：暴力搜索 */
int knapsackDFS(int[] wgt, int[] val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}

空间优化加动态规划

/* 0-1 背包：空间优化后的动态规划 */
int knapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

完全背包

空间优化加动态规划

/* 完全背包：空间优化后的动态规划 */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

Leetcode 322.零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        int types = coins.length;
        int dp[] = new int[amount+1];
        for (int i = 0;i<=amount;i++){
            dp[i]=amount+1;
        }
        dp[0]=0;
        for (int i = 0;i<types;i++){
            for (int j=0;j<=amount;j++){
                if (j>=coins[i]){ //会用到这个硬币
                    if(dp[j-coins[i]]+1<dp[j]){
                        dp[j] = dp[j-coins[i]]+1;
                    }
                }else{
                    continue;
                }
            }
        }
        if (dp[amount]==amount+1)return -1;
        return dp[amount];
    }
}

零钱兑换问题2

凑硬币

/* 零钱兑换 II：动态规划 */
int coinChangeIIDP(int[] coins, int amt) {
    int n = coins.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][amt + 1];
    // 初始化首列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

加空间优化

/* 零钱兑换 II：空间优化后的动态规划 */
int coinChangeIIDPComp(int[] coins, int amt) {
    int n = coins.length;
    // 初始化 dp 表
    int[] dp = new int[amt + 1];
    dp[0] = 1;
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[a] = dp[a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[a] = dp[a] + dp[a - coins[i - 1]];
            }
        }
    }
    return dp[amt];
}

编辑距离问题

14.6 编辑距离问题 - Hello 算法 (hello-algo.com)

package datastructure.dp;

public class Levenshtein {
    public static int distance(String a, String b) {
         int length1 = a.length();
         int length2 = b.length();
         int dp[][] = new int[length1+1][length2+1];


         for (int i=1;i<=length1;i++){
             dp[i][0]=i;
         }

         for (int j=1;j<=length2;j++){
             dp[0][j]=j;
         }

         for (int i = 1 ;i<=length1;i++){
             for (int j=1;j<=length2;j++){
                 if (a.charAt(i-1)==b.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                 }else{
                     dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                 }
             }
         }

         return dp[length1][length2];

     }
     public static void main(String[] args) {
          String s1 = "kitten";
          String s2 = "sitting";
          int ans = distance(s1,s2);
          System.out.println(ans);
      }
}

Leetcode 198.打家劫舍

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1)return nums[0];
        int dp [] = new int [length];
        dp[0] = nums[0];
        for (int i=1; i< length;i++){
            int before = i-2;
            if (i==1){
                dp[i]=Math.max(nums[i],nums[i-1]);
                continue;
            }
            else{
                dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
            }
        }
        return dp[length-1];

    }
}

Leetcode 139.单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int length = s.length();
        boolean dp[] = new boolean[length+1];
        dp[0]=true;
        for(int i = 0;i<length;i++){
            for (int j=i+1;j<length+1;j++){
                if (dp[i]&&wordDict.contains(s.substring(i,j))){
                    dp[j]=true;
                }
            }
        }
        return dp[length];
    }
}

Leetcode 300.最长递增子序列

解法1：一种特殊思想

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> ans = new ArrayList();
        int length = nums.length;
        for (int i=0;i<length;i++){
            if (ans.size()==0||nums[i]>ans.get(ans.size()-1)){
                ans.add(nums[i]);
            }else{
                int index = findSmallIndex(ans,nums[i]);
                if (index!=-1){
                    ans.set(index,nums[i]);
                }
            }
        }
        return ans.size();
    }
    public int findSmallIndex(List<Integer> ans,int num){
        int length  = ans.size();
        for (int i=0;i<length;i++){
            if (ans.get(i)>=num){
                return i;
            }
        }
        return -1;

    }
}

解法2：动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if (length==1)return 1;
        int dp[]= new int[length];
        for (int i=0;i<length;i++){
            dp[i]=1;
        }
        int ans=1;
        for (int i=1;i<length;i++){
            for (int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    
                }
            }
            ans = Math.max(dp[i],ans);
        }
        return ans;
    }

}

Leetcode 120.三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int depth = triangle.size();
        int dp[][]=new int[depth][depth];
        dp[0][0]=triangle.get(0).get(0);
        if (depth==1){
            return dp[0][0];
        }
        for (int i=1;i<depth;i++){
            dp[i][0]=dp[i-1][0]+triangle.get(i).get(0);
            for (int j=1;j<triangle.get(i).size()-1;j++){
                dp[i][j]=Math.min(dp[i-1][j-1]+triangle.get(i).get(j),dp[i-1][j]+triangle.get(i).get(j));
            }
            dp[i][triangle.get(i).size()-1]=dp[i-1][triangle.get(i-1).size()-1]+triangle.get(i).get(triangle.get(i).size()-1);
        }
        int ans = Integer.MAX_VALUE;
        for(int i=0;i<triangle.get(depth-1).size();i++){
            ans = Math.min(dp[depth-1][i],ans);
        }
        return ans;
    }
}

Leetcode 221.最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        int length = matrix.length;
        int length2 = matrix[0].length;
        int ans = 0;
        int dp[][] = new int [length][length2];

        for (int i=0;i<length;i++){
            for(int j=0;j<length2;j++){
                if (matrix[i][j]=='1'){
                    if (i==0||j==0){
                        dp[i][j]=1;
                        ans = Math.max(ans,dp[i][j]);
                    }else{
                        dp[i][j]=1+getSmallest(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]);
                        ans = Math.max(ans,dp[i][j]);
                    }  
                }else{
                    dp[i][j]=0;
                }
            }
        }
        return ans*ans;


    }
    public int getSmallest(int a,int b,int c){
        if (a>b){
            if (b>c)return c;
            else return b;
        }else{
            if (a>c)return c;
            else return a;
        }
    }
}

Leetcode 72.编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        int dp[][] = new int[length1+1][length2+1];
        dp[0][0]=0;
        if (length1*length2==0)return length1+length2;
        if (length1>1){
            for (int i=1;i<=length1;i++){
            dp[i][0]=dp[i-1][0]+1;
            }
        }
        if (length2>1){
            for (int j=1;j<=length2;j++){
            dp[0][j]=dp[0][j-1]+1;
            }
        }
        
        for (int i=1;i<=length1;i++){
            for (int j=1;j<=length2;j++){
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    // dp[i][j]= getSmallest(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1);
                    dp[i][j]= getSmallest(dp[i-1][j-1]-1,dp[i-1][j],dp[i][j-1])+1;
                }else{
                    dp[i][j]= 1+getSmallest(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]);
                }
            }
        }


        return dp[length1][length2];
    }
    public int getSmallest(int a,int b,int c){
        if (a>b){
            if (b>c)return c;
            return b;
        }else{
            if (a>c)return c;
            return a;
        }
    }
}

贪心

一般情况下，贪心算法的适用情况分以下两种。

1. 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
2. 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的。

贪心问题的解决流程大体可分为以下三步。

1. 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及。
2. 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。
3. 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。

加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sumGas = 0;
        int sumCost = 0;
        for (int i = 0; i < n; i++) {
            sumCost += cost[i];
            sumGas += gas[i];
        }
        if (sumCost > sumGas)
            return -1;
        for (int i = 0; i < n; i++) {
            int rest = 0;
            int hasPassed = 0;
            for (int j = i; hasPassed < n; j++) {
                if (j == n)
                    j = 0;
                rest += gas[j];
                if (rest >= cost[j]) {
                    rest -= cost[j];
                    hasPassed++;
                } else {
                    i = j;
                    break;
                }
            }
            if (hasPassed == n)
                return i;
        }
        return 1;
    }
}

LCP 03. 机器人大冒险

class Solution {
    public boolean robot(String cmd, int[][] obstacles, int x, int y) {
        int n = cmd.length();
        int sx = 0, sy = 0;
        // 记录走完一轮后机器人的位置
        for (int i = 0; i < n; ++ i) {
            char c = cmd.charAt(i);
            if (c == 'U') ++ sy;
            else ++ sx;
        }
        // 先计算能否到达终点 不考虑障碍物
        // 若不能直接返回false
        boolean canFinish = canReach(cmd, x, y, sx, sy);
        if (!canFinish) return false;
        // 判断在终点前会不会遇到障碍物 
        // 若遇到则返回false
        for (int[] o : obstacles) {
            if (o[0] > x || o[1] > y)
                continue;
            if (canReach(cmd, o[0], o[1], sx, sy)) return false;
        }
        return true;
    }

    // 判断能否从坐标(x, y)到达(tx, ty)
    public boolean canReach(String cmd, int tx, int ty, int x, int y) {
        // round记录走到目标点至少要走多少轮
        int round = Math.min(tx/x, ty/y);
        int nx = round*x, ny = round*y;
        if (nx == tx && ny == ty) return true;
        int n = cmd.length();
        for (int i = 0; i < n; ++ i) {
            char c = cmd.charAt(i);
            if (c == 'U') ++ ny;
            else ++ nx;
            if (nx > tx || ny > ty) return false;
            if (nx == tx && ny == ty) return true;
        }
        return true;
    }
}

Leetcode 135.分发糖果

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
}

Leetcode 42.接雨水

class Solution {
    public int trap(int[] height) {
        int length = height.length;
        int ans = 0;
        for (int i =1;i<length-1;i++){
            int max_left = 0;
            for (int j = i-1;j>=0;j--){
                if (height[j]>max_left)
                max_left = height[j];
            }
            int max_right = 0;
            for (int j = i+1;j<length;j++){
                if (height[j]>max_right)
                max_right = height[j];
            }
            if (height[i]<Math.min(max_left,max_right)){
                ans+=Math.min(max_left,max_right)- height[i];
            }

        }
        return ans;

    }
}

Leetcode 13.罗马数字转整形

class Solution {
    public int romanToInt(String s) {
        HashMap<Character,Integer> romanMap = new HashMap();
        romanMap.put('I',1);
        romanMap.put('V',5);
        romanMap.put('X',10);
        romanMap.put('L',50);
        romanMap.put('C',100);
        romanMap.put('D',500);
        romanMap.put('M',1000);
        int length = s.length();
        int ans = 0;
        for (int i = 0;i<length;i++){
            if (i==length-1)ans+=romanMap.get(s.charAt(i));
            else{
                if (romanMap.get(s.charAt(i))<romanMap.get(s.charAt(i+1))){
                    ans-=romanMap.get(s.charAt(i));
                }else{
                    ans+=romanMap.get(s.charAt(i));
                }
            }
            
        }
        return ans;
    }
}

Leetcode 12.整数转罗马数字

class Solution {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }


}

Leetcode 63.不同路径2

动态规划

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // dp[i][j] 表示到达 (i, j) 的路径数
        int[][] dp = new int[m][n];

        // 初始化第一行
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) break; // 遇到障碍物，之后的格子路径数为0
            dp[0][j] = 1;
        }

        // 初始化第一列
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) break; // 遇到障碍物，之后的格子路径数为0
            dp[i][0] = 1;
        }

        // 填充 dp 表
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = 0; // 遇到障碍物，路径数为0
                }
            }
        }

        return dp[m - 1][n - 1]; // 返回右下角的路径数
    }
}

Leetcode 68.文本左右对齐

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<String>();
        int right = 0, n = words.length;
        while (true) {
            int left = right; // 当前行的第一个单词在 words 的位置
            int sumLen = 0; // 统计这一行单词长度之和
            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }

            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right == n) {
                StringBuffer sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;

            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            if (numWords == 1) {
                StringBuffer sb = new StringBuffer(words[left]);
                sb.append(blank(numSpaces));
                ans.add(sb.toString());
                continue;
            }

            // 当前行不只一个单词
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuffer sb = new StringBuffer();
            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词
            ans.add(sb.toString());
        }
    }

    // blank 返回长度为 n 的由空格组成的字符串
    public String blank(int n) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; ++i) {
            sb.append(' ');
        }
        return sb.toString();
    }

    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    public StringBuffer join(String[] words, int left, int right, String sep) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }
}

Leetcode 125.验证回文串

class Solution {
    public boolean isPalindrome(String s) {
        String s2 = s.toLowerCase();
        Stack stack = new Stack();
        Queue queue = new LinkedList();
        int length = s2.length();
        for (int i=0;i<length;i++){
            if (Character.isLetter(s2.charAt(i))||Character.isDigit(s2.charAt(i))){
                stack.push(s2.charAt(i));
                queue.offer(s2.charAt(i));
            }
        }
        boolean ans = true;
        while (!stack.isEmpty()){
            if (stack.peek()==queue.peek()){
                stack.pop();
                queue.poll();
            }else{
                ans = false;
                break;
            }
        }
        return ans;
    }
}

Leetcode 167.两数之和 II - 输入有序数组

//双指针
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }
}

Leetcode 11.盛最多水的容器

//这个方法会超时
class Solution {
    public int maxArea(int[] height) {
        int length = height.length;
        int ans = -1;
        for (int i =0;i<length-1;i++){
            for (int j=i+1;j<length;j++){
                if ((j-i)*Math.min(height[i],height[j])>ans){
                    ans = (j-i)*Math.min(height[i],height[j]);
                }
            }
        }
        return ans;
    }
}
//双指针，正确性可以用反证法：如果高度更高的反而改变了，那么能装的水肯定是变小的，所以这种策略一定是让能装的水变多的
class Solution {
    public int maxArea(int[] height) {
        int length = height.length;
        int ans = 0;
        int start = 0;
        int end = length-1;
        while(start<end){
            int minHeight = Math.min(height[start],height[end]);
            if ((end-start)*minHeight>ans){
                ans = (end-start)*minHeight;
            }
            if (minHeight==height[start])start++;
            else end--;
        }
        return ans;
    }
}

Leetcode 15.三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>>ans = new ArrayList<List<Integer>>();
        for (int i =0;i<n;i++){
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int k = n-1;
            int t = -nums[i];
            for (int j = i+1;j<n;j++){
                if (j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                while (j<k&&nums[j]+nums[k]>t){
                    k--;
                }
                if (j==k)break;
                if (nums[j]+nums[k]==t){
                    List<Integer>list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        return ans;



    }
}

Leetcode 209.长度最小的子数组

//暴力 会超时
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int length = nums.length;
        int presum[]=new int[length+1];
        int ans = 100000;

        for (int i=1;i<=length;i++){
                presum[i]=presum[i-1]+nums[i-1];
        }
        if (presum[length]<target)return 0;
        for (int i=0;i<length;i++){
            for (int j=length;j>=i;j--){
                    if (presum[j]-presum[i]>=target){
                        if (j-i<ans)ans = j-i;
                    }
            }
        }
        return ans;
    }
}
//滑动窗口
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int length = nums.length;
        int sum = 0;
        int start = 0;
        int end = 0;
        int ans = 100000;
        boolean flag =false;
        for (int i=0;i<length;i++){
            sum+=nums[i];
            end++;
            if (sum>=target){
                while (sum>=target){
                    if (end-start<ans)ans = end -start;
                    flag = true;
                    sum-=nums[start];
                    start++;
                } 
            }
        }
        if (!flag)return 0;
        return ans;
}
}

Leetcode 3.无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map= new HashMap();
        int start = 0;
        int ans = 0;
        for (int i = 0;i<s.length();i++){
            if (map.get(Character.valueOf(s.charAt(i)))!=null&&start<map.get(Character.valueOf(s.charAt(i)))+1){ //发现有重复的了
                start=map.get(Character.valueOf(s.charAt(i)))+1; //跳到没有重复的地方
            }
            map.put(Character.valueOf(s.charAt(i)),i);
            if (i-start+1>ans)ans = i-start+1;
        }
        return ans;
    }
}

Leetcode 36.有效的数独

暴力解法

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] >= '0' && board[i][j] <= '9'){
                    if(!getEffective(i, j, board)){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public boolean getEffective(int i, int j, char[][] board){
        // 验证一行
        for(int k = 0; k < board[i].length; k++){
            if(board[i][k] == board[i][j] && k != j){
                return false;
            }
        }
        // 验证一列
        for(int k = 0; k < board.length; k++){
            if(board[k][j] == board[i][j] && k != i){
                return false;
            }
        }
        // 验证当前 3 * 3 数组
        int heng = (i / 3) * 3;
        int zhong = (j / 3) * 3;

        for(int k1 = heng; k1 < heng + 3; k1++){
            for(int k2 = zhong; k2 < zhong + 3; k2++){
                if((board[k1][k2] == board[i][j]) && (k1 != i && k2 != j)){
                    return false;
                }
            }
        }

        return true;
    }
}

Leetcode 54.螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}

Leetcode 48.旋转图像

这种旋转的题就注意位置映射关系就好

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}

Leetcode 289.生命游戏

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        boolean isAlive[][]=new boolean[m][n];
        for (int i =0;i<m;i++){
            for (int j =0;j<n;j++){
                int num = getNum(board,i,j,m,n);
                if (board[i][j]==1){
                    if (num<2||num>3)isAlive[i][j]=false;
                    if (num==2||num==3)isAlive[i][j]=true;
                }else{
                    if (num==3)isAlive[i][j]=true;
                }
            }
        }
        for (int i=0;i<m;i++){
            for (int j =0;j<n;j++){
                if (isAlive[i][j])board[i][j]=1;
                else{
                    board[i][j]=0;
                }
            }
        }

    }

    public int getNum(int[][] board,int x,int y,int m, int n){
        int num = 0;
        for (int i=x-1;i<=x+1;i++){
            if (i<0||i>=m)continue;
            for (int j= y-1;j<=y+1;j++){
                if (j<0||j>=n||i==x&&j==y)continue;
                if (board[i][j]==1)num++;
            }
        }
        return num;
    }
}

哈希表

Leetcode 383.赎金信

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int nums[]=new int[26];
        int size = magazine.length();
        for (int i=0;i<size;i++){
            nums[magazine.charAt(i)-'a']+=1;
        }
        int rSize= ransomNote.length();
        for (int i =0;i<rSize;i++){
            if (nums[ransomNote.charAt(i)-'a']<=0)return false;
            nums[ransomNote.charAt(i)-'a']-=1;
        }
        return true;
    }
}

Leetcode 205.同构字符串

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> cMap = new HashMap<Character,Character>();
        Map<Character,Character> cMap2 = new HashMap<Character,Character>();
        int length = s.length();
        for (int i = 0;i<length;i++){
            if (cMap.containsKey(Character.valueOf(s.charAt(i)))||cMap2.containsKey(Character.valueOf(t.charAt(i)))){
                if (cMap.get(Character.valueOf(s.charAt(i)))!=Character.valueOf(t.charAt(i)))
                return false;
            }else{
                cMap.put(Character.valueOf(s.charAt(i)),Character.valueOf(t.charAt(i)));
                cMap2.put(Character.valueOf(t.charAt(i)),Character.valueOf(s.charAt(i)));
            }
        }
        return true;
    }
}

Leetcode 290.单词规律

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character,String> cMap = new HashMap<Character,String>();
        
        Map<String,Character> cMap2 = new HashMap<String,Character>();
        int length = pattern.length();
        String words[]=s.split(" ");
        if (words.length!=length)return false;
        for (int i = 0;i<length;i++){
            if (cMap.containsKey(Character.valueOf(pattern.charAt(i)))){
                if (!cMap.get(Character.valueOf(pattern.charAt(i))).equals(words[i])){
                return false;}
            }
            else if (cMap2.containsKey(words[i])){
                return false;
            }
            
            else{
                cMap.put(Character.valueOf(pattern.charAt(i)),words[i]);
                cMap2.put(words[i],Character.valueOf(pattern.charAt(i)));
            }
        }
        return true;
    }
}

Leetcode 49.字母异位词分组

//错误解法,没考虑到次数，但注意keySet的使用
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<HashSet<Character>,ArrayList<String>> map = new HashMap();
        int length = strs.length;
        for (int i = 0; i<length; i++){
            int length2=strs[i].length();
            HashSet<Character>set = new HashSet();
            for (int j = 0 ;j<length2;j++){
                set.add(Character.valueOf(strs[i].charAt(j)));
            }
            if (!map.containsKey(set)){
                ArrayList<String>list = new ArrayList();
                list.add(strs[i]);
                map.put(set,list);
            }else{
                map.get(set).add(strs[i]);
            }
        }
        List<List<String>> ans = new ArrayList<List<String>>();
        for (HashSet<Character> key: map.keySet()){
            ans.add(map.get(key));
        }
        return ans;

    }
}

//正确解法，注意char的数组可以直接new String转为String类
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
       Map<String,List<String>>map = new HashMap();
        int length = strs.length;
        for (int i = 0; i<length; i++){
            int length2=strs[i].length();
            char word[]=new char[length2];
            for (int j = 0;j<length2;j++){
                word[j]=strs[i].charAt(j) ;
            }
            Arrays.sort(word);
            String key = new String(word);
            if (!map.containsKey(key)){
                List<String> list = new ArrayList();
                list.add(strs[i]);
                map.put(key,list);
            }else{
                map.get(key).add(strs[i]);
            }      
        }
        List<List<String>> ans = new ArrayList<List<String>>();
        for (String key: map.keySet()){
            ans.add(map.get(key));
        }
        return ans;

    }
}

Leetcode 128.最长连续序列

class Solution {
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        if (length==0||length==1)return length;
        int num = 1;
        int ans = 1;
        for (int i = 1;i<length;i++){
            if (nums[i-1]+1==nums[i]){
                num++;
                ans=Math.max(num,ans);
            }else if(nums[i-1]==nums[i]){
                continue;
            }else{
                num=1;
            }      
        }
        return ans;
    }
}

Leetcode 76.最小覆盖子串

class Solution {
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() {
        Iterator iter = ori.entrySet().iterator(); 
        while (iter.hasNext()) { 
            Map.Entry entry = (Map.Entry) iter.next(); 
            Character key = (Character) entry.getKey(); 
            Integer val = (Integer) entry.getValue(); 
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        } 
        return true;
    }
}

区间

Leetcode 228.汇总区间

注意Integer.toString（）和StringBuilder的用法

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {
                i++;
            }
            int high = i - 1;
            StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));
            if (low < high) {
                temp.append("->");
                temp.append(Integer.toString(nums[high]));
            }
            ret.add(temp.toString());
        }
        return ret;
    }
}

Leetcode 56.合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]); //List.toArray(array)，注意array是新开辟的未分配的空间
    }
}

Leetcode 57.插入区间

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int length1 = intervals.length;
        int length2 = length1+1;
        int [][]ans = new int[length2][2];
        for (int i = 0;i<length1;i++){
            ans[i][0]=intervals[i][0];
            ans[i][1]=intervals[i][1];
        }
        ans[length1][0]=newInterval[0];
        ans[length1][1]=newInterval[1];
        Arrays.sort(ans,new Comparator<int[]>(){
            public int compare(int[]nums1,int[] nums2){
                return nums1[0]-nums2[0];
            }
        });
        List<int[]>ans2 = new ArrayList<int[]>();
        for (int i=0;i<length2;i++){
            if (ans2.size()==0||ans2.get(ans2.size()-1)[1]<ans[i][0]){
                ans2.add(new int[]{ans[i][0],ans[i][1]});
            }else{
                ans2.get(ans2.size()-1)[1]=Math.max(ans[i][1],ans2.get(ans2.size()-1)[1]);
            }
        }
        return ans2.toArray(new int[ans2.size()][]);
    }
}

Leetcode 452.用最少数量的箭引爆气球

注意贪心

class Solution {
    public int findMinArrowShots(int[][] points) {
        int length = points.length;
        Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
        List<int[]> ans = new ArrayList();
        for (int i =0;i<length;i++){
            if (ans.size()==0||ans.get(ans.size()-1)[1]<points[i][0]){
                ans.add(new int[]{points[i][0],points[i][1]});
            }else{
               continue;
            }
        }
        return ans.size();
    }
}

栈

Leetcode 71.简化路径

注意双端队列Deque用LinkedList来实现，StringBuilder.tostring()转为字符串。

class Solution {
    public String simplifyPath(String path) {
        String []strs = path.split("/");
        Deque<String>stack = new LinkedList();
        for (String str:strs){
            if ("..".equals(str)){
                if (!stack.isEmpty()){
                    stack.pollLast();
                }
            }else if (str.length()>0&&!".".equals(str)){
                stack.offerLast(str);
            }
        }
        StringBuilder sb = new StringBuilder();
        if (stack.isEmpty()){
            sb.append("/");
        }else{
            while (!stack.isEmpty()){
                sb.append("/");
                sb.append(stack.pollFirst());
            }
        }
        return sb.toString();
    }
}

Leetcode 155.最小栈

class MinStack {
    ArrayList<Integer> stack;
    public MinStack() {
        this. stack =  new ArrayList();
    }
    
    public void push(int val) {
        stack.add(val);
    }
    
    public void pop() {
        stack.remove(stack.size()-1);
    }
    
    public int top() {
        return stack.get(stack.size()-1).intValue();
    }
    
    public int getMin() {  
        int ans = Integer.MAX_VALUE;
        for (Integer num:stack){
            if (num<ans)ans = num;
        }
        return ans;
    }
}

Leetcode 150.逆波兰表达式

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String>stack = new Stack();
        for (String str:tokens){
            if (!"+".equals(str)&&!"-".equals(str)&&!"*".equals(str)&&!"/".equals(str)){
                stack.push(str);
            }else {
                int b = Integer.parseInt(stack.pop());
                int a = Integer.parseInt(stack.pop());
                if ("+".equals(str)){
                    stack.push(String.valueOf(a+b));
                }else if ("-".equals(str)){
                    stack.push(String.valueOf(a-b));
                }else if ("*".equals(str)){
                    stack.push(String.valueOf(a*b));
                }else if ("/".equals(str)){
                    stack.push(String.valueOf(a/b));
                }
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

链表

注意哑结点的构造，很方便！！！

Leetcode 21.合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

Leetcode 141.环形链表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow =head;
        ListNode fast = head;
        while(fast!=null&&slow!=null){
            slow=slow.next;
            fast = fast.next;
            if (fast==null)return false;
            fast = fast.next;
            if (fast == slow)return true;
        }
        return false;
    }
}

Leetcode 2.两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

Leetcode 206.反转链表

递归做法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null)return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next=null;
        return newHead;
    }
}

Leetcode 92.反转链表2

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}

Leetcode 138.随机链表的复制

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    Map<Node,Node>map = new HashMap();
    public Node copyRandomList(Node head) {
        if (head == null)return null;
        if (!map.containsKey(head)){
            Node newNode = new Node(head.val);
            map.put(head,newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
}

Leetcode 19.删除链表的倒数第N个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode currentNode = head;
        ArrayList<ListNode> nodes = new ArrayList(); 
        while(currentNode!=null){
            nodes.add(currentNode);
            currentNode = currentNode.next;
        }
        int num = nodes.size();
        if (num == 1)return null;
        ListNode pre = new ListNode(-1,head);
        currentNode = pre;
        for (int i=1;i<num-n+1;i++){
            currentNode = currentNode.next;
        }
        currentNode.next=currentNode.next.next;
        return pre.next;
    }
}

Leetcode 82.删除排序链表中的重复元素2

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

Leetcode 61.旋转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ArrayList<ListNode> nodes = new ArrayList();
        ListNode dumbNode = new ListNode(-111,head);
        ListNode cur = head;
        while(cur!=null){
            nodes.add(cur);
            cur=cur.next;
        }
        int num = nodes.size();
        if (num==0)return head;
        k = k%num;
        if (k==0)return head;
        int preOrder = num-k-1;
        cur = dumbNode;
        for (int i = 0;i<=preOrder;i++){
            cur = cur.next;
        }
        ListNode preNode = cur;
        ListNode next =preNode.next;
        ListNode last = next;
        while(last!=null){
            if (last.next==null)break;
            last = last.next;
        }
        dumbNode.next = next;
        last.next = head;
        preNode.next = null;
        return dumbNode.next;


    }
}

Leetcode 146.LRU缓存

直接继承LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

哈希+双链表

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

二分查找

Leetcode 35.搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        int ans=nums.length;
        if (nums[0]>=target)return 0;
        while(start<=end){
            int mid = (end-start)/2+start;
            if (nums[mid]>=target){
                end =mid-1;
                ans =mid;
            }else{
                start =mid+1;
            }
        }
        return ans;
    }
}

Leetcode 74.搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i=0;i<m;i++){
            if (target>matrix[i][n-1])continue;
            for (int j=0;j<n;j++){
                if (matrix[i][j]==target)return true;
            }
            return false;
        }
        return false;
    } 
}

Leetcode 200.岛屿数量

常规的dfs,甚至不用回溯

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

Leetcode 130.被围绕的区域

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i=0;i<m;i++){
            dfs(board,i,0);
            dfs(board,i,n-1);
        }
        for (int i=0;i<n;i++){
            dfs(board,0,i);
            dfs(board,m-1,i);
        }
        for (int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (board[i][j]=='V')board[i][j]='O';  
                else if(board[i][j]=='O'){
                    board[i][j]='X';
                }  
            }
        }
    }
    public void dfs(char[][]board,int x, int y){
        if (x<0||y<0||x>=board.length||y>=board[0].length||board[x][y]!='O')return;
        board[x][y]='V';
        dfs(board,x+1,y);
        dfs(board,x,y+1);
        dfs(board,x-1,y);
        dfs(board,x,y-1);
    }
}

Leetcode 2576.求出最多标记下标

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int m = n / 2;
        int res = 0;
        for (int i = 0, j = m; i < m && j < n; i++) {
            while (j < n && 2 * nums[i] > nums[j]) {
                j++;
            }
            if (j < n) {
                res += 2;
                j++;
            }
        }
        return res;
    }
};

Leetcode 300.最长递增子序列

会用到二分查找,nlogn复杂度

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
}

拓扑排序

Leetcode 115.序列重建

证明挺精彩的

class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        int[] indegrees = new int[n + 1];
        Set<Integer>[] graph = new Set[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new HashSet<Integer>();
        }
        for (int[] sequence : sequences) {
            int size = sequence.length;
            for (int i = 1; i < size; i++) {
                int prev = sequence[i - 1], next = sequence[i];
                if (graph[prev].add(next)) {
                    indegrees[next]++;
                }
            }
        }
        Queue<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 1; i <= n; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            if (queue.size() > 1) {
                return false;
            }
            int num = queue.poll();
            Set<Integer> set = graph[num];
            for (int next : set) {
                indegrees[next]--;
                if (indegrees[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return true;
    }
}

二叉树

Leetcode 226.翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root==null)return root;
        TreeNode temp=root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Leetcode 104.二叉树的最大深度

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root==null)return root;
        TreeNode temp=root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Leetcode 100.相同的树

class Solution {
    boolean flag =true;
    public boolean isSameTree(TreeNode p, TreeNode q) {
        findIsSameTree(p,q);
        return flag;
    }
    public void findIsSameTree(TreeNode p,  TreeNode q){
        if (p!=null&&q!=null){
            findIsSameTree(p.left,q.left);
            findIsSameTree(p.right,q.right);
        }
    
        if (p!=null&&q!=null){
            if (p.val==q.val){
                return;
            }else{
                flag =false;
            }
        }else if(p==null&&q==null){
            return;
        }else{
            flag =false;
        }
    }
}

Leetcode 101.对称二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    boolean flag =true;
    public boolean isSymmetric(TreeNode root) {
        findIsSymmetric(root,root);
        return flag;
    }
    public void findIsSymmetric(TreeNode a,TreeNode b){
        if (a==null&&b==null){
            return;
        }else if (a!=null&&b!=null){
            if (a.val!=b.val)flag =false;
            findIsSymmetric(a.left,b.right);
            findIsSymmetric(a.right,b.left);
        }else{
            flag=false;
        }
    }
}

Leetcode 105.从前序和中序遍历序列构造二叉树

/* 构建二叉树：分治 */
TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
    // 子树区间为空时终止
    if (r - l < 0)
        return null;
    // 初始化根节点
    TreeNode root = new TreeNode(preorder[i]);
    // 查询 m ，从而划分左右子树
    int m = inorderMap.get(preorder[i]);
    // 子问题：构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题：构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    //构建右子树稍微复杂一些。首先，需要确定右子树的根节点在前序遍历中的位置。由于左子树的根节点之后的所有元素都属于右子树，所以右子树的根节点在前序遍历中的位置是 i + 1 + (m - l)。这里的 m - l 表示左子树的大小，即左子树有多少个节点。
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode buildTree(int[] preorder, int[] inorder) {
    // 初始化哈希表，存储 inorder 元素到索引的映射
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}

Leetcode 106.从中序和后序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> map = new HashMap<>();
        int length = inorder.length;
        for (int i = 0; i < length; i++) {
            map.put(inorder[i], i);
        }
        return dfs(inorder, postorder, map, 0, length - 1, length - 1);
    }

    public TreeNode dfs(int[] inorder, int[] postorder, Map<Integer, Integer> map, int left, int right, int index) {
        if (left > right) {
            return null;
        }
        int val = postorder[index];
        int mid = map.get(val);
        TreeNode node = new TreeNode(val);
        node.right = dfs(inorder, postorder, map, mid + 1, right, index-1);
        node.left = dfs(inorder, postorder, map, left, mid - 1, index-1-(right-mid));
        return node;
    }
}

判断是不是二叉平衡树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)    return true;
        //求左子树的深度
        int left = deepFind(root.left);
        //求右子树的深度
        int right = deepFind(root.right);
        //判断每个节点是否满足平衡二叉树的定义，全部都是，才是真正的平衡二叉树
        return (Math.abs(left - right) < 2 ? true : false) && isBalanced(root.left) && isBalanced(root.right);
    }
	
	//判断一棵树的深度
    public int deepFind(TreeNode node){
        if(node == null)    return 0;
        return Math.max(deepFind(node.left), deepFind(node.right))+1;
    }
}

Leetcode 129.求根节点到叶节点数字之和

class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        StringBuilder sb = new StringBuilder("");
        getSum(root,sb);
        return sum;
    }
    public void getSum(TreeNode node,StringBuilder sb){
        if (node==null)return;
        //不为空
        StringBuilder sb2 = new StringBuilder();
        String num = String.valueOf(node.val);
        sb2.append(sb.toString());
        sb2.append(num);
        if (node.left==null&&node.right==null){
            System.out.println(sb2.toString());
            sum+=Integer.parseInt(sb2.toString());
        }
        getSum(node.left,sb2);
        getSum(node.right,sb2);
    }
}

Leetcode 199.二叉树的右视图

class Solution {

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer>ans = new ArrayList<Integer>();
        Queue<TreeNode>tq = new LinkedList();
        Queue<Integer>depthQueue = new LinkedList();
        Map<Integer,Integer>map = new HashMap();
        tq.add(root);
        depthQueue.add(0);
        int maxDepth = -1;
        while(!tq.isEmpty()){
            TreeNode node = tq.poll();
            int depth = depthQueue.poll();
            if (node!=null){
                maxDepth = Math.max(maxDepth,depth);
                map.put(depth,node.val);
                tq.add(node.left);
                tq.add(node.right);
                depthQueue.add(depth+1);
                depthQueue.add(depth+1);
            }
        }
        for (int i=0;i<=maxDepth;i++){
            ans.add(map.get(i));
        }
        return ans;
    }

}

Leetcode 117.填充每个节点的下一个右侧节点指针2

class Solution {
    public Node connect(Node root) {
        Map<Integer,List<Node>>map = new HashMap();
        Queue<Node> nodeQueue = new LinkedList();
        Queue<Integer> depthQueue = new LinkedList();
        int maxDepth = -1;
        nodeQueue.add(root);
        depthQueue.add(0);

        while(!nodeQueue.isEmpty()){
            Node node = nodeQueue.poll();
            int depth = depthQueue.poll();
            if (node !=null){
                maxDepth = Math.max(depth,maxDepth);
                if (!map.containsKey(depth)){
                    List<Node>nodeList = new LinkedList();
                    nodeList.add(node);
                    map.put(depth,nodeList);
                }else{
                    map.get(depth).add(node);
                }
                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth+1);
                depthQueue.add(depth+1);
            }
        }
        for (int depth=0;depth<=maxDepth;depth++){
            if (map.get(depth).size()==1)continue;
            int size=map.get(depth).size();
            for (int index=0;index<size-1;index++){
                map.get(depth).get(index).next=map.get(depth).get(index+1);
            }
        }
        return root;
    }
}

Leetcode 114.二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        Queue<TreeNode> q = new LinkedList();
        q=getPreQueue(root,q);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if (q.size()==0)break;
            node.left = null;
            node.right = q.peek();
        }

    }
    public Queue<TreeNode> getPreQueue(TreeNode node,Queue<TreeNode> q){
        if (node!=null){
            q.add(node);
            getPreQueue(node.left,q);
            getPreQueue(node.right,q);
        }
        
        return q;
    }
}

Leetcode 230.二叉搜索树中第K小的元素

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Queue<TreeNode>q = new LinkedList();
        q = addToQueue(root,q);
        while(k-->0){
            if (k==0)return q.peek().val;
            q.poll();
        }
        return -1;
    }
    public Queue<TreeNode> addToQueue(TreeNode node,Queue<TreeNode>q){
        if (node!=null){
            addToQueue(node.left,q);
            q.add(node);
            addToQueue(node.right,q);
        }
        return q;
    }
}

Leetcode 98.验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        Queue<TreeNode>q = new LinkedList();
        q = addToQueue(root,q);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if (q.size()==0)return true;
            if (node.val>=q.peek().val)return false;
        }
        return true;
    }
    public Queue<TreeNode> addToQueue(TreeNode node,Queue<TreeNode>q){
        if (node!=null){
            addToQueue(node.left,q);
            q.add(node);
            addToQueue(node.right,q);
        }
        return q;
    }
}

Leetcode 112.路径总和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    boolean flag = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        judgeDFS(root,0,targetSum);
        return flag;
    }
    public void judgeDFS(TreeNode node,int currentNum,int targetSum){
        if (node!=null){
            currentNum+=node.val;
            if (currentNum==targetSum&&node.left==null&&node.right==null)flag = true;
            judgeDFS(node.left,currentNum,targetSum);
            judgeDFS(node.right,currentNum,targetSum);
        }
    }
}

Leetcode 173.二叉搜索树迭代器

class BSTIterator {
    int currentIndex = -1;
    List<TreeNode> nodeList = new ArrayList(); 
    public BSTIterator(TreeNode root) {
        midOrder(root);
    }
    public void midOrder(TreeNode node){
        if (node==null)return;
        midOrder(node.left);
        nodeList.add(node);
        midOrder(node.right);
    }
    
    public int next() {
        currentIndex++;
        return nodeList.get(currentIndex).val;
    }
    
    public boolean hasNext() {
        int nextIndex = currentIndex+1;
        return nextIndex<nodeList.size();
    }
}

Leetcode 222.完全二叉树的节点个数

class Solution {
    int count=0;
    public int countNodes(TreeNode root) {
        getCount(root);
        return count;
    }
    public void getCount(TreeNode node){
        if (node==null)return;
        count++;
        getCount(node.left);
        getCount(node.right);
    }
}

Leetcode 236.二叉树的最近公共祖先

class Solution {
    Map<TreeNode,TreeNode>fatherMap = new HashMap();
    Map<TreeNode,Integer>depthMap = new HashMap();
    int depth=0;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        getMap(root);
        Queue<TreeNode>queue = new LinkedList();
        Queue<Integer>queue2 = new LinkedList();
        queue.add(root);
        queue2.add(depth);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            int depth = queue2.poll();
            if (node!=null){
                depthMap.put(node,depth);
                queue.add(node.left);
                queue.add(node.right);
                queue2.add(depth+1);
                queue2.add(depth+1);
            }
        }
        int depth1 = depthMap.get(p);
        int depth2 = depthMap.get(q);
        TreeNode ans = null;
        TreeNode p1 = p;
        TreeNode q1 = q;
        if (depth1==depth2){
            while(true){
                TreeNode father1 = fatherMap.get(p1);
                TreeNode father2 = fatherMap.get(q1);
                if (father1==father2){
                    ans = father1;
                    return ans;
                }
                p1 = father1;
                q1 = father2;
            }
        }else {
            int gap = Math.abs(depth1-depth2);
            if (depth1>depth2){
                for (int i=0;i<gap;i++){
                    p1=fatherMap.get(p1);
                }
                //此时depth相等;
                //若已经相同
                if (p1==q1)return p1;
                while(true){
                TreeNode father1 = fatherMap.get(p1);
                TreeNode father2 = fatherMap.get(q1);
                if (father1==father2){
                    ans = father1;
                    return ans;
                    }
                p1 = father1;
                q1 = father2;
                }
            }else{
                for (int i=0;i<gap;i++){
                    q1=fatherMap.get(q1);
                }
                //此时depth相等;
                //若已经相同
                if (p1==q1)return p1;
                while(true){
                TreeNode father1 = fatherMap.get(p1);
                TreeNode father2 = fatherMap.get(q1);
                if (father1==father2){
                    ans = father1;
                    return ans;
                    }
                p1 = father1;
                q1 = father2;
                }
            }
        }
            // return ans;
        }
        public void getMap(TreeNode node){
        if (node ==null)return;
        if (node.left!=null)fatherMap.put(node.left,node);
        if (node.right!=null)fatherMap.put(node.right,node);
        getMap(node.left);
        getMap(node.right);
    }
    }

递归的做法

class Solution {

    private TreeNode ans;

    public Solution() {
        this.ans = null;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
}

Leetcode 102.二叉树的层序遍历

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        Map<Integer,List<Integer>> depthNodeListMap = new HashMap();
        Queue<TreeNode> nodeQueue = new LinkedList();
        Queue<Integer> depthQueue = new LinkedList();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (root==null)return ans;
        int firstDepth = 0;
        nodeQueue.add(root);
        depthQueue.add(firstDepth);
        int maxDepth = -1;
        while(!nodeQueue.isEmpty()){
            TreeNode node =nodeQueue.poll();
            int depth  = depthQueue.poll();
            if (node!=null){
                maxDepth = Math.max(depth,maxDepth);
                if (!depthNodeListMap.containsKey(depth)){
                    List<Integer> list= new ArrayList();
                    depthNodeListMap.put(depth,list);
                }
                depthNodeListMap.get(depth).add(node.val);
                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth+1);
                depthQueue.add(depth+1);
            }
        }
        
        for (int depth=0;depth<=maxDepth;depth++){
            ans.add(depthNodeListMap.get(depth));
        }
        return ans;
    }
}

Leetcode 427.建立四叉树

官方题解

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}
*/
class Solution {
    public Node construct(int[][] grid) {
        return dfs(grid, 0, 0, grid.length, grid.length);
    }

    public Node dfs(int[][] grid, int r0, int c0, int r1, int c1) {
        boolean same = true;
        for (int i = r0; i < r1; ++i) {
            for (int j = c0; j < c1; ++j) {
                if (grid[i][j] != grid[r0][c0]) {
                    same = false;
                    break;
                }
            }
            if (!same) {
                break;
            }
        }
		//全相同即为叶子结点
        if (same) {
            return new Node(grid[r0][c0] == 1, true);
        }
		//否则递归返回
        Node ret = new Node(
            true,
            false,
            dfs(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            dfs(grid, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            dfs(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            dfs(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return ret;
    }
}

Leetcode 124.二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getAns(root);
        return ans;
    }
    public int getAns(TreeNode node){
        if (node==null)return 0;
        int leftMax = Math.max(getAns(node.left),0);
        int rightMax = Math.max(getAns(node.right),0);

        int currentNum = node.val + leftMax + rightMax;
        ans = Math.max(ans,currentNum);
        //返回最大的子节点
        return node.val+Math.max(rightMax,leftMax);
    }
}

Leetcode 637.二叉树的层平均值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDepth = -1;
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double>ans = new ArrayList();
        Queue<TreeNode>q = new LinkedList();
        Queue<Integer> depthQ = new LinkedList();
        Map<Integer,List<TreeNode>> map = new HashMap();
        q.add(root);
        depthQ.add(0);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            int depth = depthQ.poll();
            if (node!=null){
                maxDepth = Math.max(maxDepth,depth);
                List<TreeNode> nodeList = map.getOrDefault(depth,new  ArrayList<TreeNode>());
                nodeList.add(node);
                map.put(depth,nodeList);
                q.add(node.left);
                q.add(node.right);
                depthQ.add(depth+1);
                depthQ.add(depth+1);
            }
        }
        for (int i =0;i<=maxDepth;i++){
            List<TreeNode> nodeList = map.get(i);
            if (nodeList!=null)
            ans.add(getAverage(nodeList));
        }
        return ans;

    }
    public double getAverage(List<TreeNode> nodeList){
        int size= nodeList.size();
        double sum = 0;
        for (TreeNode node:nodeList){
            sum =sum+node.val;
        }
        return sum/size;
    }
}

Leetcode 103.二叉树的锯齿形层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDepth =-1;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<TreeNode>q = new LinkedList();
        Map<Integer,List<Integer>>map = new HashMap();
        Queue<Integer> depthQ = new LinkedList();
        q.add(root);
        depthQ.add(0);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            int depth = depthQ.poll();
            if (node!=null){
                maxDepth = Math.max(depth,maxDepth);
                List<Integer>list = map.getOrDefault(depth,new ArrayList<Integer>());
                list.add(node.val);
                map.put(depth,list);
                q.add(node.left);
                q.add(node.right);
                depthQ.add(depth+1);
                depthQ.add(depth+1);
            }
        }
        for (int i=0;i<=maxDepth;i++){
            List<Integer>list = map.get(i);
            if (i%2==0){
                ans.add(list);
            }else{
                Collections.reverse(list);
                ans.add(list);
            }
        }
        return ans;
    }
}

Leetcode 530.二叉搜索树的最小绝对差

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Queue<Integer>q = new PriorityQueue<Integer>((a,b)->a-b);

    public int getMinimumDifference(TreeNode root) {
        preOrder(root);
        int ans = Integer.MAX_VALUE;
        while (!q.isEmpty()){
            int a = q.poll();
            if (q.isEmpty())break;
            int b = q.peek();
            ans = Math.min(ans,Math.abs(a-b));
        }
        return ans;
    }
    public void preOrder(TreeNode node){
        if (node==null)return;
        q.add(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }
}

堆

Leetcode 373.查找和最小的K对数字

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2)->{
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });
        List<List<Integer>> ans = new ArrayList<>();
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i < Math.min(m, k); i++) {
            pq.offer(new int[]{i,0});
        }
        while (k-- > 0 && !pq.isEmpty()) {
            int[] idxPair = pq.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            ans.add(list);
            if (idxPair[1] + 1 < n) {
                pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
            }
        }
        
        return ans;
    }
}

Leetcode 215.数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer>q = new PriorityQueue(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return b-a;
            }
        });
        for (int num:nums){
            q.add(num);
        }
        while(k-->0){
            if (k==0)return q.poll();
            q.poll();
        }
        return 0;
    }
}

数学

Leetcode 201.数字范围按位与

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int move = 0;
        int m=left;
        int n=right;
        while (m!=n){
            m=m>>1;
            n=n>>1;
            move++;
        }
        return m<<move;
    }
}

Kadane算法

Leetcode 53.最大子数组和

常规用前缀和会超时

//超时
class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int prefixSum[] = new int[length+1];
        prefixSum[0]=0;
        for (int i=0;i<length;i++){
            prefixSum[i+1]=prefixSum[i]+nums[i];
        }
        int ans = Integer.MIN_VALUE;
        for (int i=0;i<length;i++){
            for (int j=i+1;j<=length;j++){
                int gap = prefixSum[j]-prefixSum[i];
                ans = Math.max(gap,ans);
            }
        }
        return ans;
    }
}

优化后的前缀和

class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int prefixSum[] = new int[length+1];
        prefixSum[0]=0;
        for (int i=0;i<length;i++){
            prefixSum[i+1]=prefixSum[i]+nums[i];
        }
        int ans = Integer.MIN_VALUE;
        int p=0;
        for (int i=1;i<=length;i++){
            if (prefixSum[p]>=prefixSum[i]){
                ans = Math.max(ans, prefixSum[i]-prefixSum[i-1]);
                p=i;
            }else{
                ans = Math.max(ans, prefixSum[i]-prefixSum[p]);
            }
        }
        return ans;
    }
}