之前没有很留意,没想到大一学过的数组也能有很多精彩的算法题。本文收录了数组类算法常见的:前缀和、差分数组、常数时间查找和删除数组元素和数组去重问题。
- 前缀和数组:用于频繁求解给定区间内,数组元素的和
- 差分数组:用于频繁更改给定区间内数组元素的取值,最后得到数组
前面两个侧重频繁修改数组,常规模拟算法必然超时。而至于常数时间内查找和删除数组元素,数组元素去重已经是固定要求的题目了,文末直接给出题解。
之前没有很留意,没想到大一学过的数组也能有很多精彩的算法题。本文收录了数组类算法常见的:前缀和、差分数组、常数时间查找和删除数组元素和数组去重问题。
前面两个侧重频繁修改数组,常规模拟算法必然超时。而至于常数时间内查找和删除数组元素,数组元素去重已经是固定要求的题目了,文末直接给出题解。
栈有着广泛的应用,比如逆波兰表达式,表达式求值,迷宫问题求解,程序调用等,不过这些问题今天都不涉及哈哈哈哈。关于程序执行期间,各个函数的相互调用使用的调用栈,可以参考这里。
单调栈属于栈的具体应用,而非栈这种数据结构的简单使用。此类问题一般用于求解以下场景:序列中某个元素的下一个最大元素,元素间的最大跨度,维持某一状态持续的最长时间等。以序列 [2,1,3,4]
为例,1 的下一个最大元素就是 3,而不是 4;最大上升的跨度为从 2 到 4,跨越了 2 个数。对于这种问题都可以用单调栈求解。
动态规划作为算法中较难的部分,还是下定决心慢慢整理。人生建议:遇到太难的动态规划,建议直接放弃。动态规划解题也有技巧,一般而言题目的问题都是:移动最少的次数到达终点。此时我们只需要:
dp
数组,数组大小一般和输入相同,但细节需要微操。dp[i]
的含义是,到达 i
的最少次数dp
数组进行初始化,即开始动态规划时,起始所需的次数,一般为 0,不过也有特殊情况dp
的转移,如何从上一状态计算当前状态掌握这三点,一般难度的动态规划是可以做出来的。
算法继续整理系列之区间问题。这类问题可以总结或者变化为:给定多个区间,求满足覆盖范围的最小相交区间的数量。一般而言都是:题目给定一个乱序的区间。我们需要对区间进行排序调整和统计结果,来满足题目条件。其中变化的部分只有如何处理相交区间,因此整理一个通用的算法模板。
之前一直好奇 C++
中的 this
和 python
中的 self
到底是什么关系,为什么 C++
要显式的写出来,python
则不需要。顺便深入了解一下 this
。
之前对 static
的理解仅限于:在类中声明这种类型的变量,可以通过这个变量知道这个类被创建了多少个对象。但是前些日子刷 leetcode
的时候,发现类中自定义的 cmp
函数如果不是 static
类型,就无法被类内的 sort
函数识别。所以今天来一探究竟。
不出意外的话,这应该是 python
复习的最后一部分了,之前写 python
的时候,一般是在实践中积累一些常见的用法而后系统的学习,比如生成器装饰器、高级数据结构、各种工具库乃至 __init__.py
等细节。但 python
帮开发者自动进行了垃圾回收,所以一直没涉足这个领域,今天来了解一下 python
中垃圾回收的三种机制:引用计数、标记清除和分代回收。