牛客281174060号

题解

/ 注册

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

题解 | #单链表的排序#

用了两种方法求解。第一种方法是非常容易求解的，新建一个list存放所有的listnode，然后用sorted()函数进行排序就行了，其中key取的是listnode的val，然后将排序好的listnode按照顺序连接起来就行。第二种方法是使用归并排序，首先找到待排序的listnode的中间结点，...

Python3

2022-04-15

0 361

题解 | #正则表达式匹配#

做了2个小时终于解出来了，使用dp来解，设dp[i][j]为str[0:i]和pattern[0:j]是否可以匹配，存放true或者false。接着写状态转移方程： dp[i][j]=dp[i−1][j−1],if str[i−1]=pattern[j−1]dp[i][j]=dp[i-1...

Python3

2022-04-14

0 368

题解 | #编辑距离(一)#

有点难，详细的写在这里面了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param str1 string字符串 # @param str2 string字符串 # @return int整型 # class Solution: d...

Python3

2022-04-13

1 359

题解 | #链表相加(二)#

用了两种方法求解：转化成数字在求解，先分别遍历两个链表得到两个链表的数字，然后数字求和，求和得到结果后把结果变成listnode就行了。时间复杂度是O(n)，空间复杂度是O(n)，但是没有通过，报错是时间超时，应该是python语言导致的，因此使用了第二种方法。把head1和head2两...

Python3

2022-04-12

0 410

题解 | #数字字符串转化成IP地址#

有点难，一直在想怎么用dp解，其实根本不是用dp解的，大意了。使用递归求解该题，递归函数传进去三个参数，第一个是s：剩余字符串，第二个是num，已经有的ip数字的数量，第三个是ip，目前已经组成好前面部分的ip，如255.255.255。然后如果构成完整的ip了，就存在self.result = ...

Python3

2022-04-12

2 431

题解 | #合并两个有序的数组#

比较简单的题目，两个指针，分别遍历两个数组，然后合并起来就行了。但是踩了python语言本身的一个坑，在这里记录下。由于python对于list可以直接insert，所以其实程序里的帮忙对A做扩容对我们是没用的，程序开头需要把扩容的给删掉。删除扩容我这边用了两种方法： A = A[:m]; ...

Python3

2022-04-11

0 311

题解 | #最长回文子串#

方法1：首先将字符串翻转，然后找到原字符串和翻转字符串的最长公共子串，就是最长回文字符串，我自己测试了一些都是正确的，但是提交后只通过了25/26个测试示例，这个不知道是为什么。方法2：暴力求解。遍历一遍字符串，然后以A[i]元素为中心向两边遍历，看最长回文字符串的长度，不过需要注意的是回文字符...

Python3

2022-04-11

0 438

题解 | #最长公共前缀#

比较简单，首先初始化设定最长公共前缀是s = strs[0]，然后遍历每一个元素，依次找出s和strs[i]的最长公共前缀，更新s，即可。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param strs string字符串一维数组 # @re...

Python3

2022-04-10

2 324

题解 | #连续子数组的最大和#

较简单的dp，设dp[i]为以array[i]结尾的子串，达到sum最大，状态转移方程如下式所示： dp[i]=max{array[i],array[i]+dp[i−1]}dp[i]=max\{array[i],array[i]+dp[i-1] \}dp[i]=max{array[i],array[...

Python3

2022-04-10

0 252

题解 | #字符串变形#

利用python的split函数即可，按照空格分开后倒着遍历，然后遍历的同时大小写转换即可。关键可能是要记得python的split函数，大小写转换函数upper()和lower()就行了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param...

Python3

2022-04-09

0 342