讨论/技术交流/「春招学习计划」 周常总结 Week10/
「春招学习计划」 周常总结 Week10

「春招学习计划」 周常总结 Week10

简介

大家好,我负责「春招学习计划」第八周(2021.03.8 - 2021.03.15) 的Leetor,这周学习计划主要内容是动态规划。

以下是往期总结链接:

  • Week 1 主要内容:数组、二分查找、并查集。
  • Week 2 主要内容:数组、字符串、KMP 和字典树。
  • Week 3 主要内容:双指针、滑动窗口。
  • Week 4 主要内容:栈、队列。
  • Week 5 主要内容:链表、哈希表。
  • Week 6 主要内容:树、图。
  • Week 7 主要内容:递归、位运算、数学。
  • Week 8 主要内容:排序算法。
  • Week 9 主要内容:深度优先搜索、广度优先搜索、分治和贪心。

动态规划

动态规划通常耗时远远小于朴素解法,通常思路将问题分解为子问题,在解决子问题的基础上求得原问题的解。

wiki对动态规划适用问题总结如下:

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态規劃算法解决问题提供了重要线索。
  2. 无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
  3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态規劃算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率,降低了时间复杂度。

可以通过以下两个过程解决动态规划问题:

  1. 如何将子问题定义为状态,如何确定初始状态对应的值
  2. 状态之间如何转移

对应解法通常有两种编码方式:

  1. 自底向上,在确认初始状态和转移方程,通过循环将子问题向原始问题递推。
  2. 自顶向下,从原始问题开始递归,递归的出口是初始状态和对应的值。在该情况下,通常采用记忆化方式防止重复计算子问题。

学习建议

关于动态规划的种类和对应介绍,可以参考oi-wiki 动态规划

动态规划需要明确了解状态定义、转移和初始化,因此十分考验对此类问题的熟练度,对于新手,在想不出答案的时候,建议直接看答案,了解套路后并多刷几道同类型的DP问题。对于状态转移不清楚的情况,建议手动模拟一下状态的转移过程,不同状态的定义和转移方式对应不同的循环写法,例如在自底向上的区间DP,可通过枚举区间长度实现状态的转移,而对于状压DP,通常使用枚举子集方式实现状态转移。

关于动态规划的题目以及分类,推荐阅读这篇文章打怪升级:力扣上的 DP 问题分类汇总

对于背包问题,推荐阅读:背包九讲

每日一题问题汇总

LeetCode0191 位 1 的个数 有没有好心人给解释一下法一中那句:res = sum (1 for i in range (32) if n & (1 << i)) 当中 sum 函数 为什么 1 开头 是什么意思啊

推荐阅读 Python 列表推导。该代码类似于:

tmp = [1 for i in range(32) if n & (1 << i)]
'''
List Comprehensions
tmp = []
for i in range(32):
   if n & (1 << i):
       tmp.append(1)
'''
res = sum(tmp)

LeetCode0191 位 1 的个数 请问为什么 方法二:位运算优化 的时间复杂度是 O (log n) 啊,想了半天没想明白。求热心网友解释下

注意是在2进制上面做操作,时间复杂度与二进制的位数相关。对于十进制nn, 其二进制数位为log2(n)+1\lfloor\log_2(n)+ 1\rfloor。因此时间复杂度为log(n)\log(n)

LeetCode0341 扁平化嵌套列表迭代器 请问解法二中stk.emplace(nestedList.begin(), nestedList.end()); 是把所有元素正序入栈,为什么最后输出元素也是正序的呢

可以手动模拟一下过程,这是模拟了DFS的过程。emplace 是存入一个pair,并不是所有元素入栈。stk 中保存的是方法1中,当前深度对应递归函数遍历到的位置,以及终止的位置。pop_backemplace_back 对应的就是方法一中进入下一层递归和递归函数返回的过程。

LeetCode0341 扁平化嵌套列表迭代器 指针向后移动一位 的操作在哪?没太看明白

如果是说的next()函数,看题解:

return stk.top().first++->getInteger(); 
// top().fisrt() 是一个迭代器,返回对应的数值,并移动。

