算法常用方法

# 算法常用方法 ## 一、数组 ### 获取长度 \`\`\`java // 数组获取长度 int\[\] nums; int m = nums.length; // 没有括号 // 字符串获取长度 String str; int len = str.length(); // 有括号 \`\`\` ### 数组进行二分查找 \`\`\`java int index = Arrays.binarySearch(array, key); // 前提是array有序 \`\`\` \> \`array\`：\*\*必须是已经升序排序好的数组\*\*（否则结果不可靠） \> \> \`key\`：你要查找的目标值 \> \> \`index\`：返回目标值在数组中的下标（如果找不到会返回负数） ### 数组排序 \`\`\`java int\[\] ans = {3, 1, 4, 2}; Arrays.sort(ans); // 对数组进行升序排序 \`\`\` ### 数组遍历 \`\`\`java for (char c : chars) { System.out.print(c + " "); } \`\`\` ### 数组复制将字符串 \`s\` 转为字符数组，然后把其中的前 \`sOldSize\` 个字符复制到目标数组 \`newS\` 中，从索引 0 开始放。 \`\`\`java String s = "hello"; int sOldSize = s.length(); char\[\] newS = new char\[100\]; System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize); \`\`\` ## 二、字符串 ### 获取字符串的字符 \`\`\`java String s = "asdfjkld" for(int i = 0; i \< s.length(); i++) { char a = s.charAt(i); } \`\`\` ### 字符串转字符数组 \`\`\`java String str = "hello"; char\[\] chars = str.toCharArray(); \`\`\` ### 判断字符是否为数字判断参数 \`ch\` 是否为 \*\*一个十进制数字字符\*\*（即 \`'0'\` 到 \`'9'\`） \`\`\`java Boolean isDigit = Character.isDigit('5'); \`\`\` ### 字符串倒置 \`\`\`java String reverse = new StringBuffer(s).reverse().toString(); //字符串倒置 \`\`\` ### 可变长字符串场景：一般用于处理比较复杂或麻烦的字符串操作，常用的有追加和反转。 \`\`\`java StringBuffer ans1 = new StringBuffer(); // 线程安全 StringBuilder ans2 = new StringBuilder(); // 速度快 \`\`\` 两者方法基本相同： \| 方法 \| 说明 \| \| -------------------- \| ---------------- \| \| \`append(...)\` \| 追加字符串/字符 \| \| \`insert(int, str)\` \| 插入字符串 \| \| \`delete(start, end)\` \| 删除指定范围字符 \| \| \`reverse()\` \| 反转字符串 \| \| \`toString()\` \| 转为 \`String\` \| \| \`setCharAt(i, c)\` \| 修改某个位置字符 \| \| \`length()\` \| 当前长度 \| \| \`setLength(n)\` \| 设置新长度 \| ### 截取字符串 \`\`\`java String s = "hello world"; // 从第0到5个字符（不含5）→ "hello" String part = s.substring(0, 5); \`\`\` ### 去除前后空格 \`\`\`java // 除去开头和末尾的空白字符 String s = s.trim(); \`\`\` ### 字符串分割 \`\`\`java // 正则匹配连续的空白字符作为分隔符分割 String\[\] split = s.split("\\\\s+") \`\`\` ### 数组转列表 \`\`\`java String\[\] arr = {"a", "b", "c"}; List list = Arrays.asList(arr); \`\`\` ### 以分隔符拼接字符串 \`\`\`java String result = String.join(", ", "Apple", "Banana", "Cherry"); // 拼接字符串 List list = Arrays.asList("world", "hello"); String result = String.join(" ", list); //拼接列表 \`\`\` ### 数值反转 \`\`\`java // 使用运算符 s\[l\] \^= s\[r\]; s\[r\] \^= s\[l\]; s\[l\] \^= s\[r\]; // 使用临时变量 char temp = s\[l\]; s\[l\] = s\[r\]; s\[r\] = temp; \`\`\` ### 查找一个字符或子字符串的索引 \`\`\`java String s = "Hello World"; // 查找字符 int idx1 = s.indexOf('o'); // 4 int idx2 = s.indexOf('o', 5); // 7 // 查找子字符串 int idx3 = s.indexOf("World"); int idx4 = s.indexOf("World", 3); \`\`\` ## 三、其他 ### 赋值int最大值 \`\`\`java int ans = Integer.MAX_VALUE; \`\`\` ### 判断奇偶 \`\`\`java // 判断偶数 (num \& 1) == 0 或者 num % 2 == 0 // 按位与更高效。原理：二进制中最后一位为 0 的数是偶数，通过与 1 进行按位与运算，结果为 0 则说明是偶数 \`\`\` \*\*按位与：全 1 则 1，有 0 则 0\*\* - 用\`num \& 1\`时，本质是拿num的最后一位与1做与运算： - 若结果为 \`0\`，说明 \`num\` 最后一位是 \`0\` → 偶数； - 若结果为 \`1\`，说明 \`num\` 最后一位是 \`1\` → 奇数。 ### 打印输出 \`\`\`java Scanner scanner = new Scanner(System.in); String s = scanner.next(); System.out.println(s); scanner.close(); \`\`\` ### Math工具类常用方法 \| 方法名 \| 说明 \| 示例 \| \| ----------- \| --------------------------------- \| --------------------------- \| \| \`abs(x)\` \| 取绝对值 \| \`Math.abs(-5)\` → \`5\` \| \| \`max(x, y)\` \| 取最大值 \| \`Math.max(3, 7)\` → \`7\` \| \| \`min(x, y)\` \| 取最小值 \| \`Math.min(3, 7)\` → \`3\` \| \| \`sqrt(x)\` \| 开平方 \| \`Math.sqrt(9)\` → \`3.0\` \| \| \`cbrt(x)\` \| 开立方 \| \`Math.cbrt(8)\` → \`2.0\` \| \| \`pow(a, b)\` \| 幂运算 a 的 b 次方 \| \`Math.pow(2, 3)\` → \`8.0\` \| \| \`signum(x)\` \| 判断符号（负数 -1、零 0、正数 1） \| \`Math.signum(-10)\` → \`-1.0\` \| \*\*比较两数值大小\*\* \`\`\`java int ans = Math.min(a, b); \`\`\` ### Character常用方法 \| 功能分类 \| 方法声明 \| 作用描述 \| 参数说明 \| 返回值类型 \| \| ---------------- \| --------------------------- \| ------------------------------------------------------------ \| --------------------------------- \| ---------- \| \| \*\*字符类型判断\*\* \| \`isLetter(char ch)\` \| 判断是否为字母（a-z, A-Z，包括 Unicode 字母） \| 待判断的字符 \`ch\` \| \`boolean\` \| \| \| \`isDigit(char ch)\` \| 判断是否为数字字符（0-9，包括 Unicode 数字） \| 待判断的字符 \`ch\` \| \`boolean\` \| \| \| \`isLetterOrDigit(char ch)\` \| 判断是否为字母或数字 \| 待判断的字符 \`ch\` \| \`boolean\` \| \| \| \`isWhitespace(char ch)\` \| 判断是否为空白字符（空格、\`\\t\`、\`\\n\`、\`\\r\` 等） \| 待判断的字符 \`ch\` \| \`boolean\` \| \| \| \`isUpperCase(char ch)\` \| 判断是否为大写字母（A-Z，包括 Unicode 大写字母） \| 待判断的字符 \`ch\` \| \`boolean\` \| \| \| \`isLowerCase(char ch)\` \| 判断是否为小写字母（a-z，包括 Unicode 小写字母） \| 待判断的字符 \`ch\` \| \`boolean\` \| \| \*\*字符转换\*\* \| \`toUpperCase(char ch)\` \| 将字符转换为大写（仅对小写字母有效，其他字符不变） \| 待转换的字符 \`ch\` \| \`char\` \| \| \| \`toLowerCase(char ch)\` \| 将字符转换为小写（仅对大写字母有效，其他字符不变） \| 待转换的字符 \`ch\` \| \`char\` \| \| \| \`toTitleCase(char ch)\` \| 将字符转换为首字母大写（如小写转大写，大写 / 数字不变） \| 待转换的字符 \`ch\` \| \`char\` \| \| \*\*数值相关\*\* \| \`getNumericValue(char ch)\` \| 获取字符对应的数值（数字字符返回对应数字，字母 A-Z 对应 10-35，其他返回 - 1） \| 待转换的字符 \`ch\` \| \`int\` \| \| \| \`digit(char ch, int radix)\` \| 以 \`radix\` 为基数，将字符转换为整数（失败返回 - 1） \| \`ch\`：字符；\`radix\`：基数（2-36） \| \`int\` \| \| \*\*其他常用\*\* \| \`charCount(int codePoint)\` \| 判断 Unicode 代码点是否需要用 2 个 \`char\` 表示（如 emoji 字符） \| Unicode 代码点 \`codePoint\` \| \`int\` \| \| \| \`isISOControl(char ch)\` \| 判断是否为控制字符（如 \`\\b\` 退格、\`\\r\` 回车） \| 待判断的字符 \`ch\` \| \`boolean\` \| \> 实际开发中，\*\*字符类型判断\*\*和\*\*大小写转换\*\*是最常用的两类方法 \> \> 所有方法均为 \`static\` 静态方法，直接通过 \`Character.方法名(...)\` 调用。 ## 四、链表 ### 链表基本操作 \*\*链表节点基本定义\*\* \`\`\`java public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } \`\`\` \*\*创建虚拟头结点\*\* \`\`\`java ListNode dummyHead = new ListNode(0); // 或 ListNode dummy = new ListNode(0, head); \`\`\` \*\*删除节点\*\* \`\`\`java ListNode temp.next = temp.next.next; \`\`\` \*\*链表逆序打印\*\* 使用栈实现 \*\*查找单链表中的倒数第k个结点\*\* 快慢指针法 \*\*链表反转\*\*：部分代码双指针法 \`\`\`java while (curr != null) { ListNode next = curr.next; // 存储下一个节点 curr.next = prev; // 反转 prev = curr; // 第一个指针后移 curr = next; // 第二个指针后移 } return prev; // 最后prev指针刚好指向最后一个节点，直接返回 \`\`\` ## 五、集合 ### List列表 \| 方法 \| 作用 \| 常见算法场景 \| \| --------------------------- \| ---------------------- \| ---------------------- \| \| \`add(E e)\` \| 添加元素到末尾 \| 构建结果集，动态收集 \| \| \`add(int index, E e)\` \| 在指定位置插入元素 \| 插入排序，模拟结构 \| \| \`get(int index)\` \| 获取指定位置的元素 \| 遍历、二分查找 \| \| \`set(int index, E e)\` \| 修改指定位置元素 \| 更新数据 \| \| \`remove(int index)\` \| 删除指定位置的元素 \| 删除操作，双指针去重等 \| \| \`remove(Object o)\` \| 删除首次出现的指定对象 \| 去除特定值 \| \| \`contains(Object o)\` \| 判断是否包含某个元素 \| 去重、判定 \| \| \`size()\` \| 返回当前元素数量 \| 判断边界、for 循环条件 \| \| \`isEmpty()\` \| 是否为空 \| 特判处理 \| \| \`clear()\` \| 清空列表 \| 多轮处理、初始化 \| \| \`indexOf(Object o)\` \| 返回第一次出现的位置 \| 模拟查找 \| \| \`subList(from, to)\` \| 获取子列表（左闭右开） \| 分块、滑动窗口、切片 \| \| \`Collections.sort(list)\` \| 排序（默认升序） \| 排序算法题 \| \| \`Collections.reverse(list)\` \| 反转列表 \| 翻转数据，后处理 \| ## 六、哈希表 ### 哈希数组 "哈希数组"是一种特殊形式的哈希表，它用\*\*普通数组\*\*替代 HashMap，\*\*数组索引为键，值为计数/状态/频率等\*\*。 \*\*统计频率\*\* \*\*快速查找是否存在\*\* ### HashMap \`\`\`java Map map = new HashMap\<\>(); // 也可以用 HashMap map = new HashMap\<\>(); // 添加元素 map.put("apple", 3); // 获取元素 int count1 = map.get("apple"); // 3 // 如果 key 不存在，则返回你提供的默认值 defaultValue，而不是 null。 int count2 = map.getOrDefault("banana", 0); // banana 不存在，返回默认值 0 // 判断是否存在 key boolean hasBanana = map.containsKey("banana"); // true // 获取所有key值：用于遍历 Set keys = map.keySet(); // 遍历所有value值 for (String key : map.keySet()) { System.out.println(key + " -\> " + map.get(key)); } // 删除元素 map.remove("orange"); \`\`\` ### HashSet HashSet 基于 \`HashMap\` 实现，只能存 key，且不可重复，可用于： \*\*去除重复元素\*\* \*\*判断某个元素是否出现过\*\* \`\`\`java Set set = new HashSet\<\>(); //也可以用 HashSet set = new HashSet\<\>(); // 添加元素 set.add("apple"); // 判断是否存在 set.contains("apple"); // true // 删除元素 set.remove("apple"); // 获取大小 set.size(); // 清空集合 set.clear(); // 遍历 for (String item : set) { System.out.println(item); } \`\`\` ## 七、栈与队列 Java 中可使用 \`Stack\` 类或 \`Deque\` 来实现栈（一般用\`Deque\`，可以同时当栈和队列来使用）。\`Deque\`（Double Ended Queue，双端队列）是 \*\*Java 中的双端队列接口\*\*，它允许分别在\*\*队列的头部和尾部\*\*进行 \*\*插入（push/offer）、删除（pop/poll）\*\* 操作。 ### \*\*栈的使用\*\* 应用于：括号匹配、中缀表达式、单调栈、反转等 \`\`\`java Stack stack = new Stack\<\>(); stack.push(1); // 入栈 int top = stack.pop(); // 出栈 int peek = stack.peek(); // 查看栈顶元素但不移除 boolean empty = stack.isEmpty(); // 栈是否为空 \`\`\` \`\`\`java Deque deque = new LinkedList\<\>(); // 或者使用ArrayDeque deque.push('A'); // 入栈操作 char c = deque.peek(); // 查看栈顶元素 deque.pop(); // 出栈操作 \`\`\` 用 \`Deque\` 替代 \`Stack\` 是 Java 现代开发的最佳实践，特别是使用 \`ArrayDeque\`。除非你特别需要线程安全或兼容老代码，否则不应使用 \`Stack\`。 ### \*\*队列的使用\*\* 1. \*\*普通队列（最常用）\*\* \`\`\`java Queue queue = new LinkedList\<\>(); // 或 Deque queue = new LinkedList\<\>(); queue.offer(10); // 入队（尾部） int num = queue.peek(); // 查看队首 // 出队（头部） while (!queue.isEmpty()) { queue.poll(); } \`\`\` 2. \*\*\`ArrayDeque\`（性能更优）\*\* \`\`\` Deque queue = new ArrayDeque\<\>(); \`\`\` - 优于 \`LinkedList\`，因为没有节点开销。 - 不能存 \`null\`。 3. \*\*优先队列（自动排序）\*\* \`\`\`java PriorityQueue pq = new PriorityQueue\<\>(); pq.offer(5); pq.offer(1); pq.poll(); // 输出 1（最小的先出） //使优先队列中的数据倒序排列 PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(int\[\] pair1, int\[\] pair2) { return pair1\[0\] != pair2\[0\] ? pair2\[0\] - pair1\[0\] : pair2\[1\] - pair1\[1\]; } }); \`\`\` \> 默认是小顶堆（最小元素优先）。也可以传比较器来自定义排序。 4. \*\*阻塞队列（线程间通信）\*\* \`\`\`java BlockingQueue queue = new ArrayBlockingQueue\<\>(10); queue.put(1); // 若满则阻塞 queue.take(); // 若空则阻塞 \`\`\` \> 适合多线程生产者消费者模型。 ## 八、线程 ### 两个线程轮流打印通过 \`Runnable\` + \`synchronized + wait/notify\`实现 \| 关键字 \| 作用 \| \| -------------- \| -------------------------------------------- \| \| \`synchronized\` \| 同步代码块，确保同一时刻只有一个线程可以执行 \| \| \`wait()\` \| 当前线程释放锁并挂起，等待被唤醒 \| \| \`notify()\` \| 唤醒正在等待这个锁的某个线程 \| \| \`notifyAll()\` \| 唤醒所有在这个锁上等待的线程 \| \`\`\`java public class AlternatePrint { // 共享计数器 private int count = 1; // 最大打印值 private static final int MAX = 10; // 锁对象 private final Object lock = new Object(); // 线程A：打印奇数 public void printOdd() { synchronized (lock) { while (count \<= MAX) { // 如果是奇数，当前线程打印 if (count % 2 == 1) { System.out.println("Thread A: " + count); count++; // 通知其他线程 lock.notifyAll(); } else { // 如果是偶数，当前线程等待 try { lock.wait(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } // 打印完毕，唤醒可能等待的线程 lock.notifyAll(); } } // 线程B：打印偶数 public void printEven() { synchronized (lock) { while (count \<= MAX) { // 如果是偶数，当前线程打印 if (count % 2 == 0) { System.out.println("Thread B: " + count); count++; // 通知其他线程 lock.notifyAll(); } else { // 如果是奇数，当前线程等待 try { lock.wait(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } // 打印完毕，唤醒可能等待的线程 lock.notifyAll(); } } public static void main(String\[\] args) { AlternatePrint printer = new AlternatePrint(); // 创建并启动线程A（打印奇数） Thread threadA = new Thread(printer::printOdd, "Thread-A"); // 创建并启动线程B（打印偶数） Thread threadB = new Thread(printer::printEven, "Thread-B"); threadA.start(); threadB.start(); } } \`\`\` \> 线程创建的简化方式： \> \> \*\*1、最原始：匿名内部类\*\* \> \> \`\`\`java \> // 通过匿名内部类实现 Runnable 接口 \> Thread threadA = new Thread(new Runnable() { \> @Override \> public void run() { \> // 调用 printer 的 printOdd() 方法 \> printer.printOdd(); \> } \> }, "Thread-A"); \> \`\`\` \> \> \*\*2、lambda 表达式\*\* \> \> \`\`\`java \> // 用 lambda 表达式简化匿名内部类（省略接口名和方法名） \> Thread threadA = new Thread(() -\> { \> printer.printOdd(); // 直接写要执行的方法 \> }, "Thread-A"); \> \`\`\` \> \> \*\*3、再简化：方法引用\*\* \> \> \`\`\`java \> // 用方法引用进一步简化（直接引用已有的方法） \> Thread threadA = new Thread(printer::printOdd, "Thread-A"); \> \`\`\`