Harry Blog

# 前言 最近好多事情，最近前端分享会也如期而至，有幸这次分享会，正好周末有时间，做个总结吧。 这次想分享的就是算法与数据结构，刷了一段时间题目，逛了逛 LeetCode，看了很多关于这个方面的文章，有所感悟，准备做个记录吧。 当你想花时间去了解学习一件对你来说，很苦难的事情的时候，我们需要明确目标，学习它的意义，它有什么用，对你有哪方面帮助。 升职加薪必备，对以后成长有所帮助，嗯，加薪，加薪，加薪。 那么问题来了，为什么要进大厂呢⬇️ 年轻时候去大厂的目标，是为了避免，【你得顿悟，是别人的基本功】 嗯，闲聊就止步于此，接下来开始吧～ 接下来，我们就根据这个脑图来梳理一遍吧～ # 数据结构 数据结构可以说是算法的基石，如果没有扎实的数据结构基础，想要把算法学好甚至融会贯通是非常困难的，而优秀的算法又往往取决于你采用哪种数据结构。学好这个专题也是很有必要的，那么我们可以稍微的做个分类。 常用数据结构 数组，字符串 链表 栈 队列 树 高级数据结构 图 前缀树 线段树 树状数组 主席树 那么显然，最常见的数据结构一定是需要掌握的，对于高级的数据结构而言，如果你有 ...

# 算法 - 并查集 算法 - 并查集 前言 Quick Find Quick Union 加权 Quick Union 路径压缩的加权 Quick Union 比较 # 前言 用于解决动态连通性问题，能动态连接两个点，并且判断两个点是否连通。 方法 描述 UF(int N) 构造一个大小为 N 的并查集 void union(int p, int q) 连接 p 和 q 节点 int find(int p) 查找 p 所在的连通分量编号 boolean connected(int p, int q) 判断 p 和 q 节点是否连通 public abstract class UF { protected int[] id; public UF(int N) { id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; }
...

# 算法 - 排序 # 约定 待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo () 方法，可以用它来判断两个元素的大小关系。 使用辅助函数 less () 和 swap () 来进行比较和交换的操作，使得代码的可读性和可移植性更好。 排序算法的成本模型是比较和交换的次数。 public abstract class Sort<T extends Comparable<T>> { public abstract void sort(T[] nums); protected boolean less(T v, T w) { return v.compareTo(w) < 0; } protected void swap(T[] a, int i, int j) { T t = a[i]; a[i] = a[j]; a[j] = t; } } # 选择排序 从数 ...

# 算法 - 栈和队列 算法 - 栈和队列 栈 1. 数组实现 2. 链表实现 队列 # 栈 public interface MyStack<Item> extends Iterable<Item> { MyStack<Item> push(Item item); Item pop() throws Exception; boolean isEmpty(); int size(); } # 1. 数组实现 public class ArrayStack<Item> implements MyStack<Item> { // 栈元素数组，只能通过转型来创建泛型数组 private Item[] a = (Item[]) new Object[1]; // 元素数量 private int N = 0; @Override public MyStack<Item> push(Item item)
...

# 算法 - 符号表 算法 - 符号表 前言 初级实现 1. 链表实现无序符号表 2. 二分查找实现有序符号表 二叉查找树 1. get() 2. put() 3. 分析 4. floor() 5. rank() 6. min() 7. deleteMin() 8. delete() 9. keys() 10. 分析 2-3 查找树 1. 插入操作 2. 性质 红黑树 1. 左旋转 2. 右旋转 3. 颜色转换 4. 插入 5. 分析 散列表 1. 散列函数 2. 拉链法 3. 线性探测法 小结 1. 符号表算法比较 2. Java 的符号表实现 3. 稀疏向量乘法 # 前言 符号表（Symbol Table）是一种存储键值对的数据结构，可以支持快速查找操作。 符号表分为有序和无序两种，有序符号表主要指支持 min ()、max () 等根据键的大小关系来实现的操作。 有序符号表的键需要实现 Comparable 接口。 public interface UnorderedST<Key, Value> { ...

