一：栈
1.1 删除字符串中的所有相邻重复项
题目链接：删除字符串中的所有相邻重复项
class Solution {
public String removeDuplicates(String _s) {
// 用 StringBuffer 模拟一下栈结构
StringBuffer ret = new StringBuffer();
// 接着把 _s 转换为字符数组方便操作
char[] s = _s.toCharArray();
// 接着遍历一下这个字符数组
for(char ch : s){
// 因为栈顶元素的索引是 ret 的长度减一，为了保证不发生越界访问，我们要保证 ret 中的元素不为空
//要避免越界异常，需要首先判断 ret 是否为空，再访问栈顶元素： if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1))
if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1)) ret.deleteCharAt(ret.length() - 1);
else ret.append(ch);
}
// 循环结束后 ret 就存储着最终的结果，返回即可
return ret.toString();
}
}
1.2 比较含退格的字符串
题目链接：比较含退格的字符串
class Solution {
public boolean backspaceCompare(String s, String t)
{
// 调用 changeStr 方法处理字符串 s 和 t，比较它们的处理结果是否相等
return changeStr(s).equals(changeStr(t));
}
// 辅助方法：将字符串中的退格符号（#）应用到字符串，返回最终的结果
public String changeStr(String s){
// 此时使用 StringBuffer 模拟栈结构
StringBuffer ret = new StringBuffer();
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(ch != '#') ret.append(ch);
else{
// 如果栈非空（ret 中有字符），删除栈顶字符（出栈操作）
if (ret.length() > 0) ret.deleteCharAt(ret.length() - 1);
}
}
return ret.toString();
}
}
1.3 基本计算器 II
题目链接：基本计算器 II
class Solution {
public int calculate(String _s) {
// 用栈存储 Integer 类型的数字
Stack<Integer> st = new Stack<>();
char[] s = _s.toCharArray();
char op = '+'; // 因为这题没有括号，我们明显知道乘除的优先级是大于加减的，因此不必用一个栈来存储符号，用一个字符即可
int i = 0,n = s.length; // 遍历字符串的变量 i 以及字符数组 s 的长度 n
// 开始遍历字符串
while(i < n){
// 首先先跳过空格
if(s[i] == ' ') i++;
else if (s[i] >= '0' && s[i] <= '9') {
// 先把数字提取出来，用 tmp 临时存储一下数字
int tmp = 0;
while(i < n && s[i] <= '9' && s[i] >= '0'){ // 因为在提取字符时要让 i 移动，所以我们要保证 i 不越界以及这个字符是数字
tmp = tmp * 10 + (s[i] - '0');
i++;
}
// 接着分情况讨论
if(op == '+') st.push(tmp);
else if(op == '-') st.push(-tmp);
else if(op == '*') st.push(st.pop() * tmp);
else st.push(st.pop() / tmp);
}else op = s[i++];
}
// while 循环结束后，st 存的就都是正数和负数了，我们要把栈中的元素取出来相加
int sum = 0;
for(int x : st) sum += x;
return sum;
}
}
1.4 字符串解码
题目链接：字符串解码
class Solution {
public String decodeString(String _s) {
// 我们用两个 Stack 分别存储字符串和重复数字
Stack<StringBuffer> st = new Stack<>(); // 存储字符串
Stack<Integer> nums = new Stack<>(); // 存储重复次数
st.push(new StringBuffer());; // 先往 st 中丢一个空字符串，方便处理边界情况
char[] s = _s.toCharArray();
int n = s.length, i = 0; // n 用于存储字符数组的长度， i 用于遍历字符数组
while(i < n){
if(s[i] >= '0' && s[i] <= '9'){ // 当 i 遇到数字时
int tmp = 0; // 用 tmp 临时存储一下数字
while(i < n && s[i] >= '0' && s[i] <= '9'){ // 因为 i 会加加，为了防止数组越界还是判断一下，并判断一下当前的字符加加后是不是还是数字
tmp = tmp * 10 + (s[i] - '0');
i++;
}
nums.push(tmp);
}
else if(s[i] == '['){ // 当 i 遇到了左括号时
// 把左括号后面的字符提取出来，放入 st 中
i++; // 先跳过字符'['
StringBuffer tmp = new StringBuffer(); // 用于存储括号内的部分字符串
while(s[i] >= 'a' && s[i] <= 'z'){
tmp.append(s[i]);
i++;
}
// 当循环结束后，把 tmp 丢入 st 中
st.push(tmp);
}
else if(s[i] == ']'){ // 当 i 遇到了右括号时
// 取出 st 中的字符串和 nums 中的数字进行解析，解析完后拼接在 st 栈顶元素的后面
StringBuffer tmp = st.pop();
int k = nums.pop();
while(k > 0){
st.peek().append(tmp);
k--;
}
i++; // 跳过右括号
}
else{ // 遇到了普通的字符
StringBuffer tmp = new StringBuffer(); // 临时存储连续的字母
while (i < n && s[i] >= 'a' && s[i] <= 'z'){
tmp.append(s[i]);
i++;
}
// 将提取的字母拼接到当前栈顶字符串中
st.peek().append(tmp);
}
}
// 返回最终拼接结果
return st.peek().toString();
}
}
1.5 验证栈序列
题目链接：验证栈序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 用 st 来记录已经入栈的信息
Stack<Integer> st = new Stack<>();
int i = 0, n = popped.length; // i 用来遍历 popped 数组，n 用来记录数组长度
for(int x : pushed){
// 先把元素丢进 st 中
st.push(x);
// 接着循环判断一下是否需要出栈,出栈要保证元素不为空
while(st.isEmpty() == false && st.peek() == popped[i]){
st.pop();
i++;
}
}
//循环结束后判断一下 i 是否等于 n 就可以了
return i == n;
}
}
二：队列+宽搜
2.1 N 叉树的层序遍历
题目链接：N 叉树的层序遍历
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
// 用 ret 存储最终的结果
List<List<Integer>> ret = new ArrayList<>();
// 用队列 q 来模拟层序遍历的过程
Queue<Node> q = new LinkedList<>();
// 如果根节点为空，直接返回空列表
if (root == null) return ret;
else q.add(root); // 先把根节点丢进去
// 接下来开始循环了，只要队列不为空就一直循环
while(!q.isEmpty()){
// 首先用 sz 存储一下这一层有多少个元素
int sz = q.size();
List<Integer> tmp = new LinkedList<>(); // 用来临时存储这一层的 t.val 值
for(int i = 0; i < sz; i++){
Node t = q.poll();
tmp.add(t.val);
// 接着把 t 的子元素放进去
for(Node child : t.children){
if (child != null) q.add(child);
}
}
// 将当前层的节点值列表加入最终结果列表
ret.add(tmp);
}
// 当循环结束后 ret 就存储着最终结果
return ret;
}
}
2.2 二叉树的锯齿形层序遍历
题目链接：二叉树的锯齿形层序遍历
/**
* 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// 用 ret 存储最终的结果,q 模拟程序遍历的过程
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
int level = 1; // 用于标记当前的层数
if(root == null) return ret; // 如果 root 为空，返回一个空的 ret
else q.add(root);
while(!q.isEmpty()){
int sz = q.size();
List<Integer> tmp = new LinkedList<>();
for(int i = 0; i < sz; i++){
TreeNode t = q.poll();
tmp.add(t.val);
if (t.left != null) q.add(t.left);
if (t.right != null) q.add(t.right);
}
// 判断一下是否需要翻转
if(level % 2 == 0) Collections.reverse(tmp);
ret.add(tmp);
// 这一层结束后让 level 加一
level++;
}
return ret;
}
}
2.3 二叉树最大宽度
题目链接：二叉树最大宽度
/**
* 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 widthOfBinaryTree(TreeNode root) {
// 用 List 模拟队列，pair 分别存储节点以及节点对应的编号
List<Pair<TreeNode, Integer>> q = new ArrayList<>();
// 因为 root 不为空，所以我们直接把 root 添加进去
q.add(new Pair<TreeNode, Integer>(root, 1));
int ret = 0; // 用 ret 记录最终的结果
// 当这一层的队列不为空就继续循环直到这一层的队列元素为空
while(!q.isEmpty()){
// 先计算当前层级的最大宽度，并看看是否需要更新结果
Pair<TreeNode, Integer> t1 = q.get(0); // 获取这层第一个节点
Pair<TreeNode, Integer> t2 = q.get(q.size() - 1); // 获取这层的最后一个节点
ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);
// 接着开始把下一层元素弄到 tmp 中，接着让 tmp 当下一层的 q
// 设置元素需要先获取当前元素的引用和索引
List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
for (Pair<TreeNode, Integer> t : q) {
TreeNode node = t.getKey();
int index = t.getValue();
if (node.left != null) tmp.add(new Pair<TreeNode,Integer>(node.left, index * 2)); // 先处理左孩子
if (node.right != null) tmp.add(new Pair<TreeNode,Integer>(node.right, index * 2 + 1)); // 再处理右孩子
}
// 循环结束后把 tmp 赋给 q，让他当下一层的 q
q = tmp;
}
// 返回最大宽度
return ret;
}
}
2.4 在每个树行中找最大值
题目链接：在每个树行中找最大值
/**
* 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 List<Integer> largestValues(TreeNode root) {
// 用 ret 存储最终的结果
List<Integer> ret = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
if(root == null) return ret;
else q.add(root);
while(!q.isEmpty()){
int sz = q.size(), tmp = Integer.MIN_VALUE; // 先用 sz 记录一下这层的元素个数,tmp 记录这一层的最大值
for(int i = 0; i < sz; i++){
// 从队列中取出一个节点
TreeNode t = q.poll();
// 更新当前层的最大值
tmp = Math.max(tmp, t.val);
// 接着把这个节点的左右孩子添加进去
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
// 循环结束后把 tmp 存在 ret 中
ret.add(tmp);
}
return ret;
}
}
三：优先级队列
3.1 最后一块石头重量
题目链接：最后一块石头重量
class Solution {
public int lastStoneWeight(int[] stones) {
// 此处使用大根堆模拟解题过程
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
// 接着把数组中的元素全丢入大根堆中
for(int x : stones) heap.offer(x);
while(heap.size() >= 2){
int a = heap.poll();
int b = heap.poll();
if(a > b) heap.offer(a - b);
}
// 循环结束后如果大根堆还有元素就是最后的答案，没有元素返回 0
return heap.isEmpty() ? 0 : heap.peek();
}
}
3.2 数据流中的第 K 大元素
题目链接：数据流中的第 K 大元素
class KthLargest {
// 创建一个大小为 k 的小根堆
PriorityQueue<Integer> heap;
// 存储 k 的值
int _k;
public KthLargest(int k, int[] nums) {
// 干两件事，一是初始化 k，二是把 nums 中的元素放入堆中，最后用堆存储筛前 k 大的元素
_k = k;
heap = new PriorityQueue<>();
for(int x : nums){
heap.offer(x);
if(heap.size() > _k) heap.poll();
}
}
public int add(int val) {
heap.offer(val);
if(heap.size() > _k) heap.poll();
return heap.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
3.3 前 K 个高频单词
题目链接：前 K 个高频单词
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// 先用一个哈希表统计一下 words 中字符串以及对应字符串出现的频率
Map<String, Integer> hash = new HashMap<>();
for(String s : words) hash.put(s, hash.getOrDefault(s, 0) + 1);
// 接着创建一个堆，并初始化一个比较器，
// 堆的排序规则：
// - 频率低的单词排在前面（优先移除）。
// - 如果频率相同，按字典序降序排列（为了保持正确的优先顺序）。
PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>(
(a, b) -> {
if(a.getValue().equals(b.getValue())) return b.getKey().compareTo(a.getKey()); // 如果出现次数相同就按照字符序降序比较
else return a.getValue() - b.getValue(); // 按照频率顺序比较
}
);
// 接下来开始循环，把 words 中的元素都丢入堆中，同时保持堆的大小为 k
for (Map.Entry<String, Integer> e : hash.entrySet()) {
heap.offer(new Pair<>(e.getKey(), e.getValue()));
if(heap.size() > k) heap.poll();
}
// 4. 提取结果
List<String> ret = new ArrayList<>();
while(!heap.isEmpty())
ret.add(heap.poll().getKey());
// 因为堆的顺序是从低频到高频，结果需要逆序
Collections.reverse(ret);
// 返回结果
return ret;
}
}
3.4 数据流中的中位数
题目链接：数据流中的中位数
class MedianFinder {
// 使用两个堆来管理数据流
PriorityQueue<Integer> left; // 大根堆，存储较小的一半元素
PriorityQueue<Integer> right; // 小根堆，存储较大的一半元素
// 初始化两个堆
public MedianFinder() {
left = new PriorityQueue<>((a, b) -> b - a); // 大堆，从大到小排序
right = new PriorityQueue<>((a, b) -> a - b); // 小堆，从小到大排序
}
// 添加数字
public void addNum(int num) {
// 分情况讨论，首先看看两个堆的关系，是 m == n 还是 m == n+1
if(left.size() == right.size()){ // m == n
if(left.isEmpty() || num <= left.peek()) left.offer(num);
else{right.offer(num); left.offer(right.poll());}
}else{ // m == n+1
if(num <= left.peek()){left.offer(num); right.offer(left.poll());}
else right.offer(num);
}
}
// 返回当前数据流的中位数
public double findMedian() {
if(left.size() == right.size()) return (left.peek() + right.peek()) / 2.0;
else return left.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
![[ 网络安全介绍 5 ] 为什么要学习网络安全？](https://i-blog.csdnimg.cn/direct/c7e6039198cd498eb9fc2e2bd5d4e45e.png)
