1、最长公共子串
牛客网：最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=191&&tqId=36137&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
思路1:贪心
1、一个变量来记录最大长度
2、不断去贪心地寻找比最大长度长一的子串是否在另一个字符串中
res = ""
maxlen = 0
for i in range(len(str2)):
if str2[i-maxlen : i+1] in str1:
res = str2[i-maxlen:i+1]
maxlen = maxlen + 1
return res
思路2:动态规划
1、dp记录最大程度
2、另一个变量记录最大的索引位置
m=len(str1)
n=len(str2)
dp=[[0 for i in range(n+1)] for j in range(m+1)]
maxlen = 0
index=0
for i in range(m):
for j in range(n):
if str1[i]==str2[j]:
dp[i+1][j+1]=dp[i][j]+1
if (maxlen<dp[i+1][j+1]):
maxlen=dp[i+1][j+1]
index=i+1
return str1[index-maxlen:index] if maxlen!=0 else "-1"
2、最长公共子序列（不要求连续）
描述
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
class Solution:
def LCS(self , s1 , s2 ):
# write code here
m=len(s1)
n=len(s2)
dp=[["" for j in range(n+1)] for i in range(m+1)]
for i in range(m):
for j in range(n):
if s1[i]==s2[j]:
dp[i+1][j+1]=dp[i][j]+s1[i]
else:
if len(dp[i][j+1])>len(dp[i+1][j]):
dp[i+1][j+1]= dp[i][j+1]
else:
dp[i+1][j+1]= dp[i+1][j]
return dp[m][n] if dp[m][n]!="" else "-1"
3、最长回文子串
描述
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。
动态规划：
核心思路：
1、确定回文长度d
2、遍历每一个元素，判断是否能形成回文
3、记录最大值
代码如下：
class Solution:
def getLongestPalindrome(self, A, n):
# write code here
dp=[[False]*n for i in range(n)]
smax=0
for d in range(n):
for i in range(n-d):
j=i+d
if A[i]==A[j]:
if d==0 or d==1 or d==2:
dp[i][j]=True
else:
dp[i][j]=dp[i+1][j-1]
if dp[i][j]:
smax=max(smax,d+1)
return smax
4、最长递增子序列
（1）leetcode上最长子序列长度
动态规划：暴力
贪心+二分：
核心思路
d = []
for n in nums:
if not d or n > d[-1]:
d.append(n)
else:
l, r = 0, len(d) - 1
loc = r
while l <= r:
mid = (l + r) // 2
if d[mid] >= n:
loc = mid
r = mid - 1
else:
l = mid + 1
d[loc] = n
return len(d)
复杂度分析
（2）牛客网上最长子序列
https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481?tpId=191&&tqId=38003&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
5、字符串的全排
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=191&&tqId=36141&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
核心代码如下：
res=[]
c=list(ss)
k=len(c)
if k==1:
return c
else:
for i in range(k):
first=str(c[i])
for tmp in self.Permutation(''.join(c[:i]+c[i+1:])):
second=''.join(tmp)
s=first+second
if s not in res:
res.append(s)
return res
网友评论