ToB企服应用市场:ToB评测及商务社交产业平台

标题: Day6 25/2/19 WED [打印本页]
作者: 杀鸡焉用牛刀    时间: 2025-2-20 14:52
标题: Day6 25/2/19 WED
【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据布局底子到高级百口桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358
目录
4、表
4.1 按存储布局划分
4.1.1 哈希表
4.1.1.1 函数调用
4.1.1.2 增删改查操作
4.1.2 单链表 & 双链表​
4.1.2.1 练习题
4.1.2.2 面试时的方法论
4.2 按元素数值大小划分
4.2.1 有序表

条记：
4、表

哈希表和链表的区别：
哈希表是根据关键码值（Key Value）而直接进行访问的数据布局。它通过把关键码值映射到哈希表中的一个位置来访问记录，以加速查找的速度。
链表是一种物理存储单元上非连续、非序次的存储布局，数据元素的逻辑序次是通过链表中的指针链接序次实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态天生。
4.1 按存储布局划分

4.1.1 哈希表

4.1.1.1 函数调用

如果只有key没有value，在java中可以使用HashSet布局。
如果既有key也有value，在java中可以使用HashMap布局。
有无value数据就是set和map的唯一区别。
4.1.1.2 增删改查操作

哈希表增删改查操作的时间复杂度都是常数级别的，但这个常数时间一样平常较长。
map中的put()方法既是插入操作，也是更新操作，比如：
  1. HashMap<Integer, String> testMap = new HashMap();
  3. testMap.put(1, “abc”);
  5. testMap.put(1, “ghj”);
  7. System.out.print(testMap.get(1)); //会打印出ghj，而非abc。
复制代码
map插入/更新操作：map名.put(键名, 值);
map查询键是否存在的操作：map名.contsinKey(键名); //在则表现true
map查询某个键是否存在值的操作：map名.get(键名); //在则表现值，不在则返回null
map移除操作：map名.remove(键名);

set插入/更新操作：set名.add(键名);
set查询是否存在的操作：set名.contians(键名); //在则表现true
set移除操作：set名.remove(键名);
哈希表中，如果key的类型不是底子类型，是自己界说的Node等类型，存储到key中的就是内存地址；如果key是底子类型，存储的就是值而非地址。
4.1.2 单链表 & 双链表



  

4.1.2.1 练习题

分别实现反转单向链表、反转双向链表。要求链表长度为N，时间复杂度O(N)，额外空间复杂度O(1)。
反转单向链表：
  1. struct  Node
  2. {
  3.         int value;
  4.         Node *next;
  5.         Node(int data){
  6.                 value = data;
  7.         }
  8. };
  11. static Node *reverseList(Node *head){
  12.         Node *pre = nullptr;
  13.         Node *next = nullptr;
  14.         while (head != nullptr)
  15.         {
  16.                 next = head->next;
  17.                 head->next = pre;
  18.                 pre = head;
  19.                 head = next;
  20.         }
  21.         return pre;
  22. }
复制代码

反转双向链表：
  1. struct DoubleNode{
  2.         int value;
  3.         DoubleNode *last;
  4.         DoubleNode *next;
  5.         DoubleNode(int data){
  6.                 value = data;
  7.         }
  8. };
  11. static DoubleNode *reverseDoubleList(DoubleNode *head){
  12.         DoubleNode *pre = nullptr;
  13.         DoubleNode *next = nullptr;
  14.         while (head != nullptr)
  15.         {
  16.                 next = head->next;
  17.                 head->next = pre;
  18.                 head->last = next;
  19.                 pre = head;
  20.                 head = next;
  21.         }
  22.         return pre;
  23. }
复制代码

4.1.2.2 面试时的方法论

所有链表题在做的时候，一律贯彻笔试和面试区别对待的方式。
（1）对于笔试，不用太在乎时间复杂度，一切为了时间复杂度。
（2）对于面试，时间复杂度仍紧张，但也要找到空间最省的方法。
（3）紧张本领：额外数据布局记录（哈希表）、快慢指针

例题平凡版：判断一个链表是否为回文布局。
笔试的做法：创建一个栈，遍历链表的时候把元素依次放进去。然后再遍历一遍链表，边遍历边弹栈，比力二者是否一样。（栈弹出的序次是先辈后出，也就是链表的逆序）
另一个做法：只把后一半链表压入栈，边遍历前一半链表边弹栈比力二者是否相同，如许空间使用从N变为了N/2。用“快慢指针”可以实现，慢指针s一次走一格，快指针f一次走两格，当快指针遍历到链表末尾的时候，慢指针正好抵达链表中央。把从慢指针指向的元素到链表末尾都压入栈。
补充，快慢指针这块需要根据题目要求去修改详细的代码。当链表为偶数时，慢指针有可能指向中线的左侧或右侧，这是界限问题，需要按题目需求去详细分析快慢指针哪个先走。

例题进阶版：要求时间复杂度O(N)，额外空间复杂度O(1)。
快慢指针中的慢指针遍历到中点的时候，慢指针边以后便利边把元素指向改为指向中点。改完后再用两个指针分别从两端往中央遍历，边遍历边比力，遍历到中点指向的null之后制止。

最后再把链表的指向改归去。

这个方法无实际作用，只是面试时纯粹为了考验编程能力。

4.2 按元素数值大小划分

4.2.1 有序表

如果只有key没有value，java中可用TreeSet布局。
如果既有key也有value，java中可用TreeMap布局。
有序表和哈希表的区别是：哈希表的key是无序的，有序表的key是有序的。
有序表中，如果key的类型不是底子类型，是自己界说的Node等类型，存储到key中的就是内存地址，而且必须设置个比力器来告诉程序如何比力非底子类型；如果key是底子类型，存储的就是值而非地址。
有序表的时间复杂度是O(logN)。

   

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4