牛客281174060号

分类

题解(61)

/ 注册

全部文章（共60篇）

题解 | #最长公共子序列(二)#

关键在于找到状态转移方程。令LCS[i][j]代表s1[0:i+1],s2[0,j+1]的最长公共子串，则状态转移方程为： LCS[i][j]=LCS[i−1][j−1]+s1[i],ifs1[i]=s2[j]LCS[i][j]=LCS[i-1][j-1]+s1[i],if s1[i]=s2[j]...

Python3

2022-04-05

0 295

题解 | #合并两个排序的链表#

两个指针分别指向两个链表，cur指针指向目前已排序好链表的末尾，然后两个指针的node去比，cur指向小的那个，小的那个链表指针后移即可。注意下边界条件就行了。 class ListNode: def __init__(self, x): self.val = x ...

Python3

2022-04-04

0 291

题解 | #最小花费爬楼梯#

符合DP一模型三特征，因此用DP来解。关键在于找到状态转移方程，假设x(n)为爬到楼梯第n阶台阶的最小花费。需要注意一下题目里爬到楼顶是需要爬到len(cost)这个index的台阶的，因此为了方便我们往cost最后加一个0，作为楼梯顶。状态转移方程为： x(n)=min{(x(n−1)+cos...

Python3

2022-04-04

1 270

题解 | #跳台阶#

关键在于找到规律，x(s)为到s级台阶的最多走法，要到s级台阶两个方法，到s-1级台阶或到s-2级台阶，因此得到状态转移方程：x(s)=x(s-1)+x(s-2)，于是和斐波那契数列一样了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param...

Python3

2022-04-03

0 368

题解 | #斐波那契数列#

首先最简单的无疑是直接根据递推式去递归，但是递归时间复杂度和空间复杂度都很高，所以改用更好的方法，也就是DP。看了下题解，有一个总结的很好，在此记录： DP适用的题目：一个模型三个特征一个模型：多阶段最优决策模型三个特征：最优子结构：后面阶段的最优解可以通过前面阶段的最优解解出；无后效性...

Python3

2022-04-03

0 276

题解 | #有重复项数字的全排列#

这个链接中是解决没有重复项数字的全排列的思路。此时我的总体递归思想是，取出第一个数字，递归得到剩下list的全排列，然后把第一个数字插入到结果的每一个位置。这样一种递归思想确实能得到全排列，但是当有重复数字时，很难将结果按照字典顺序返回。因为这种递归思想中对于重复数字的解决办法是得到递归结果，然后把...

Python3

2022-04-03

3 417

题解 | #没有重复项数字的全排列#

这一题看着简单但是写起来一下子还找不到思路，看了下题解也无法一下子理解，大家的方法都比较抽象，花了很久才想出直观的解决该题的思路。解决算法如下所示：把第一个元素取出来，记作a；递归解决剩下的list的全排列，得到结果为[[...],[...],...,]; 对于得到的结果进行遍历，然后将元素...

Python3

2022-04-02

17 1287

题解 | #数组中只出现一次的两个数字#

解释放在这个链接里了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型一维数组 # class Solution: def FindNumsAppearOnce(s...

Python3

2022-04-02

0 280

题解 | #数组中出现次数超过一半的数字#

遍历一遍，看每个值出现的次数并且存在dict里就行。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param numbers int整型一维数组 # @return int整型 # class Solution: def MoreTha...

Python3

2022-04-01

0 256

题解 | #两数之和#

我自己写的比较复杂，看了下题解实际上确实简单，先说下我自己的解题方法。 1.遍历一遍数组，存入哈希表，key是numbers[i],value是target - numbers[i],此处遍历时需要注意如果遇到numbers已经在key中存在了，需要做一个判断，如果numbers[i]*2==tar...

Python3

2022-04-01

0 300