103-【八股】数据结构与算法

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

八股

哈希表

实现原理：

哈希函数的作用是将给定的键转换为一个数组的索引。哈希函数接收一个输入并输出一个整数，这个整数在哈希表中对应的索引位置。

哈希函数的设计要确保以下几点：

  • 均匀分布：哈希函数应当能够将输入均匀地映射到表中的各个桶位置，减少碰撞的概率。
  • 低冲突：哈希函数应尽量减少不同的键映射到同一个位置（即哈希冲突）。

冲突解决方式：

  1. 链接法：每个桶是一个链表，发生冲突就在该位置尾插冲突元素。
  2. 开放地址法：开放地址法是一种将所有元素直接存储在哈希表数组中的方法，不使用链表来处理冲突。当发生冲突时，系统会查找哈希表中的下一个空桶位置，并将元素插入到该位置。常见的开放地址法有以下几种：
    • 线性探测（Linear Probing）：当发生冲突时，检查当前位置的下一个位置，直到找到空位置为止。
    • 二次探测（Quadratic Probing）：探测时按照二次方规律进行，即 i=(h+f(i))mod  TableSizei = (h + f(i)) TableSizei=(h+f(i))modTableSize，其中 f(i)f(i)f(i) 是一个平方数序列。
    • 双重哈希（Double Hashing）：使用第二个哈希函数来决定下一个探测位置。

堆和栈

栈是一种 先进后出数据结构，通常用于存储局部变量和函数调用信息（如函数的参数、返回地址等）。栈由操作系统管理，程序的执行栈在函数调用时不断压入和弹出。

堆是一块由程序员显式管理的内存区域，用于存储动态分配的内存。程序员通过 new（C++）或 malloc（C）等函数申请内存，并在使用完毕后，通过 delete（C++）或 free（C）手动释放这部分内存。

特性栈（Stack）堆（Heap）
内存分配方式自动分配和回收，遵循先进后出（LIFO）规则动态分配，由程序员手动管理
内存大小内存有限，通常较小（几 MB）内存较大，通常受限于操作系统的总内存大小
生命周期随着函数调用的开始和结束自动管理由程序员控制，直到显式释放
分配和回收速度快，栈指针的移动慢，涉及内存查找和分配
存储内容存储局部变量、函数参数、返回地址等存储动态分配的对象（如 new 或 malloc 创建的）
内存溢出栈溢出（stack overflow），当栈的空间用完时堆溢出（heap overflow），当堆空间不足时
内存管理方式由操作系统自动管理需要手动管理，程序员负责内存的分配和释放
内存的访问模式由操作系统管理，分配紧凑且连续（低碎片化）内存是分散的，可能会导致碎片化

算法题

链表

  1. 约瑟夫环问题的三种解法讲解 - 力扣（LeetCode）：环形链表模拟，有序集合模拟，数学归纳推导

二叉树

  1. 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
  2. 106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
  3. 889. 根据前序和后序遍历构造二叉树 - 力扣（LeetCode）

哈希

  1. 594. 最长和谐子序列 - 力扣（LeetCode）

二分查找

  1. 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
  2. 【不用库函数求】69. x 的平方根 - 力扣（LeetCode）：也能用牛顿迭代

分治法

  1. 12.4 汉诺塔问题 - Hello 算法 (hello-algo.com)

智力题

  1. 将一根木棍分成三段，求这三段构成三角形的概率