// 数组基础操作示例
public class ArrayOperations {
    private int[] arr;
    private int size;
    private int capacity;
    
    // 动态扩容
    private void resize() {
        capacity *= 2;
        int[] newArr = new int[capacity];
        System.arraycopy(arr, 0, newArr, 0, size);
        arr = newArr;
    }
    
    // 插入元素 - O(n)
    public void insert(int index, int value) {
        if (size >= capacity) resize();
        for (int i = size; i > index; i--) {
            arr[i] = arr[i-1];
        }
        arr[index] = value;
        size++;
    }
}

// 双向链表节点定义
class ListNode {
    int val;
    ListNode prev, next;
    
    ListNode(int val) { this.val = val; }
}

// 双向链表核心操作
public class DoublyLinkedList {
    private ListNode head, tail;
    
    // 在指定节点后插入 - O(1)
    public void insertAfter(ListNode node, int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = node.next;
        newNode.prev = node;
        if (node.next != null) {
            node.next.prev = newNode;
        }
        node.next = newNode;
    }
}

// 基于数组的栈实现
public class ArrayStack<T> {
    private T[] stack;
    private int top = -1;
    
    public void push(T item) {
        stack[++top] = item;
    }
    
    public T pop() {
        return stack[top--];
    }
    
    // 括号匹配应用示例
    public boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (!stack.isEmpty() && matches(stack.peek(), c)) {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

// 循环队列实现
public class CircularQueue {
    private int[] queue;
    private int front, rear, size, capacity;
    
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
    }
    
    public boolean enqueue(int value) {
        if (isFull()) return false;
        queue[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }
    
    public boolean dequeue() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
}

// 链地址法哈希表实现
public class HashTable<K, V> {
    private class Entry {
        K key; V value; Entry next;
        Entry(K key, V value) { this.key = key; this.value = value; }
    }
    
    private Entry[] table;
    private int size, capacity;
    private static final double LOAD_FACTOR = 0.75;
    
    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }
    
    public V put(K key, V value) {
        if (size >= capacity * LOAD_FACTOR) {
            resize();
        }
        
        int index = hash(key);
        Entry entry = table[index];
        
        // 查找是否已存在
        while (entry != null) {
            if (entry.key.equals(key)) {
                V oldValue = entry.value;
                entry.value = value;
                return oldValue;
            }
            entry = entry.next;
        }
        
        // 插入新节点
        Entry newEntry = new Entry(key, value);
        newEntry.next = table[index];
        table[index] = newEntry;
        size++;
        return null;
    }
}

// 最小堆实现
public class MinHeap {
    private int[] heap;
    private int size;
    
    // 上浮操作
    private void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        if (parent >= 0 && heap[parent] > heap[index]) {
            swap(parent, index);
            heapifyUp(parent);
        }
    }
    
    // 下沉操作
    private void heapifyDown(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        
        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }
        
        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }
    
    public void insert(int value) {
        heap[size] = value;
        heapifyUp(size);
        size++;
    }
    
    public int extractMin() {
        int min = heap[0];
        heap[0] = heap[--size];
        heapifyDown(0);
        return min;
    }
}

// 二叉树节点定义
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// 二叉搜索树基本操作
public class BinarySearchTree {
    private TreeNode root;
    
    // 查找 - O(log n) 平均，O(n) 最坏
    public boolean search(int val) {
        return searchHelper(root, val);
    }
    
    private boolean searchHelper(TreeNode node, int val) {
        if (node == null) return false;
        if (node.val == val) return true;
        return val < node.val ? 
            searchHelper(node.left, val) : searchHelper(node.right, val);
    }
    
    // 插入 - O(log n) 平均
    public void insert(int val) {
        root = insertHelper(root, val);
    }
    
    private TreeNode insertHelper(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val) {
            node.left = insertHelper(node.left, val);
        } else if (val > node.val) {
            node.right = insertHelper(node.right, val);
        }
        return node;
    }
}

// AVL树旋转操作核心
class AVLTree {
    class Node {
        int val, height;
        Node left, right;
    }
    
    // 右旋转
    private Node rotateRight(Node y) {
        Node x = y.left;
        y.left = x.right;
        x.right = y;
        updateHeight(y);
        updateHeight(x);
        return x;
    }
    
