贪心 贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。 45. 跳跃游戏 II 300. 最长递增子序列 3292. 形成目标字符串需要的最少字符串数 II：其中用到的贪心就是跳跃游戏 反悔贪心 概念 反悔贪心算法是一种优化算法，通常用于解决组合优化问题。与传统的贪心算法不同，反悔贪心算法在每一步决策之后考虑可能的反悔，以确保最终的决策是最佳的。它的目标是最小化决策的后悔或损失。 流程 初始决策： 算法开始时会做出初始决策，通常基于某种贪心策略来选择一个方案。 模拟反悔： 在每个决策步骤之后，算法会模拟所有可能的替代决策，计算每个替代决策的后悔值或损失。后悔值是当前决策相对于其他可能决策的性能差距。 选择最小后悔： 算法会选择具有最小后悔值的替代决策作为最终决策。这意味着算法会选择对整体性能改进最大的替代决策。 迭代： 反悔贪心算法会重复执行步骤 2 和步骤 3，每次迭代都会尝试改进当前的决策，直到后悔值不再减小或达到某个停止条件。 应用 反悔贪心算法的应用 ...

一些常见的排序

二分查找 概念 二分查找（Binary Search）是一种高效的搜索算法，适用于有序数组或有序列表。它通过不断地将搜索范围减半来查找目标元素，从而在O(log n)的时间复杂度内找到特定元素的位置。 基本思想是 在有序数组中找到中间位置的元素，与目标元素进行比较。如果中间元素等于目标元素，则搜索成功；如果中间元素大于目标元素，则在数组的左半部分继续进行二分查找；如果中间元素小于目标元素，则在数组的右半部分进行二分查找。通过不断重复这个过程，直到找到目标元素或搜索范围缩小到为空为止。 此外，二分查找也可以进行变种，例如找到大于/小于目标元素的最小/最大元素，或者找到目标元素的第一个/最后一个位置等。它在各种应用场景中都有广泛的应用，如在搜索引擎、数据库查询、游戏开发等领域中都能发挥重要作用。 基本模板 找到大于等于target的第一个数 12345while (l < r) { int m = l + (r-l)/2; if (nums[m] < target) l = m + 1; else r = m;} 找到大于target ...

并查集（union-find） 介绍 概念 当涉及到处理元素之间的等价关系、集合的合并与查询等问题时，它是一种用于维护不相交集合的有效方法，常被用于解决诸如连通性、网络连接状态、等价关系等问题。 核心思想 并查集通过构建一个森林（或者称为集合），其中每个元素都属于一个集合，每个集合以一个代表元素来标识。这样的数据结构可以高效地进行两个关键操作：查找和合并。 操作 查找（Find）： 查找一个元素所属的集合，通常以代表元素作为标识。这个操作通常用于判断两个元素是否属于同一个集合，即判断它们的代表元素是否相同。 123int find(int x) { return pa[x] == x ? x : (pa[x] = find(pa[x]));} 合并（Union）： 将两个不相交的集合合并为一个集合，即将两个集合的代表元素连接在一起。 1234567void union(int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return; if (rank[ ...

质数 计算不同质因子的数目 比方说，300的不同质因子的数目为3，因为 300 = 2 * 2 * 3 * 5 * 5 。 1234567891011// 计算10^5内的数的不同质因子的数目private static final int MX = (int) 1e5 + 1;private static final int[] omega = new int[MX];static { for (int i = 2; i < MX; i++) if (omega[i] == 0) // i 是质数 for (int j = i; j < MX; j += i) omega[j]++; // i 是 j 的一个质因子}// 作者：灵茶山艾府// 链接：https://leetcode.cn/problems/apply-operations-to-maximize-score/solutions/2385936/gong-xian-fa-dan-diao-zhan-pythonjav ...

链表相关 翻转链表 12345678910ListNode reverseList(ListNode head) { ListNode pre = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre;} 快慢指针找中间节点 12345678ListNode getMidNode(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow;} ...