Hilda

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

023 随机快速排序

经典随机快速排序和用荷兰国旗问题优化后的随机快速排序。经典快排易受重复元素影响，优化后的版本通过荷兰国旗问题将数组划分为小于、等于、大于x三部分，提升效率。文章分析了普通快排和随机快排在不同情况下的时间和空间复杂度，强调随机选择的重要性，并指出随机快排的期望时间复杂度为O(n log n)，空间复杂度为O(log n)。

概览： 前置知识：讲解007-时间复杂度和空间复杂度-分析随机行为的时间复杂度的部分 007笔记 经典随机快速排序流程讲解 荷兰国旗问题优化随机快速排序流程讲解 荷兰国旗问题优化后的过程： 在当前范围上选择一个数字x，利用荷兰国旗问题进行数组的划分，<x =x >x 对<x范围重复这个过程，对>x范围重复这个过程 荷兰国旗问题的优化点：选出一个数字x，数...

Posted by Hilda on March 19, 2025

008 数据结构和算法 简介

左老师将算法分为硬计算（精确求解，复杂度可能高，程序员必备，面试常考）和软计算（逼近求解，时间可控，算法工程师需要）两类。数据结构则宏观地分为连续结构和跳转结构，所有数据结构都是这两者的组合。

概览：（下面的“我”指左老师本人） 说一个我觉得比较有趣、有用的算法分类 硬计算类算法、软计算类算法 注意：这两个名词都不是计算机科学或算法中的标准术语 那为啥要提这个呢？因为很有现实意义。 硬计算类算法：精确求解。但是某些问题使用硬计算类的算法，可能会让计算的复杂度较高 大厂算法和数据结构笔试、面试题、acm比赛或者和acm形式类似的比赛，考察的都是硬计算类算法。 软计算类算...

Posted by Hilda on March 18, 2025

java基础(1) 按值传递

Java 采用按值传递，方法接收的是实参值的副本。基本类型传递值的副本，引用类型传递对象地址的副本。方法内修改对象会影响原始对象，但重新赋值引用不会。可理解为“按引用传递”传递地址副本，但Java始终传递的是值的副本。设计目的是规避C/C++指针的复杂性，利于工程开发。

首先 这篇介绍的是Java中的按值传递和按引用传递。 需要明确的是Java只有按值传递，所谓的“按引用传递”其实传递的是实参引用的对象在堆中的地址。 1 实参和形参 实参（实际参数，Arguments）：用于传递给函数/方法的参数，必须有确定的值。 形参（形式参数，Parameters）：用于定义函数/方法，接收实参，不需要有确定的值。 看一个例子： 1 2 3...

Posted by Hilda on March 18, 2025

007 时间复杂度和空间复杂度

算法分析与设计的关键概念，包括时间/空间复杂度、常数时间操作、均摊分析，以及递归与分治策略。特别强调了不能仅凭代码结构判断时间复杂度，需理解算法本质。覆盖了二进制运算、排序算法、KMP算法等，适合算法初学者。

算法系列： 003~005 二进制和位运算，三傻排序算法，对数器 006 二分搜索 017 二叉树及其三种序的递归实现 019 算法笔试中处理输入和输出 020 递归和master公式 021 归并排序 022 归并分治 041 最大公约数 和 同余原理 100 KMP算法原理和代码详解 概览： 1，常数操作，固定时间的操作，执行时间和数据量无关 2，时间复杂...

Posted by Hilda on March 17, 2025

022 归并分治

归并分治将问题分解为左右子问题及跨越左右的答案。若左右有序能简化跨越部分计算，则适合归并分治。解题时融入归并排序保证左右有序。牛客小和累积和与力扣493翻转对是典型例题，关键在于高效统计跨越左右的答案。归并分治也可用线段树等解决，并能处理更复杂问题。

概览： 原理： 1）思考一个问题在大范围上的答案，是否等于，左部分的答案 + 右部分的答案 + 跨越左右产生的答案 2）计算“跨越左右产生的答案”时，如果加上左、右各自有序这个设定，会不会获得计算的便利性 3）如果以上两点都成立，那么该问题很可能被归并分治解决（话不说满，因为总有很毒的出题人） 4）求解答案的过程中只需要加入归并排序的过程即可，因为要让左、右各自有序，来获得计算...

Posted by Hilda on March 16, 2025

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

FEATURED TAGS
书籍阅读 算法 人工智能AI基础 机器学习-吴恩达 力扣 Java基础 numpy ollama工具 pandas spring6
ABOUT ME

自由 解放

FRIENDS