# arithmetic **Repository Path**: raoyuan/arithmetic ## Basic Information - **Project Name**: arithmetic - **Description**: LeetCode算法整理 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2020-06-13 - **Last Updated**: 2026-01-06 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # arithmetic ### 前置知识 在学习算法前，了解一些和算法不直接相关但是有用的知识或工具，对我们解决算法会起到事半功倍的效果 1. **ascii字母对应值：** A~Z = 65~90 a~z = 97~122 2. **异或运算：** [xor](src/com/yuan/xor) **异或运算逻辑：** 相同为0,不同为1。相当于无进位相加 * 异或满足交换律和分配律。即： + 1.a^b和b^a相同 + 2.(a^b)^c和a^(b^c)相同 * a和b进行交换. a =a ^ b; b = a ^ b; a = a ^ b. > **注意：** 在数组中利用异或交换数值时,注意避免同一位置交换,否则会将该位置置为0. `arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; ` 如果i和j相等,就会将该位置置为0. ### 一、二分法 🚩 [dichotomy](src/com/yuan/dichotomy) 1.在有序数组中寻找数值是否存在，这种情况比较容易想到用二分法。 2.在乱序中找某个数，数据乱序、定义复杂，需要考虑能不能进行排序，从而构建二分法。 > **注意：** 计算中位坐标的时候,不能用 （首+尾）/2的方式,因为可能存在溢出, 应该用 首 + （尾-首）/2的方式进行计算。 * **相关题型:** 1. 有序数组中查找某个值 [code01_BSExist](src/com/yuan/dichotomy/code01_BSExist.java) ___ ### 二、链表 [link](src/com/yuan/a02link) **单向链表：** 每个节点只能找到自己的下一个节点。 * **相关题型：** 1. 回文链表 [IsPalindrome](src/com/yuan/a02link/IsPalindrome.java) 2. 单向链表反转 [ReverseList](src/com/yuan/a02link/ReverseList.java) **双向链表：** 每个节点既可以找到自己的上一个节点，也可以找到自己的下一个节点。 * **相关题型：** ___ ### 三、数组 [array](src/com/yuan/a01array) > **注意：** 不要想追赶,利用一个字段解决存储长度反而更好解决。 * **相关题型：** + 基于数组实现队列 + 基于数组实现栈 ___ ### 四、队列 > 取时将数据全部导入另一个人队列,留最后一个元素返回。 + 基于队列实现栈 ___ ### 五、栈 > 取时栈为空讲另一个栈倒出来,有则继续弹出。 + 基于栈实现队列, --- ### 六、排序 > 原地排序指额外空间复杂度为1的排序，稳定性是指相同数据前后位置不会发生变动 时间复杂度 额外空间复杂度 稳定性 选择排序 O(N^2) O(1) 无 冒泡排序 O(N^2) O(1) 有 插入排序 O(N^2) O(1) 有 归并排序 O(N*logN) O(N) 有 快速排序 O(N*logN) O(logN) 无 堆排序 O(N*logN) O(1) 无 ========================================================== 基数排序 O(N) O(M) 有 桶排序 O(N) O(N) 有 ####排序算法总结 1. 不基于比较的排序，对样本数据有严格要求，不易改写。 2. 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用。 3. 基于比较的排序，时间复杂度的极限O(N*logN)。 4. 时间复杂度O(N*logN)、额外空间复杂度低于O(N)，且稳定的基于比较的排序是不存在的。 5. 为了绝对的速度选快排、为了节省空间选堆排、为了稳定性选归并。 ### 七、二叉树 1. 先序遍历：按照先父，再左子，再右子的逻辑进行遍历 2. 中序遍历：按照先左子，再父，再右子的逻辑进行遍历 3. 后序遍历：按照先左子，再右子，再父的逻辑进行遍历 > 完全二叉树: 若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树 > 满二叉树：二叉树的深度为 h，且总节点数为2^n-1，则该二叉树为满二叉树。 > 搜索二叉树：1.节点的左子树只包含小于当前节点的数；2.节点的右子树只包含大于当前节点的数；3.所有左子树和右子树自身必须也是二叉搜索树。 > 平衡二叉树：1.每个节点左右两个子树的高度差不超过1；2.每个左子树和右子树自身必须也是平衡二叉树 ### 八、并查集 🚩 并查集是一种树型数据结构，用于处理一些不相交集合的合并及查询问题(即所谓的并、查) ### 九、图 图结构的表达 - 邻接表法 - 邻接矩阵法 - 等等 图的算法都不难，只不过coding的代价相对较高。 我们可以先将题目给出的图结构转换成我们熟悉的图结构，再调用模板或改写。 图的相关知识点： #### 宽度优先遍历(BPS) 1. 利用队列实现 2. 从源节点开始依次按照宽度进队列，然后弹出，`打印或业务处理` 3. 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列 4. 直到队列为空 #### 深度优先遍历(DPS) 1. 利用栈实现 2. 将第一个节点`打印或业务处理`，放如栈中 3. 弹出节点，获取节点的相邻节点，判断没有进过栈的点进入栈中，并`打印或业务处理` 4. 将当前节点和对应的相邻节点依次加入栈中。 5. 直到栈为空。 #### 拓扑序问题 1. 在图中找到所有入度为0的点输出 2. 把所有入度为0的点在图中删掉，继续找入度为0的点输出，循环往复 3. 图的所有点都被删除后，依次输出的顺序就是拓扑排序 #### 最小生成树算法之Kruskal 1. 总是从权值最小的边开始考虑，依次考察权值依次变大的边 2. 当前的边要么进入最小生成树的集合，要么丢弃 3. 如果当前的边进入最小生成树的集合中不会形成环，就要当前边 4. 如果当前的边进入最小生成树的集合中会形成环，就不要当前边 5. 考察完所有的边之后，最小生成树的集合也得到了 #### 最小生成树算法之Prim 1. 可以从任意节点出发来寻找最小生成树 2. 某个点加入到被选取的点中后，解锁这个点出发的所有新的边 3. 在所有解锁的边中选择最小的边，然后看看这个边会不会形成环 4. 如果会，不要当前边，继续考察剩下解锁边中最小的边，重复3 5. 如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2 6. 当所有点都被选取，最小生成树就得到了 #### Dijkstra算法 1. Dijkstra算法必须指定一个源点 2. 生成一个源点到各个点的最小距离表，一开始只有一条记录，即源点到自己的距离最小为0，源点到其他所有点的最小距离都为正无穷大。 3. 从距离表中拿出没拿到过记录的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步。 4. 源点到所有点的记录如果过都被拿过一遍，过程停止，最小距离表得到了。 该算法可以在寻找没拿到过记录的最小记录时，可以通过记录拿到过的，然后每次进行遍历寻找。也可以通过加强堆来进行优化，提高时间复杂度。 ### 十、递归 #### 暴力递归 暴力递归就是尝试 1. 把问题转化为规模缩小了的同类问题的子问题 2. 有明确的不需要继续进行递归的条件(base case) 3. 有当得到了子问题的结果之后的决策过程 4. 不记录每个子问题的解 相关算法练习 1. 打印n层汉诺塔从左边移动到最右边的全部过程 2. 打印一个字符串的全部子序列 3. 打印一个字符串的全部子序列，要求不要出现重复字面值的序列 4. 打印一个字符串的全部排列 5. 打印一个字符串的全部排列，要求不要出现重复的排列 #### 从暴力递归到动态规划 如何找到某个问题的动态规划方式？ 1. 设计暴力递归: 重要原则 + 4种常见尝试模型 ⭐ 2. 分析有没有重复解: 套路解决 3. 用记忆化搜索 -> 用严格表结构实现动态规划: 套路解决 4. 看看是否继续优化: 套路解决 面试种设计暴力递归过程的原则 1. 每一个可变参数的类型，一定不要比int类型更加复杂 2. 原则1可以违反，让类型突破到一维线性结构，那必须是单一的可变参数 3. 如果发现原则1被违反，但不违反原则2，只需要做到记忆化搜索即可 4. 可变参数个数，能少则少 常见的4种尝试模型 1. 从左往右的尝试模型 2. 范围上的尝试模型 3. 多样本位置全对应的尝试模型 4. 寻找业务限制的尝试模型 动态规划的进一步优化 1. 空间压缩 2. 状态化简 3. 四边形不等式 4. 其他优化技巧 ### 十一、滑动窗口 #### 滑动窗口 1. 将一个数组利用双端队列从左到右收集从大到小(从小到大)元素索引，比如[1,4,3,7,4,2]。收集完对应索引后应该是[3, 4, 5]([0, 5]) 2. 如果指定窗口的大小，那么左边已经移出的元素的索引位置也需要从双端队列中移出。