    // 获取平衡因子
    private int getBalance(Node node) {
        return height(node.left) - height(node.right);
    }
}

// 红黑树插入后调整
class RedBlackTree {
    enum Color { RED, BLACK }
    
    class Node {
        int val;
        Color color;
        Node left, right, parent;
    }
    
    // 插入后修复红黑树性质
    private void fixInsert(Node node) {
        while (node.parent != null && node.parent.color == Color.RED) {
            // 根据父节点是祖父的左子还是右子进行不同处理
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                if (uncle != null && uncle.color == Color.RED) {
                    // 情况1：叔叔节点是红色，重新着色
                    node.parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    node = node.parent.parent;
                } else {
                    // 情况2/3：叔叔节点是黑色，需要旋转
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    rotateRight(node.parent.parent);
                }
            }
            // 对称处理右侧情况...
        }
        root.color = Color.BLACK; // 根节点始终为黑色
    }
}

// B+树简化实现
class BPlusTree {
    private int order; // B+树的阶数
    
    abstract class Node {
        int[] keys;
        int keyCount;
        Node parent;
        boolean isLeaf;
    }
    
    class InternalNode extends Node {
        Node[] children;
        
        // 查找子节点
        Node findChild(int key) {
            int i = 0;
            while (i < keyCount && key >= keys[i]) i++;
            return children[i];
        }
    }
    
    class LeafNode extends Node {
        String[] values; // 实际数据
        LeafNode next;   // 链接到下一个叶子节点
        
        // 范围查询
        List<String> rangeQuery(int start, int end) {
            List<String> result = new ArrayList<>();
            LeafNode current = this;
            
            while (current != null) {
                for (int i = 0; i < current.keyCount; i++) {
                    if (current.keys[i] >= start && current.keys[i] <= end) {
                        result.add(current.values[i]);
                    }
                    if (current.keys[i] > end) return result;
                }
                current = current.next;
            }
            return result;
        }
    }
    
    // 搜索操作
    public String search(int key) {
        Node current = root;
        
        // 从根节点向下查找到叶子节点
        while (!current.isLeaf) {
            current = ((InternalNode) current).findChild(key);
        }
        
        // 在叶子节点中查找具体值
        LeafNode leaf = (LeafNode) current;
        for (int i = 0; i < leaf.keyCount; i++) {
            if (leaf.keys[i] == key) {
                return leaf.values[i];
            }
        }
        return null;
    }
}

// LSM-Tree核心操作实现
class LSMTree {
    private SkipListMap<String, String> memTable;
    private List<SSTable> sstables;
    private int memTableThreshold = 1000;
    
    // 写入操作 - O(log n)
    public void put(String key, String value) {
        memTable.put(key, value);
        
        // 检查是否需要刷写
        if (memTable.size() >= memTableThreshold) {
            flushMemTable();
        }
    }
    
    // 读取操作 - O(log n * 层数)
    public String get(String key) {
        // 1. 检查MemTable
        if (memTable.containsKey(key)) {
            return memTable.get(key);
        }
        
        // 2. 检查各层SSTable
        for (SSTable table : sstables) {
            if (table.mightContain(key)) { // Bloom Filter检查
                String value = table.get(key);
                if (value != null) return value;
            }
        }
        
        return null; // 未找到
    }
    
    // 刷写MemTable到磁盘
    private void flushMemTable() {
        SSTable newTable = new SSTable(memTable);
        sstables.add(newTable);
        memTable.clear();
        
        // 触发压缩检查
        checkCompaction();
    }
    
    // 压缩操作
    private void checkCompaction() {
        if (sstables.size() > 4) {
            // 选择需要压缩的SSTable
            List<SSTable> toCompact = selectTablesForCompaction();
            SSTable merged = mergeTables(toCompact);
            
            // 替换旧表
            sstables.removeAll(toCompact);
            sstables.add(merged);
        }
    }
}

// SSTable简化实现
class SSTable {
    private Map<String, String> data;
    private BloomFilter<String> bloomFilter;
    
