Sarf Lab

前几种时间复杂度为O(n * n)的排序 选择排序 12345678910111213141516171819202122232425public static void SeletSort(int[] arr){ if (arrs == null || arrs.Length < 2) return; for(int i = 0; i < arr.Length;i++){ int newIndex = i; for(int j = i+1;j<arr.Length;j++){ newIndex = arr[j] < arr[newIndex] ? j:newIndex; } Swap(arr,i,newIndex); }} public static void Swap(int[] arr, int i, int j) { int temp = arr[j]; arr[j] = a...

迭代归并排序123456789101112131415161718192021222324252627282930313233343536public void Sort(int[] arrs, int L, int R) { int step = 1; int N = arrs.length; while (step < N) { int left = 0; while (left < N) { int mid = left + step - 1; if (mid >= N) break; int right = Math.min(left + 2 * step - 1, N - 1); // 修正右边界计算 Merge(arrs, left, mid, right); // 修正方法调用参数 left = right + 1; &#...

异或：2进制相同为0，不同为1。同时满足交换律和结合律 0 ^ N = N N ^ N = 0 同或：2进制相同为1，不同为0 题一：如何不用额外遍历交换两个数默认情况是使用临时变量来存储一个数，最后交换。在此处我们使用异或运算，依靠异或的下列特点来进行交换。 123456789//默认情况int tmp = a;a = b;b = tmp;//依靠异或,但是条件是，A，B指向的是不同的内存区域a = a ^ b;b = a ^ b;a = a ^ b; 0 ^ N = N N ^ N = 0 题二：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并且打印这种数（LeetCode136）默认情况是使用字典进行存储，将每种数作为键进行存储，值则为出现的次数，最后循环找到奇数次的那种数. 创建一个变量赋值为 0，使用该变量异或遍历每一个数组的值，即可。 1234567891011static void Main(string[] args){ int[] arrs = { 1, 1,2, 2, ...

并查集并查集（Union-Find）是一种用于管理不相交集合（Disjoint Sets）的数据结构，主要支持以下两种高效操作： Find（查找）：查询某个元素所属的集合（通常返回该集合的代表元素）。 Union（合并）：将两个集合合并为一个集合。 此外，并查集通常还支持： 初始化（MakeSet）：为每个元素单独创建一个集合。 判断两个元素是否属于同一集合（isSameSet）。 核心概念 集合的代表（Root / Parent）： 每个集合有一个代表元素（通常称为根节点或父节点）。 所有属于该集合的元素的 Find操作最终都会指向这个代表元素。 路径压缩（Path Compression）： 在 Find操作时，将查询路径上的所有节点直接指向根节点，以优化后续查询效率。 按秩合并（Union by Rank / Size）： 在 Union操作时，将较小的集合合并到较大的集合中，以保持树的平衡，提高效率。 操作 普通实现 路径压缩 + 按秩合并 Find O(n) O(α(n)) (接近常数) Union O(n) ...

复杂度常数操作在算法分析中，”常数操作”（constant-time operation）指的是执行时间不随输入规模变化的操作，其时间复杂度为 O(1)。以下是关于复杂度和常数操作的详细说明： 常数操作的定义 特点：执行时间固定，与输入数据量无关。 示例： 基本算术运算（如 a + b、x * y）。 数组通过索引访问（如 arr[i]）。 指针解引用或赋值（如 p = q）。 简单的比较（如 if (x < y)）。 哈希表的插入、查找（假设哈希冲突极少）。 复杂度分析中的常数操作 大 O记号：忽略常数项和低阶项，但实际编程中常数因子可能影响性能。 例如，两个算法均为 O(n)，但一个的常数操作更少，可能更快。 示例对比： 算法 A：每次循环执行 2 次常数操作 → 2n次操作 → O(n)。 算法 B：每次循环执行 5 次常数操作 → 5n次操作 → 仍为 O(n)，但实际更慢。 选择，冒泡，插入都是O(n * n)的时间复杂度，其中插入排序的最好时间复杂度是O(n)，最差的O(n * n)。 对数器对数器（对数器测试法）是一种用于验证算法正确性的测试方...

比较器在 C# 中，比较器用于定义对象的排序规则。主要有以下几种实现方式： 1. IComparable 接口实现 IComparable 接口可以让对象自身具有比较能力： 1234567891011121314151617public class Person : IComparable<Person>{ public string Name { get; set; } public int Age { get; set; } public int CompareTo(Person other) { if (other == null) return 1; // 先按年龄比较 int ageComparison = Age.CompareTo(other.Age); if (ageComparison != 0) return ageComparison; // 年龄相同再按...

图结构图 = 点 + 边 点结构1234567891011121314public class Node{ public int value; //点值 public int in; //入度 public int out; //出度 public List<Node> nexts; //从该点能找到邻居 public List<Edge> edges; //能找到邻居的边集 public Node(int v){ value = v; in = 0; out = 0; nexts = new List<Node>(); edges = new List<Edge>(); }} 边结构12345678910public class Edge{ public int weight;//权重 public Node from; //那个点出发 public Nod...

暴力递归暴力递归的关键要素一个典型的暴力递归算法包含三个要素： 1.递归终止条件： 定义问题最简单的情况，并直接返回结果。这是递归的出口，没有它会导致无限递归。 2.问题分解： 在每一步，将当前问题分解成一个或多个规模更小的同类型子问题。 3.决策与尝试： 对于当前步骤，做出一个选择（或尝试所有可能的选择），然后基于这个选择递归地解决子问题，并将子问题的结果组合起来形成当前问题的解。 Hanoi塔问题设a,b,c是3个塔座。要求由a移动到b。移动圆盘时遵守以下移动规则规则1:每次只能移动1个圆盘;规则2:任何时刻都不允许较大的圆盘压在较小的圆盘之上:规则3:在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上， 123456789101112131415public class Solution { public void Hanota(IList<int> A, IList<int> B, IList<int> C) { Hanoi(A.Count,A,B,C); } ...

前缀树前缀树（Trie，发音类似 “try”）是一种树形数据结构，用于高效存储和检索字符串集合。它的核心特点是共享公共前缀，适用于自动补全、拼写检查、IP路由等场景。 1. 前缀树的特点 节点结构：每个节点存储一个字符，从根节点到某个节点的路径构成一个字符串。 共享前缀：不同单词的相同前缀会共享同一条路径，节省空间。 快速查找：查找时间复杂度为 O(L)（L 是单词长度），比哈希表更适合前缀匹配。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104public class Node1{ public int pass; public int end; public Node1[] Next;//存...

分治法思想：分+治+分（将一个大规模的问题分成若干块小问题去求解，如果小问题也不好直接解决，则继续分成更小的问题） 分治法： ​ (1)分治法产生的子问题是原问题的较小模式.​ (2)反复应用分治手段，可以使子问题规模不断缩小，​ (3)最终使子问题缩小到很容易直接求出其解。​ (4)将规模较小问题的答案逐级向上合并，可得大问题答案 ​ 分治法解决问题通常使用递归算法​ 直接或间接地调用自身的算法称为递归算法， 例题1：Fibonnacci数列​ 斐波那契数列Q(Fibonacclsequence)，又称“黄金分割”数列，比如这样一个数列:1，1，2，3，5，8，13，21，34，55，89….数列从第3项开始，每一项都等于前两项之和。递归定义为如下： 123456int Fibonacci(int n){ if(n<=1) return 1; else return Fibonacci(n-1) + Fibonacci(n-2);} 例题2：Ackerman函数​ 一个函数及它的一个变量是由函数自身定义...