小锵的博客

每日一题 - 股票问题 时间： 2021-01-10 题目链接： 买卖股票的最佳时机 买卖股票的最佳时机 II 买卖股票的最佳时机 III 买卖股票的最佳时机 IV 买卖股票的最佳时机含手续费 最佳买卖股票时机含冷冻期 题目内容：给一组数组，代表一段时期内的股票价格，如何买卖股票可以让我们获利最多。 只可以交易一次时 没有交易次数限制，尽可能多的交易次数时 只可以交易两次时 规定交易次数限制时 没有交易次数限制，但每次交易都有手续费时 卖完第二天的冷静期无法购买时 tag：动态规划 难易程度：从简单到困难 买卖股票的最佳时机 题目信息 题目描述： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 示例1: 1234输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, ...

题目信息 tag：链表 哈希表 难易程度：中等 题目描述： 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能 set(key, value)：将记录(key, value)插入该结构 get(key)：返回key对应的value值 若opt=1，接下来两个整数x, y，表示set(x, y) 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1 对于每个操作2，输出一个答案 示例1: 123456789101112输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3输出：[1,-1]说明：第一次操作后：最常使用的记录为("1", 1)第二次操作后：最常使用的记录为("2", 2)，("1", 1)变为最不常用的第三次操作后：最常使用的记录为("3", 2)，("1", 1)还是最不常用的第四次操作后：最常用的记录为("1", 1)，("2", 2)变为最不常用的第五次操作后：大小超过了3，所以移除此时最不常使用的记录("2", 2)，加入记录("4", 4)， ...

前言 这个问题已经是老生常谈了，更是经常被作为面试的压轴题出现，网上也有很多文章，但最近闲的无聊，然后就自己做了一篇笔记，感觉比之前理解更透彻了。 这篇笔记是我这两天看了数十篇文章总结出来的，所以相对全面一点，但由于我是做前端的，所以会比较重点分析浏览器渲染页面那一部分，至于其他部分我会罗列出关键词，感兴趣的可以自行查阅， 本文转自4ark **注意：**本文的步骤是建立在，请求的是一个简单的 HTTP 请求，没有 HTTPS、HTTP2、最简单的 DNS、没有代理、并且服务器没有任何问题的基础上，尽管这是不切实际的。 大致流程 URL 解析 DNS 查询 TCP 连接 处理请求 接受响应 渲染页面 URL 解析 地址解析： 首先判断你输入的是一个合法的 URL 还是一个待搜索的关键词，并且根据你输入的内容进行自动完成、字符编码等操作。 HSTS 由于安全隐患，会使用 HSTS 强制客户端使用 HTTPS 访问页面。详见：你所不知道的 HSTS 其他操作 浏览器还会进行一些额外的操作，比如安全检查、访问限制（之前国产浏览器限制 996.icu）。 检查缓存 DNS 查 ...

代理模式 代理模式是一种比较好的理解的设计模式。简单来说就是 我们使用代理对象来代替对真实对象(real object)的访问，这样就可以在不修改原目标对象的前提下，提供额外的功能操作，扩展目标对象的功能。 代理模式的主要作用是扩展目标对象的功能，比如说在目标对象的某个方法执行前后你可以增加一些自定义的操作。 举个例子：你的找了一小红来帮你问话，小红就看作是代理我的代理对象，代理的行为（方法）是问话。 代理模式有静态代理和动态代理两种实现方式，我们 先来看一下静态代理模式的实现。 静态代理 介绍 静态代理中，我们对目标对象的每个方法的增强都是手动完成的（*后面会具体演示代码_），非常不灵活（比如接口一旦新增加方法，目标对象和代理对象都要进行修改）且麻烦(_需要对每个目标类都单独写一个代理类*)。 实际应用场景非常非常少，日常开发几乎看不到使用静态代理的场景。 上面我们是从实现和应用角度来说的静态代理，从 JVM 层面来说， 静态代理在编译时就将接口、实现类、代理类这些都变成了一个个实际的 class 文件。 静态代理使用步骤 定义一个接口及其实现类； 创建一个代理类同样实现 ...

