lucifer

leetcode.jpeg

我花了几天时间,从力扣中精选了五道相同思想的题目,来帮助大家解套,如果觉得文章对你有用,记得点赞分享,让我看到你的认可,有动力继续做下去。

前四道题都是滑动窗口的子类型,我们知道滑动窗口适合在题目要求连续的情况下使用, 而前缀和也是如此。二者在连续问题中,对于优化时间复杂度有着很重要的意义。 因此如果一道题你可以用暴力解决出来,而且题目恰好有连续的限制, 那么滑动窗口和前缀和等技巧就应该被想到。

除了这几道题, 还有很多题目都是类似的套路, 大家可以在学习过程中进行体会。今天我们就来一起学习一下。

我们先来看下什么是序列化,以下定义来自维基百科:

序列化(serialization)在计算机科学的数据处理中,是指将数据结构或对象状态转换成可取用格式(例如存成文件,存于缓冲,或经由网络中发送),以留待后续在相同或另一台计算机环境中,能恢复原先状态的过程。依照序列化格式重新获取字节的结果时,可以利用它来产生与原始对象相同语义的副本。对于许多对象,像是使用大量引用的复杂对象,这种序列化重建的过程并不容易。面向对象中的对象序列化,并不概括之前原始对象所关系的函数。这种过程也称为对象编组(marshalling)。从一系列字节提取数据结构的反向操作,是反序列化(也称为解编组、deserialization、unmarshalling)。

可见,序列化和反序列化在计算机科学中的应用还是非常广泛的。就拿 LeetCode 平台来说,其允许用户输入形如:

1
[1,2,3,null,null,4,5]

这样的数据结构来描述一颗树:

([1,2,3,null,null,4,5] 对应的二叉树)

其实序列化和反序列化只是一个概念,不是一种具体的算法,而是很多的算法。并且针对不同的数据结构,算法也会不一样。本文主要讲述的是二叉树的序列化和反序列化。看完本文之后,你就可以放心大胆地去 AC 以下两道题:

之前出了一篇穿上衣服我就不认识你了?来聊聊最长上升子序列,收到了大家的一致好评。今天给大家带来的依然是换皮题 - 最长公共子序列系列。

最长公共子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长公共子序列。那么问题来了,它穿上衣服你还看得出来是么?

如果你完全看不出来了,说明抽象思维还不到火候。经常看我的题解的同学应该会知道,我经常强调抽象思维。没有抽象思维,所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题,那你做的题意义何在?

虽然抽象思维很难练成,但是幸好算法套路是有限的,经常考察的题型更是有限的。从这些入手,或许可以让你轻松一些。本文就从一个经典到不行的题型《最长公共子序列》,来帮你进一步理解抽象思维

注意。 本文是帮助你识别套路,从横向上理清解题的思维框架,并没有采用最优解,所有的题目给的解法可能不是最优的,但是都可以通过所有的测试用例。如果你想看最优解,可以直接去讨论区看。或者期待我的深入剖析系列

最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长上升子序列。那么问题来了,它穿上衣服你还看得出来是么?

如果你完全看不出来了,说明抽象思维还不到火候。经常看我的题解的同学应该会知道,我经常强调抽象思维。没有抽象思维,所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题,那你做的题意义何在?

虽然抽象思维很难练成,但是幸好算法套路是有限的,经常考察的题型更是有限的。从这些入手,或许可以让你轻松一些。本文就从一个经典到不行的题型《最长上升子序列》,来帮你进一步理解抽象思维

注意。 本文是帮助你识别套路,从横向上理清解题的思维框架,并没有采用最优解,所有的题目给的解法都不是最优的,但是都可以通过所有的测试用例。如果你想看最优解,可以直接去讨论区看。或者期待我的深入剖析系列

我花了几天时间,从力扣中精选了四道相同思想的题目,来帮助大家解套,如果觉得文章对你有用,记得点赞分享,让我看到你的认可,有动力继续做下去。

这就是接下来要给大家讲的四个题,其中 1081 和 316 题只是换了说法而已。

我本身刷了大概 600 道左右的题目,总结 200 多篇的题解,另外总结了十多个常见的算法专题,基本已经覆盖了大多数的常见考点和题型,全部放在我的 Github https://github.com/azl397985856/leetcode

然而作为一个新手,看着茫茫多的题解和资料难免会陷入一种“不知从何开始”的境地。不必担心,你不是一个人。

实际上,我最近一直在思考“初学者如何快速提高自己的算法能力,高效刷题”。因此我也一直在不断定位自己,最终我对自己作出了定位“用清晰直白的语言还原解题全过程,做西湖区最好的算法题解”。

然而我意识到,我进去了一个很大的误区。我的想法一直是“努力帮助算法小白提高算法能力,高效刷题”。然而算法小白除了清晰直白的算法题解外,还需要系统的前置知识。因此我的假设“大家都会基础的数据结构和算法”很可能就是不成立的。

笔者最早接触滑动窗口是滑动窗口协议,滑动窗口协议(Sliding Window Protocol),属于 TCP 协议的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。 发送方和接收方分别有一个窗口大小 w1 和 w2。窗口大小可能会根据网络流量的变化而有所不同,但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。

我们算法中的滑动窗口也是类似,只不过包括的情况更加广泛。实际上上面的滑动窗口在某一个时刻就是固定窗口大小的滑动窗口,随着网络流量等因素改变窗口大小也会随着改变。接下来我们讲下算法中的滑动窗口。



博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒...