01.栈的定义
a.基本概念
栈是一种后进先出LIFO的线性数据结构，只能在栈顶进行插入和删除操作。
b.核心操作
a.push入栈
在栈顶添加元素，时间复杂度O(1)。
b.pop出栈
删除并返回栈顶元素，时间复杂度O(1)。
c.peek查看栈顶
返回栈顶元素但不删除，时间复杂度O(1)。
d.isEmpty判空
判断栈是否为空。
c.栈的特点
后进先出、只能访问栈顶元素、操作受限的线性表。
02.数组实现栈
a.Java实现
---
public class ArrayStack {
private int[] data;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
data = new int[capacity];
top = -1;
}
public void push(int val) {
if (top == capacity - 1) {
throw new RuntimeException("栈已满");
}
data[++top] = val;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return data[top--];
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return data[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
}
---
b.Go实现
---
type ArrayStack struct {
data []int
top int
}
func NewArrayStack(capacity int) *ArrayStack {
return &ArrayStack{
data: make([]int, capacity),
top: -1,
}
}
func (s *ArrayStack) Push(val int) {
if s.top == len(s.data)-1 {
panic("栈已满")
}
s.top++
s.data[s.top] = val
}
func (s *ArrayStack) Pop() int {
if s.IsEmpty() {
panic("栈为空")
}
val := s.data[s.top]
s.top--
return val
}
func (s *ArrayStack) Peek() int {
if s.IsEmpty() {
panic("栈为空")
}
return s.data[s.top]
}
func (s *ArrayStack) IsEmpty() bool {
return s.top == -1
}
---
03.链表实现栈
a.Java实现
---
public class LinkedStack {
private ListNode top;
private int size;
public void push(int val) {
ListNode node = new ListNode(val);
node.next = top;
top = node;
size++;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
int val = top.val;
top = top.next;
size--;
return val;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return top.val;
}
public boolean isEmpty() {
return top == null;
}
}
---
04.Java Stack类
a.使用示例
---
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
int top = stack.peek(); // 20
int val = stack.pop(); // 20
boolean empty = stack.isEmpty();
---
b.注意事项
Stack继承自Vector，是线程安全的但性能较差，推荐使用Deque接口的实现类。
3.2 栈的应用场景
01.表达式求值
a.中缀表达式转后缀
使用栈将中缀表达式（如3+4*5）转换为后缀表达式（如345*+）。
b.后缀表达式求值
a.算法步骤
遇到数字入栈，遇到运算符弹出两个数字计算后入栈。
b.Java实现
---
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/")) {
int b = stack.pop();
int a = stack.pop();
int result = 0;
switch (token) {
case "+": result = a + b; break;
case "-": result = a - b; break;
case "*": result = a * b; break;
case "/": result = a / b; break;
}
stack.push(result);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
---
02.括号匹配
a.问题描述
判断字符串中的括号是否匹配，如"({[]})"是匹配的，"({[})"不匹配。
b.解决方案
a.算法思路
遇到左括号入栈，遇到右括号弹出栈顶检查是否匹配。
b.Java实现
---
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return stack.isEmpty();
}
---
c.Go实现
---
func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
for _, c := range s {
if c == '(' || c == '[' || c == '{' {
stack = append(stack, c)
} else {
if len(stack) == 0 {
return false
}
if stack[len(stack)-1] != pairs[c] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
---
03.函数调用栈
a.调用栈原理
每次函数调用时，将返回地址和局部变量压入栈，函数返回时弹出。
b.递归实现
递归函数利用系统调用栈保存中间状态。
c.栈溢出
递归层数过深会导致栈溢出StackOverflowError。
04.浏览器前进后退
a.实现原理
使用两个栈，一个存储历史记录，一个存储前进记录。
b.代码示例
---
public class BrowserHistory {
private Stack<String> backStack;
private Stack<String> forwardStack;
private String current;
public BrowserHistory(String homepage) {
backStack = new Stack<>();
forwardStack = new Stack<>();
current = homepage;
}
public void visit(String url) {
backStack.push(current);
current = url;
forwardStack.clear();
}
public String back(int steps) {
while (steps > 0 && !backStack.isEmpty()) {
forwardStack.push(current);
current = backStack.pop();
steps--;
}
return current;
}
public String forward(int steps) {
while (steps > 0 && !forwardStack.isEmpty()) {
backStack.push(current);
current = forwardStack.pop();
steps--;
}
return current;
}
}
---
3.3 队列的概念与实现
01.队列的定义
a.基本概念
队列是一种先进先出FIFO的线性数据结构，在队尾插入元素，在队头删除元素。
b.核心操作
a.enqueue入队
在队尾添加元素，时间复杂度O(1)。
b.dequeue出队
删除并返回队头元素，时间复杂度O(1)。
c.peek查看队头
返回队头元素但不删除。
d.isEmpty判空
判断队列是否为空。
c.队列特点
先进先出、只能访问队头和队尾、操作受限的线性表。
02.数组实现队列
a.简单实现
a.问题
出队后队头位置浪费，需要移动元素或使用循环队列。
b.Java实现
---
public class ArrayQueue {
private int[] data;
private int front;
private int rear;
private int size;
public ArrayQueue(int capacity) {
data = new int[capacity];
front = 0;
rear = 0;
size = 0;
}
public void enqueue(int val) {
if (size == data.length) {
throw new RuntimeException("队列已满");
}
data[rear] = val;
rear = (rear + 1) % data.length;
size++;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
int val = data[front];
front = (front + 1) % data.length;
size--;
return val;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return data[front];
}
public boolean isEmpty() {
return size == 0;
}
}
---
03.链表实现队列
a.Java实现
---
public class LinkedQueue {
private ListNode front;
private ListNode rear;
private int size;
public void enqueue(int val) {
ListNode node = new ListNode(val);
if (rear == null) {
front = rear = node;
} else {
rear.next = node;
rear = node;
}
size++;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
int val = front.val;
front = front.next;
if (front == null) {
rear = null;
}
size--;
return val;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return front.val;
}
public boolean isEmpty() {
return front == null;
}
}
---
b.Go实现
---
type LinkedQueue struct {
front *ListNode
rear *ListNode
size int
}
func (q *LinkedQueue) Enqueue(val int) {
node := &ListNode{Val: val}
if q.rear == nil {
q.front = node
q.rear = node
} else {
q.rear.Next = node
q.rear = node
}
q.size++
}
func (q *LinkedQueue) Dequeue() int {
if q.IsEmpty() {
panic("队列为空")
}
val := q.front.Val
q.front = q.front.Next
if q.front == nil {
q.rear = nil
}
q.size--
return val
}
---
04.Java Queue接口
a.常用实现类
a.LinkedList
基于链表实现，支持队列和双端队列操作。
b.ArrayDeque
基于循环数组实现，性能优于LinkedList。
c.PriorityQueue
基于堆实现的优先队列。
b.使用示例
---
import java.util.Queue;
import java.util.LinkedList;
Queue<Integer> queue = new LinkedList<>();
queue.offer(10); // 入队
queue.offer(20);
int head = queue.peek(); // 查看队头
int val = queue.poll(); // 出队
boolean empty = queue.isEmpty();
---
3.4 循环队列
01.循环队列概述
a.定义
使用固定大小的数组实现队列，通过取模运算实现循环使用数组空间。
b.优点
避免了普通数组队列的空间浪费问题，充分利用数组空间。
c.关键问题
如何区分队列为空和队列已满的情况。
02.循环队列实现
a.方案一：牺牲一个空间
a.判断条件
队空：front == rear，队满：(rear + 1) % capacity == front。
b.Java实现
---
public class CircularQueue {
private int[] data;
private int front;
private int rear;
private int capacity;
public CircularQueue(int k) {
capacity = k + 1; // 多分配一个空间
data = new int[capacity];
front = 0;
rear = 0;
}
public boolean enQueue(int value) {
if (isFull()) return false;
data[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
return true;
}
public int Front() {
if (isEmpty()) return -1;
return data[front];
}
public int Rear() {
if (isEmpty()) return -1;
return data[(rear - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
}
---
b.方案二：使用size变量
a.判断条件
队空：size == 0，队满：size == capacity。
b.Go实现
---
type CircularQueue struct {
data []int
front int
rear int
size int
capacity int
}
func NewCircularQueue(k int) *CircularQueue {
return &CircularQueue{
data: make([]int, k),
capacity: k,
}
}
func (q *CircularQueue) EnQueue(value int) bool {
if q.IsFull() {
return false
}
q.data[q.rear] = value
q.rear = (q.rear + 1) % q.capacity
q.size++
return true
}
func (q *CircularQueue) DeQueue() bool {
if q.IsEmpty() {
return false
}
q.front = (q.front + 1) % q.capacity
q.size--
return true
}
func (q *CircularQueue) IsEmpty() bool {
return q.size == 0
}
func (q *CircularQueue) IsFull() bool {
return q.size == q.capacity
}
---
03.LeetCode题目
a.设计循环队列
LeetCode 622 - 实现循环队列的基本操作。
b.设计循环双端队列
LeetCode 641 - 支持在队头和队尾进行插入删除操作。
3.5 双端队列
01.双端队列概述
a.定义
双端队列Deque是一种可以在两端进行插入和删除操作的线性数据结构。
b.核心操作
addFirst、addLast、removeFirst、removeLast、peekFirst、peekLast。
c.应用场景
可以同时作为栈和队列使用，是更通用的数据结构。
02.Java Deque接口
a.常用实现类
a.ArrayDeque
基于循环数组实现，性能优秀，推荐使用。
b.LinkedList
基于双向链表实现，也实现了Deque接口。
b.使用示例
---
import java.util.Deque;
import java.util.ArrayDeque;
Deque<Integer> deque = new ArrayDeque<>();
// 作为栈使用
deque.push(10); // 入栈
deque.push(20);
int top = deque.pop(); // 出栈
// 作为队列使用
deque.offer(30); // 入队
deque.offer(40);
int head = deque.poll(); // 出队
// 双端操作
deque.addFirst(5); // 队头插入
deque.addLast(50); // 队尾插入
deque.removeFirst(); // 队头删除
deque.removeLast(); // 队尾删除
---
03.ArrayDeque实现原理
a.底层结构
使用循环数组实现，维护head和tail两个指针。
b.扩容机制
当容量不足时，扩容为原来的2倍。
c.性能特点
所有操作时间复杂度O(1)，比LinkedList性能更好。
04.Go实现双端队列
a.代码示例
---
type Deque struct {
data []int
}
func NewDeque() *Deque {
return &Deque{data: []int{}}
}
func (d *Deque) AddFirst(val int) {
d.data = append([]int{val}, d.data...)
}
func (d *Deque) AddLast(val int) {
d.data = append(d.data, val)
}
func (d *Deque) RemoveFirst() int {
if len(d.data) == 0 {
panic("deque is empty")
}
val := d.data[0]
d.data = d.data[1:]
return val
}
func (d *Deque) RemoveLast() int {
if len(d.data) == 0 {
panic("deque is empty")
}
val := d.data[len(d.data)-1]
d.data = d.data[:len(d.data)-1]
return val
}
---
01.堆的定义
a.基本概念
堆是一种完全二叉树，分为最大堆和最小堆。
b.最大堆
每个节点的值大于等于其子节点的值，根节点是最大值。
c.最小堆
每个节点的值小于等于其子节点的值，根节点是最小值。
02.堆的数组表示
a.索引关系
a.父节点
索引为i的节点，其父节点索引为(i-1)/2。
b.左子节点
索引为i的节点，其左子节点索引为2*i+1。
c.右子节点
索引为i的节点，其右子节点索引为2*i+2。
03.堆的基本操作
a.插入元素
---
public void insert(int val) {
heap.add(val);
siftUp(heap.size() - 1);
}
private void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap.get(i) >= heap.get(parent)) break;
swap(i, parent);
i = parent;
}
}
---
b.删除最小值
---
public int removeMin() {
if (heap.isEmpty()) {
throw new RuntimeException("堆为空");
}
int min = heap.get(0);
int last = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, last);
siftDown(0);
}
return min;
}
private void siftDown(int i) {
int n = heap.size();
while (2 * i + 1 < n) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int minChild = left;
if (right < n && heap.get(right) < heap.get(left)) {
minChild = right;
}
if (heap.get(i) <= heap.get(minChild)) break;
swap(i, minChild);
i = minChild;
}
}
---
04.堆排序
a.算法步骤
建堆O(n)，然后依次取出最大值O(n log n)。
b.Java实现
---
public void heapSort(int[] arr) {
int n = arr.length;
// 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 排序
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
---
4.6 树的遍历
01.前序遍历
a.递归实现
---
public void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
---
b.迭代实现
---
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return result;
}
---
02.中序遍历
a.递归实现
---
public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
---
b.迭代实现
---
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
result.add(curr.val);
curr = curr.right;
}
return result;
}
---
03.后序遍历
a.递归实现
---
public void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.val + " ");
}
---
04.层序遍历
a.BFS实现
---
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
---
b.Go实现
---
func levelOrder(root *TreeNode) [][]int {
result := [][]int{}
if root == nil {
return result
}
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
level := []int{}
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
---
01.Go Map基础
a.声明和初始化
---
// 声明
var m1 map[string]int
// 使用make初始化
m2 := make(map[string]int)
m3 := make(map[string]int, 10) // 指定初始容量
// 字面量初始化
m4 := map[string]int{
"apple": 1,
"banana": 2,
"orange": 3,
}
---
b.基本操作
---
m := make(map[string]int)
// 添加元素
m["apple"] = 1
m["banana"] = 2
// 获取元素
value := m["apple"] // 1
// 检查键是否存在
value, ok := m["grape"]
if ok {
fmt.Println("存在:", value)
} else {
fmt.Println("不存在")
}
// 删除元素
delete(m, "banana")
// 遍历
for key, value := range m {
fmt.Printf("%s: %d\n", key, value)
}
// 获取长度
length := len(m)
---
02.Go Map底层实现
a.数据结构
使用哈希表实现，包含桶数组和溢出桶。
b.扩容机制
负载因子超过6.5时进行扩容，采用渐进式扩容。
c.并发安全
Go的map不是并发安全的，需要使用sync.Map或加锁。
03.sync.Map
a.使用场景
适用于读多写少的场景。
b.使用示例
---
import "sync"
var m sync.Map
// 存储
m.Store("key1", "value1")
// 读取
value, ok := m.Load("key1")
if ok {
fmt.Println(value)
}
// 删除
m.Delete("key1")
// 遍历
m.Range(func(key, value interface{}) bool {
fmt.Printf("%v: %v\n", key, value)
return true // 返回false停止遍历
})
---
5.6 应用场景
01.计数统计
a.字符频率统计
---
public Map<Character, Integer> countChars(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
return map;
}
---
b.单词频率统计
---
public Map<String, Integer> countWords(String[] words) {
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
return map;
}
---
02.去重
a.数组去重
---
public int[] removeDuplicates(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
return set.stream().mapToInt(Integer::intValue).toArray();
}
---
03.快速查找
a.两数之和
---
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
---
04.缓存实现
a.LRU缓存
使用HashMap加双向链表实现O(1)时间复杂度的LRU缓存。
b.简单缓存
---
class Cache {
private Map<String, Object> cache = new HashMap<>();
public Object get(String key) {
return cache.get(key);
}
public void put(String key, Object value) {
cache.put(key, value);
}
}
---
5.7 经典题目
01.两数之和
a.题目
LeetCode 1 - 给定数组和目标值，找出数组中和为目标值的两个数的索引。
b.哈希表解法
---
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
---
02.字母异位词分组
a.题目
LeetCode 49 - 将字母异位词分组。
b.哈希表解法
---
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
---
03.最长连续序列
a.题目
LeetCode 128 - 找出数组中最长连续序列的长度。
b.哈希表解法
---
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (int num : set) {
if (!set.contains(num - 1)) {
int currentNum = num;
int currentLen = 1;
while (set.contains(currentNum + 1)) {
currentNum++;
currentLen++;
}
maxLen = Math.max(maxLen, currentLen);
}
}
return maxLen;
}
---
04.有效的字母异位词
a.题目
LeetCode 242 - 判断两个字符串是否为字母异位词。
b.哈希表解法
---
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (char c : t.toCharArray()) {
int count = map.getOrDefault(c, 0);
if (count == 0) return false;
map.put(c, count - 1);
}
return true;
}
---
6 字符串
6.1 字符串基础
01.字符串定义
a.Java String
String是不可变的字符序列，底层使用char数组或byte数组存储。
b.Go string
string是不可变的字节序列，底层是byte数组。
02.字符串基本操作
a.Java实现
---
String s = "hello";
// 长度
int len = s.length();
// 字符访问
char c = s.charAt(0);
// 子串
String sub = s.substring(1, 4); // "ell"
// 拼接
String s2 = s + " world";
String s3 = s.concat(" world");
// 比较
boolean eq = s.equals("hello");
int cmp = s.compareTo("world");
// 查找
int index = s.indexOf('l'); // 2
int lastIndex = s.lastIndexOf('l'); // 3
// 替换
String replaced = s.replace('l', 'L');
// 分割
String[] parts = "a,b,c".split(",");
---
b.Go实现
---
s := "hello"
// 长度
length := len(s)
// 字符访问
b := s[0] // byte
// 子串
sub := s[1:4] // "ell"
// 拼接
s2 := s + " world"
// 比较
eq := s == "hello"
// 查找
import "strings"
index := strings.Index(s, "l")
// 替换
replaced := strings.Replace(s, "l", "L", -1)
// 分割
parts := strings.Split("a,b,c", ",")
---
03.StringBuilder和StringBuffer
a.StringBuilder
可变字符序列，线程不安全，性能高。
b.StringBuffer
可变字符序列，线程安全，性能较低。
c.使用示例
---
StringBuilder sb = new StringBuilder();
sb.append("hello");
sb.append(" ");
sb.append("world");
String result = sb.toString();
// 插入
sb.insert(5, ",");
// 删除
sb.delete(5, 6);
// 反转
sb.reverse();
---
6.2 字符串匹配
01.暴力匹配
a.算法思想
逐个比较文本串和模式串的字符，不匹配时回退。
b.Java实现
---
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int n = haystack.length();
int m = needle.length();
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
j++;
}
if (j == m) return i;
}
return -1;
}
---
c.时间复杂度
O(n*m)，其中n是文本串长度，m是模式串长度。
02.Rabin-Karp算法
a.算法思想
使用哈希函数快速比较子串，只有哈希值相同时才逐字符比较。
b.滚动哈希
---
public int rabinKarp(String text, String pattern) {
int n = text.length();
int m = pattern.length();
if (m > n) return -1;
int base = 256;
int mod = 101;
int patternHash = 0;
int textHash = 0;
int h = 1;
// 计算h = base^(m-1) % mod
for (int i = 0; i < m - 1; i++) {
h = (h * base) % mod;
}
// 计算模式串和文本串第一个窗口的哈希值
for (int i = 0; i < m; i++) {
patternHash = (base * patternHash + pattern.charAt(i)) % mod;
textHash = (base * textHash + text.charAt(i)) % mod;
}
// 滑动窗口
for (int i = 0; i <= n - m; i++) {
if (patternHash == textHash) {
if (text.substring(i, i + m).equals(pattern)) {
return i;
}
}
if (i < n - m) {
textHash = (base * (textHash - text.charAt(i) * h) +
text.charAt(i + m)) % mod;
if (textHash < 0) {
textHash += mod;
}
}
}
return -1;
}
---
6.3 KMP算法
01.KMP算法原理
a.核心思想
利用已匹配的信息，避免不必要的回退，通过next数组记录模式串的前缀信息。
b.时间复杂度
O(n+m)，其中n是文本串长度，m是模式串长度。
02.next数组计算
a.定义
next[i]表示模式串前i个字符的最长相等前后缀长度。
b.Java实现
---
private int[] getNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
---
03.KMP匹配
a.Java实现
---
public int kmp(String text, String pattern) {
int n = text.length();
int m = pattern.length();
if (m == 0) return 0;
int[] next = getNext(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
---
b.Go实现
---
func kmp(text, pattern string) int {
n, m := len(text), len(pattern)
if m == 0 {
return 0
}
next := getNext(pattern)
j := 0
for i := 0; i < n; i++ {
for j > 0 && text[i] != pattern[j] {
j = next[j-1]
}
if text[i] == pattern[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}
func getNext(pattern string) []int {
m := len(pattern)
next := make([]int, m)
j := 0
for i := 1; i < m; i++ {
for j > 0 && pattern[i] != pattern[j] {
j = next[j-1]
}
if pattern[i] == pattern[j] {
j++
}
next[i] = j
}
return next
}
---
6.4 Trie树
01.Trie树定义
a.基本概念
Trie树又称字典树或前缀树，用于高效存储和检索字符串集合。
b.特点
根节点不包含字符，每条边代表一个字符，从根到某节点的路径代表一个字符串。
c.时间复杂度
插入和查找的时间复杂度为O(m)，其中m是字符串长度。
02.Trie树实现
a.节点定义
---
class TrieNode {
TrieNode[] children;
boolean isEnd;
TrieNode() {
children = new TrieNode[26]; // 假设只有小写字母
isEnd = false;
}
}
---
b.Trie树类
---
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 插入单词
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true;
}
// 查找单词
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd;
}
// 查找前缀
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
---
03.Trie树应用
a.自动补全
根据输入前缀，返回所有可能的单词。
b.拼写检查
检查单词是否在字典中。
c.IP路由
最长前缀匹配。
6.5 字符串处理技巧
01.双指针技巧
a.反转字符串
---
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
---
b.回文判断
---
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
---
02.滑动窗口
a.最长无重复子串
---
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
---
03.字符统计
a.字符数组统计
---
public boolean canConstruct(String ransomNote, String magazine) {
int[] count = new int[26];
for (char c : magazine.toCharArray()) {
count[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
if (--count[c - 'a'] < 0) {
return false;
}
}
return true;
}
---
6.6 经典题目
01.反转字符串中的单词
a.题目
LeetCode 151 - 反转字符串中的单词顺序。
b.Java解法
---
public String reverseWords(String s) {
String[] words = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i]);
if (i > 0) sb.append(" ");
}
return sb.toString();
}
---
02.最长回文子串
a.题目
LeetCode 5 - 找出字符串中最长的回文子串。
b.中心扩展法
---
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() &&
s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
---
03.字符串相加
a.题目
LeetCode 415 - 实现大数相加。
b.Java解法
---
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = n1 + n2 + carry;
sb.append(sum % 10);
carry = sum / 10;
i--;
j--;
}
return sb.reverse().toString();
}
---
04.实现strStr
a.题目
LeetCode 28 - 实现字符串匹配函数。
b.KMP解法
使用KMP算法实现高效的字符串匹配。