    public SSTable(Map<String, String> memTable) {
        this.data = new TreeMap<>(memTable);
        this.bloomFilter = BloomFilter.create(
            Funnels.stringFunnel(Charset.defaultCharset()), 
            data.size()
        );
        
        // 构建Bloom Filter
        for (String key : data.keySet()) {
            bloomFilter.put(key);
        }
    }
    
    public boolean mightContain(String key) {
        return bloomFilter.mightContain(key);
    }
    
    public String get(String key) {
        return data.get(key);
    }
}

// 场景1：内存数据库 - 选择红黑树
class InMemoryDatabase {
    private TreeMap<String, Object> index = new TreeMap<>(); // 基于红黑树
    
    public void insert(String key, Object value) {
        index.put(key, value); // O(log n)，插入删除平衡
    }
    
    public List<Object> rangeQuery(String start, String end) {
        return index.subMap(start, true, end, true)
                   .values().stream().collect(Collectors.toList());
    }
}

// 场景2：数据库索引 - 选择B+树
class DatabaseIndex {
    private BPlusTree index = new BPlusTree(100); // 高扇出比
    
    // 范围查询高效，磁盘I/O少
    public List<Record> rangeQuery(int start, int end) {
        return index.rangeQuery(start, end); // 叶子节点链表扫描
    }
}

// 场景3：高吞吐写入系统 - 选择LSM-Tree
class HighThroughputWriteSystem {
    private LSMTree storage = new LSMTree();
    
    public void batchWrite(List<KeyValue> data) {
        for (KeyValue kv : data) {
            storage.put(kv.key, kv.value); // 写入MemTable，批量刷写
        }
    }
}

// 邻接矩阵实现
class GraphMatrix {
    private int[][] matrix;
    private int vertices;
    
    public GraphMatrix(int vertices) {
        this.vertices = vertices;
        this.matrix = new int[vertices][vertices];
    }
    
    // 添加边 - O(1)
    public void addEdge(int from, int to, int weight) {
        matrix[from][to] = weight;
        // 无向图需要双向添加
        // matrix[to][from] = weight;
    }
    
    // 检查是否有边 - O(1)
    public boolean hasEdge(int from, int to) {
        return matrix[from][to] != 0;
    }
    
    // 获取所有邻居 - O(V)
    public List<Integer> getNeighbors(int vertex) {
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            if (matrix[vertex][i] != 0) {
                neighbors.add(i);
            }
        }
        return neighbors;
    }
}

// 邻接表实现
class GraphList {
    private List<List<Edge>> adjacencyList;
    private int vertices;
    
    class Edge {
        int to, weight;
        Edge(int to, int weight) { this.to = to; this.weight = weight; }
    }
    
    public GraphList(int vertices) {
        this.vertices = vertices;
        this.adjacencyList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }
    
    // 添加边 - O(1)
    public void addEdge(int from, int to, int weight) {
        adjacencyList.get(from).add(new Edge(to, weight));
        // 无向图需要双向添加
        // adjacencyList.get(to).add(new Edge(from, weight));
    }
    
    // 检查是否有边 - O(degree)
    public boolean hasEdge(int from, int to) {
        return adjacencyList.get(from).stream()
                .anyMatch(edge -> edge.to == to);
    }
    
    // 获取所有邻居 - O(degree)
    public List<Edge> getNeighbors(int vertex) {
        return adjacencyList.get(vertex);
    }
}

// 图遍历算法实现
class GraphTraversal {
    private GraphList graph;
    
    // 深度优先搜索 - 递归实现
    public void dfsRecursive(int start, boolean[] visited) {
        visited[start] = true;
        System.out.print(start + " ");
        
        for (GraphList.Edge edge : graph.getNeighbors(start)) {
            if (!visited[edge.to]) {
                dfsRecursive(edge.to, visited);
            }
        }
    }
    
