算法模版 算法模板持续更新中… 1.二分查找// 找到大于等于目标数的第一个位置 public int lower_bound(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low < high) { int mid = (high - low) / 2 + 2024-02-12 算法与数据结构 算法 数据结构 模版
Trie(前缀树) Trie：前缀树应用：可以用来找文本中的敏感词，先将所有敏感词建树，然后从目标文本的第一个位置开始遍历，如果以该字符开头的串在数中，则在对应敏感词里记录该下标。 面试题 17.17. 多次搜索 Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应 2024-02-12 算法与数据结构 算法 数据结构 Trie 前缀树
并查集 题目题目5995. 字符串分组 class UF { int[] p, r; int setCount; public UF(int n) { this.setCount = n; this.p = new int[n]; this.r = new int[n]; for (int i = 2024-02-12 算法与数据结构 算法 数据结构 并查集
树状数组与线段树 数据结构 区间求和 区间最大值 区间修改 单点修改 前缀和 ✓ ✕ ✕ ✕ 差分 ✕ ✕ ✓ ✕ 树状数组 ✓ ✓ ✕ ✓ 线段数 ✓ ✓ ✓ ✓ 树状数组单点修改，求区间和： 初始化时间复杂度度：$O(N)$ 单次修改时间复杂度：$O(logN)$ 单次修改时间复杂度：$O(logN)$ 空间复杂度：$O(N)$ 单点修改，区间求最值： 单点修改：$O( 2024-02-12 算法与数据结构 算法 数据结构 树状数组 线段树 区间信息
链表 双向链表与单链表相比，双向链表多了一个指向其前一个节点的指针，在实际使用时，通常使用两个哑节点分别作为哑头节点和哑尾节点，方便操作。 // 节点类 class DLinkedNode{ int val; DLinkedNode prev; DLinkedNode next; public DLinkedNode(){} publ 2024-02-12 算法与数据结构 算法 数据结构 链表 双向链表 LRU LFU
Meet in the middle Meet in the middle（折半搜索）讲解：https://www.geeksforgeeks.org/meet-in-the-middle/ 题目：5897. 将数组分成两个数组并最小化数组和的差 1755. 最接近目标值的子序列和 956. 最高的广告牌 描述：「Meet in the middle」是一个搜索技巧，可以在输入很小但是却不足以小到可以使用暴力法算时使用。就像分治法把问 2024-02-12 算法与数据结构 算法 位运算 进阶算法 折半搜索
小知识 数据范围 数据范围 算法时间复杂度 最小包含2进制位数 $10^{5}$ $O(n)或者O(nlogn)$ 17 $3^{19}$ 整型中3的最大次幂 1162261467 int 最大值 2147483647 long 最大值 9223372036854775807 $10^{18}$ 常用结论 ID Key Words Conclusion 1 2024-02-12 算法与数据结构 小知识 算法 数据结构
前缀和&差分 前缀和前缀和可以在$O(1)$时间内的计算一块区域的总和 一维前缀和3127. 来，骗 // 计算 int[] getPrefix(int[] arr) { int n = arr.length; int[] prefix = new int[n+1]; // 添加一位初始和，简化代码 for (int i = 1; i <= n; i++) { 2024-02-12 算法与数据结构 算法 数据结构 基础知识 前缀和 差分
排序 Shopee-002. Shoffee 剑指 Offer 51. 数组中的逆序对 排序算法比较 算法 平均时间复杂度 最优时间复杂度 最坏时间复杂度 空间复杂度 稳定性 冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定 归并排序 $O(nlogn)$ $O(nlogn 2024-02-12 算法与数据结构 算法 数据结构 基础知识 排序
基本计算器-后缀表达式 表达式值计算通用解法：将中缀表达式转换为后缀表达式 1.遇到数字，直接存入后缀 2.遇到(，入栈 3.遇到)，不断弹出栈顶元素，直到遇到( 4.遇到其他运算符，不断弹出优先级大于等于当前运算符的的元素，最后将当前运算符入栈。*,/优先级大于+,- 5.最后弹出栈中元素，直到栈空 224. 基本计算器 1597. 根据中缀表达式构造二叉表达式树 public List<String> ge 2024-02-12 算法与数据结构 秋招 笔试 算法题
