那些和“公共“有关的算法题
程序员文章站
2024-03-19 15:28:10
...
一、二叉树类
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root ==q:
return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if not left:
return right
if not right:
return left
return root
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root==p or root==q:
return root
if root.val>p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left,p,q)
if root.val<p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right,p,q)
return root
3、首个共同祖先
暂时空
二、链表类
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# if not headA and not headB:
# return None
node1,node2 = headA,headB
while node1 != node2:
node1 = node1.next if node1 else headB
node2 = node2.next if node2 else headA
return node1
2、环形链表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next :
return False
slow = head
fast = head
while (fast and fast.next):
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
3、环形链表 II
暂时为空
三、动态规划类
1、最长公共子串
转移方程为:
同时输出长度和公共子串
class LCS3:
def lcs3_dp(self, text1, text2):
# input_y as column, input_x as row
dp = [([0] * (len(text2)+1)) for i in range(len(text1)+1)]
maxlen = maxindex = 0
for i in range(1, len(text1)+1):
for j in range(1, len(text2)+1):
if i == 0 or j == 0: # 在边界上,自行+1
dp[i][j] = 0
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > maxlen: # 随时更新最长长度和长度开始的位置
maxlen = dp[i][j]
maxindex = i - maxlen
else:
dp[i][j] = 0
for dp_line in dp:
print(dp_line)
return maxlen, text1[maxindex:maxindex + maxlen]
2、最长公共子序列:
转移方程为:
同时输出长度和公共子序列:
class Solution:
def LCS(list_n, list_m):
# 计算LCS的长度
n = len(list_n)
m = len(list_m)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if list_n[i-1] == list_m[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[m][n])
# 输出LCS
if dp[-1][-1] == 0:
return -1
list_LCS = []
i, j = n, m
while i > 0 and j > 0:
if list_n[i-1] == list_m[j-1]:
list_LCS.append(list_n[i-1])
i -= 1
j -= 1
continue
else:
if dp[i][j-1] >= dp[i-1][j]:
j -= 1
else:
i -= 1
return ''.join(list(reversed(list_LCS)))
四、字符串类
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ''
max_str = max(strs)
min_str = min(strs)
for i,j in zip(max_str,min_str):
if i==j:
res+=i
else:
return res
return min_str
上一篇: 二分查找(python实现)
下一篇: Python实现二分查找算法