    // 深度优先搜索 - 栈实现
    public void dfsIterative(int start) {
        boolean[] visited = new boolean[graph.vertices];
        Stack<Integer> stack = new Stack<>();
        
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int current = stack.pop();
            
            if (!visited[current]) {
                visited[current] = true;
                System.out.print(current + " ");
                
                // 将邻居加入栈（逆序以保持顺序）
                List<GraphList.Edge> neighbors = graph.getNeighbors(current);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    if (!visited[neighbors.get(i).to]) {
                        stack.push(neighbors.get(i).to);
                    }
                }
            }
        }
    }
    
    // 广度优先搜索
    public void bfs(int start) {
        boolean[] visited = new boolean[graph.vertices];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");
            
            for (GraphList.Edge edge : graph.getNeighbors(current)) {
                if (!visited[edge.to]) {
                    visited[edge.to] = true;
                    queue.offer(edge.to);
                }
            }
        }
    }
    
    // BFS最短路径
    public List<Integer> shortestPath(int start, int end) {
        boolean[] visited = new boolean[graph.vertices];
        int[] parent = new int[graph.vertices];
        Queue<Integer> queue = new LinkedList<>();
        
        Arrays.fill(parent, -1);
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            if (current == end) {
                // 重构路径
                List<Integer> path = new ArrayList<>();
                int node = end;
                while (node != -1) {
                    path.add(0, node);
                    node = parent[node];
                }
                return path;
            }
            
            for (GraphList.Edge edge : graph.getNeighbors(current)) {
                if (!visited[edge.to]) {
                    visited[edge.to] = true;
                    parent[edge.to] = current;
                    queue.offer(edge.to);
                }
            }
        }
        
        return new ArrayList<>(); // 无路径
    }
}

// 基础排序算法实现
public class BasicSorting {
    
    // 冒泡排序
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }
            // 优化：如果没有交换，说明已排序
            if (!swapped) break;
        }
    }
    
    // 选择排序
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            // 找到最小元素的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            swap(arr, i, minIdx);
        }
    }
    
    // 插入排序
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // 将大于key的元素向右移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// 斐波那契数列 - 自底向上
public int fibonacci(int n) {
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 空间优化版本
public int fibonacciOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

// 最长递增子序列
public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int maxLength = 1;
    
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    return maxLength;
}

// 0-1背包问题
public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i-1] <= w) {
                // 可以选择第i个物品
                dp[i][w] = Math.max(
                    dp[i-1][w],  // 不选
                    dp[i-1][w-weights[i-1]] + values[i-1]  // 选择
                );
            } else {
                // 不能选择第i个物品
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][capacity];
}

// 空间优化版本
public int knapsackOptimized(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < weights.length; i++) {
        // 从右到左更新，避免重复使用
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

// 最长公共子序列
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

// 活动选择问题
public int activitySelection(int[] start, int[] end) {
    int n = start.length;
    // 按结束时间排序
    Integer[] indices = new Integer[n];
    for (int i = 0; i < n; i++) indices[i] = i;
    Arrays.sort(indices, (a, b) -> end[a] - end[b]);
    
    int count = 1;
    int lastEnd = end[indices[0]];
    
    for (int i = 1; i < n; i++) {
        if (start[indices[i]] >= lastEnd) {
            count++;
            lastEnd = end[indices[i]];
        }
    }
    return count;
}

// 分糖果问题
public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);
    
    // 从左到右，保证右边比左边高分的孩子糖果更多
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    
    // 从右到左，保证左边比右边高分的孩子糖果更多
    for (int i = n-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            candies[i] = Math.max(candies[i], candies[i+1] + 1);
        }
    }
    
    return Arrays.stream(candies).sum();
}

// 归并排序（分治经典例子）
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // 分解
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // 合并
        merge(arr, left, mid, right);
    }
}

// 最大子数组问题（分治解法）
public int maxSubArrayDivide(int[] nums, int left, int right) {
    if (left == right) return nums[left];
    
    int mid = left + (right - left) / 2;
    
    // 分别计算左半部分和右半部分的最大子数组
    int leftMax = maxSubArrayDivide(nums, left, mid);
    int rightMax = maxSubArrayDivide(nums, mid + 1, right);
    
    // 计算跨越中点的最大子数组
    int leftSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }
    
    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }
    
    int crossMax = leftSum + rightSum;
    
    // 返回三者中的最大值
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

// 线性查找实现
public class LinearSearch {
    
