LeetCode面试题记录：掌握空间复杂度计算

### 知识点一：空间复杂度计算 在算法分析中，空间复杂度是一个描述算法在运行过程中临时占用存储空间大小的度量。对于给定的问题，空间复杂度越低，意味着算法在执行时占用的内存空间越少，效率越高。在LeetCode这类在线编程平台上，计算空间复杂度是面试准备中的一个基础而重要的环节。 空间复杂度通常用大O符号表述，如O(1)、O(n)、O(n²)等，分别表示常数空间复杂度、线性空间复杂度和二次方空间复杂度。在实际计算中，需要考虑如下几个方面： - **变量声明所占空间**：基础数据类型变量所占空间相对固定。 - **数组或对象**：动态分配的空间，其大小与输入数据规模n成正比。 - **递归调用栈空间**：递归函数每次调用都会在调用栈上增加一层，可能产生额外的空间开销。 - **临时变量**：在算法中使用的临时变量，如果其生命周期覆盖整个算法过程，也应计入空间复杂度。 在LeetCode面试中，面试官可能会要求应聘者对某些算法或代码段进行空间复杂度的分析。 ### 知识点二：Python基础知识点 1. **装饰器（AOP/面向切面编程）**： 装饰器是Python中一个非常实用的功能，它允许用户在不修改函数或类定义的情况下，增加额外的功能。面向切面编程（AOP）是一种编程范式，它允许分离横切关注点，即将分散在多个组件中的相同行为集中处理。 2. **Python代码执行原理**： Python代码在执行前需要编译成字节码，然后由Python虚拟机执行。这个过程涉及到编译器、解释器和虚拟机的知识。 3. **Python的int实现**： Python中的整数是动态大小的，可以根据需要扩展其大小。Python 3中的整数已经完全支持大数，没有了Python 2中的int和long的区别。 4. **is和==的区别**： `is`用于判断两个变量是否引用自同一个对象；`==`用于判断两个变量的值是否相等。前者是判断引用（内存地址），后者是判断值。 5. **深拷贝与浅拷贝**： 深拷贝会递归复制对象中的所有元素，而浅拷贝只会复制对象引用的第一层。在Python中，`copy`模块提供了深拷贝(`deepcopy`)和浅拷贝(`copy`)的功能。 6. **read, readline 和 readlines**： 这三个函数都与文件读取相关。`read(size)`读取文件中最多`size`个字符，`readline()`读取一行，`readlines()`读取所有行并返回一个列表。 7. **Python2.7与Python3.x的区别**： Python 3是Python语言的未来，其与Python 2.x系列存在许多不兼容的改动。例如，打印语句变为函数，字符串和字节串有了明确区分等。 8. **Python自省**： 自省是Python的一种能力，允许程序在运行期间检查对象的类型，属性等。Python的内置函数`type()`, `dir()`, `getattr()`, `hasattr()`等都支持自省。 9. **Python中的下划线**： 在Python中，下划线（_）有不同的用途，它可以表示某个变量为临时变量，也可以在模块导入时作为特殊变量使用。 10. **Python字符串格式化**： Python中常用的字符串格式化有`%`格式化、`format()`方法以及Python 3.6引入的f-string。 ### 知识点三：面向对象编程 1. **all的作用**： `all()`是一个内置函数，用于判断给定的可迭代对象中的所有元素是否都为真。如果所有元素都为真，返回True；否则返回False。 2. **装饰器作用**： 装饰器除了在函数编程中的应用，也可以用于面向对象编程，提高代码复用性和可读性。 3. **面向对象的三大特性**： 封装、继承和多态是面向对象编程的核心概念。封装隐藏了对象的内部细节，继承实现了代码的复用，多态允许使用通用的接口操作不同的对象。 ### 知识点四：多线程 多线程编程是指在一个程序中执行多个线程，这些线程可以并发执行。Python的多线程由于全局解释器锁（GIL）的存在，并不能利用多核处理器的优势，适合I/O密集型任务。 ### 知识点五：Pandas加速 Pandas是Python中一个强大的数据分析和处理库。提高Pandas运行速度的方法有多种，比如使用更高效的数据类型，减少数据复制，利用向量化操作等。 ### 知识点六：Java基础知识点 1. **容器**： Java中的容器指的是集合框架，如List、Set、Map等接口及其实现类。 2. **并发**： 并发是Java编程中处理多任务执行的一种机制，Java通过synchronized关键字、Lock接口和并发包（java.util.concurrent）来提供并发编程的支持。 ### 知识点七：计算机网络基础 1. **网络分层体系结构**： 计算机网络的分层体系结构如OSI七层模型或TCP/IP五层模型，每一层都有其特定的功能。 2. **HTTP从发起到接受的过程**： HTTP请求包含建立连接、客户端请求、服务器响应和关闭连接四个阶段。 3. **计算机网络分层**： 计算机网络通常分为应用层、传输层、网络层、数据链路层和物理层。 4. **TCP/UDP**： TCP（传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层通信协议，而UDP（用户数据报协议）则是一种无连接的、尽最大努力交付的协议。 5. **TCP和UDP的区别**： TCP提供可靠的面向连接服务，UDP提供简单的无连接通信。 6. **TCP如何保证可靠传输**： 通过序列号、确认应答、重发控制、连接管理以及流量控制等机制实现。 7. **三次握手和四次挥手**： 三次握手是指TCP建立连接的过程，四次挥手是指TCP断开连接的过程。三次握手是为了确保双方都有接收和发送能力，四次挥手是为了确保所有数据都传输完毕。 8. **为何三次握手，2次不行吗**： 两次握手无法保证双方的发送和接收能力均正常。 9. **为什么要传回SYN**： 在三次握手中，第二次握手时传回SYN是为了同步双方的初始序列号。 10. **为何客户端最后还要等待2MSL**： MSL是报文最大生存时间，等待2MSL是为了确保服务器端收到最后一个ACK，保证TCP连接的正确关闭。 掌握上述知识点对于IT专业人员尤其是应聘者在面试中面对技术问题时非常有帮助，能够在面试过程中展示出对计算机科学基础知识的熟练掌握和应用能力。