设计模式之美—适配器模式本文将对责任链模式(职责链模式)分为四个部分进行讲解
原理
实现
应用
练习
让大家系统全面的学会使用责任链模式, 并应用到开发中去
原理篇
一般来说,适配器模式可以看作一种“补偿模式”,用来补救设计上的缺陷。
适配器模式的英文翻译是 Adapter Design Pattern, 在GoF的设计模式中的定义如下
Avoid coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it.
“将请求的发送和接收解耦,让多个接收对象都有机会处理这个请求。将这些接收对象串成一条链,并沿着这条链传递这个请求,直到链上的某个接收对象能够处理它为止。”
实际上就是将请求通过类似链表的结构, 通过结点处理并线性的传递下 ...
Java源码
未读HashMap 源码解析Hey 大家好,我是 Shio👋。今天我们将深入探讨 Java 的HashMap源码, HashMap 是Java提供的存放键值对的容器, 其最大的特点是大多情况下可以通过O(1)的时间复杂度通过键来获取值
其底层是由数组 + 链表的组成的,链表主要是用拉链法解决Hash冲突 , 在JDK1.8之后引入了树化机制 ,在达到一定条件后,会将链表转化为红黑树。
扰动函数HashMap通过调用键的hashCode()方法获取hash值,然后通过扰动函数,使hash值在最后和数组长度取余((n - 1) & hash)后分布的更为均匀
扰动函数就是为了防止一些实现比较差的hashCode(), 使得使用扰动函数后, 减少哈希碰撞的概率。
static final int hash(Object key) { int h; // key.hashCode():返回散列值也就是hashcode // ^:按位异或 // >>>:无符号右移,忽略符号位,空位都以0补齐 return (key == nul ...
算法笔试「骗分」套路首先回答一个问题,刷力扣题是直接在网页上刷比较好还是在本地 IDE 上刷比较好?
如果是牛客网笔试那种自己处理输入输出的判题形式,一定要在 IDE 上写,这个没啥说的,但像力扣这种判题形式,我个人偏好直接在网页上刷,原因有二:
1、方便
因为力扣有的数据结构是自定的,比如说 TreeNode,ListNode 这种,在本地你还得把这个类 copy 过去。
而且在 IDE 上没办法测试,写完代码之后还得粘贴到网页上跑测试数据,那还不如直接网页上写呢。
算法又不是工程代码,量都比较小,IDE 的自动补全带来的收益基本可以忽略不计。
2、实用
到时候面试的时候,面试官给你出的算法题大都是希望你直接在网页上完成的,最好是边写边讲你的思路。
如果平时练习的时候就习惯没有 IDE 的自动补全,习惯手写代码大脑编译,到时候面试的时候写代码就能更快更从容。
之前我面快手的时候,有个面试官让我 实现 LRU 算法,我直接把双链表的实现、哈希链表的实现,在网页上全写出来了,而且一次无 bug 跑通,可以看到面试官惊讶的表情😂
我秋招能当 offer 收割机,很大程度上就是因为手写算法 ...
一个方法团灭 nSum 问题读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode
力扣
难度
1. Two Sumopen in new window
1. 两数之和open in new window
🟢
15. 3Sumopen in new window
15. 三数之和open in new window
🟠
167. Two Sum II - Input Array Is Sortedopen in new window
167. 两数之和 II - 输入有序数组open in new window
🟠
18. 4Sumopen in new window
18. 四数之和open in new window
🟠
-
剑指 Offer II 007. 数组中和为 0 的三个数open in new window
🟠
经常刷力扣的读者肯定知道鼎鼎有名的 twoSum 问题,不过除了 twoSum 问题,力扣上面还有 3Sum,4Sum 问题,以后如果想出个 5Sum,6Sum 也不是不可以。
总结来说,这类 nSu ...
算法时空复杂度分析实用指南我以前的文章主要都是讲解算法的原理和解题的思维,对时间复杂度和空间复杂度的分析经常一笔带过,主要是基于以下两个原因:
1、对于偏小白的读者,我希望你集中精力理解算法原理。如果加入太多偏数学的内容,很容易把人劝退。
2、正确理解常用算法底层原理,是进行复杂度的分析的前提。尤其是递归相关的算法,只有你从树的角度进行思考和分析,才能正确分析其复杂度。
鉴于现在历史文章已经涵盖了所有常见算法的核心原理,所以我专门写一篇时空复杂度的分析指南,授人以鱼不如授人以渔,教给你一套通用的方法分析任何算法的时空复杂度。
本文会篇幅较长,会涵盖如下几点:
1、Big O 表示法的几个基本特点。
2、非递归算法中的时间复杂度分析。
3、数据结构 API 的效率衡量方法(摊还分析)。
4、递归算法的时间/空间复杂度的分析方法,这部分是重点,我会用动态规划和回溯算法举例。
废话不多说了,接下来一个个看。
#Big O 表示法首先看一下 Big O 记号的数学定义:
O(g(n)) = { f(n): 存在正常量 c 和 n_0,使得对所有 n ≥ n_0,有 0 ≤ ...
Kruskal 最小生成树算法读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode
力扣
难度
1135. Connecting Cities With Minimum Costopen in new window🔒
1135. 最低成本联通所有城市open in new window🔒
🟠
1584. Min Cost to Connect All Pointsopen in new window
1584. 连接所有点的最小费用open in new window
🟠
261. Graph Valid Treeopen in new window🔒
261. 以图判树open in new window🔒
🟠
图论中知名度比较高的算法应该就是 Dijkstra 最短路径算法,环检测和拓扑排序,二分图判定算法 以及今天要讲的最小生成树(Minimum Spanning Tree)算法了。
最小生成树算法主要有 Prim 算法(普里姆算法)和 Kruskal 算法(克鲁斯卡尔算法)两种,这两种算法虽然都运用了贪心思想,但从实现 ...
一道数组去重的算法题把我整不会了读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode
力扣
难度
1081. Smallest Subsequence of Distinct Charactersopen in new window
1081. 不同字符的最小子序列open in new window
🟠
316. Remove Duplicate Lettersopen in new window
316. 去除重复字母open in new window
🟠
关于去重算法,应该没什么难度,往哈希集合里面塞不就行了么?
最多给你加点限制,问你怎么给有序数组原地去重,这个我们前文 双指针技巧秒杀七道数组题目 讲过。
本文讲的问题应该是去重相关算法中难度最大的了,把这个问题搞懂,就再也不用怕数组去重问题了。
这是力扣第 316 题「去除重复字母open in new window」,题目如下:
316. 去除重复字母 | 力扣 open in new window | LeetCode&nbs ...
Git原理之最近公共祖先读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode
力扣
难度
1644. Lowest Common Ancestor of a Binary Tree IIopen in new window🔒
1644. 二叉树的最近公共祖先 IIopen in new window🔒
🟠
1650. Lowest Common Ancestor of a Binary Tree IIIopen in new window🔒
1650. 二叉树的最近公共祖先 IIIopen in new window🔒
🟠
1676. Lowest Common Ancestor of a Binary Tree IVopen in new window🔒
1676. 二叉树的最近公共祖先 IVopen in new window🔒
🟠
235. Lowest Common Ancestor of a Binary Search Treeopen in new window
235. 二叉搜索树的最近公共祖先open in ...
东哥带你刷二叉搜索树(构造篇)读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode
力扣
难度
95. Unique Binary Search Trees IIopen in new window
95. 不同的二叉搜索树 IIopen in new window
🟠
96. Unique Binary Search Treesopen in new window
96. 不同的二叉搜索树open in new window
🟠
Info
在开头先打个广告,我的 手把手刷二叉树课程open in new window 按照公式和套路讲解了 150 道二叉树题目,只需一顿饭钱,就能手把手带你刷完二叉树分类的题目,迅速掌握递归思维,让你豁然开朗。我绝对有这个信心,信不信,可以等你看完我的二叉树算法系列文章再做评判。
之前写了两篇手把手刷 BST 算法题的文章,第一篇 讲了中序遍历对 BST 的重要意义,第二篇 写了 BST 的基本操作。
本文就来写手把手刷 BST 系列的第三篇,循序渐进地讲两道题,如何计算所有有效 BST。
第一道题是力扣第 ...
二分搜索怎么用?我又总结了套路读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode
力扣
难度
1011. Capacity To Ship Packages Within D Daysopen in new window
1011. 在 D 天内送达包裹的能力open in new window
🟠
410. Split Array Largest Sumopen in new window
410. 分割数组的最大值open in new window
🔴
875. Koko Eating Bananasopen in new window
875. 爱吃香蕉的珂珂open in new window
🟠
-
剑指 Offer II 073. 狒狒吃香蕉open in new window
🟠
我们前文 我写了首诗,把二分搜索变成了默写题 详细介绍了二分搜索的细节问题,探讨了「搜索一个元素」,「搜索左侧边界」,「搜索右侧边界」这三个情况,教你如何写出正确无 bug 的二分搜索算法。
但是前文总结的二分搜索代码框架仅仅局限于「 ...