Hilda

「离开世界之前 一切都是过程」

021 归并排序merge sort

归并排序通过递归或非递归方式，将数组分为有序左右两部分，再利用merge过程整体排序。Merge过程比较左右元素，小的放入辅助数组并拷贝回原数组。时间复杂度O(n log n)，空间复杂度O(n)。 归并排序效率高于O(n^2)排序，因为比较行为不浪费。可用于解决力扣912题，需用静态辅助数组。

概览： 1）左部分排好序、右部分排好序、利用merge过程让左右整体有序 2）merge过程：谁小拷贝谁，直到左右两部分所有的数字耗尽，拷贝回原数组 3）递归实现和非递归实现 4）时间复杂度\(O(n * logn)\) 5）需要辅助数组，所以额外空间复杂度\(O(n)\) 6）归并排序为什么比\(O(n^2)\)的排序快？因为比较行为没有浪费！ 7）利用归并排序的便利性可...

Posted by Hilda on March 16, 2025

020 递归和master公式

递归需画图辅助理解，底层用系统栈实现。任何递归可转非递归，工程上常需避免栈溢出。Master公式适用于子问题规模相同的递归，根据log(b,a)与c关系判断复杂度。特例T(n) = 2*T(n/2) + O(n*logn)复杂度为O(n * (logn)^2)。

1）从思想上理解递归：对于新手来说，递归去画调用图是非常重要的，有利于分析递归 2）从实际上理解递归：递归不是玄学，底层是利用系统栈来实现的 3）任何递归函数都一定可以改成非递归，不用系统帮你压栈（系统栈空间），自己压栈呗（内存空间） 4）递归改成非递归的必要性： ​ a. 工程上几乎一定要改，除非确定数据量再大递归也一定不深，归并排序、快速排序、线段树、很多的平衡树等，后...

Posted by Hilda on March 15, 2025

算法笔试中处理输入与输出

有填函数（框架处理I/O）和ACM风格（需自行处理I/O）两种。ACM推荐使用BufferedReader/PrintWriter等高效I/O类，避免Scanner/System.out。不推荐临时动态空间，优先使用全局静态空间预分配内存。Kattio和FastReader/Writer可处理特殊情况，但StreamTokenizer效率更高。

1）填函数风格 2）acm风格（笔试、比赛最常见） ​ a. 规定数据量(BufferedReader、StreamTokenizer、PrintWriter)，其他语言有对等的写法 ​ b. 按行读(BufferedReader、PrintWriter)，其他语言有对等的写法 ​ c. 不要用Scanner、System.out，IO效率慢 3）不推荐：临时...

Posted by Hilda on March 15, 2025

041 最大公约数 最小公倍数 同余原理

力扣 878: 第 N 个神奇数字，同余原理，这是处理大数运算的重要工具

求最大公约数 1) 欧几里得算法的过程 : 辗转相除法 2) 正确性的证明过程见代码注释部分，润色的证明过程非常好懂，不过直接记忆过程即可 3) 求gcd(a,b)，其中a>b，时间复杂度为O((log a)的3次方)，时间复杂度证明略，这个复杂度足够好了 4) 简单转化就可以求最小公倍数 5) 更高效求最大公约数的Stein算法、由最大公约数扩展出的“裴蜀定理”，比赛同学有兴趣...

Posted by Hilda on March 14, 2025

017 二叉树及其三种序的递归实现

二叉树及其三种序(先中后)的递归实现

二叉树及其三种序的递归实现 1）二叉树的节点 2）二叉树的先序、中序、后序 3）递归序加工出三种序的遍历 4）时间复杂度O(n)，额外空间复杂度O(h)，h是二叉树的高度 1 什么是二叉树的先序、中序、后序遍历 这个概念比较简单 参考帖子 2 代码:二叉树的先序、中序、后序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...

Posted by Hilda on March 14, 2025

摩尔投票算法 力扣169，229，1150，2404

力扣169，229，1150，2404

下面2道已经做过，记录1150和2404两道题，这4道题都是和摩尔投票算法相关的。 169 169解法 229 229解法 1150. 检查一个数是否在数组中占绝大多数 1150. 检查一个数是否在数组中占绝大多数 1 2 3 4 5 6 7 8 9 class Solution { public boolean isMajorityElement(int[] nu...

Posted by Hilda on March 13, 2025

三段逆置 力扣189 轮转数组

力扣189 轮转数组

189. 轮转数组 189. 轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1: 1 2 3 4 5 6 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] ...

Posted by Hilda on March 13, 2025

力扣 88. 合并两个有序数组

88. 合并两个有序数组

88. 合并两个有序数组 88. 合并两个有序数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { if (n == 0) return; ...

Posted by Hilda on March 12, 2025

力扣 27. 移除元素 26. 删除有序数组中的重复项 80. 删除有序数组中的重复项 II

3道题：27. 移除元素 26. 删除有序数组中的重复项 80. 删除有序数组中的重复项 II

27. 移除元素 27. 移除元素 1 2 3 4 5 6 7 8 9 10 11 class Solution { public int removeElement(int[] nums, int val) { int k = 0; for (int i = 0; i < nums.length; i++) { ...

Posted by Hilda on March 12, 2025

力扣 229. 多数元素 II(摩尔投票算法)

229. 多数元素 II

229. 多数元素 II 229. 多数元素 II 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 示例 1： 1 2 输入：nums = [3,2,3] 输出：[3] 示例 2： 1 2 输入：nums = [1] 输出：[1] 示例 3： 1 2 输入：nums = [1,2] 输出：[1,2] 提示： 1 <=...

Posted by Hilda on March 12, 2025

FEATURED TAGS
书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib AI思想启蒙 spring6 算法题库 Java基础 java集合 ollama工具 python爬虫
ABOUT ME

自由 解放

FRIENDS