前言:
今天咱们对“python公共方法”大体比较注重,各位老铁们都想要学习一些“python公共方法”的相关资讯。那么小编也在网上网罗了一些有关“python公共方法””的相关内容,希望姐妹们能喜欢,朋友们快快来学习一下吧!关注我的微信公众号:后端技术漫谈
不定期推送关于后端开发、爬虫、算法题、数据结构方面的原创技术文章,以及生活中的逸闻趣事。
我目前是一名后端开发工程师。主要关注后端开发,数据安全,网络爬虫,物联网,边缘计算等方向。
原创博客主要内容
Java知识点复习全手册Leetcode算法题解析剑指offer算法题解析SpringCloud菜鸟入门实战系列SpringBoot菜鸟入门实战系列Python爬虫相关技术文章后端开发相关技术文章
最长公共子序列LCS
动态规划状态转移方程式
这里写图片描述
Python
递归
def LCS(a, b): if a == '' or b == '': return '' elif a[-1] == b[-1]: return LCS(a[:-1], b[:-1]) + a[-1] else: sol_a = LCS(a[:-1], b) sol_b = LCS(a, b[:-1]) if len(sol_a) > len(sol_b): return sol_a return sol_bif __name__ == "__main__": a = 'abc' print(a[::-1]) print(LCS(a,a[::-1]))
动态规划
def lcs_dp(self, input_x, input_y): # input_y as column, input_x as row dp = [([0] * (len(input_y)+1)) for i in range(len(input_x)+1)] for i in range(1, len(input_x)+1): for j in range(1, len(input_y)+1): if i == 0 or j == 0: # 在边界上,自行+1 dp[i][j] = 1 elif input_x[i-1] == input_y[j-1]: # 不在边界上,相等就加一 dp[i][j] = dp[i - 1][j - 1] + 1 else: # 不相等 dp[i][j] = max(dp[i - 1][j], dp[i][j -1]) for dp_line in dp: print(dp_line) return dp[-1][-1]
Java
动态规划
public static int lcs(String str1, String str2) { int len1 = str1.length(); int len2 = str2.length(); int c[][] = new int[len1+1][len2+1]; for (int i = 0; i <= len1; i++) { for( int j = 0; j <= len2; j++) { if(i == 0 || j == 0) { c[i][j] = 0; } else if (str1.charAt(i-1) == str2.charAt(j-1)) { c[i][j] = c[i-1][j-1] + 1; } else { c[i][j] = max(c[i - 1][j], c[i][j - 1]); } } } return c[len1][len2]; }
最长回文子串
动态规划状态转移方程式
这里写图片描述
Python
动态规划
同时输出长度和字符串
class LCS3: def lcs3_dp(self, input_x, input_y): # input_y as column, input_x as row dp = [([0] * (len(input_y)+1)) for i in range(len(input_x)+1)] maxlen = maxindex = 0 for i in range(1, len(input_x)+1): for j in range(1, len(input_y)+1): if i == 0 or j == 0: # 在边界上,自行+1 dp[i][j] = 0 if input_x[i-1] == input_y[j-1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > maxlen: # 随时更新最长长度和长度开始的位置 maxlen = dp[i][j] maxindex = i - maxlen # print('最长公共子串的长度是:%s' % maxlen) # print('最长公共子串是:%s' % input_x[maxindex:maxindex + maxlen]) else: dp[i][j] = 0 for dp_line in dp: print(dp_line) return maxlen, input_x[maxindex:maxindex + maxlen]if __name__ == '__main__': lcs3 = LCS3() print(lcs3.lcs_dp('cabdec','cbdec'))
运行结果
[1, 0, 0, 0, 1][0, 0, 0, 0, 0][0, 1, 0, 0, 0][0, 0, 2, 0, 0][0, 0, 0, 3, 0][1, 0, 0, 0, 4]bdec
Java
动态规划(懒得加上返回字符串了)
public static int lcs3(String str1, String str2) { int len1 = str1.length(); int len2 = str2.length(); int result = 0; //记录最长公共子串长度 int c[][] = new int[len1+1][len2+1]; for (int i = 0; i <= len1; i++) { for( int j = 0; j <= len2; j++) { if(i == 0 || j == 0) { c[i][j] = 0; } else if (str1.charAt(i-1) == str2.charAt(j-1)) { c[i][j] = c[i-1][j-1] + 1; result = max(c[i][j], result); } else { c[i][j] = 0; } } } return result; }
标签: #python公共方法