讨论/技术交流/【春招学习计划】周常总结 Week7/
【春招学习计划】周常总结 Week7

各位小伙伴们好,我是负责春招学习计划第七周(2021.03.01 - 2021.03.07)的 Leetor. 本周学习计划主要学习内容为递归、位运算和数学,而每日一题内容较为综合。

往期链接

  • Week 1 主要内容:数组、二分查找、并查集。

  • Week 2 主要内容:数组、字符串、KMP 和字典树。

  • Week 3 主要内容:双指针、滑动窗口。

  • Week 4 主要内容:栈、队列。

  • Week 5 主要内容:链表、哈希表。

  • Week 6 主要内容:树、图。

学习建议

递归

递归,指程序调用自身的编程技巧,是计算机科学中的一个重要概念。它是许多其他算法和数据结构的基础。实现调用自身的函数的诀窍在于,每当递归函数调用自身时,它都会将给定的问题拆解为子问题。递归调用继续进行,直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环,它应具有以下属性:

  1. 一个简单的基本案例(basic case)(或一些案例) —— 能够不使用递归来产生答案的终止方案。

  2. 一组规则,也称作递推关系(recurrence relation),可将所有其他情况拆分到基本案例。

注意,函数可能会有多个位置进行自我调用。 link

事实上,递归和回溯基本类似,都是部分或者全部遍历一个 n-叉树(解空间树/决策树)的过程。因此建议把相关内容放在 标签的学习与训练时进行。事实上,树标签的很多题目就考察对于递归的运用。因此,无论是数据结构和算法新手还是对于相关内容有所生疏的编程者,都可以通过相关题目练习和提升。

另外,很多动态规划问题都可以用记忆化递归来解决。由于递归本身就是将问题化归为一些子问题来求解,因此有些时候记忆化递归相对于自底向下上的方式可能更为直观。同时对于状态较为稀疏的情况,记忆化递归可以降低很多复杂度。举例而言:

数学

数学在很大程度上是数据结构和算法的基础,也是最体现个人水平积淀的地方。同时也有很多比较具有智力特点的题目与数学强相关。另外,在算法竞赛中,各种数学问题(包括但不限于数论、组合等)也是常见的题目。

对于数据结构和算法而言,所遇到的数学大部分都是离散的而非连续的,因此例如微积分等课程对于计算机水平的提升较为有限。

这方面的学习建议主要分为两方面:

  1. 要学习,但是不要本末倒置

  2. 如果实在学有余力并且想系统学习可以参考相关的专业教材。不过对于面试难度而言,可能数学的最大用处是专业知识的考察而非算法上(例如深度学习方面的很多统计内容等)。

位运算

位运算就是基于整数的二进制表示进行的运算。算机底层的基本操作就是基于位的操作,因此位运算是相当快的。

常用的运算符共 6 种,分别为与( & )、或( | )、异或( ^ )、取反( ~ )、左移( << )和右移( >> )。

关于位运算的技巧纷繁复杂,也有许多零散的常见结论。希望读者可以自行在做题中总结一些常用操作与技巧。

同时在包括但不限于状态压缩动态规划等题目中也会经常用到位运算的一些技巧。

关于位运算的详细介绍可以参见:

  • OI-wiki 位运算条目。

  • Bithacks 里面有许多奇怪的位运算技巧。

问题汇总

LC304 为什么一维前缀和里面的 col2 + 1 不会越界?

为了方便计算,前缀和数组开头多补了一个不包含任何数字的初始值,也就是 0.

LC304 这里定义前缀和数组为什么要再开头加一行一列啊?

为了减去不必要的对于边界条件的讨论,可以通过加行列来使得代码和思路更清晰简洁。同理,某些和区间有关的问题(区间 DP 等)也可以使用这样的技巧。

LC338
y=x &(x-1) 这是啥思路啊。。。。

将二进制位表示最低的 1 改为 0, 具体的可以找一些数作为例子体会一下。

位运算有很多类似的技巧,具体可以参见 link1 link2.

LC338 如何理解“最低设置位”这个概念?