    // 基本线性查找
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // 未找到
    }
    
    // 改进的线性查找 - 哨兵技术
    public static int sentinelLinearSearch(int[] arr, int target) {
        int n = arr.length;
        int last = arr[n - 1];
        arr[n - 1] = target; // 设置哨兵
        
        int i = 0;
        while (arr[i] != target) {
            i++;
        }
        
        arr[n - 1] = last; // 恢复原值
        
        if (i < n - 1 || arr[n - 1] == target) {
            return i;
        }
        return -1;
    }
    
    // 查找所有匹配元素
    public static List<Integer> findAll(int[] arr, int target) {
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                indices.add(i);
            }
        }
        return indices;
    }
}

// 二分查找及其变种
public class BinarySearch {
    
    // 标准二分查找
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    // 递归版本二分查找
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) return -1;
        
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right);
        } else {
            return binarySearchRecursive(arr, target, left, mid - 1);
        }
    }
    
    // 查找第一个等于target的位置
    public static int findFirst(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1; // 继续向左查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    
    // 查找最后一个等于target的位置
    public static int findLast(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1; // 继续向右查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    
    // 在旋转排序数组中查找
    public static int searchInRotatedArray(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断哪一半是有序的
            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

// 哈希查找实现
public class HashSearch {
    
    // 简单哈希表实现
    static class SimpleHashTable {
        private static class Entry {
            String key;
            Integer value;
            Entry next;
            
            Entry(String key, Integer value) {
                this.key = key;
                this.value = value;
            }
        }
        
        private Entry[] table;
        private int size;
        private int capacity;
        private static final double LOAD_FACTOR = 0.75;
        
        public SimpleHashTable(int initialCapacity) {
            this.capacity = initialCapacity;
            this.table = new Entry[capacity];
            this.size = 0;
        }
        
        private int hash(String key) {
            return Math.abs(key.hashCode()) % capacity;
        }
        
        // 查找操作 - O(1) 平均时间复杂度
        public Integer search(String key) {
            int index = hash(key);
            Entry current = table[index];
            
            while (current != null) {
                if (current.key.equals(key)) {
                    return current.value;
                }
                current = current.next;
            }
            return null;
        }
        
        // 插入操作
        public void put(String key, Integer value) {
            if (size >= capacity * LOAD_FACTOR) {
                resize();
            }
            
            int index = hash(key);
            Entry current = table[index];
            
            // 检查是否已存在
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            
            // 插入新节点
            Entry newEntry = new Entry(key, value);
            newEntry.next = table[index];
            table[index] = newEntry;
            size++;
        }
        
        private void resize() {
            Entry[] oldTable = table;
            capacity *= 2;
            table = new Entry[capacity];
            size = 0;
            
            for (Entry head : oldTable) {
                while (head != null) {
                    put(head.key, head.value);
                    head = head.next;
                }
            }
        }
    }
}

// 树查找实现
public class TreeSearch {
    
    // 二叉搜索树查找
    static class BSTSearch {
        static class TreeNode {
            int val;
            TreeNode left, right;
            TreeNode(int val) { this.val = val; }
        }
        
        // 递归查找
        public static TreeNode search(TreeNode root, int target) {
            if (root == null || root.val == target) {
                return root;
            }
            
            if (target < root.val) {
                return search(root.left, target);
            } else { 
                return search(root.right, target);
            }
        }
        
        // 迭代查找
        public static TreeNode searchIterative(TreeNode root, int target) {
            while (root != null && root.val != target) {
                if (target < root.val) {
                    root = root.left;
                } else {
                    root = root.right;
                }
            }
            return root;
        }
        
        // 查找最小值
        public static TreeNode findMin(TreeNode root) {
            while (root != null && root.left != null) {
                root = root.left;
            }
            return root;
        }
        
        // 查找最大值
        public static TreeNode findMax(TreeNode root) {
            while (root != null && root.right != null) {
                root = root.right;
            }
            return root;
        }
        
        // 查找前驱节点
        public static TreeNode findPredecessor(TreeNode root, int target) {
            TreeNode predecessor = null;
            
            while (root != null) {
                if (target > root.val) {
                    predecessor = root;
                    root = root.right;
                } else {
                    root = root.left;
                }
            }
            return predecessor;
        }
    }
    
    // Trie树查找（字典树）
    static class TrieSearch {
        static class TrieNode {
            TrieNode[] children = new TrieNode[26];
            boolean isEnd = false;
        }
        
        private TrieNode root;
        
        public TrieSearch() {
            root = new TrieNode();
        }
        
        // 插入单词
        public void insert(String word) {
            TrieNode current = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (current.children[index] == null) {
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }
            current.isEnd = true;
        }
        
        // 查找完整单词
        public boolean search(String word) {
            TrieNode node = searchNode(word);
            return node != null && node.isEnd;
        }
        
        // 查找前缀
        public boolean startsWith(String prefix) {
            return searchNode(prefix) != null;
        }
        
        private TrieNode searchNode(String word) {
            TrieNode current = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (current.children[index] == null) {
                    return null;
                }
                current = current.children[index];
            }
            return current;
        }
        
        // 获取所有以prefix开头的单词
        public List<String> getWordsWithPrefix(String prefix) {
            List<String> result = new ArrayList<>();
            TrieNode prefixNode = searchNode(prefix);
            
            if (prefixNode != null) {
                dfs(prefixNode, prefix, result);
            }
            return result;
        }
        
        private void dfs(TrieNode node, String current, List<String> result) {
            if (node.isEnd) {
                result.add(current);
            }
            
            for (int i = 0; i < 26; i++) {
                if (node.children[i] != null) {
                    dfs(node.children[i], current + (char)('a' + i), result);
                }
            }
        }
    }
}

// 布隆过滤器实现
public class BloomFilter {
    private BitSet bitSet;
    private int size;
    private int hashFunctions;
    
    public BloomFilter(int expectedElements, double falsePositiveRate) {
        this.size = calculateOptimalSize(expectedElements, falsePositiveRate);
        this.hashFunctions = calculateOptimalHashFunctions(expectedElements, size);
        this.bitSet = new BitSet(size);
    }
    
    // 添加元素
    public void add(String element) {
        for (int i = 0; i < hashFunctions; i++) {
            int hash = hash(element, i);
            bitSet.set(Math.abs(hash % size));
        }
    }
    
    // 查找元素（可能存在）
    public boolean mightContain(String element) {
        for (int i = 0; i < hashFunctions; i++) {
            int hash = hash(element, i);
            if (!bitSet.get(Math.abs(hash % size))) {
                return false; // 确定不存在
            }
        }
        return true; // 可能存在
    }
    
    private int hash(String element, int seed) {
        return element.hashCode() * seed;
    }
    
    private int calculateOptimalSize(int n, double p) {
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
    
    private int calculateOptimalHashFunctions(int n, int m) {
        return (int) (m / n * Math.log(2));
    }
}

// 基础字符串操作
public class BasicStringOperations {
    
    // 字符串反转
    public static String reverse(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }
    
    // 回文判断
    public static boolean isPalindrome(String s) {
        // 忽略大小写和非字母数字字符
        String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        int left = 0, right = cleaned.length() - 1;
        
        while (left < right) {
            if (cleaned.charAt(left) != cleaned.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    
    // 字符频率统计
    public static Map<Character, Integer> countCharacters(String s) {
        Map<Character, Integer> frequency = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0) + 1);
        }
        return frequency;
    }
    
    // 最长回文子串
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        
        int start = 0, maxLen = 1;
        
        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 > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }
    
    private static 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;
    }
    
    // 字符串压缩
    public static String compress(String s) {
        if (s.length() <= 2) return s;
        
        StringBuilder compressed = new StringBuilder();
        int count = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                compressed.append(s.charAt(i - 1));
                if (count > 1) {
                    compressed.append(count);
                }
                count = 1;
            }
        }
        
        // 添加最后一组
        compressed.append(s.charAt(s.length() - 1));
        if (count > 1) {
            compressed.append(count);
        }
        
        return compressed.length() < s.length() ? compressed.toString() : s;
    }
}

