Home

青蛙跳台阶问题 这是一道斐波那契数列的follow-up，所以可以用解决斐波那契数列的方法解决这一题，分析题目，我们发现由于青蛙一次只能跳一步或两部，所以用f（n）来表示青蛙跳到n阶台阶可能的跳法，其运算过程可以表示为f（n）= f（n-1）+ f（n-2）。我们能够轻易地发现这和斐波那契数列的递推公式是相同的，所以可以仿照其，写出代码。算法一中的状态转移过程所用的存储空间不是最优的，故用两个变量进行了优化。最终，这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def numWays1(self, n: int) -> int: dp = [1] * (n + 1) for i in range...

合并区间 想做一下新的题型，结果好像又和双指针有点关系？啊可是这是区间合并的题型，然后主流的算法都是先将输入的区间排序然后遍历做的，就是扫描线算法？ 如代码所示，排序后。我们用另一个数组来存储答案，首先将第一个区间加入merged数组，然后开始判断区间数组中的第一个区间左端点是否大于merged数 组中最后一个区间的右端点，如果不是，说明没有重合，可以直接将区间加入merged数组。如果有重合，则进行合并，其方法是将merged里最后一个数组的 右端点改为”merged最后区间的右端点与区间数组中第一个区间的右端点中的最大值”。 （这种题型是不是和线段树有联系啊？）//待更新 class Solution: def merge(self, intervals: List[...

16种模式： 滑动窗口 sliding window （单调队列和单调栈？） 双指针 two pointers 快慢指针 fast&slow pointers 区间合并 merge intervals （扫描线，线段树？） 循环排序 cyclic sort 原地反转链表 in-place reversal of linkedlist 树上的BFS tree breadth first search 树上的DFS tree depth first search 双堆 two heaps 子集 subsets 变种二分 modified binary search 位运算异或 bitwise XOR 最大前K个元素 top ...

对一个初高中甚至大学都没有接触计算机算法竞赛的我来说，动态规划还是需要用心才能理解的，所以要总结一下。该文章某些部分取自刘汝佳的《算法竞赛入门经典（第2版）》 理解状态和状态转移方程 理解最优子结构和重叠子问题 熟练运用递推法和记忆化搜索求解数字三角形问题 熟悉DAG上动态规划的常见思路、两种状态定义方法和刷表法 掌握记忆化搜索在实现方面的注意事项 掌握记忆化搜素和递推中输出方案的方法 掌握递推中滚动数组的使用方法 熟练解决经典动态规划问题 相关概念 最小子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。 相关题型 背包DP 区间DP 线性DP DAG上的DP 树形DP 状压DP ...

股票的最大利润 这个题用蛮力很容易做出来，既然只交易一次，那么就O（n^2）的时间复杂度，但也可以时间复杂度为O（n）的动态规划来做，分析如下： 状态定义：设动态规划数组dp，dp[i] 为以prices[i] 为结尾的数组的最大利润（即前i日的最大利润）。 转移方程：由于只交易一次，因此前i日最大利润为前i-1日的最大利润与第i天卖出的最大利润中的最大值的和：用公示表示为(dp[i] = max(dp[i−1], prices[i] − min(prices[0:i]))) 初始状态：dp[0]=0，即首日利润为零 返回值：dp[n-1], n为dp列表长度 注意到min(prices[0:i]) 的时间复杂度为O（i），我们完全可以用一个变量在遍历数组的时...

数组中重复的数字 加一个系列，剑指offer里的题，比较容易想到的就是将数组遍历一遍然后用一个哈希表在O（1）复杂度内检查有无重复的数字，有则返回，时间复杂度为 O（n），但是这种方法提高效率是以一个大小为O（n）的哈希表为代价的。第二种常见的算法是将数组排序，再扫描一遍从其中找出重复数字，比较简单， 时间复杂度(因为排序)为O（nlogn）。第三种方法比较经典，其思路是，从头开始遍历数组，检查第i个数的值与i是否相等，若相等则继续，若不想等，则 将第i个数字与第第i个数字所指的值的数比较，若相同，则返回值，若不同，则继续该步骤直至找到重复数字或满足第一个条件（即第i个数的值与i相等）, 虽然代码中有两重循环，但对每个数来说最多只需两次即可找到自己的位置，所以该算法的时间复杂度为O（...

相交链表 看到群友在群里聊到面试问了这个题，记得之前做过有印象，就随手做了一下，思路很简单，也可以说是双指针法，即将两个链表拼接，得到两个相同长度但前后顺序不同的链表（假设输入的是两个链表X和Y，则拼接成的新链表为XY和YX）。分别从头遍历这俩链表，当节点值相等时则为相交位置，否则遍历结束返回指针指向的None。 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, he...

环形链表 因为之前做过，所以对我来说是一个简单的题（其实对谁来说都是），找链表中的环最经典的做法是用快慢指针，慢指针一次走一步，快指针一次走两步，开 始遍历后两个指针再相遇时就是环入口节点的位置。啊不过代码实现起来还是要注意一些边界，比如说要判定下一个节点是不是None，注意到快指针比较快， 应该判断快指针所指的节点的下一个节点是不是None。另外，还有一种方法是用哈希表实现，其思想是遍历链表并将每个节点的值都存在哈希表中，当某个 节点为null时，意味着已到链表末尾，所以该链表中无环，否则，当哈希表中出现重复值的时候，说明该链表中有环。 # Definition for singly-linked list. # class ListNode: # def __init_...

合并两个有序数组 再做一个可以用双指针法做的题，将两个数组的值都合并到第一个数组里面去，注意到其实这就是归并排序。解法如下，分别用两个指针指向两个数组非零数 的末尾, 再用另一个指针t指向数组1的最末尾，然后比较这两个数的大小并将比较大的数存到第一个t指针所指的位置，存储后将t也往前移动一位。注意我们 不能从前往后移动，因为t指针所指的位置会将未处理的数组1中的数字给覆盖掉。随着三个指针的移动，合并也相应完成了，但是注意到，由于判定条件是两个 指针都不能越界，故数组1中都指针指向数组最开始时会停下，但此时数组2中的数字并未全被加入数组1中（由于数组2中遗留的数字比数组1中在数组开头的第 一个数字还小的缘故），我们要做进一步的处理即将数组2中剩余的数字复制到数组1最开头。另外，这种操作...

最小覆盖子串 这个寻找字串，容易看出来是用滑动窗口法。其中长的字符串为S，短的字符串为T， 关于怎么实现寻找覆盖的字串，我们可以各用一个哈希表来记录，甚至更节省空间的做法只用一个哈希表，具体来说是在用哈希表记录T时，往该表里加入字符\n 与个数，当计数S中的窗口时，则将该表里的字符相继减少。