-
Hash
哈希表 1.哈希表定义 哈希表就是一个根据关键码的值而直接进行访问的数据结构。一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个数字是否在这个集合里面。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。我们只需要初始化把这数字都存在哈希表里，在查询的时候通过索引直接就可以知道某个数字在不在这所学校里了。将一个元素映射到哈希表上就涉及到了hash function ，也就是哈希函数。 这就是一个哈希函数，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值。如果hashCode得到的数值大于哈希表的大小了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了元素一定可以映射到哈希表上了。此时。如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。这就导致了哈希冲突。 我如何对a和e进行安排呢，这里有两种方法，一种是线性探测，就是一个一个问后面是否有空格，找到一个空的位置就把e塞进去就好了： 还有一种叫拉链法，就是变成一个链表： 除此之外还有二次探测，双哈希等等方法，这个在这里不是重点。 当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构：数组、set、map。 在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示： set 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率 std::set 红黑树 有序 否 否 O(log n) O(log n) std::multiset 红黑树 有序 是 否 O(logn) O(logn) std::unordered_set 哈希表 无序 否 否 O(1) O(1) map 底层实现 是否有序 数值是否可以重复...
-
List
链表 1.如何构造一个链表？ 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null。链表的入口节点称为链表的头结点也就是head。 struct ListNode { int val; // 节点上存储的元素 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数 }; int main(){ ListNode *head = new ListNode(1); // 创建头节点 ListNode *second = new ListNode(2); // 创建第二个节点 ListNode *third = new ListNode(3); // 创建第三个节点 head->next = second; //...
-
Array
数组 数组是存放在连续内存空间上的相同类型数据的集合。可以方便的通过下标索引的方式获取到下标对应的数据。而且值得注意的是，数组的元素不可删除，只可以覆盖。 对于数组类题目我们有如下的做题技巧： 1.二分法 例题：输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4。 最需要注意的是闭区间还是左闭右开区间，这时候判断条件会发生变化。 #include<iostream> #include<vector> using namespace std; //以闭区间为例 int search(vector<int>& v,int target){ int left=0; int right=v.size()-1; while(left<=right){ int mid=left+(right-left)/2; if(v[mid]<target){ left=mid+1; }else if(v[mid]==target){ return mid; }else{ right=mid-1; } } return -1; } int main(){ vector<int> v{-1,0,3,5,9,12}; int target=9;...