Kafka消息中间件到底会不会丢消息 大型互联网公司一般都会要求消息传递最大限度的不丢失，比如用户服务给代金券服务发送一个消息，如果消息丢失会造成用户未收到应得的代金券，最终用户会投诉。 为避免上面类似情况的发生，除了做好补偿措施，更应该在系设计的时候充分考虑各种异常，设计一个稳定、高可用的消息系统。 认识Kafka 看一下维基百科的定义 Kafka是分布式发布-订阅消息系统。它最初由LinkedIn公司开发，之后成为Apache项目的一部分。 Kafka是一个分布式的，可划分的，冗余备份的持久性的日志服务。它主要用于处理活跃的流式数据。 kafka架构 Kafka的整体架构非常简单，是显式分布式架构，主要由producer、broker（kafka）和consumer组成。 Producer（生产者）可以将数据发布到所选择的topic（主题）中。生产者负责将记录分配到topic的哪一个 partition（分区）中。可以使用循环的方式来简单地实现负载均衡，也可以根据某些语义分区函数(如记录中的key)来完成。 Consumer（消费者）使用一个consumer group（ ...

Kafka 如何做到支持百万级 TPS ？ 谈到大数据传输都会想到 Kafka，Kafka 号称大数据的杀手锏，在业界有很多成熟的应用场景并且被主流公司认可。这款为大数据而生的消息中间件，以其百万级TPS的吞吐量名声大噪，迅速成为大数据领域的宠儿，在数据采集、传输、存储的过程中发挥着举足轻重的作用。 在业界已经有很多成熟的消息中间件如：RabbitMQ, RocketMQ, ActiveMQ, ZeroMQ，为什么 Kafka 在众多的敌手中依然能有一席之地，当然靠的是其强悍的吞吐量。下面带领大家来揭秘。 顺序读写磁盘 生产者写入数据和消费者读取数据都是顺序读写的，先来一张图直观感受一下顺序读写和随机读写的速度 从图中可以看出传统硬盘或者SSD的顺序读写甚至超过了内存的随机读写，当然与内存的顺序读写对比差距还是很大。 所以Kafka选择顺序读写磁盘也不足为奇了。 下面以传统机械磁盘为例详细介绍一下什么是顺序读写和随机读写。 盘片和盘面：一块硬盘一般有多块盘片，盘片分为上下两面，其中有效面称为盘面，一般上下都有效，也就是说：盘面数 = 盘片数 * 2。 磁头：磁头切换磁道读写数 ...

题目信息 题目：剑指 Offer 30. 包含min函数的栈 时间： 2020-09-08 题目链接：Leetcode tag：栈 难易程度：简单 题目描述： 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例: 12345678MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.min(); --> 返回 -2. 解题思路 本题难点 普通栈的 push() 和 pop() 函数的复杂度为 O(1)；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)。 具体思路 将 min() 函数复杂度降为 O(1) ，可通过建立辅助栈实 ...

题目信息 题目；剑指 Offer 31. 栈的压入、弹出序列 时间： 2020-09-08 题目链接：Leetcode tag：栈 难易程度：中等 题目描述： 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例1: 12345输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 示例2: 123输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出：false解释： ...

题目信息 题目：剑指 Offer 32 - I. 从上到下打印二叉树 时间： 2020-09-08 题目链接：Leetcode tag：BFS（广度优先搜索） 队列 难易程度：中等 题目描述： 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 示例1: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回：[3,9,20,15,7] 提示 11.节点数量 <= 1000 解题思路 本题难点 二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。 具体思路 BFS 通常借助 队列 的先入先出特性来实现。 代码 12345678910111213141516171819202122232425262728293031323334class Solution { public int[] levelOrder(TreeNode root) { //当树的根节点为空，则直接返回空列表 ...

题目信息 题目：剑指 Offer 32 - II. 从上到下打印二叉树 II 时间： 2020-09-08 题目链接：Leetcode tag： 队列 BFS 难易程度：简单 题目描述： 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。 示例1: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回其层次遍历结果： 12345[ [3], [9,20], [15,7]] 提示 11.节点总数 <= 1000 解题思路 本题难点 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS） 具体思路 BFS 通常借助 队列 的先入先出特性来实现。 每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。 代码 123456789101112131415161718192021222324252627282930313233343536class S ...