方法1：首先将字符串翻转，然后找到原字符串和翻转字符串的最长公共子串，就是最长回文字符串，我自己测试了一些都是正确的，但是提交后只通过了25/26个测试示例，这个不知道是为什么。 方法2：暴力求解。遍历一遍字符串，然后以A[i]元素为中心向两边遍历，看最长回文字符串的长度，不过需要注意的是回文字符串可能是奇数也可能是偶数，因此需要用两种方式从中心向两边扩散。 代码如下： # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param A string字符串 # @return int整型 # class Solution: def ge...

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

较简单的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[i]+dp[i−1]} 然后注意下初始条件就行。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型 # import copy class Solution: d...

利用python的split函数即可，按照空格分开后倒着遍历，然后遍历的同时大小写转换即可。关键可能是要记得python的split函数，大小写转换函数upper()和lower()就行了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @param n int整型 # @return string字符串 # class Solution: def trans(self , s: str, n: int) -> str: # write code here ...

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

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

这个题目还是有点复杂的，主要在于时间复杂度要求O(n)，空间复杂度要求O(1)。因此常规的思路都不行，最后还是看了题解才知道咋做。 首先要明白缺失第一个正整数要么是1-n，要么是n+1，其中n是nums数组的长度。这是很容易理解的，因为当nums数组里存放的就是1-n，那么最小正整数就是n+1，如果数组中有大于等于1个元素不在范围1-n中，则缺失的最小正整数就是1-n之间的某个值。 遍历该数组，如果nums[i]元素是在1-n范围间的话，就存在数组的nums[i]下标处。也就是令nums[nums[i]]=nums[i]，当然这样操作时要把原来nums[nums[i]]中的元素放到nums[...

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

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

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

遍历矩阵的每个元素，如果是1那么就给岛屿数量加上1，同时用dfs或bfs去遍历该岛屿的所有邻接岛屿（其实就是遍历这个点的连通图），将所有邻接岛屿都重新标记为0，然后继续往下遍历就行。其实这个题就是在找矩阵中的连通图数量。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 判断岛屿数量 # @param grid char字符型二维数组 # @return int整型 # class Solution: def solve(self , grid) -> int: # write code here if l...

同样是最经典最简单的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] , dp[i][j-1]+matrix[i][j]\}dp[i][j]=min{dp[i−1][j]+matrix[i][j],dp[i][j−1]+matrix[i][j]} 有了状态转移方程后就没问题了，代码如下： # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 #...

最简单经典的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] 代码如下： # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param m int整型 # @param n int整型 # @return int整型 # class Solution: def uniquePaths(self , m: int, n: int)...

首先是用dp来解这道题，dp解的话关键就在于找到状态转移方程，这个题的状态转移方程和找最长公共子序列不同，因为子串必须要是连续的串。 LCS[i][j]为以s1[i]和s2[j]为结尾最长子串，因此就容易得到状态转移方程了,if s1[i]!=s2[j]的话，那么LCS[i][j]=''，而如果s1[i]==s2[j]的话，那么LCS[i][j]=LCS[i-1][j-1]+s1[i]。有了状态转移方程之后就很好写代码了，但是用python写dp的话会报时间复杂度不过关，应该是python语言导致的，复杂度肯定是满足要求的。 但是从状态转移方程就可以看出来这道题用dp做确实有点浪费，可以用划窗...