岁迹

比较器在 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函数​ 一个函数及它的一个变量是由函数自身定义...

数组二分查找二分查找这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。 二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？ 大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。 写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。 12345678910111213141516public class Solution { public int Search(int[] nums,...

1.好名字给定一个字符串，需要找出最长的连续子串（即“好名字”），满足条件： •在这个子串中，每个字符最多出现2次。 •并且最多只能有一个字符出现恰好2次（其他字符只能出现0次或1次）。 换句话说： •子串中所有字符的频率最多为2。 •并且至多有一个字符的频率为2（其他字符频率必须≤1）。 我们需要返回最长这样的子串的长度。 方法：滑动窗口（双指针）思路： 1.使用滑动窗口 [left, right]来代表当前子串。 2.用 freq数组（或哈希表）记录窗口内每个字符的出现次数。 3.维护两个关键计数： •countTwo`：记录当前窗口内出现次数恰好为2的字符的个数（应该最多为1）。 •countOver：记录当前窗口内出现次数超过2的字符的个数（应该为0）。 4.扩展右指针 right，增加字符，更新频率和计数。 5.如果当前窗口违反条件（即 countOver > 0或 countTwo > 1），则收缩左指针 left直到窗口再次合法。 6.在每一步中，如果窗口合法，更新最大长度。 注意： •由于条件要求最多一个字符出现2次，且没有...

动态数组 装箱：装箱是指将值类型转换为引用类型的过程。值类型（如 int、char、struct 等）通常存储在栈上，而引用类型存储在堆上。当进行装箱操作时，会在堆上为值类型创建一个对象实例，并将值类型的值复制到该对象中，最后返回这个对象的引用。 拆箱：拆箱则是将引用类型转换为值类型的过程。它需要先检查引用类型是否为某个特定值类型的装箱实例，然后将堆上对象中存储的值复制到栈上的新值类型变量中。 装箱开销：装箱操作会在堆上分配内存，并且需要复制值类型的值，这会带来一定的性能开销，尤其是在频繁进行装箱操作时，会导致内存分配和垃圾回收的压力增加。 拆箱开销：拆箱操作需要进行类型检查，确保引用类型确实是某个值类型的装箱实例，这也会带来一定的性能开销。 动态数组指的是是大小能在程序运行期间动态调整的数组，可根据实际需求增添或删减元素。与固定大小的数组不同，动态数组能够灵活应对元素数量的变化，从而更高效地管理内存。以下通过自定义的类实现动态数组，使用泛型类，来进行动态数组的实现，这样可以根据数组的类型，实现相应的功能，同时实现IEnumerable接口，可以被foreach循环遍历...

哈希表两数之和 解答一：使用暴力算法 12345678910111213public int[] TwoSum(int[] nums, int target) { int[] arrs = new int[2]; for(int i = 0; i < nums.Length; i++) { for(int j = i + 1; j < nums.Length; j++) { if(nums[i] + nums[j] == target) { arrs[0] = i; arrs[1] = j; return arrs; // 找到后立即返回，提升效率 } } } return arrs;} 解答二：使用字典 12345678910111213141516public class Solution ...

Manacher算法 预处理：统一奇偶长度 回文串有奇数长度（如”aba”）和偶数长度（如”abba”）之分，这会给统一处理带来麻烦。 Manacher算法通过在原始字符串的每个字符之间以及首尾插入一个原字符串中不存在的特殊字符（通常用#）来进行预处理。例如，"abba"会被处理成 "#a#b#b#a#"。 这样做的好处是：无论原字符串如何，新字符串的长度总是奇数，所有回文子串都变成了奇数长度，从而可以统一以每个字符为中心进行扩展检查。 利用回文对称性 算法维护一个回文半径数组 P（也称为辅助数组），P[i]表示以新字符串中第 i个字符为中心的最长回文子串的半径（包含中心字符本身）。例如，对于字符串 "#a#b#a#"，以中间的 b（位于索引4）为中心，其回文半径是4。 关键在于，算法在从左至右遍历字符串时，会动态维护一个当前已知的最右回文边界 R 以及达到该边界的中心位置 C。 当遍历到位置 i时，如果 i在当前最右边界 R之内，则可以找到 i关于中心 C的对称点 j。根据回文的对称性，可以利用 P[j]的值来快速...