LeetCode0341 扁平化嵌套列表迭代器 想不太明白法一 C++ 解法,dfs 遍历调用 getList 函数,那么 next 函数和 hasNext 函数有什么用呢

把嵌套列表先通过DFS展开成1维数组,这样next() 函数直接遍历这个数组就可以了。

LeetCode0456 132 模式 首先我们判断 a [i] 是否可以作为 1。如果 a [i]<max_k,那么它就可以作为 1,我们就找到了一组满足 132 模式的三元组; 方法二就没看懂,有一有二了三在哪呢?

方法二使用的是单调递减栈。max_k通过出栈元素进行更新,这意味着如果max_k存在的话,栈顶元素大于max_k。此时栈顶元素是模式3。

LeetCode0456 132 模式 upper_bound () 里为什么是 left_min

题解一 left_min 是模式1,当前遍历的元素是模式3。需要在有序集合搜索比模式1大数的最小值,判断是否能作为模式2,因此upper_bound 里面是left_min

LeetCode0456 132模式方法二:如果我们从左到右枚举1 的下标 i,那么 j, k 的下标范围都是减少的,这样就不利于对它们进行维护。因此我们可以考虑从右到左枚举 i。怎么理解这句话?

方法二使用单调递减栈维护j, k。如果从左到右枚举123无法通过均摊复杂度O(1)O(1)求解。例如从左到右枚举位置为i,需要在[i+1,N1][i + 1, N - 1] 这个坐标区间内,遍历找到3,并在[j + 1, N - 1] 这个区间内寻找是否有符合要求的2。这个过程时间复杂度为O(N2)O(N^2) 总时间复杂度为O(N3)O(N^3),显然这也不是单调栈的思路,因为在遍历过程中,无法维护栈,例如指针右移一位,需要弹出栈底元素,而不会插入新的元素。从左到右枚举的过程中,jk搜索的空间是从N1N - 100

如果从右到左枚举。jk 搜索空间的范围是从00N1N - 1。此时通过单调栈实现,初始化栈为空或者只含最右端元素,在向左扫描过程中根据当前扫描值,对栈进行压入和弹出,均摊复杂度为O(1)O(1)。总时间复杂度为O(N)O(N)

LeetCode0082 删除排序链表中的重复元素 II int x = cur.next.val; while (cur.next != null && cur.next.val == x) 这段代码是啥意思呀,x 存值,再判断 cur.next.val 是不是 x 的值???? 真心看不懂

请看代码注释:

while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) { // 说明下一个节点是重复元素
                int x = cur->next->val; //记录重复元素的值
                while (cur->next && cur->next->val == x) { 
                    cur->next = cur->next->next; // 更改当前节点的下一个指针,直到跳过相同值的节点
                  // 1(cur) -> 2 -> 2 -> 3
                  // 1(cur) -> 2 -> 3
                  // 1(cur) -> 3 // 此时 cur->next->val = 3 != 2
                }
            }
            else {
                cur = cur->next;
            }
        }

LeetCode0082 删除排序链表中的重复元素 II 为什么 while 循环的判断条件里要同时满足 cur->next 和 cur->next->next 呢?cur->next->next 存在不能说明 cur->next 存在吗?

因为cur->next 不存在的时候cur->next->next 会报错。例如cur->nextNULL,此时访问NULL->next

LeetCode0173 二叉搜索树迭代器

在数据上设计迭代器的话,是「一定」不能修改原始的数据的。

借楼贴个 Morris 遍历。O(1) 空间复杂度,均摊 O(1) 时间复杂度。

这里需要提示一下,Morris遍历会更改树的结构,在此基础上设计的迭代器改变了原始数据的结构。

10
共 6 个回复

赞一个。怎么样才能做leetor呀?

1

👍谢谢

赞👍

你好呀~感谢你的力扣的支持与信赖!目前 Leetor 招募尚未开放,如有招募计划我们将会在社区等渠道与大家同步,还请随时留意我们的消息哦~

好耶!Leetor 真棒!