牛客281174060号

题解

/ 注册

全部文章 / 题解（共60篇）

题解 | #两个链表的第一个公共结点#

直接使用蛮力法，先遍历第一个链表，然后遍历第二个，判断是不是同一个结点，是的话返回就行，但是这样时间复杂度O(m*n)。改进一步可以先得到两个链表的长度la和lb，假设la>lb（反过来当然一样），然后la先走la-lb步，然后双指针同步走，相同的第一个元素就是公共节点，返回即可。 clas...

Python3

2022-04-09

0 327

题解 | #最长上升子序列(一)#

这个题目还是有点难的，状态转移方程比较难确定。设定dp[i]为以num[i]这个元素为最后一个元素的最长的严格递增序列的长度。于是状态转移方程为： dp[i]=dp[j]+1,其中dp[j]满足下列要求：j<i,num[j]<num[i],dp[j]为满足该要求里的最大的那个。dp[i...

Python3

2022-04-09

0 263

题解 | #缺失的第一个正整数#

这个题目还是有点复杂的，主要在于时间复杂度要求O(n)，空间复杂度要求O(1)。因此常规的思路都不行，最后还是看了题解才知道咋做。首先要明白缺失第一个正整数要么是1-n，要么是n+1，其中n是nums数组的长度。这是很容易理解的，因为当nums数组里存放的就是1-n，那么最小正整数就是n+1，如...

Python3

2022-04-08

0 259

题解 | #兑换零钱(一)#

关键还是在于找到状态转移方程，设dp[i]为i块钱最少需要几张货币来兑换，于是可以想到状态转移方程为： dp[i]=min(dp[i−arr[j]])+1,对于任意的j,if i not in arrdp[i]=min(dp[i-arr[j]])+1, 对于任...

Python3

2022-04-08

0 216

题解 | #字符串的排列#

比较简单，返回全排列而已。使用下面的思路即可：如果字符串长度是1，就直接返回；若大于1，首先对字符串排序，然后遍历字符串，将第i个字符作为首个元素，得到剩下元素的全排列（递归实现），如果第i个元素和第i-1个元素一样就不用递归了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接...

Python3

2022-04-07

0 392

题解 | #把数字翻译成字符串#

这个题本身不难，状态转移方程也好写，主要麻烦的是0的存在。设dp[i]为到第i个字符为止的数组共有多少中译码方式，于是状态转移方程如下： dp[i+1]=dp[i],if nums[i−1,i+1]>26 or nums[i+1]==′0′ or&nb...

Python3

2022-04-07

0 225

题解 | #岛屿数量#

遍历矩阵的每个元素，如果是1那么就给岛屿数量加上1，同时用dfs或bfs去遍历该岛屿的所有邻接岛屿（其实就是遍历这个点的连通图），将所有邻接岛屿都重新标记为0，然后继续往下遍历就行。其实这个题就是在找矩阵中的连通图数量。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即...

Python3

2022-04-06

0 288

题解 | #矩阵的最小路径和#

同样是最经典最简单的dp了，设dp[i][j]为到达地i行第j列时的最短路径，则状态转移方程为： dp[i][j]=min{dp[i−1][j]+matrix[i][j],dp[i][j−1]+matrix[i][j]}dp[i][j]=min\{dp[i-1][j]+matrix[i][j] , ...

Python3

2022-04-06

0 281

题解 | #不同路径的数目(一)#

最简单经典的dp了，状态转移方程如下：dp[i][j]为到达i行j列时的路径的数量。 dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j]+dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1] 代码如下： # # 代码中的...

Python3

2022-04-06

0 293

题解 | #最长公共子串#

首先是用dp来解这道题，dp解的话关键就在于找到状态转移方程，这个题的状态转移方程和找最长公共子序列不同，因为子串必须要是连续的串。 LCS[i][j]为以s1[i]和s2[j]为结尾最长子串，因此就容易得到状态转移方程了,if s1[i]!=s2[j]的话，那么LCS[i][j]=''，而如果s1...

Python3

2022-04-05

4 388