# 算法 - 算法分析 算法 - 算法分析 数学模型 1. 近似 2. 增长数量级 3. 内循环 4. 成本模型 注意事项 1. 大常数 2. 缓存 3. 对最坏情况下的性能的保证 4. 随机化算法 5. 均摊分析 ThreeSum 1. ThreeSumSlow 2. ThreeSumBinarySearch 3. ThreeSumTwoPointer 倍率实验 # 数学模型 # 1. 近似 N3/6-N2/2+N/3 ~ N3/6。使用～f (N) 来表示所有随着 N 的增大除以 f (N) 的结果趋近于 1 的函数。 # 2. 增长数量级 N3/6-N2/2+N/3 的增长数量级为 O (N3)。增长数量级将算法与它的具体实现隔离开来，一个算法的增长数量级为 O (N3) 与它是否用 Java 实现，是否运行于特定计算机上无关。 # 3. 内循环 执行最频繁的指令决定了程序执行的总时间，把这些指令称为程序的内循环。 # 4. 成本模型 使用成本模型来评估算法，例如数组的访问次数就是一种成本模型。 # 注意事项 # 1. 大常数 在求近似时，如果 ...

# 算法知识总结 本部分主要是笔者在学习算法知识和一些相关面试题所做的笔记，如果出现错误，希望大家指出！ # 目录 常用算法和数据结构总结 排序 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 基数排序 快速排序相对于其他排序效率更高的原因 系统自带排序实现 稳定性 排序面试题目总结 树 二叉树相关性质 满二叉树 完全二叉树 平衡二叉查找树（AVL） B - 树 B 树 数据库索引 红黑树 Huffman 树 二叉查找树 求解二叉树中两个节点的最近公共祖先节点 链表 反转单向链表 动态规划 爬楼梯问题 递归方法分析 备忘录方法 迭代法 经典笔试题 1. js 实现一个函数，完成超过范围的两个大整数相加功能 2. js 如何实现数组扁平化？ 3. js 如何实现数组去重？ 4. 如何求数组的最大值和最小值？ 5. 如何求两个数的最大公约数？ 6. 如何求两个数的最小公倍数？ 7. 实现 IndexOf 方法？ 8. 判断一个字符串是否为回文字符串？ 9. 实现一个累加函数的功能比如 sum (1,2,3)(2).valueOf () 10 ...

# 计算机操作系统 - 概述 # 基本特征 # 1. 并发 并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。 操作系统通过引入进程和线程，使得程序能够并发运行。 # 2. 共享 共享是指系统中的资源可以被多个并发进程共同使用。 有两种共享方式：互斥共享和同时共享。 互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。 # 3. 虚拟 虚拟技术把一个物理实体转换为多个逻辑实体。 主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。 多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。 虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。 # 4. 异步 异步指进程不是一次性执行完毕，而是走走停停，以不可知 ...

# JUC # 进程 # 概述 进程：程序是静止的，进程实体的运行过程就是进程，是系统进行资源分配的基本单位 进程的特征：并发性、异步性、动态性、独立性、结构性 线程：线程是属于进程的，是一个基本的 CPU 执行单元，是程序执行流的最小单元。线程是进程中的一个实体，是系统独立调度的基本单位，线程本身不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源 关系：一个进程可以包含多个线程，这就是多线程，比如看视频是进程，图画、声音、广告等就是多个线程 线程的作用：使多道程序更好的并发执行，提高资源利用率和系统吞吐量，增强操作系统的并发性能 并发并行： 并行：在同一时刻，有多个指令在多个 CPU 上同时执行 并发：在同一时刻，有多个指令在单个 CPU 上交替执行 同步异步： 需要等待结果返回，才能继续运行就是同步 不需要等待结果返回，就能继续运行就是异步 参考视频：https://www.bilibili.com/video/BV16J411h7Rd 笔记的整体结构依据视频编写，并随着学习的深入补充了很多知识 # 对比 线程进程对比 ...

# 一、基础 javascript 篇 # 1. get 请求传参长度的误区 _误区：我们经常说 get 请求参数的大小存在限制，而 post 请求的参数大小是无限制的。 _ 实际上 HTTP 协议从未规定 GET/POST 的请求长度限制是多少。对 get 请求参数的限制是来源与浏览器或 web 服务器，浏览器或 web 服务器限制了 url 的长度。为了明确这个概念，我们必须再次强调下面几点: HTTP 协议 未规定 GET 和 POST 的长度限制 GET 的最大长度显示是因为 浏览器和 web 服务器限制了 URI 的长度 不同的浏览器和 WEB 服务器，限制的最大长度不一样 要支持 IE，则最大长度为 2083byte，若只支持 Chrome，则最大长度 8182byte # 2. 补充 get 和 post 请求在缓存方面的区别 post/get 的请求区别，具体不再赘述。 补充补充一个 get 和 post 在缓存方面的区别： get 请求类似于查找的过程，用户获取数据，可以不用每次都与数据库连接，所以可以使用缓存。 post 不同，post 做的一般是修改和删除的 ...