// 暴力字符串匹配
public class BruteForceStringMatch {
    
    // 基本暴力匹配
    public static int bruteForceSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i; // 找到匹配
            }
        }
        return -1; // 未找到
    }
    
    // 查找所有匹配位置
    public static List<Integer> findAllMatches(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        
        for (int i = 0; i <= n - m; i++) {
            if (text.substring(i, i + m).equals(pattern)) {
                matches.add(i);
            }
        }
        return matches;
    }
}

// KMP算法实现
public class KMPAlgorithm {
    
    // 构建失效函数（部分匹配表）
    private static int[] buildFailureFunction(String pattern) {
        int m = pattern.length();
        int[] failure = new int[m];
        int j = 0;
        
        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = failure[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            failure[i] = j;
        }
        return failure;
    }
    
    // KMP搜索
    public static int kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0) return 0;
        if (m > n) return -1;
        
        int[] failure = buildFailureFunction(pattern);
        int j = 0; // pattern的索引
        
        for (int i = 0; i < n; i++) { // text的索引
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = failure[j - 1]; // 跳跃
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1; // 找到匹配
            }
        }
        return -1; // 未找到
    }
    
    // 查找所有匹配位置
    public static List<Integer> kmpSearchAll(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0 || m > n) return matches;
        
        int[] failure = buildFailureFunction(pattern);
        int j = 0;
        
        for (int i = 0; i < n; i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = failure[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                matches.add(i - m + 1);
                j = failure[j - 1]; // 继续查找下一个匹配
            }
        }
        return matches;
    }
}

