Java 数据结构基础构建方法整理
本文持续更新，总结不完整或有误的地方请谅解。
版权归属：LP学长
ACM 模式 Input/Output
主函数模板
import java.util.*;
public class Main {
public static void main(String[] args) {
// ....
}
}java.util.Scanner
- nextInt()：直至读取到空格或回车之后结束本次的 int 值；
- next()：直至读取到空格或回车之后结束本次的 String 值，不可读取回车；
- nextLine()：直至读取到换行符（回车）之后结束本次读取的 String，可读取回车（空值）
- hasNext()：如果此扫描器的输入中有另一个标记，则返回 true
/* 读取连续整数 */
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int a = sc.nextInt();
int b = sc.nextInt();
}
/* 读取有限整数 */
Scanner in = new Scanner(System.in);
int n = in.nextInt();
while(n-- > 0){
int a = in.nextInt();
int b = in.nextInt();
System.out.println(a + b);
}
/* 分隔符 */
Scanner in = new Scanner(System.in);
String[] strs = in.nextLine().split(" ");java.io.BufferedReader 和 java.io.InputStreamReader
/* 输入为一个字符串 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
/* 输入为多个数字 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
String[] strs = line.trim().split(" ");
int n = Integer.parseInt(strs[0]);转换符
| 转换符 | 说明 | 示例 | 输出 |
|---|---|---|---|
| %s | 字符串 | “Hi,%s:%s.%s”, “王南”,“王力”,“王张” | Hi,王南:王力.王张 |
| %c | 字符 | “字母a的大写是：%c %n”, ‘A’ | 字母a的大写是：A |
| %b | 布尔 | “3>7的结果是：%b %n”, 3>7 | 3>7的结果是：false |
| %d | 整数(十进制) | “100的一半是：%d %n”, 100/2 | 100的一半是：50 |
| %x | 整数(十六进制) | “100的16进制数是：%x %n”, 100 | 100的16进制数是：64 |
| %o | 整数(八进制) | “100的8进制数是：%o %n”, 100 | 100的8进制数是：144 |
| %f | 浮点 | “50元的书打8.5折扣是：%f 元%n”, 50*0.85 | 50元的书打8.5折扣是：42.500000 元 |
| %a | 浮点(十六进制) | “上面价格的16进制数是：%a %n”, 50*0.85 | 上面价格的16进制数是：0x1.54p5 |
| %e | 指数 | “上面价格的指数表示：%e %n”, 50*0.85 | 上面价格的指数表示：4.250000e+01 |
| %g | 通用浮点(f和e类型中较短的) | “上面价格的指数和浮点数结果的长度较短的是：%g %n”, 50*0.85 | 上面价格的指数和浮点数结果的长度较短的是：42.5000 |
| %h | 散列码 | “字母A的散列码是：%h %n”, ‘A’ | 字母A的散列码是：41 |
| %% | 百分比 | “上面的折扣是%d%% %n”, 85 | 上面的折扣是85% |
| %n | 换行符 | ||
| %tx | 日期与时间 |
eg.
String str = null;
str = String.format("Hi, %s, %.2f", "小超", 3.141);
System.out.println(str); // Hi, 小超, 3.1401 链表
构造类
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}节点操作
/* 添加节点 */
prev.next.next = prev.next;
prev.next.val = value;
/* 删除节点 */
prev.next = prev.next.next;
/* 查找中间节点 */
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next; // slow -> 中部
fast = fast.next.next; // fast -> 结尾
}反转链表
定义：输入一个单链表头结点，将该链表反转，返回新的头结点
// 迭代方法
ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
// 递归方法
ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}链表排序
/* 无序链表-->升序链表（插入排序） */
ListNode sortListNode(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 新建一个哨兵节点，next 指向头节点
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode cur = head.next;
head.next = null;
// 遍历链表所有节点
while (cur != null) {
// 从链表头开始寻找插入位置
ListNode pre = dummyHead;
ListNode temp = cur.next;
while (pre.next != null && cur.val > pre.next.val) {
pre = pre.next;
}
// 插入节点
cur.next = pre.next;
pre.next = cur;
cur = temp;
}
return dummyHead.next;
}
/* 合并两个有序链表 */
ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
} else if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list2.next, list1);
return list2;
}
}02 数组
内置数组
/* 动态读取整型数组 */
Scanner scan = new Scanner(System.in);
String[] str = scan.nextLine().split(" "); // 字符串以空格分割
int[] nums = new int[str.length];
for (int i = 0; i < str.length; i++) {
nums[i] = Integer.parseInt(String.valueOf(str[i]));
}
/* 输出 */
System.out.println(Arrays.toString(nums));ArrayList
/* 初始化 */
List<String> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>(Arrays.asList("apple", "banana", "orange"));
List<String> list3 = new ArrayList<>(Collections.nCopies(2, "orange")); // [orange, orange]
// 匿名内部类
List<String> list4 = new ArrayList<>() {
{
add("apple");
add("banana");
add("orange");
}
};
/* 输出 */
System.out.println(list4);数组和 List 的转换
整型数组需要进行 Integer[] -> int[] 的转换，需要用到 InputStream，建议采用循环赋值的方法
/* List -> Object[] */
List<String> list = new ArrayList<String>(){{add("aa"); add("bb"); add("cc");}};
String[] strs = list.toArray(new String[list.size()]);
/* Object[] -> List */
String[] arrays = {"aa", "bb", "cc"};
List<String> arrayList = Arrays.asList(arrays);
/* 以上方法不适用于基本数据类型 */
/* int[] -> Integer[] */
int[] arrays = {1, 2, 3};
Integer[] integers1 = Arrays.stream(arrays).boxed().toArray(Integer[]::new);
/* Integer[] -> int[] */
Integer[] integers = {1, 2, 3};
int[] arr = Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();
/* List -> int[] */
List<Integer> list = new ArrayList<Integer>(){{add(1); add(2); add(3);}};
int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
/* int[] -> List */
int[] arrays = {1, 2, 3};
List<Integer> list = Arrays.stream(arrays).boxed().collect(Collectors.toList());自定义排序规则
[void] Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
根据指定比较器引发的顺序对指定对象数组的指定范围进行排序
eg. 区间排序，根据左边界大小升序
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
// lambda 简化为：
Arrays.sort(intervals, (interval1, interval2) -> {
return interval1[0] - interval2[0];
// String: return str1.compareTo(str2);
});:star:前缀和、差分
一维前缀和
class NumArray {
// 前缀和数组
private int[] preSum;
/* 输入一个数组，构造前缀和 */
public NumArray(int[] nums) {
// preSum[0] = 0，便于计算累加和
preSum = new int[nums.length + 1];
// 计算 nums 的累加和
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [left, right] 的累加和 */
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}二维前缀和
class NumMatrix {
// 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
private int[][] preSum;
public NumMatrix(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
if (n == 0 || m == 0) return;
// 构造前缀和矩阵
preSum = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
}
}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
public int sumRegion(int x1, int y1, int x2, int y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
}
}一维差分数组
class Difference {
private int[] diff;
/* 输入一个初始数组，区间操作将在这个数组上进行 */
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}03 字符串
基础用法
/* 字符串和字符数组的转换 */
// String -> char[]
char[] charArr = str.toCharArray();
// char[] -> String
String str = new String(charArr);
/* StringBuilder 与 StringBuffer */
// StringBuilder 相较于 StringBuffer 有速度优势，多数情况下建议使用 StringBuilder 类。在应用程序要求线程安全的情况下，则必须使用 StringBuffer 类
StringBuilder sb = new StringBuilder("a");
sb.append("bb"); // abb字符串排序
// str = "abds237sasd9skk"
void characterSort(String str) {
System.out.println("原字符串：\n" + str);
char[] chars = str.toCharArray();
Arrays.sort(chars);
// 正序遍历输出
System.out.println("正序输出：");
for (char c : chars) {
System.out.print(c); // 2379aabddkkssss
}
// 倒序遍历输出
System.out.println("\n倒序输出：");
for (int i = chars.length - 1; i >= 0; i--) {
System.out.print(chars[i]); // sssskkddbaa9732
}
}字符串翻转
// 方法一：StringBuffer
String reverse1(String str) {
return new StringBuilder(str).reverse().toString();
}
// 方法二：字符数组翻转
void reverse(char[] chars, int start, int end) {
char tmp = 0;
while (start < end) {
tmp = chars[start];
chars[start] = chars[end];
chars[end] = tmp;
start++;
end--;
}
}:star:前缀树
class TrieNode {
public TrieNode[] nexts;
public TrieNode() {
nexts = new TrieNode[num]; // num 代表向下路径的数量
}
}
class NumTrie {
// 根节点
private TrieNode root;
public NumTrie() { root = new TrieNode(); }
// 插入节点
public void insert(T t) {
TrieNode node = root;
for (t.length) {
int index = val; // index 代表选择的路径
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
}
}
// 删除节点
public void delete(T t) {...}
// 查找节点
public T search(T t) {...}
// 是否含有前缀
public boolean startsWith(T t) {...}
}04 二叉树
构造类（整数节点）
static 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;
}
}得到二叉树的高度：
int height = getHeight(root, 0);
int getHeight(TreeNode head, int height) {
if (head == null) {
return height;
}
return Math.max(getHeight(head.left, height + 1), getHeight(head.right, height + 1));
}序列化二叉树
1）递归遍历
List<Integer> Traversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
robot(root, ans); // 区别在于递归函数
return ans;
}
void robot(TreeNode root, List<Integer> ans) {
if(root == null) return;
/* 前序遍历 */
ans.add(root.val);
robot(root.left, ans);
robot(root.right, ans);
/* 中序遍历 */
robot(root.left, ans);
ans.add(root.val);
robot(root.right, ans);
/* 后序遍历 */
robot(root.left, ans);
robot(root.right, ans);
ans.add(root.val);
}
/* 层次遍历 */
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
robot(root, ans, 0);
return ans;
}
void robot(TreeNode root, List<List<Integer>> ans, int levelIndex) {
if (root == null) {
return;
}
if (ans.size() == levelIndex) {
ans.add(new ArrayList<>());
}
ans.get(levelIndex).add(root.val);
robot(root.left, ans, levelIndex + 1);
robot(root.right, ans, levelIndex + 1);
}2）迭代遍历
前序遍历
1．申请一个新的栈，记为 stack。然后将头节点 head 压入 stack 中。
2．从 stack 中弹出栈顶节点，记为 cur，然后打印 cur 节点的值，再将节点 cur 的右孩子节点（不为空的话）先压入 stack 中，最后将 cur 的左孩子节点（不为空的话）压入 stack 中。
3．不断重复步骤 2，直到 stack 为空，全部过程结束。
List<Integer> preOrderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root != null) {
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
ans.add(root.val);
// 将其孩子节点压入栈中（先右节点、再左节点）
if (root.right != null) {
root.push(root.right);
}
if (root.left != null) {
root.push(root.left);
}
}
}
return ans;
}中序遍历
1．申请一个新的栈，记为 stack。初始时，令变量 cur=head。
2．先把 cur 节点压入栈中，对以 cur 节点为头节点的整棵子树来说，依次把左边界压入栈中，即不停地令 cur=cur.left，然后重复步骤 2。
3．不断重复步骤 2，直到发现 cur 为空，此时从 stack 中弹出一个节点，记为 node。打印 node 的值，并且让 cur=node.right，然后继续重复步骤 2。
4．当 stack 为空且 cur 为空时，整个过程停止。
List<Integer> inOrderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root != null) {
Deque<TreeNode> stack = new ArrayDeque<>();
while (!stack.isEmpty() || root != null) {
// 一直放入左儿子（左）
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
ans.add(root.val);
root = root.right;
}
}
}
return ans;
}后序遍历
1．申请一个栈，记为 s1，然后将头节点 head 压入 s1 中。
2．从 s1 中弹出的节点记为 cur，然后依次将 cur 的左孩子节点和右孩子节点压入 s1 中。
3．在整个过程中，每一个从 s1 中弹出的节点都放进 s2 中。
4．不断重复步骤 2 和步骤 3，直到 s1 为空，过程停止。
5．从 s2 中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。
List<Integer> postOrderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (head != null) {
Deque<TreeNode> s1 = new ArrayDeque<>();
Deque<TreeNode> s2 = new ArrayDeque<>();
s1.push(root);
while (!s1.isEmpty()) {
root = s1.pop();
s2.push(root);
if (root.left != null) {
s1.push(root.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()) {
ans.add(s2.pop().val);
}
}
return ans;
}层次遍历
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> current = new ArrayList<>();
for (int i = 0; i < queue.size(); ++i) {
TreeNode node = queue.poll();
current.add(node.val);
// 依次将 node 的左右子节点加入队列
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ans.add(current);
}
return ans;
}:star:构造二叉树
前序、中序遍历构造二叉树
public TreeNode buildTree(int[] pre, int[] in) {
return robot(pre, in, 0, 0, in.length - 1);
}
private TreeNode robot(int[] pre, int[] in, int preStart, int inStart, int inEnd) {
if (preStart >= pre.length || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
int pos = 0;
// 找到 pos
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == root.val) {
pos = i;
break;
}
}
root.left = robot(pre, in, preStart + 1, inStart, pos - 1);
root.right = robot(pre, in, preStart + 1 + pos - inStart, pos + 1, inEnd);
return root;
}中序、后序遍历构造二叉树
public TreeNode buildTree(int[] in, int[] post) {
return robot(in, post, 0, in.length - 1, 0, post.length - 1);
}
private TreeNode robot(int[] in, int[] post, int inStart, int inEnd, int postStart, int postEnd) {
if (postStart > postEnd) {
return null;
}
TreeNode root = new TreeNode(post[postEnd]);
int pos = 0;
// 找到 pos
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == root.val) {
pos = i;
break;
}
}
root.left = robot(in, post, inStart, pos - 1, postStart, postStart + pos - inStart - 1);
root.right = robot(in, post, pos + 1, inEnd, postEnd + pos - inEnd, postEnd - 1);
return root;
}构造二叉搜索树
二叉搜索树（Binary Search Tree, BST），又名二叉查找树、二叉排序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。
有序数组构建二叉搜索树
TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return rebot(nums, 0, nums.length - 1);
}
private TreeNode rebot(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = rebot(nums, left, mid - 1);
root.right = rebot(nums, mid + 1, right);
return root;
}先序遍历构造二叉搜索树
- 1 <= preorder.length <= 100
- 先序 preorder 中的值是不同的
int index = 0;
public TreeNode bstFromPreorder(int[] preorder) {
return robot(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode robot(int[] preorder, int min, int max) {
if (index == preorder.length) {
return null;
}
int val = preorder[index];
if (val < min || val > max) {
return null;
}
index++;
TreeNode root = new TreeNode(val);
root.left = robot(preorder, min, val);
root.right = robot(preorder, val, max);
return root;
}判断平衡二叉树
平衡二叉查找树：简称平衡二叉树（AVL 树）。假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。
// 方法一：采用后序遍历，可以避免重复遍历节点
boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
private int height(TreeNode root) {
if (root == null) {
return 0;
}
int left = height(root.left);
int right = height(root.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
// 非平衡二叉树赋值为 -1
return -1;
} else {
return Math.max(left, right) + 1;
}
}
// 方法二：树形 dp 套路
class ReturnType {
public boolean isBalanced;
public int height;
public ReturnType(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
ReturnType process(Node head) {
if (head == null) {
return new ReturnType(true, 0);
}
ReturnType leftData = process(head.left);
ReturnType rightData = process(head.right);
int height = Math.max(leftData.height, rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced
&& Math.abs(leftData.height - rightData.height) < 2;
return new ReturnType(isBalanced, height);
}
boolean isBalanced(Node head) {
return process(head).isBalanced;
}判断完全二叉树
完全二叉树：对于一个树高为 h 的二叉树，其第 0 层至第 h-1 层的节点都满，如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。（特殊结构：满二叉树）
boolean isCBT(TreeNode head) {
if (head == null) {
return true;
}
Deque<TreeNode> queue = new LinkedList<>();
boolean leaf = false;
TreeNode l = null, r = null;
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if ((leaf&&(l!=null||r!=null)) || (l==null&&r!=null)) {
return false;
}
if (l != null) {
queue.offer(l);
}
if (r != null) {
queue.offer(r);
} else {
leaf = true;
}
}
return true;
}05 栈和队列
双端队列 Deque
JDK 中提供了一个堆栈类 Stack，继承了 Vector，提供了常见的 push 和 pop 操作，但已经不再建议使用，可以使用更完善、可靠性更强的 LIFO 操作，由
Deque接口和它的实现类，它既可以当栈使用，又可以当队列使用。
Deque 接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：
| Queue 方法 | 等效 Deque 方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：
| 堆栈方法 | 等效 Deque 方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
为什么选择 ArrayDeque ?
- ArrayDeque 底层循环数组实现，不容置疑，查询效率肯定高于 LinkedList。
- 循环数组不会存在删除数据后需要挪动后面的数据，所以摒弃了数组删除效率慢的问题。
优先队列 PriorityQueue
// 默认为最小优先队列
Queue<Integer> min = new PriorityQueue<>();
min.offer(1);
min.offer(3);
min.offer(10);
min.peek(); // 1
// 自定义比较器
Queue<Integer> max = new PriorityQueue<>((x, y) -> y - x);
max.offer(1);
max.offer(3);
max.offer(10);
max.peek(); // 10:star:单调栈结构
Deque<Integer> stack = new ArrayDeque<>();
// 遍历这个数组
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && 限制条件) {
弹出数据;
更新结果;
}
压入数据;
}
// 遍历栈中剩余元素并更新结果
while (!stack.isEmpty()) {
弹出数据;
更新结果;
}参考：
06 递归和动态规划
一般解题步骤：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
经典题目参考：动态规划 - Zbiao | 多吃一点
07 Map 映射关系
HashMap 与 LinkedHashMap
| 关注点 | HashMap | LinkedHashMap |
|---|---|---|
| 是否允许空 | Key 和 Value 都允许空 | Key 和 Value 都允许空 |
| 是否允许重复数据 | Key 重复会覆盖、Value 允许重复 | Key 重复会覆盖、Value 允许重复 |
| 是否有序 | 无序 | 有序 |
| 是否线程安全 | 非线程安全 | 非线程安全 |
遍历 Map
/* for-each 循环 */
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
/* 遍历 keys 或 values */
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//遍历 map 中的键
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
//遍历 map 中的值
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
/* 使用 Iterator 遍历 */
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}08 有序表结构
TreeMap
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(7, "我是7");
treeMap.put(5, "我是5");
treeMap.put(9, "我是9");
treeMap.put(2, "我是2");
treeMap.firstKey(); // 2 (最小)
treeMap.lastKey(); // 9 (最大)
treeMap.floorKey(8); // 7 (<=8)
treeMap.ceilingKey(8); // 9 (>=8)
treeMap.remove(5);TreeSet
Node nodeA = new Node(5);
Node nodeB = new Node(3);
// 非基础类型必须提供比较器
TreeSet<Node> treeSet = new TreeSet<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
});
treeSet.add(nodeA);
treeSet.add(nodeB);
treeSet.first();
treeSet.last();
treeSet.floor(4); // nodeB
treeSet.ceiling(4); // nodeA09 多叉树
public class MultiTree {
public static class TreeNode {
int val;
List<TreeNode> children;
public TreeNode(int val) {
this.val = val;
this.children = new ArrayList<>();
}
}
/**
* 根据邻接关系构建多叉树
*
* @param edges 邻接关系数组
* @param n 节点总数
* @return 多叉树
*/
public static TreeNode buildTree(List<int[]> edges, int n) {
Map<Integer, List<Integer>> graph = new HashMap<>();
// 使用邻接表存储图的信息
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
if (!graph.containsKey(from)) {
graph.put(from, new ArrayList<>());
}
graph.get(from).add(to);
}
// 使用 DFS 构造多叉树
boolean[] visited = new boolean[n];
TreeNode root = new TreeNode(0);
dfs(graph, visited, root);
return root;
}
private static void dfs(Map<Integer, List<Integer>> graph, boolean[] visited, TreeNode node) {
visited[node.val] = true;
List<Integer> neighbors = graph.get(node.val);
if (neighbors == null) return;
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
TreeNode child = new TreeNode(neighbor);
node.children.add(child);
dfs(graph, visited, child);
}
}
}
/**
* 输出多叉树的所有路径
*
* @param root
* @return
*/
public static List<String> listPath(TreeNode root) {
List<String> pathList = new ArrayList<>();
listPath(root, "", pathList);
return pathList;
}
private static void listPath(TreeNode root, String path, List<String> pathList) {
if (root.children.isEmpty()) { // 叶子节点
path = path + root.val;
pathList.add(path); // 将结果保存在list中
} else { // 非叶子节点
path = path + root.val + "->";
// 进行子节点的递归
List<TreeNode> children = root.children;
for (TreeNode node : children) {
listPath(node, path, pathList);
}
}
}
}Java 数据结构基础构建方法整理
http://lpxz.work/posts/9692e0ef/