刷题记

简介 记录刷题过程中遇到问题及新知识

System.Collections

ArrayList

在C#中，数组由于是固定长度的，由于这种限制不方便，所以出现了ArrayList
ArrayList是可变长数组，可以将任意多的数据Add到ArrayList里面。其内部维护的数组，当长度不足时，会自动扩容为原来的两倍。
但是ArrayList也有一个缺点，就是存入ArrayList里面的数据都是Object类型的，所以如果将值类型存入和取出的时候会发生装箱、拆箱操作(就是值类型与引用类型之间的转换)，这个会影响程序性能。在.Net 2.0泛型出现以后，就提供了List。

List

List是ArrayList的泛型版本，它不再需要装箱拆箱，直接取，直接用，它基本与ArrayList一致，不过在使用的时候要先设置好它的类型，而设置好类型之后，不是这种类型的数据，是不允许Add进去的
就性能来说，如果要存进数组的只有一种数据，那么无疑List是最优选择
List存储的数据是有序并且可以重复的。 采用链表存储数据

List<int> ListInt = new List<int>();
// 属性
Count
// 方法
Add(T)
AddRange(IEnumerable<T>)
Clear()
Contains(T)
Find(Predicate<T>) //搜索与指定谓词所定义的条件相匹配的元素，并返回整个 List<T> 中的第一个匹配元素
FindAll(Predicate<T>) //检索与指定谓词定义的条件匹配的所有元素 返回List<>
IndexOf(T)	//搜索指定的对象，并返回整个 List<T> 中第一个匹配项的从零开始的索引
LastIndexOf(T)	//搜索指定对象并返回整个 List<T> 中最后一个匹配项的从零开始索引
IndexOf(T, Int32)	//搜索指定对象并返回 List<T> 中从指定索引到最后一个元素这部分元素中第一个匹配项的从零开始索引
IndexOf(T, Int32, Int32)	//搜索指定对象并返回 List<T> 中从指定索引开始并包含指定元素数的这部分元素中第一个匹配项的从零开始索引
Insert(Int32, T)	//将元素插入到 List<T> 中的指定索引处
Remove(T) //从 List<T> 中删除特定对象的第一个匹配项
Reverse()	//将整个 List<T> 中元素的顺序反转
Reverse(Int32, Int32)	//将指定范围中元素的顺序反转
Sort()	//使用默认比较器对整个 List<T> 中的元素进行排序
ToArray()	//将 List<T> 的元素复制到新数组中

HashTable

HashTable是一种根据key查找非常快的键值数据结构，不能有重复key，而且由于其特点，其长度总是一个素数，所以扩容后容量会比2倍大一点点，加载因子为0.72f。
当要大量使用key来查找value的时候，HashTable无疑是最有选择，HashTable与ArrayList一样，是非泛型的，value存进去是object,存取会发生装箱、拆箱，所以出现了Dictionary<T,T>

// 属性
Count //获取包含在 Hashtable 中的键/值对的数目
Keys
Values

// 方法
Add(Object, Object)
Clear()
Clone()
Contains(Object)
ContainsKey(Object)
ContainsValue(Object)
GetHash(Object)	//返回指定键的哈希代码
Remove(Object)

Dictionary<T,T>

Dictionary<T,T>是HashTable的泛型版本，存取同样快，但是不需要装箱和拆箱了。而且，其优化了算法，Hashtable是0.72，它的浪费容量少了很多

Dictionary<string,Person> Dic = new Dictionary<string,Person>();

HashSet

HashSet类，算法，存储结构都与哈希表相同，主要是设计用来做高性能集运算的，例如对两个集合求交集、并集、差集等。集合中包含一组不重复出现且无特定顺序的元素
HashSet存储的数据是无序并且唯一的，底层使用HashMap存储数据
Add(T) 方法返回值为如果该元素添加到 HashSet 对象中则为 true；如果该元素已存在则为 false

HashSet<int> numbers1;
HashSet<int> numbers2;
//分别进行numbers1和numbers2的值初始化或赋值
numbers1.UnionWith(numbers2);//求两个集合的并集。
numbers1.IntersectWith(numbers2);//求两个集合的交集。
numbers1.ExceptWith(numbers2);//求两个集合的差集。
numbers1.SymmetricExceptWith(numbers2);//求两个集合的对称差集。
// 属性
Count //获取集中包含的元素数
Comparer //获取用于确定集中的值是否相等的 IEqualityComparer<T> 对象
// 方法
Add() //将项目添加到HashSet之中
Clear() //清空HashSet里面的值
Remove() //从HashSet中移除值
Contains() //判断HashSet是否包含指定项目
Equals(Object) //判断是否相等

Queue、Queue

Queue队列，Queue泛型队列，队列，先进先出

// 属性
Count
// 方法
Clear()
Contains(T)
Dequeue()	//移除并返回位于 Queue<T> 开始处的对象
Enqueue(T)	//将一个对象添加到 Queue<T> 的末尾
Peek()	//返回位于 Queue<T> 开始处的对象但不将其移除

Stack、Stack

Stack堆栈，先进后出

// 属性
Count
// 方法
Clear()
Contains(T)
Pop()	//删除并返回 Stack<T> 顶部的对象
Push(T)	//在 Stack<T> 的顶部插入一个对象
Peek()	//返回位于 Stack<T> 顶部的对象但不将其移除
TryPop(T)	//返回一个值，该值指示 Stack<T> 的顶部是否有对象；如果有，则将其复制到 result 参数，并从 Stack<T> 中删除它

SortedList、SortedList<TKey,TValue>

SortedList集合中的数据是有序的。可以通过key来匹配数据，也可以通过int下标来获取数据
添加操作比ArrayList，Hashtable略慢；查找、删除操作比ArrayList快，比Hashtable慢

SortedDictionary<TKey,TValue>

SortedDictionary<TKey,TValue>相比于SortedList<TKey,TValue>其性能优化了，SortedList<TKey,TValue>其内部维护的是数组而SortedDictionary<TKey,TValue>内部维护的是红黑树(平衡二叉树)的一种，因此其占用的内存，性能都好于SortedDictionary<TKey,TValue>。唯一差在不能用下标取值

ListDictionary(单向链表),LinkedList(双向链表)

List,ArrayList,Hashtable等容器类，其内部维护的是数组Array来，ListDictionary和LinkedList不用Array，而是用链表的形式来保存。链表最大的好处就是节约内存空间
ListDictionary是单向链表
LinkedList双向链表。双向链表的优势，可以插入到任意位置

HybridDictionary

HybridDictionary的类，充分利用了Hashtable查询效率高和ListDictionary占用内存空间少的优点，内置了Hashtable和ListDictionary两个容器，添加数据时内部逻辑如下:
当数据量小于8时，Hashtable为null，用ListDictionary保存数据
当数据量大于8时，实例化Hashtable，数据转移到Hashtable中，然后将ListDictionary置为null

BitArray

BitArray用于二进制运算，”或”、”非”、”与”、”异或非”等这种操作，只能存true或false

字符串动态匹配算法

BF算法
RK算法
BM算法
KPM算法
Sunday算法

动态规划

可理解为数列求通项过程
f(n) = f(n - 1) + f(n - 2)

逻辑运算符短路效应

if(A && B)  // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false

if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true