哈希表

在C++中称为：UnOrderedMap/UnSortedMap/Set :::info Map: key-value
Set：only Key
key是唯一的，也只对应一个value值；remove此key时，对应的value也会删除；可以按照key查找；
若是只有key没有value，是set；要是有key又有对应的value，则是map

  • 放入hash表的东西，若是基础类型，内部是按照值传递的，内存占据的是该类型的大小
  • 若是非基础类型（自定义的类），内部是按照引用传递的，内存是占用此类型的指针（地址）的大小 :::

:::tips Hash表认为增删改查一直是常数时间的！ :::

有序表

:::info C++中称为OrderedSet或者OrderedMap
有序表会把Key按照顺序组织起来，但是Hash表不会
放入OrderedMap的东西，若是非基础类型，需要提供比较器！ :::

链表

  1. //单链表
  2. Class Node{
  3.     public:
  4.     T value;
  5.     Node* next;
  6. }
  7. //双链表
  8. Class DNode{
  9.     public:
  10.         T value;
  11.     DNode* pre;
  12.     Dnode* suc;
  13. }
  • 笔试时，不用太过在乎空间复杂度，一切为了时间复杂度
  • 面试时，时间复杂度仍是放在第一位，但是空间复杂度需要考虑最省的方法

额外重要的技巧

  • 额外的数据结构记录（哈希表）
  • 快慢指针
  • 递归

快慢指针

判断一个链表是否为回文

:::info 回文结构是什么？
1->2->3->2->1
1->20->20->1 ::: 笔试中？
依次放到栈里，放完后直接弹出，并且从头开始遍历；
or只放如一半；
不使用额外空间：快慢指针
快指针一次走2步，慢指针一次走1步，快指针走的时候改变链表的指向，
image.png

单链表的倒数第 k 个节点

从前往后寻找单链表的第 k 个节点很简单，一个 for 循环遍历过去就找到了，但是如何寻找从后往前数的第 k 个节点呢？
那你可能说，假设链表有 n 个节点，倒数第 k 个节点就是正数第 n - k 个节点，不也是一个 for 循环的事儿吗？
是的，但是算法题一般只给你一个 ListNode 头结点代表一条单链表，你不能直接得出这条链表的长度 n，而需要先遍历一遍链表算出 n 的值，然后再遍历链表计算第 n - k 个节点。
也就是说，这个解法需要遍历两次链表才能得到出倒数第 k 个节点。 :::info 解法是先用一个指针先出发，走k步，然后此时将一个新的指针指向头节点，这样两个指针同时出发，当之前的指针走到末尾时，后出发的指针即走到了n-k个节点！ :::

summary

:::info

  • 快慢指针
  • 一个指针先出发一个指针后出发
  • 快慢指针中，快指针的步数最后总还是慢指针的2倍；记住这个关系 :::

合并链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
合并链表

  1. class Solution {
  2. public:
  3.     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
  4.         ListNode* head=new ListNode(-1);
  5.         ListNode* p=head;
  6.         while(list1!=nullptr&&list2!=nullptr){
  7.             if(list1->val>list2->val){
  8.                 p->next=list2;
  9.                 p=p->next;
  10.                 list2=list2->next;
  11.             }else{
  12.                 p->next=list1;
  13.                 p=p->next;
  14.                 list1=list1->next;
  15.             }
  16.         }
  17.         if(list1!=nullptr){
  18.             p->next=list1;
  19.         }
  20.         if(list2!=nullptr){
  21.             p->next=list2;
  22.         }
  23.         return head->next;
  25.     }
  26. };

:::info 思路是比较简单的，类似归并排序中merge ::: :::tips 代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。你可以试试，如果不使用 dummy 虚拟节点，代码会复杂很多，而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。 :::

链表的递归

链表是有一定的递归性的，递归有时候可能并不会节省空间，但是很帅。
具体参考labuladong :::info 递归的注意点在于，有时候在思考的时候不要跳入递归中，因为压栈的操作自己想着想着可能就晕了，而是把递归后的结果弄清楚，每次递归完前一级返回的是什么样的； :::