最低设置位 指的是二进制展开后最右侧的 1, 为了区别于最低(有效)位(最后一位,无论取值)。

摘录一段官方题解下 @lysias 的评论:

三种动规对应三种缩小二进制数的方法:

  1. 去掉左起第一个 1

  2. 右移 1 位

  3. 去掉右起第一个 1

其中 1 3 方法会稳定减少一个 1。而 2 方法是否减少 1 取决于最低位是否为 1(最低位为 1 才会被右移丢失)。我认为最核心的技巧是,围绕 1 的数量的、缩小二进制数的 位运算。

LC338 第一种计算方法的时间复杂度中的 K 应该为 int 型的二进制中 1 的个数,而不是 32 .

对于不同的数,二进制位中 1 的个数是不一样的。通过计算可以知道,对于 k 位的二进制数(包含前导零),1期望k/2k/2 的(每一位一半几率取 01),因此总复杂度依然是 O(nk)O(nk).

LC354 我有一个问题啊。比如信封参数如下:[[1,2],[2,3],[2,1],[2,4],[3,4]]。 按照题解排序完之后如下:[[1, 2], [2, 4], [2, 3], [2, 1], [3, 4]]。但是通过 binarySearch() 方法得到的 f 集合是这样的:[1, 3, 4]。虽然个数正确,但是对应的信封是 [2, 1], [2, 3], [3, 4] 感觉不对啊。

得到的集合并不代表实际的上升序列,只是集合的长度代表当前数组可以构成的上升子序列的最大长度,具体可以参见LC300的题解

题解也提到了,数组的第 k 个元素代表数组长度为 k 的上升子序列中结尾的最小可能值。

LC354 除了题解的排序外,还可以将 [[1,2],[1,3],[1,4]] 变成 [[3,2],[2,3],[1,4]] ,直接 sort 即可。这样正确吗?

如果数组尾部有一个 [2, 3], 那结果就错误了。

LC354 没看懂为什么要按照 envelopes[0] 升序, envelopes[1] 降序就可以不用判断 envelopes[0].

因为这样可以保证同宽度的信封在高度上升的子序列中最多出现一次,进而最长上升子序列中就不会出现宽度相同的解。这也是一种常见的处理方法。

LC354 := 是什么意思?这是哪个版本的py更新的语句?为什么我本地无法执行这一句?

Python 3.8 link.

LC232 题目要求的“均摊复杂度”是啥意思,单次 peekpop 操作最坏复杂度是线性的啊?

算法的均摊复杂度指的是多次操作的总复杂度除以次数。OI-wiki.

对于本问题而言,我们可以通过考虑单个特定元素来分析复杂度。对于任意一个元素,最多被放入栈中和弹出常数次,因而平均之后,单次操作均摊复杂度依旧是 O(1)O(1).

LC131 为什么第一种方法里更新结果需要 ret.add(new ArrayList<String>(ans)); 以及 ret.append(ans[:]) 呢?

因为结果数组中存储的实际上是指向单个 ans 的引用。如果不更新一份的话,引用会一直指向回溯过程中维护的 ans, 进而使得最终结果中每一项都会以相同的方式改变(最终为空)。而无论是 Javanew 还是 Python[:] 或者 copy / deepcopy 都会复制一个新的数组并将指向新数组的引用传入结果中。

另外要注意深拷贝和浅拷贝的区别,尤其是在复制嵌套数组的情况下。

同样的道理, Python 新建高维数组也不能直接用 * 来复制。

LC131 为什么要在回溯之后删除 s[i:j] ?

可以把回溯过程想象在一个解空间树中遍历。如果要返回上层节点,需要把进入当前节点及之后的操作撤销。这实际也就是回溯的主要框架:操作,进入深层递归,撤销操作。

LC131 没想到官方解答也是 2^n-ish 级别的时间复杂度, 有可能将时间复杂度降到多项式级别的嘛?

考虑最坏情况例如 aaaaaaaaaa 这样的,最终结果就会有长度的指数个,因此无法最坏多项式时间内解决。

11
共 3 个回复

好耶!学长好长!

4

好耶!学长好棒!

2

好耶!学长好棒!

1