// Rabin-Karp算法实现
public class RabinKarpAlgorithm {
    private static final int PRIME = 101; // 用于哈希计算的质数
    
    public static int rabinKarpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        if (m > n) return -1;
        
        long patternHash = calculateHash(pattern, m);
        long textHash = calculateHash(text, m);
        
        for (int i = 0; i <= n - m; i++) {
            // 如果哈希值相等，进行字符比较
            if (patternHash == textHash && checkEqual(text, i, pattern)) {
                return i;
            }
            
            // 计算下一个窗口的哈希值
            if (i < n - m) {
                textHash = recalculateHash(text, i, i + m, textHash, m);
            }
        }
        return -1;
    }
    
    private static long calculateHash(String str, int length) {
        long hash = 0;
        for (int i = 0; i < length; i++) {
            hash += str.charAt(i) * Math.pow(PRIME, i);
        }
        return hash;
    }
    
    private static long recalculateHash(String str, int oldIndex, int newIndex, 
                                       long oldHash, int patternLength) {
        long newHash = oldHash - str.charAt(oldIndex);
        newHash = newHash / PRIME;
        newHash += str.charAt(newIndex) * Math.pow(PRIME, patternLength - 1);
        return newHash;
    }
    
    private static boolean checkEqual(String text, int start, String pattern) {
        for (int i = 0; i < pattern.length(); i++) {
            if (text.charAt(start + i) != pattern.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

// 编辑距离算法
public class EditDistance {
    
    // 计算编辑距离
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        // dp[i][j] 表示 word1[0...i-1] 转换为 word2[0...j-1] 的最小操作数
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // 删除所有字符
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // 插入所有字符
        }
        
        // 填充DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需要操作
                } else {
                    dp[i][j] = 1 + Math.min(
                        Math.min(dp[i - 1][j],     // 删除
                                dp[i][j - 1]),     // 插入
                        dp[i - 1][j - 1]           // 替换
                    );
                }
            }
        }
        return dp[m][n];
    }
    
    // 空间优化版本
    public static int minDistanceOptimized(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        // 只需要两行
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        // 初始化第一行
        for (int j = 0; j <= n; j++) {
            prev[j] = j;
        }
        
        for (int i = 1; i <= m; i++) {
            curr[0] = i;
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    curr[j] = prev[j - 1];
                } else {
                    curr[j] = 1 + Math.min(Math.min(prev[j], curr[j - 1]), prev[j - 1]);
                }
            }
            // 交换数组
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        return prev[n];
    }
    
    // 获取编辑操作序列
    public static List<String> getEditOperations(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        // 构建DP表（同上）
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                }
            }
        }
        
        // 回溯操作序列
        List<String> operations = new ArrayList<>();
        int i = m, j = n;
        
        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && word1.charAt(i - 1) == word2.charAt(j - 1)) {
                i--; j--;
            } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
                operations.add(0, "Replace " + word1.charAt(i - 1) + " with " + word2.charAt(j - 1));
                i--; j--;
            } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
                operations.add(0, "Delete " + word1.charAt(i - 1));
                i--;
            } else {
                operations.add(0, "Insert " + word2.charAt(j - 1));
                j--;
            }
        }
        return operations;
    }
}